Многие задачи программирования используют динамические структуры данных. Например, организация каталога книг в библиотеке. Нельзя зара-нее определить количество книг, числящихся в библиотечном фонде, так как идет постоянное поступление новых книг и списание старых. Для реализации таких задач существуют различные связные списки: однонаправлен-ные, двунаправленные; бинарные деревья и т.д.

Однонаправленные связные списки

Элементы списка называются узлами. Узел представляет собой объект, содержащий в себе указатель на другой объект того же типа и данные. Очевидным способом реализации узла является структура:
struct TelNum
{
TelNum * next; //указатель на следующий элемент
long telephon; // данные
char name[30]; // данные
};

Список представляет собой последовательность узлов, связанных ука-
зателями, содержащимися внутри узла. Простейшим списком является линейный или однонаправленный список. Признаком конца списка является значение указателя на следующий элемент равное NULL. Для работы со списком должен существовать указатель на первый элемент — заголовок списка.

Указатель заголовок
Основными операциями, производимыми со списками, являются обход,
вставка и удаление узлов. Можно производить эти операции в начале списка, в середине и в конце.

Вставка узла

a) в начало списка
start
temp
temp->next = start;
start = temp;

b) в середину списка

start current
temp

temp->next = current->next;
current->next = temp;

b) в конец списка

end temp

end->next = temp;
end = temp;

Удаление узла из списка

a) первого узла
start

TelNum *del = start;
start = start->next;
delete del;

b) В середине писка
current del

TelNum *del = current->next;
current->next = del->next;
delete del;

c) в конце списка

current end
TelNum *del = end;
current->next=NULL;
delete del;
end = current;

Алгоритмы, приведенные выше, обладают существенным недостатком — если необходимо произвести вставку или удаление ПЕРЕД заданным уз-
лом, то так как неизвестен адрес предыдущего узла, невозможно получить доступ к указателю на удаляемый (вставляемый) узел и для его поиска надо произвести обход списка, что для больших списков неэффективно. Избежать этого позволяет двунаправленный список, который имеет два указателя: один — на последующий узел, другой — на предыдущий.

// Пример программы работы с односвязным списком
#include <stdio.h>
#include <conio.h>
struct TelNum;
int printAllData(TelNum * start);
int inputData(TelNum * n);
struct TelNum
{
TelNum * next;
long number;
char name[30];
};
// Описание: печать списка
int printAllData(TelNum * start){
int c=0;
for(TelNum * next=start;next; next= next->next)
printf(«#%3.3i %7li %s\n»,++c,next->number,next->name);
return 0;
}
// Описание: ввод данных в структуру n конец ввода — ввод нуля
// в первое поле. Возвращает 1 если конец ввода
int inputData(TelNum * n){
printf(«Номер?»); scanf(«%7li»,&n->number);
if(!n->number) return 1;
printf(«Имя? «); scanf(«%30s»,&n->name);
return 0;
}
void main(void){
TelNum * start = NULL; //сторож
TelNum * end = start;
do{ //блок добавления записей
TelNum * temp = new TelNum;
if(inputData(temp))
{delete temp;
break;
}
else { if(start==NULL) {
temp->next = start;
start = temp;
end = temp;
}
else {
end->next=temp;
end=temp;
end->next=NULL;
}
}
}while(1);
printf(«\nЗаписи после добавления новых:\n»);
printAllData(start);
getch();
do{ //блок удаления записей
TelNum * deleted = start;
start = start->next;
delete deleted;
printAllData(start);
getch();
}while(start!=NULL);
}