• Авторизация


Алгоритмы добавления/исключения звеньев списка 24-06-2009 15:57 к комментариям - к полной версии - понравилось!


Алгоритм включения звена  в список после звена, на которое указывает заданная ссылка
Доработаем алгоритм после найденного значения списка, вставим новое значение.
cout<<endl<<"Enter insert member:";
 cin>>n;
 node *ins;
 ins=new (node);
 (*ins).next=(*Res).next;
 (*ins).value=n;
 (*Res).next=ins;
 for (curr=first; curr!=NULL; curr=(*curr).next)
  cout<<(*curr).value << " ";  
 cout<<endl;
Алгоритм включения звена в список перед звеном, на которое указывает заданная ссылка
cout<<endl<<"Enter insert member:";
 cin>>n;
 node *ins;
 ins=new (node);
 (*ins).next=(*Res).next;
 (*ins).value=(*Res).value;
 (*Res).value=n;
 (*Res).next=ins;
 for (curr=first; curr!=NULL; curr=(*curr).next)
  cout<<(*curr).value << " ";  
 cout<<endl;
Алгоритм удаления звена из списка после звена, на которое указывает заданная ссылка
Для начала, введем список, в котором все элементы будут пронумерованы, включая заглавное звено.
#include <iostream.h>
struct node
{
 int value; //Информационный элемент звена списка
  node *next; // Указатель на следующее звено списка  
};
void main()
{
 int n=0;
 node *first, *curr, *Res;
 first = new (node);
 curr = first;
 (*curr).next=NULL;
 (*curr).value=0;
 for (int i=1;i<10;i++)
 {
 (*curr).next=new(node);
 curr=(*curr).next; 
 (*curr).value=i; 
 }
 (*curr).next=NULL;
Таким образом, вводим список из 10-ти элементов, и последний элемент устанавливаем в NULL. Сразу же выведем список на экран, чтобы убедиться, что все элементы мы ввели правильно.
for (curr=first; curr!=NULL; curr=(*curr).next)
  cout<<(*curr).value << " ";  
cout<<endl;
Теперь мы сделаем запрос с клавиатуры номера элемента, в который нужно переместиться и построим цикл поиска этого элемента:
cout<<"Enter number of element:";
 cin>>n;
curr=first;
 for (i=0;i<n && (*curr).next!=NULL;i++)
 {
 curr=(*curr).next; 
 }
Если конец списка наступит раньше, чем искомый элемент, то цикл прервется, а curr будет указывать на последний элемент. Таким образом, сейчас указатель curr указывает на элемент с тем номером, который мы хотели найти. Для дальнейших действий, нам понадобится еще один указатель. Этот указатель нужен для того, чтобы в последствии, высвободить память, которую занимал удаляемый элемент.
 Res=(*curr).next;
Проверим, что Res не указывает на последний элемент списка, иначе нам нечего будет удалять. При успешной проверке, переназначим ссылки, и освободим занимаемую память.
После чего, выведем оставшийся список на экран.
if (Res==NULL)
 {
 cout<<"Nothing to delete.Last element"<<endl;
 }
 else
 {
 (*curr).next=(*(*curr).next).next;
 delete Res;
 }
 for (curr=first; curr!=NULL; curr=(*curr).next)
  cout<<(*curr).value << " ";  
 cout<<endl;
}
Алгоритм удаления из списка звена, на которое указывает заданная ссылка
Во-первых: нам нужно найти предшествующий элемент чтобы переназначить на него ссылку. Для поиска этого элемента мы будем использовать указатели (q и q1), один из которых опережает другой. При этом, нам нужно учесть, что искомый элемент может оказаться последним в списке, что нужно обрабатывать отдельным алгоритмом.
Res=(*curr).next;
 node *q,*q1;
 q=first;
 q1=(*q).next;
 while (q1!=curr)
 {
 q=q1;
 q1=(*q1).next;
 }
 if (Res==NULL)
 {
 (*q).next=NULL; 
 }
 else
 {
 (*q).next=(*(*q).next).next;
 }
 delete q1;
 for (curr=first; curr!=NULL; curr=(*curr).next)
  cout<<(*curr).value << " ";  
 cout<<endl;
}
Находим предшествующий элемент, зануляем ссылку на следующий, и освобождаем память, занимаемую последним элементом.

 

вверх^ к полной версии понравилось! в evernote


Вы сейчас не можете прокомментировать это сообщение.

Дневник Алгоритмы добавления/исключения звеньев списка | TheLenka - Дневник Рыжей Девчонки | Лента друзей TheLenka / Полная версия Добавить в друзья Страницы: раньше»