Алгоритмы и структуры данных. АСДиИСИС_ПР. Программа работы со связным списком

• Название: Программа работы со связным списком
• Анкор: Алгоритмы и структуры данных
• Дата: 02.01.2023
• Размер: 112.53 Kb.
• Имя файла: АСДиИСИС_ПР.docx
• Тип: Программа; #870931

Программа работы со связным списком

1. Создать тип данных, описывающий звено двусвязного списка.

struct Zveno {

unsigned short Data;

Zveno *next;

Zveno *prev;

};

2. Создать процедуры работы с кольцевым двусвязным списком.

Процедура добавления звена в список

void i1(Zveno* Pred, unsigned short data)

{

Zveno* Loc = new Zveno;

Loc->Data = data;

Loc->next = Pred->next;

Loc->prev = Pred;

Pred->next = Loc;

}
Процедура удаления звена из списка

void d2(Zveno* Pred)

{

Zveno* Loc;

Loc = Pred->next;

Pred->next = Loc->next;

Loc->next->prev = Pred;

delete Loc;

}
Процедура просмотра списка

void prosmotr(Zveno* Start)

{

std::cout << Start->Data << " ";

Zveno* Cur = Start->next;

while (Cur!=Start)

{

std::cout << Cur->Data << " ";

Cur = Cur->next;

}

std::cout << "\n";

}
Процедура поиска звена в списке

int p2(Zveno* Start, Zveno*& Find, Zveno*& Pred, unsigned short Key)

{

Zveno* Cur = Start->next;

Pred = Start;

int Success = 0;

while (Cur!=Start && !Success)

{

if(Cur->Data == Key)

{

Find = Cur;

Success = 1;

break;

}

Pred = Cur;

Cur = Cur->next;

}

return Success;

}

3. Создать ведущее звено кольцевого двусвязного списка.

Zveno* L1;

L1 = new Zveno;

L1->Data = 0;

L1->next = L1;

L1->prev = L1;

4. Заполнить список данными, используя, например, цикл for и добавляя данные в начало списка (за ведущим звеном). Число данных выбрать в количестве 7 – 8 элементов.

for (unsigned short counter = 0; counter < 8; counter ++ )

i1(L1,counter+1);

5. Просмотреть содержимое списка.

prosmotr(L1);

6. Удалить звено, следующее за ведущим.

d2(L1);

prosmotr(L1);

7. Просмотреть содержимое списка.

prosmotr(L1);

8. Удалить звено из середины списка, используя операцию поиска данных в списке.

Zveno* F1;

F1 = new Zveno;

Zveno* P1;

P1 = new Zveno;

p2(L1,F1,P1,5);

d2(P1);

9. Просмотреть содержимое списка.

prosmotr(L1);

Пример работы программы:

Работа со списком как со стеком

Процедуры для работы со стеком:

Добавление звена

void i1(Zveno* Pred, unsigned short data)

{

Zveno* Loc = new Zveno;

Loc->Data = data;

Loc->prev = Pred->prev;

Loc->next = Pred;

Pred->prev->next = Loc;

Pred->prev = Loc;

}
Просмотр списка

void prosmotr(Zveno* Start, Zveno* Zero)

{

Zveno* Cur = Zero->prev;

while (Cur!=Start && Cur!=Zero)

{

std::cout << Cur->Data << " ";

Cur = Cur->prev;

d2(Cur);

}

std::cout << "\n";

}
10. Добавить 1 звено в начало списка (в позицию за ведущим звеном).

for (unsigned short counter = 0; counter < 1; counter ++ )

i1(L1,counter+1);
11. Просмотреть содержимое списка.

prosmotr(L1,L1);

prosmotr(L1,L1);

12. Считать данные из вершины стека (т.е. из начала списка – из звена, следующего за ведущим).

for (unsigned short counter = 0; counter < 8; counter ++ )

i1(L1,counter+1);

prosmotr(L1->prev->prev,L1);

13. Просмотреть содержимое списка.

prosmotr(L1->next,L1);

prosmotr(L1,L1);



14. Повторить пункты 10, 11 несколько раз с разными данными.

15. Повторить пункты 12, 13 несколько раз.

for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+10);

prosmotr(L1->prev->prev,L1);

prosmotr(L1->next,L1);

prosmotr(L1,L1);



for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+10);

prosmotr(L1->next->next,L1);

prosmotr(L1->next,L1);

prosmotr(L1,L1);



16. Считать все звенья из начала списка. После каждой операции считывания выполнять просмотр списка.

Дополнительная процедура для просмотра списка без удаления звена

void prosmotr2(Zveno* Start, Zveno* Zero)

{

Zveno* Cur = Start->prev;

while (Cur!=Start && Cur!=Zero)

{

std::cout << Cur->Data << " ";

Cur = Cur->prev;

}

std::cout << Zero->Data << " ";

std::cout << "\n";

}

for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+1);
for (unsigned short counter = 0; counter < 10; counter ++ ) {

prosmotr(L1->prev->prev,L1);

prosmotr2(L1,L1);

}



