Динамические структуры данных — КиберПедия


Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Динамические структуры данных



1. ЦЕЛЬ РАБОТЫ:изучение ссылочных типов данных, работа со связными списками.

 

ОДНОСВЯЗНЫЕ СПИСКИ

Список – это последовательность структур, каждая из которых содержит ссылку, связывающую её с другой структурой. Для организации списков используются структуры, состоящие из двух смысловых частей – информационной и дополнительной. Информационная часть содержит подлежащую обработке информацию, в дополнительной находятся указатели на последующую или предыдущую структуру списка:

Struct spis { char data[20];

struct spis *next; }; // Указатель на структуру

Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.

 

Пример создания и просмотра односвязного списка.

//lab12_1

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

struct spis

{ char data[20];

struct spis *next;};

struct spis * create(void); //функция создания списка (возвращает адрес его головы)

void list(spis *head); // функция просмотра списка

struct spis *head; // глобальная переменная, адрес головы списка

main()

{ clrscr();

head= create();

list(head);

free(head);

}

struct spis * create(void)

{ spis *p, *pred; char c;

// pred – указатель на предыдущую структуру

head=pred=p=(spis *)malloc(sizeof(spis)); //выделяем память для первой записи

printf(" fam: "); scanf("%s", p->data);

do { p=(spis *)malloc(sizeof(spis));

printf("\n fam: "); scanf("%s", p->data);

pred->next=p; //ссылка из предыдущей записи на текущую

pred=p; // сохранение адреса текущей записи

printf(" Закончить? y/n ");

c=getch();

} while (c!='y');

p->next=NULL;

return head;

}

void list(spis *head)

{ spis *p;

p=head;

while (p!=NULL) // пока не конец списка

{ printf("\n fio: %s",p->data);

p=p->next; // продвижение по списку

}

getch();

}

 

ДВУХСВЯЗНЫЕ СПИСКИ

В двухсвязном списке каждая структура содержит две ссылки: на предыдущую и последующую структуры. Таким образом, по списку можно перемещаться от начала к концу и от конца к началу. Для доступа к началу и концу списка должны быть известны их адреса, которые могут сохраняться в глобальных переменных типа указатель.

 

Пример создания и работы с двухсвязным списком.

//lab12_2

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <string.h>

struct spis

{ char data[20];

struct spis *v1; // v1 – указатель на предыдущую структуру

struct spis *v2; // v2 – указатель на последующую структуру

};

void create(void); // создание

void list(spis *); // просмотр

void del(void); // удаление

struct spis *head,*tail; // указатели на начало и конец списка

main()

{

clrscr();

create();

list(head); // просмотр с начала списка

list(tail); // просмотр с конца списка

del();

list(head);

free(head);

}

void create(void)

{ spis *p,*pred;

pred=NULL;

do { p=(spis *)malloc(sizeof(spis));

printf("Фамилия: "); gets(p->data);

p->v1=pred;

if (pred != NULL)

pred->v2=p;

else

head=p;

pred=p;

puts(" Закончить - <esc>");

}

while (getch()!=27);

tail=p;

tail->v2=NULL;

}

void list(spis *p)

{ if (p==head)

while (p != NULL)

{ puts(p->data);

p=p->v2;

}

else if (p==tail)

while ( p!= NULL)

{ puts(p->data);

p=p->v1;

}

else

puts("Неверный адрес ");

getch();

}

void del(void)

{ spis *p,*temp;char f[20]; // f[20] – Строка для удаляемой фамилии

clrscr();

printf("Фамилия: ");gets(f);

p=head;

while (p!=NULL)

{ if (strcmp((p->data),f)==0) // если найдена заданная фамилия

{ if (p==head) // если найденная запись - первая

{ head=p->v2;

head->v1=NULL;

free(p);

p=head;

}

else if (p==tail) // если найденная запись - последняя

{ tail=p->v1;

tail->v2=NULL;

free(p);

p=tail;

}

else // удаление из средины списка

{ p->v2->v1=p->v1;

p->v1->v2=p->v2;

temp=p;

p=p->v2;

free(temp);

}

}

else // если заданная фамилия не найдена – продвигаемся по списку

p=p->v2;

}

}

 

Чтобы вставить новую структуру в двухсвязный список, также необходимо изменить только значения указателей. Пусть требуется вставить структуру перед найденной по заданному условию ; p – указатель на найденную структуру:

 

pn=(spis *)malloc(sizeof(spis)); // pn – указатель на новую структуру

gets(pn->data);

// если структура вставляется в средину списка

pn->v1=p->v1;

pn->v2=p;

p->v1->v2=pn;

p->v1=pn;

// если структура вставляется в начало списка

pn->v1=NULL;

pn->v2=p;

p->v1=pn;

head=pn;

// если структура вставляется в конец списка

pn->v1=tail;

pn->v2=NULL;

p->v2=pn;

tail=pn;

 

ВЫПОЛНЕНИЕ РАБОТЫ

4.1. Проанализировать приведенные программы.

4.2. Сформировать двухсвязный список и выполнить задание по своему варианту.

 

Варианты заданий

1. Структура содержит фамилию и 4 оценки. Удалить из списка неуспевающих.

2. Структура содержит фамилию и 4 оценки. Удалить из списка имеющих 2, 3.

3. Структура содержит название книги, автора, год издания. Удалить издания с годом меньше заданного.

4. Структура содержит название книги, автора, год издания. Удалить книги заданного автора.

5. Структура содержит название, цену, количество товара. Удалить из списка заданный товар.

6. Структура содержит название, цену, количество товара. Удалить из списка партии товара, превышающие заданную стоимость.

7. Структура содержит фамилию, год рождения. Добавлять новые записи так, чтобы список был упорядочен по алфавиту.

8. Структура содержит фамилию, год рождения. Добавлять новые записи так, чтобы список был упорядочен по возрасту.

9. Структура содержит название издания, газета или журнал, цена экземпляра. Добавлять новые записи так, чтобы сначала располагались журналы, затем газеты.

10. Структура содержит название издания, газета или журнал, цена экземпляра. Добавлять новые издания так, чтобы названия были упорядочены по алфавиту.

11. Структура содержит фамилию спортсмена, вид спорта, количество очков. Добавлять новые записи так, чтобы информация по каждому виду спорта располагалась последовательно.

12. Структура содержит фамилию спортсмена, вид спорта, количество очков. Добавлять новые записи так, чтобы они были упорядочены по убыванию очков.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

5.1. Понятие статической и динамической памяти.

5.2. Как создаётся и просматривается односвязный список?

5.3. Как создаётся и просматривается двухсязный список?

5.4. Как удалить структуру из списка?

5.5. Как добавить структуру в список?

 






Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...





© cyberpedia.su 2017-2020 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.009 с.