Связанный список представляет собой структуру данных, состоящую из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением null. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи).
Приведем основные базисные операции для работы с однонаправленным связанным списком.
- Включение элемента после элемента p:
Здесь q - индекс элемента, который должен быть вставлен в список после элемента с индексом.
- Исключение преемника элемента x:
Отметим, что элемент, следующий в списке за элементом x, называется преемником элемента x, а элемент, расположенный перед элементом x, называется предшественником элемента x. Если элемент x не имеет преемника, то содержащемуся в нем указателю присваивается значение null.
- Включение элемента y перед элементом x:
Здесь link[0] является началом списка.
|
|
Отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка.
В двунаправленном связанном списке каждый элемент имеет два указателя (succlink - описывает связь элемента с преемником, predlink - с предшественником).
Приведем основные базисные операции для работы с двунаправленным связанным списком.
- Включение элемента перед элементом x:
- Включение элемента y после элемента x:
- Исключение элемента x:
Пример 1:
/* В список помещаются цифры 1...10Вводится число 11, сначала вставляется за цифрой 10, затем рвется связь между 3 и 4, между ними вставляется число 11.Пример дает навык работы:- с динамической памятью;- создания абстрактной структуры данных - список и модификации списка;- со структурами данных;- с функциями. */#include <stdlib.h>#include <string.h>#include <stdio.h>#include <conio.h>#include <math.h>#include <dos.h>struct List { int i; List *next;};/* структура данных, первое поле для хранения целого, второе поле-адрес в динамической памяти*/List*head=NULL; /* начальный адрес*/void Hed(int i) /* функция, которая создает очередной элемент списка */{ if(head==NULL) { head=(List*)malloc(sizeof(List)); head->i=1; head->next=NULL; } else { struct List *p,*p1; p=head; while(p->next!=NULL) p=p->next; p1=new List; p1->i=i; p1->next=NULL; p->next=p1; }}int s=0;void Print(List*p)/* вывод списка на экран */{ printf(" %d",p->i); if(p->next!=NULL)Print(p->next);}void delist()/* освобождение динамической памяти */{ List*p; while(head!=NULL) { p=head; head=head->next; free(p); }}void Vstavka(int i1,int c) /*вставка нового элемента*/{ List*p=head,*p1; while(p->i!=i1) p=p->next; p1=new List; p1->i=c; p1->next=p->next; p->next=p1;}void main()/* вход в программу */{ clrscr();/* очистить экран */ for(int i=1;i<=10;i++) Hed(i);/* создание списка */ Print(head);/* вывод списка на экран */ Vstavka(10,11); printf("\n"); Print(head); Vstavka(3,11); printf("\n"); Print(head); delist(); getch();}