Работа со списком как с очередью

Процедуры для работы со стеком:

Добавление звена

void i1(Zveno* Pred, unsigned short data)

{

Zveno* Loc = new Zveno;

Loc->Data = data;

Pred->next->prev = Loc;

Loc->next = Pred->next;

Loc->prev = Pred;

Pred->next = Loc;

}
Просмотр списка

void prosmotr(Zveno* Start, Zveno* Zero)

{

Zveno* Cur = Zero->prev;

while (Cur!=Start && Cur!=Zero)

{

std::cout << Cur->Data << " ";

Cur = Cur->prev;

d2(Cur);

}

std::cout << "\n";

}
Дополнительный (проверочный) просмотр списка без удаления узла

void prosmotr2(Zveno* Start, Zveno* Zero)

{

std::cout << Start->Data << " ";

Zveno* Cur = Start->next;

while (Cur!=Start)

{

std::cout << Cur->Data << " ";

Cur = Cur->next;

}

std::cout << "\n";

}

17. Добавить 1 звено в конец очереди (т.е. в конец списка – в позицию перед ведущим звеном).

18. Просмотреть содержимое списка.

for (unsigned short counter = 0; counter < 1; counter ++ )

i1(L1,counter+1);
prosmotr(L1->prev->prev,L1);

prosmotr2(L1,L1);



19. Повторить пункты 17, 18 несколько раз с разными данными.

for (unsigned short counter = 0; counter < 8; counter ++ )

i1(L1,counter+1);
prosmotr2(L1,L1);

prosmotr(L1->prev->prev,L1);

prosmotr2(L1,L1);



for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+10);
prosmotr2(L1,L1);

prosmotr(L1->prev->prev,L1);

prosmotr2(L1,L1);



20. Считать данные из начала очереди (из звена следующего за ведущим звеном).

21. Просмотреть содержимое списка.

for (unsigned short counter = 0; counter < 8; counter ++ )

i1(L1,counter+1);
prosmotr2(L1,L1);

prosmotr(L1->next->next,L1);

prosmotr2(L1,L1);



22. Повторить пункты 20, 21 несколько раз.

for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+1);
prosmotr2(L1,L1);

prosmotr(L1->next->next->next,L1);

prosmotr2(L1,L1);
for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+1);
prosmotr2(L1,L1);

prosmotr(L1->prev->prev,L1);

prosmotr2(L1,L1);



23. Считать все звенья из начала списка. После каждой операции считывания выполнять просмотр списка.

for (unsigned short counter = 0; counter < 10; counter ++ )

i1(L1,counter+1);
for (unsigned short counter = 0; counter < 10; counter ++ ) {

prosmotr(L1->prev->prev,L1);

prosmotr2(L1,L1);

}

Работа со списком как с двухвходовой очередью (деком)

Процедуры для работы с декой:

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

void iN(Zveno* Pred, unsigned short data)

{

Zveno* Loc = new Zveno;

Loc->Data = data;

Loc->prev = Pred->prev;

Loc->next = Pred;

Pred->prev->next = Loc;

Pred->prev = Loc;

}
Просмотр списка с конца

void prosmotrN(Zveno* Start, Zveno* Zero)

{

Zveno* Cur = Zero->prev;

while (Cur!=Start && Cur!=Zero)

{

std::cout << Cur->Data << " ";

Cur = Cur->prev;

d2(Cur);

}

std::cout << "\n";

}

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

void i1(Zveno* Pred, unsigned short data)

{

Zveno* Loc = new Zveno;

Loc->Data = data;

Pred->next->prev = Loc;

Loc->next = Pred->next;

Loc->prev = Pred;

Pred->next = Loc;

}
Просмотр списка с начала

void prosmotr1(Zveno* Start, Zveno* Zero)

{

Zveno* Cur = Zero->next;

while (Cur!=Start && Cur!=Zero)

{

std::cout << Cur->Data << " ";

Cur = Cur->next;

d2(Cur->prev->prev);

}

std::cout << "\n";

}

Дополнительный (проверочный) просмотр списка без удаления узла

void prosmotr2(Zveno* Start, Zveno* Zero)

{

std::cout << Start->Data << " ";

Zveno* Cur = Start->next;

while (Cur!=Start)

{

std::cout << Cur->Data << " ";

Cur = Cur->next;

}

std::cout << "\n";

}

24. Добавить 1 звено в конец очереди (т.е. в конец списка – в позицию перед ведущим звеном).

25. Просмотреть содержимое списка.

for (unsigned short counter = 0; counter < 1; counter ++ )

iN(L1,counter+1);
prosmotr2(L1,L1);



26. Повторить пункты 24, 25 несколько раз.

for (unsigned short counter = 0; counter < 2; counter ++ )

iN(L1,counter+5);

prosmotr2(L1,L1);

for (unsigned short counter = 0; counter < 3; counter ++ )

iN(L1,counter+10);

prosmotr2(L1,L1);



