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

Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа (рис.).

 

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

 

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

 

struct имя_типа

{

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

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

};

 

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

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

 

struct point

{

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

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

};

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

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

//создание однонаправленного списка

//добавление в конец

point* make_list(int n)

{

point*beg;//указатель на первый элемент

point*p,*r;//вспомогательные указатели

beg=new(point);//выделяем память под первый элемент

cout<<"\n?";

cin>>beg->data;//вводим значение информационного поля

beg->next=0;//обнуляем адресное поле

//ставим на этот элемент указатель p (последний элемент)

p=beg;

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

{

r=new(point);//создаем новый элемент

cout<<"\n?";

cin>>r->data;

r->next=0;

p->next=r;//связываем p и r

//ставим на r указатель p (последний элемент)

p=r;

}

return beg;//возвращаем beg как результат функции

}

Для обработки списка организуется цикл, в котором нужно переставлять указатель p с помощью оператора p=p->next на следующий элемент списка до тех пор, пока указатель p не станет равен 0, т. е. будет достигнут конец списка.

void print_list(point* beg)

//печать списка

{

point* p=beg;//начало списка

while(p!=0)

{

cout<<p->data<<"\t";

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

}

}

В динамические структуры легко добавлять элементы и из них легко удалять элементы, т. к. для этого достаточно изменить значения адресных полей.

Рис. Добавление элемента в список

 

point* add_point(point* beg, int k)

//добавление элемента с номером k

{

point*p=beg;//встали на первый элемент

point*New=new(point);//создали новый элемент

cout<<"Key?";cin>>New->data;

if(k==0)//добавление в начало, если k=0

{

New->next=beg;

beg=New;

return beg;

}

for(int i=0;i<k-1&&p!=0;i++)

p=p->next;//проходим по списку до(k-1) элемента или до конца

if(p!=0)//если k-й элемент существует

{

New->next=p->next;//связываем New и k-й элемент

p->next=New;//связываем (k-1)элемент и New

}

return beg;

}

 

Рис. Удаление элемента из списка

 

point* del_point(point*beg,int k)

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

{

point*p=beg;

if(k==0)//удаление первого элемента

{

beg=beg->next;

delete p;

return beg;

}

//проходим по списку до элемента с номером k-1

for(int i=1;i<k&&p->next!=0;i++)

p=p->next;

/*если такого элемента в списке нет, то возвращаем указатель на начало списка в качестве результата функции*/

if (p->next==0) return beg;

point* r=p->next;//ставим указатель r на k-й элемент

p->next=r->next;//связываем k-1 и k+1 элемент

delete r;//удаляем k-й элемент из памяти

return beg;

}