Линейные двухсвязные списки
жүктеу/скачать 0,97 Mb.
|
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; Пример списка реализованного на базе этих структур Переделаем функцию добавления элемента, взяв за основу добавление в односвязный список. Добавление элемента. Добавление элемента в список зависит от способа организации списка (отсортированный или нет), и правил добавления элементов (только в конец, только в начало, в определенное сортировкой место). В общем виде разделяется на следующие шаги: Выделить память под новый элемент Записать данные в элемент Определить место вставки и вставить Если список пуст, новый элемент становиться единственным элементом списка. Нужно создать головной элемент. Указателям на первый и последний элемент присвоить указатель на новый элемент. Если нужно вставить в начало списка Если нужно вставить в середину, тогда нужно найти элемент, после которого произвести вставку 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