Добавление нового узла в список — КиберПедия 

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Добавление нового узла в список



Для добавления нового узла в голову списка нужно выполнить последоватеьность действий, указанных в табл.15.

Таблица 15.

Добавление нового узла в голову списка

 

Действие Иллюстрация
1. Выделить память под новый узел списка: list* ptr = new list.

 
ptr

2. Заполнить информационную часть узла и обнулить указатели в нем
 
 
данные
ptr

3. Если список пуст, то этот узел сделать головой списка: head = ptr.
head
данные

4. Если список не пуст, то  
4.1. Для нового узла следующий указатель установить на голову текущего списка: ptr -> next = head.
 
 
ptr
 

4.2. Для головы списка предыдущий указатель установить на новый узел: head -> back = ptr.
       
   
 
 
ptr

4.3. Установить на новый узел указатель на голову списка: head = ptr.
 
 
ptr

 


int val;

list head;

 

list* ptr = new list;

ptr->value = val;

ptr->next = NULL;

ptr->back = NULL;

if (head == Nil) head = ptr //список пустой?

else

{

ptr->next = head;

head->back = ptr;

head = ptr;

}

 

Добавление в хвост списка и после текущего узла списка (или перед текущим) делается аналогично:

int s

list tail;

 

list* ptr = new list;

ptr->value = val;

ptr->next = NULL;

ptr->back = NULL;

if (tail == NULL) tail = ptr //список пустой?

else

{

tail->next = ptr;

prt->back = tail;

tail = ptr;

}

 

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

При удалении узла из списка нужно рассмотреть следующие ситуации:

1. Удаляемый узел является головой списка.

2. Удаляемый узел является хвостом списка.

3. Удаляемый узел единственный в списке.

4. Удаляемый узел не является ни головой, ни хвостом, ни единственным в списке.

В конце процедуры удаления обязательно необходимо освободить ранее выделенную динамическую память для удаляемого узла с помощью стандартной процедуры free(). Разберем подробно последний случай 4, когда удаляется узел не с краев, а внутри списка (табл.16).

 

Таблица 16.

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

Действие Иллюстрация
1.   На текущий узел указывает предыдущий узел. Этот указатель нужно «перекинуть» на следующий за текущим узел: cur->back->next =cur->next;
cur->back->next
           
   
Cur->back
 
 
   
cur->next->back
 
Cur->next

2.  
cur->back->next  
Следующий узел за текущим после удаления текущего узла должен будет указывать на предыдущий от текущего узла. Заменяем этот указатель:

cur->next->back = cur->back;



 

       
   
 
cur
 
Cur->next

3.
cur->back->next  
Запомним указатель на текущий элемент во временном указателе tamp: temp=cur;

               
   
Cur->back
   
 
 
 
tail
 
cur->next->back  
 
Cur->next

4.
cur->back->next  
Текущим элементом списка будет теперь следующий за ним узел:

cur = cur->next;

           
   
Cur->back
 
 
   
cur->next->back  
 
Cur->next

5. Освобождаем память, выделенную динамически для удаляемого узла списка: free(temp);

cur

 


//удаление узла в списке

list head,tail,cur, temp;

 

// проверяем является ли узел единственным в списке?

 

if ((cur->next == NULL) && (cur->back = NULL))

{

head = NULL;

tail = NULL; // делаем список пустым

free(cur);

cur = NULL; //освобождаем память

}

else

if (cur->next == NULL) // текущий узел является хвостом?

{

tail = tail->back; // Хвостом теперь станет предпоследний узел

tail->next = NULL;

free (cur);

cur = tail;

}

else

if (cur->back == NULL) // текущий узел является головой?

{

head = head->next; // головой становится второй узел списка

head->back = NULL;

free (cur);

cur = head;

}

else //узел ни голова, ни хвост, ни единственный в списке

{

cur->back->next = cur->next;

cur->next->back = cur->back;

temp = cur;

cur = cur->next;

free (temp);

};

}






Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...





© cyberpedia.su 2017 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав

0.011 с.