Линейный однонаправленный список

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа

{

информационное поле;

адресное поле;

};

Информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка.

Информационных полей может быть несколько.

Примеры.

1. struct Node

{

int key;//информационное поле

Node*next;//адресное поле

};

2. struct point

{

char*name;//информационное поле

int age;//информационное поле

point*next;//адресное поле

};

Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом (пример 1), либо строкой (пример 2).

Над списками можно выполнять следующие операции:

- начальное формирование списка (создание первого элемента);

- добавление элемента в конец списка;

- добавление элемента в начало списка;

- удаление элемента с заданным номером;

- чтение элемента с заданным ключом;

- вставка элемента в заданное место списка (до или после элемента с заданным ключом);

- упорядочивание списка по ключу

и др.

Пример1. Создание и печать однонаправленного списка

#include <iostream.h>

#include<string.h>

//описание структуры

struct point

{char *name;//информационное поле

int age;//информационное поле

point*next;//адресное поле

};

point* make_point()

//создание одного элемента

{

point*p=new(point);//выделить память

char s[20];

cout<<"\nEnter the name:";

cin>>s;

p->name=new char[strlen(s)+1];//выделить память под динамическую строку символов

strcpy(p->name,s);//записать информацию в строку символов

cout<<"\nEnter the age";

cin>>p->age;

p->next=0;//сформировать адресное поле

return p;

}

void print_point(point*p)

//печать информационных полей одного элемента списка

{

cout<<"\nNAME:"<<p->name;

cout<<"\nAGE:"<<p->age;

cout<<"\n--------------------------------\n";

}

point* make_list(int n)

//формирование списка из n элементов

{

point* beg=make_point();//сформировать первый элемент

point*r;

for(int i=1;i<n;i++)

{

r=make_point();//сформировать следующий элемент

//добавление в начало списка

r->next=beg;//сформировать адресное поле

beg=r;//изменить адрес первого элемента списка

}

return beg;//вернуть адрес начала списка

}

int print_list(point*beg)

//печать списка, на который указывает указатель beg

{

point*p=beg;//р присвоить адрес первого элемента списка

int k=0;//счетчик количества напечатанных элементов

while(p)//пока нет конца списка

{

print_point(p);//печать элемента, на который указывает элемент p

p=p->next;//переход к следующему элементу

k++;

}

return k;//количество элементов в списке

}

void main()

{

int n;

cout<<"\nEnter the size of list";

cin>>n;

point*beg=make_list(n);//формирование списка

if(!print_list(beg)) cout<<"\nThe list is empty";}//печать списка

Пример 2. Удаление из однонаправленного списка элемента с номером k (рис 5.).

Рис. 5. Удаление элемента с номером k из однонаправленного списка

point*del_point(point*beg,int k)

//удаление элемента с номером к

{

point*p=beg,//поставить вспомогательную переменную на начало списка

*r;//вспомогательная переменная для удаления

int i=0;//счетчик элементов в списке

if(k==0)

{//удалить первый элемент

beg=p->next;

delete[]p->name;//удалить динамическое поле name

delete[]p;//удалить элемент из списка

return beg;//вернуть адрес первого элемента списка

}

while(p)//пока нет конца списка

{

if(i==k-1)//дошли до элемента с номером k-1, чтобы поменять его поле next

{//удалить элемент

r=p->next;//поставить r на удаляемый элемент

if(r)//если p не последний элемент

{

p->next=r->next;//исключить r из списка

delete[]r->name;//удалить динамическое поле name

delete[]r;//удалить элемент из списка

}

else p->next=0;//если p -последний элемент, то в поле next присвоить NULL

}

p=p->next;//переход к следующему элементу списка

i++;//увеличить счетчик элементов

}

return beg;//вернуть адрес первого элемента}