Линейные двухсвязные списки

жүктеу/скачать 0,97 Mb.

бет	1/2
Дата	04.11.2023
өлшемі	0,97 Mb.
	#189283

1 2

Байланысты:
Dvusvyaznye spiski

Добавление элемента.

Линейные двухсвязные списки
Реализация одного элемента списка
typedef struct node
{
int data;
struct node *next;
struct node *previos;
}ITEM;
Также имеет смысл хранить не только начало списка, но и конец. Объединим эти два указателя в одну структуру головного элемента
typedef struct head
{
struct node *first;
struct node *last;
}HEAD;
Пример списка реализованного на базе этих структур

Переделаем функцию добавления элемента, взяв за основу добавление в односвязный список.
Добавление элемента.
Добавление элемента в список зависит от способа организации списка (отсортированный или нет), и правил добавления элементов (только в конец, только в начало, в определенное сортировкой место).
В общем виде разделяется на следующие шаги:

Выделить память под новый элемент
Записать данные в элемент
Определить место вставки и вставить
1. Если список пуст, новый элемент становиться единственным элементом списка. Нужно создать головной элемент. Указателям на первый и последний элемент присвоить указатель на новый элемент.

Если нужно вставить в начало списка

Если нужно вставить в середину, тогда нужно найти элемент, после которого произвести вставку Prev и сделать 4 шага. 1)записать в новый элемент (new_item) в поле указатель на следующий (поле new_item–>next) тот же указатель что и в поле next элемента prev (поле prev–>next). 2) в элементе Prev изменить указатель на следующий элемент (записать адрес new_item). 3) Предыдущим элементом для нового элемента (поле new_item–>previos) сделать элемент prev. 4) Сделать новый элемент предыдущим для следующего за ним (поле new_item–>next–>previos).

Если нужно вставить в конец

Реализуем функцию
HEAD* add_node(HEAD* head, int new_data)
{
ITEM *new_item, *prev;
new_item=(ITEM *)malloc(sizeof(ITEM)); /*шаг 1 Выделить память под новый элемент*/
if(new_item==NULL)
{
printf("Error \n");
return head; /*голова не поменялась*/
}
new_item->data=new_data;/* шаг 2 Записать данные в элемент*/
if(head==NULL) /*список пуст*/
{
head=(HEAD *)malloc(sizeof(HEAD)); /*шаг 1 Выделить память под новый элемент*/
puts("List created!");
new_item->next=NULL;/*следующего элемента нет*/
new_item->previos=NULL;/*предыдущего элемента нет*/
head->first=head->last=new_item;/*новый элемент является и первым и последним*/
return head; /*новая голова*/
}
if(head->first->data>new_data)
{
/*список отсортирован по возрастанию и новый элемент нужно вставить в начало*/
printf("Element %d insert in begin \n",new_data);
new_item->next=head->first;/*следующий элемент после нового - текущий первый элемент списка*/
head->first->previos=new_item;/*новый элемент становиться предыдущим для текущего первого элемента*/
head->first=new_item;/*новый элемент становиться первым в списке*/
new_item->previos=NULL;/*предыдущего элемента для него нет*/
return head; /*голова*/
}
prev=head->first;
while(prev->next!=NULL) /*пока не конец списка*/
{
if(prev->next->data>new_data)
{
/*вставка*/
printf("Element %d inserted in middle \n",new_data);
new_item->next=prev->next;/*следующий элемент prev->next*/
prev->next=new_item;/*теперь следующим после prev будет new_item*/
new_item->previos=prev;/*предыдущим для нового будет prev*/
new_item->next->previos=new_item;/*новый станет предыдущим для следующего за ним*/
return head; /*голова не поменялась*/
}
else
{
prev=prev->next;/*переводим указатель prev на следующий за ним элемент*/
}
}
/*если вышли из цикла, значит дошли до конца списка и производим вставку в конец*/
printf("Element %d inserted in the end \n",new_data);
head->last->next=new_item;/*следующим после последнего элемента станет новый*/
new_item->previos=head->last;/*предыдущим для нового станет последний элемент списка*/
head->last=new_item;/*новый элемент стал последним в списке*/
new_item->next=NULL;/*следующего элемента после нового нет*/
return head; /*голова не поменялась*/
}
Реализуем вывод списка на печать
Первая функция выводит список от первого элемента до последнего
void print_begin(HEAD* head)
{
ITEM *cur;/*curr - указаетль на текущий узел*/
if(head==NULL || head->first==NULL)
{
puts("List empty!");
return;
}
cur=head->first;/*начинаем с первого элемента*/
while(cur!=NULL)/*пока не конец списка */
{
printf("%d ",cur->data);
/*переходим на следующий элемент*/
cur=cur->next;
}
puts("");
}

Вторая функция выводит список от последнего элемента до первого

void print_end(HEAD* head)
{
ITEM *cur;/*curr - указаетль на текущий узел*/
if(head==NULL || head->last==NULL)
{
puts("List empty!");
return;
}
cur=head->last;/*начинаем с последнего элемента*/
while(cur!=NULL)/*пока не конец списка */
{
printf("%d ",cur->data);
/*переходим на элемент перед ним*/
cur=cur->previos;
}
puts("");
}

жүктеу/скачать 0,97 Mb.

Достарыңызбен бөлісу:

1 2