27. Удалить звено из начала очереди (из звена следующего за ведущим звеном).

28. Просмотреть содержимое списка.

prosmotr1(L1->next->next,L1);

prosmotr2(L1,L1);



29. Добавить 1 звено в начало очереди (в позицию за ведущим звеном).

30. Просмотреть содержимое списка.

for (unsigned short counter = 0; counter < 1; counter ++ )

i1(L1,counter+100);

prosmotr2(L1,L1);



31. Повторить пункты 29, 30 несколько раз.

for (unsigned short counter = 0; counter < 2; counter ++ )

i1(L1,counter+105);

prosmotr2(L1,L1);

for (unsigned short counter = 0; counter < 3; counter ++ )

i1(L1,counter+110);

prosmotr2(L1,L1);



32. Удалить звено из конца очереди.

33. Просмотреть содержимое списка.

prosmotrN(L1->prev->prev,L1);

prosmotr2(L1,L1);


34. Удалить все звенья из списка.

prosmotrN(L1,L1);

prosmotr2(L1,L1);

Работа с двоичным деревом поиска

35. Для типа данных, использованного при работе с двусвязным кольцевым списком, создать процедуры, выполняющие операции с двоичным деревом поиска: добавление звена, удаление звена, поиск звена, просмотр дерева в нисходящем и последовательном порядках.

36. Удалить ведущее звено двусвязного кольцевого списка, если оно создавалось (см. пояснения к выполнению задания), и обнулить отводимый для этого звена указатель.

#include
struct Zveno {

unsigned short Data;

Zveno *left;

Zveno *right;

};
void insertData(Zveno* Start, unsigned short data)

{

if (Start->Data < data) {

if (Start->right == NULL) {

Zveno* Loc = new Zveno;

Loc->Data = data;

Start->right = Loc;

} else {

insertData(Start->right,data);

}

} else {

if (Start->left == NULL) {

Zveno* Loc = new Zveno;

Loc->Data = data;

Start->left = Loc;

} else {

insertData(Start->left,data);

}

}

}
void delData(Zveno* Start)

{

if(Start!=NULL) {

Start->left = NULL;

Start->right = NULL;

}

}
int searchData(Zveno* Start, unsigned short data)

{

if (Start->Data == data) {

return 1;

} else {

if (Start->Data < data) {

if (Start->right != NULL) {

return searchData(Start->right, data);

} else {

return 0;

}

} else {

if (Start->left != NULL) {

return searchData(Start->left, data);

} else {

return 0;

}

}

}

return 0;

}
int height(Zveno* Start)

{

if (Start == NULL) {

return 0;

} else {

return 1+std::max(height(Start->left),height(Start->right));

}

}
void prosmotr1(Zveno* Start)

{

if(Start!=NULL) {

prosmotr1(Start->left);

std::cout << Start->Data << " ";

prosmotr1(Start->right);

}

}
void prosmotr2(Zveno* Start)

{

if(Start!=NULL) {

std::cout << Start->Data << " ";

prosmotr1(Start->left);

prosmotr1(Start->right);

}

}
int main() {

Zveno* L1;

L1 = new Zveno;

std::cin >> L1->Data;

return 0;

}

37. Создать двоичное дерево поиска путѐм ввода данных (не менее 7 элементов). Данные подбирать так и вводить в таком порядке, чтобы получилось сбалансированное дерево.

38. Выполнить просмотр дерева в последовательном порядке.

39. Выполнить просмотр дерева в нисходящем порядке.

40. Выполнить поиск данных в дереве.

41. Определить высоту дерева.

42. Удалить все узлы дерева.

for (int counter = 0; counter < 7; counter ++ ) {

std::cin >> a;

insertData(L1,a);

}
std::cout << "Последовательный порядок: ";

prosmotr1(L1);

std::cout << "\n";

std::cout << "Нисходящий порядок: ";

prosmotr2(L1);

std::cout << "\n";
if (searchData(L1,5) > 0) {

std::cout << "Элемент равный 5 найден\n";

} else {

std::cout << "Элемент равный 5 не найден\n";

}

std::cout << "Высота дерева: " << height(L1);

std::cout << "\n";
delData(L1);

std::cout << "Высота дерева после удаления: " << height(L1);

std::cout << "\n";

std::cout << "Последовательный порядок: ";

prosmotr1(L1);

std::cout << "\n";
return 0;



43. Создать двоичное дерево поиска путѐм ввода упорядоченных данных (не менее 7 элементов, в таком же количестве, как и в пункте 37).

44. Выполнить просмотр дерева в последовательном порядке.

45. Выполнить просмотр дерева в нисходящем порядке. Сравнить с результатами выполнения пунктов 38 и 39

46. Определить высоту дерева. Сравнить с результатами выполнения пункта 41



Из результатов работы программы легко обнаружить связь между упорядоченностью вводимых данных и высотой сформированного на их основе дерева. Сбалансированное дерево имеет меньшую высоту и более эффективно для поиска.