// Динамические структуры данных (для всех вариантов)
Связанный линейный список — это набор узлов Node (тип данных структура(С++) или запись(Pascal)), каждый из которых имеет поле данных и поле адреса - указатель (ссылку) на следующий узел в списке. Тот, в свою очередь, тоже содержит поле данных и ссылку на продолжение списка. Последний узел списка содержит значение NULL (Nil), т.е. уже ни на что не ссылается. Начало списка формирует переменная head типа “указатель”, содержащая адрес первого узла списка. Поле данных еще называют информационной частью списка, поле адреса – адресной частью.
struct Node {
int data; // поле данных
Node* link; // поле адреса – указатель на следующий узел
};
Node* head=NULL;
Опишите функции типовых операций с списками:
1. Функция AddHead (int d) добавление узла в голову списка;
2. Функция AddEnd (int d) добавление узла в конец списка;
3. Функция ShowList() вывод списка на экран;
4. Функция Search( int d) поиск узла с заданным значением в некотором поле данных;
5. Функция FindNode ( int n) поиск узла с заданным номером;
6. Функция InsertNode(int d, int n) добавление нового узла непосредственно перед узлом с заданным значением в некотором поле;
7. Функция RemoveNode(int d) удаление узла с заданным значением в некотором поле;
8. Функция RemoveAll() удаление всего списка ;
Код: Выделить всё
#include <iostream>
using namespace std;
struct Node
{
int d;
Node* link;
};
Node* head=0;
//добавление узла в голову списка
Node* AddHead (Node* head, int dt)
{
Node* temp=new Node;
temp->link=head;
temp->d=dt;
head=temp;
return head;
}
//добавление узла в конец списка
void AddEnd (Node* head, int dt)
{
Node* temp=new Node;
temp->d=dt;
temp->link=0;
Node* temp1=head;
while (temp1->link)
{
temp1=temp1->link;
}
temp1->link=temp;
}
//вывод списка на экран
void ShowList(Node* head)
{
Node* temp=head;
if(!head)
{
cout << "Spiska net." << endl;
return;
}
while (temp)
{
cout << temp->d;
temp=temp->link;
}
}
//поиск узла с заданным значением в некотором поле данных
Node* Search(Node* head, int dt)
{
Node* temp=head;
while(temp->d!=dt)
{
temp=temp->link;
}
return temp;
}
//поиск узла с заданным номером
Node* FindNode(Node* head, int pos)
{
Node* temp=head;
pos--;
while(temp&&pos)
{
pos--;
temp=temp->link;
}
return temp;
}
//добавление нового узла непосредственно перед узлом с заданным значением в некотором поле
Node* InsertNode(Node* head, int dt, int n)
{
Node* temp=head;
Node* prev=0;
while(temp->d!=n) // ищем узел с нужным значением n, а также предыдущий узел
{
prev=temp;
temp=temp->link;
}
if(!prev) return AddHead (head, dt); // если нужный узел в голове, вставляем новую голову
Node* temp1=new Node;
temp1->link=prev->link;
temp1->d=dt;
prev->link=temp1;
return head;
}
//удаление узла с заданным значением в некотором поле
void RemoveNode(Node* head, int dt)
{
Node* prev=head;
Node* temp=head->link;
if(head->d==dt)
{
head=head->link;
delete prev;
return;
}
while(temp->d!=dt)
{
prev=temp;
temp=temp->link;
}
prev->link=temp->link;
delete temp;
}
//удаление всего списка
Node* RemoveAll(Node* head)
{
Node* temp=head;
while(temp)
{
head=temp;
temp=temp->link;
delete head;
}
return head;
}
//главная
int main()
{
head=new Node; //создание первого узла "5"
head->d=5;
head->link=0;
for (int i=0;i<4;i++) //добавление узлов "6","7","8","9"
AddEnd(head,i+6);
ShowList(head);
head=AddHead(head,4); //добавление узла "4"
ShowList(head);
AddEnd (head,10); //добавление узла "10"
ShowList(head);
cout << Search(head, 8) << endl; //поиск адреса узла со значением "8"
cout << FindNode(head, 2) << endl; //поиск адреса узла с номером 2
head=InsertNode(head,-7,8); // добавление узла "-7" перед узлом со значением "8"
ShowList(head);
RemoveNode(head, 8); //удаление узла со значением "8"
ShowList(head);
head=RemoveAll(head); //
ShowList(head);
system("pause");
return 0;
}
