Программирование
на языках высокого уровня. Язык программирования Си |
|
назад | оглавление | вперёд |
Список – это последовательность структур, каждая из которых содержит ссылку, связывающую её с другой структурой. Для организации списков используются структуры, состоящие из двух смысловых частей – информационной и дополнительной. Информационная часть содержит подлежащую обработке информацию, в дополнительной находятся указатели на последующую или предыдущую структуру списка: Struct spis { char data[20]; struct spis *next; }; // Указатель на структуру Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.
Пример создания и просмотра односвязного списка. #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(" фамилия: "); scanf("%s", p->data); do { p=(spis *)malloc(sizeof(spis)); printf("\n фамилия: "); 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 фамилия: %s",p->data); p=p->next; // продвижение по списку } getch(); }
В двусвязном списке каждая структура содержит две ссылки: на предыдущую и последующую структуры. Таким образом, по списку можно перемещаться от начала к концу и от конца к началу. Для доступа к началу и концу списка должны быть известны их адреса, которые могут сохраняться в глобальных переменных типа указатель. Пример создания и работы с двусвязным списком. #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;
13.3.1. Понятие статической и динамической памяти. 13.3.2. Как создаётся и просматривается односвязный список? 13.3.3. Как создаётся и просматривается двусвязный список? 13.3.4. Как удалить структуру из списка? 13.3.5. Как добавить структуру в список? |