#include <iostream>
#include <stdlib.h>
void main( )
{ int N; // количество элементов в списке
int a; // искомое значение
int ind; // местоположение искомого эемента
struct node
{ int dat; // информационное поле
struct node *link; // поле-указатель
};
typedef node *Node_ptr; // указатель на тип node
Node_ptr head = NULL;
Node_ptr here; // указатель на текущий элемент
cout << “Введите количество элементов в списке”;
cin >> N;
for (int i = 0; i < N; i++)
{ if (head == NULL)
{ head = new node;
head -> dat = rand() % 100 - 50; // случайным образом
cout << head -> dat << ‘ ‘;
head -> link = NULL;
}
else
{ here = new node;
here -> dat = rand() % 100 - 50;
cout << head -> dat << ‘ ‘;
here -> link = head;
head = here;
}
}
cout << endl;
cout << “Введите искомое значение”;
cin >> a;
here = head; ind = 1; // встали в начало списка
if (here == NULL)
cout << “Список пуст” << endl;
else
{ while (here -> dat != a && here -> link != NULL)
{ here = here -> link;
ind++;
}
if (here -> dat ==a)
cout << “Искомый элемент имеет индекс ” << ind << endl;
else cout << “Элемент не найден” << endl;
}
}
Мы рассмотрели работу с однонаправленными списками. По такому списку можно двигаться только в одном направлении от первого элемента к последнему, быстрого доступа к предшествующим элементам нет. Для устранения этого неудобства в употребление вводятся такие динамические структуры как двунаправленный и кольцевой списки.
Добавим в каждый элемент списка еще одно поле, значением которого будет ссылка на предыдущий элемент списка.
struct node
{ int info;
struct node *next; // указатель на следующий узел
struct node *prev; // указатель на предыдущий узел
};
typedef node *Node_ptr; // указатель на тип node
Node_ptr head = NULL;
Динамическая структура, состоящая из элементов такого типа, называется двунаправленным списком. Двунаправленный список может быть как с заглавным звеном, так и без него.
U
У последнего звена двунаправленного списка нет следующего, у первого звена – нет предыдущего. По такому списку можно двигаться в любом направлении в зависимости от условий задачи.
В программировании двунаправленные списки часто обобщают следующим образом: для последнего элемента следующим является первый, а для первого предыдущим является последний. Списки подобного рода называются кольцевыми двунаправленными списками.
U
В кольцо можно заключить и однонаправленный список. Из процедур обработки кольцевого списка принципиально отличается от процедур обработки линейного только обход списка. При обходе линейного списка мы переходим от одного элемента к другому, пока рабочий указатель не становится равным NULL. При просмотре кольцевого списка надо переходить к следующему элементу до тех пор, пока рабочий указатель не совпадет с указателем на первый элемент. Однако если мы начнем просмотр с первого элемента, то сразу же выйдем из цикла просмотра. Поэтому первый элемент должен обрабатываться отдельно, а обход при помощи цикла надо начинать со второго звена.
б) Очередь
Понятие очереди хорошо известно из повседневной жизни. Структура данных – очередь – в программировании часто используется для моделирования реальных очередей с целью определения их характеристик (средняя длина очереди, время пребывания в очереди и так далее). Поэтому очередь как структура данных должна отражать специфику реальных очередей. По своему существу очередь является сугубо динамическим объектом – с течением времени и длина очереди, и набор образующих ее элементов изменяется.
Очередь - это линейный список, где элементы добавляются в один конец списка, а удаляются с другого конца. Очереди иногда называют списками типа “первым пришел – первым ушел” (First-In-First-Out list – FIFO).
добавить
|
исключить
Описание очереди:
struct och
{int info;
struct och *next;
}
typedef och *OCH_ptr; // указатель на тип och
OCH_ptr head = NULL; // указатель на начало
OCH_ptr tail = NULL; // указатель на хвост
Над очередью определены две операции: занесение элемента в очередь и исключение элемента из очереди. Можно, кроме того, очищать очередь и получать значение первого элемента очереди. В очереди доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы.
Можно реализовать очередь массивом из определенного количества элементов и двумя счетчиками, которые будут указывать положение в массиве начала и конца очереди.
А) Нет элементов в очереди.
head tail
| NULL |
Б) Добавление первого элемента.
head tail
| Х1 | NULL |
В) Добавление второго элемента.
head tail
| Х1 | Х2 | NULL |
Г) Удаление первого элемента.
head tail
| Х2 | NULL |
Такова структура очереди, реализованной связанным динамическим списком.
в) Стек
Стек – это линейный список с одной точкой доступа к элементам, которая называется вершиной стека. Принцип работы со стеком: “последним пришел – первым ушел”. Стек называют также списком типа “LIFO” (Last-In-First-Out list). Операции со стеком возможны только в его вершине.
Стек часто встречается в реальной жизни. Простейший пример – детская пирамида. Процесс сборки и разборки ее подобен процессу функционирования стека. Стек можно сравнить со стопкой книг на полу. Вы можете добавлять книги на вершину стопки и убрать по одной с вершины, но добавить или убрать книгу из середины стопки вы не сможете.
Стек можно определить как массив определенного размера и переменную целого типа, в которой хранится значение количества заполненных элементов стека.
Мы будем реализовывать стек как динамический связанный список.
Описание стека :
struct st
{int info;
st *next;
}
typedef st *ST_ptr; // указатель на тип st
ST_ptr head = NULL; // указатель на вершину стека
Основные операции над стеком:
- выбрать элемент из стека;
- добавить элемент в стек;
- получить значение вершины стека;
- проверить наличие элементов в стеке.
Исторически сложилось, что добавление элемента в стек называют проталкиванием (pushing), а удаление – выталкиванием (popping).
Достаточно много задач в программировании решается с использованием стека. Стек используют в программировании для реализации рекурсии. Рекурсия выполняется так: сначала все вызовы накапливаются (аналогия такая: пружина сжимается), а потом выполняются вложенные процедуры и функции (пружина распрямляется). Одно из применений стека – синтаксический разбор выражения, арифметического или логического, когда не только нужно определить правильность записи, но и вычислить значение выражения. Другой пример – разбор выражения на проверку баланса открывающих и закрывающих скобок. В одном стеке храним открывающие скобки, в другом – закрывающие и соответственно помещаем новую скобку или удаляем скобки, которые являются парными.
Дата: 2019-05-28, просмотров: 224.
