Поиск элемента в однонаправленном списке
Операция поиска элемента в списке заключается в последовательном просмотре всех элементов списка до тех пор, пока текущий элемент не будет содержать заданное значение или пока не будет достигнут конец списка. В последнем случае фиксируется отсутствие искомого элемента в списке (функция принимает значение false ).
//поиск элемента в однонаправленном спискеbool Find_Item_Single_List(Single_List* Head, int DataItem){ Single_List *ptr; //вспомогательным указатель ptr = Head; while (ptr != NULL){//пока не конец списка if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } return false;}Стеки
В списках доступ к элементам происходит посредством адресации, при этом доступ к отдельным элементам не ограничен. Но существуют также и такие списковые структуры данных, в которых имеются ограничения доступа к элементам. Одним из представителей таких списковых структур является стековый список или просто стек.
Стек (англ. stack – стопка) – это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала. В стеках используется метод доступа к элементам LIFO ( Last Input – First Output, "последним пришел – первым вышел"). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю.
Стек – это список, у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.
|
|
|
Рисунок 4. Стек и его организация
Описание стека выглядит следующим образом:
struct имя_типа { информационное поле; адресное поле; };где информационное поле – это поле любого ранее объявленного или стандартного типа; адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента стека.
struct list { type pole1; list *pole2; } stack;Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с заголовком стека, то есть не требуется осуществлять просмотр элементов, удаление и вставку элементов в середину или конец списка, то достаточно использовать экономичный по памяти линейный однонаправленный список. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует, и указатель принимает значение NULL.
Описание элементов стека аналогично описанию элементов линейного однонаправленного списка. Поэтому объявим стек через объявление линейного однонаправленного списка:
|
|
|
Основные операции, производимые со стеком:
· создание стека;
· печать (просмотр) стека;
· добавление элемента в вершину стека;
· извлечение элемента из вершины стека;
· проверка пустоты стека;
· очистка стека.
Реализацию этих операций рассмотрим в виде соответствующих функций, которые, в свою очередь, используют функции операций с линейным однонаправленным списком. Обратим внимание, что в функции создания стека используется функция добавления элемента в вершину стека.
//создание стекаvoid Make_Stack(int n, Stack* Top_Stack){ if (n > 0) { int tmp;//вспомогательная переменная cout << "Введите значение "; cin >> tmp; //вводим значение информационного поля Push_Stack(tmp, Top_Stack); Make_Stack(n-1,Top_Stack); }} //добавление элемента в вершину стекаvoid Push_Stack(int NewElem, Stack* Top_Stack){ Top_Stack->Top =Insert_Item_Single_List(Top_Stack->Top,1,NewElem);} //извлечение элемента из вершины стекаint Pop_Stack(Stack* Top_Stack){ int NewElem = NULL; if (Top_Stack->Top != NULL) { NewElem = Top_Stack->Top->Data; Top_Stack->Top = Delete_Item_Single_List(Top_Stack->Top,0); //удаляем вершину } return NewElem;} //проверка пустоты стекаbool Empty_Stack(Stack* Top_Stack){ return Empty_Single_List(Top_Stack->Top); } //очистка стекаvoid Clear_Stack(Stack* Top_Stack){ Delete_Single_List(Top_Stack->Top); }Ключевые термины
|
|
|
FIFO (First Input – First Output) – это метод доступа к элементам очереди по принципу "первый пришёл – первый вышел".
LIFO (Last Input – First Output) – это метод доступа к элементам стека по принципу "последним пришел – первым вышел"
Вершина стека – это доступный элемент стека.
Конец очереди – это позиция доступного для вставки в очередь элемента.
Начало очереди – это позиция доступного для извлечения из очереди элемента.
Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления.
Стек – это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала.
Краткие итоги
1. Стек и очередь – это частные случаи линейного списка.
2. Стек является списком, у которого доступен один элемент, называемый вершиной стека. Поместить или извлечь элемент можно только из вершины списка.
3. Стек и очередь как динамические структуры данных можно организовать на основе линейного списка.
|
|
|
4. Основными операциями со стеком являются: создание стека; печать (просмотр) стека; добавление элемента в вершину стека; извлечение элемента из вершины стека; проверка пустоты стека; удаление стека.
5. Очередь является списком, у которого доступны два элемента: начало и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала.
6. Основными операциями с очередью являются: создание очереди; печать (просмотр) очереди; добавление элемента в конец очереди; извлечение элемента из начала очереди; проверка пустоты очереди; удаление очереди.
7. Стек и очередь более экономно расходуют адресное пространство по сравнению с однонаправленными и двунаправленными списками.
Пример
Составить программу обработки динамической структуры данных: в стек, элементы которого упорядочены по возрастанию, вставить новый элемент так, чтобы сохранить упорядоченность.
Математическая модель:
На вход поступает несколько чисел типа Int, формирующих стек;
На выходе получаем отсортированный стек с добавленным пользователем элементом.
Код программного модуля:
#include "stdafx.h"
#include "iostream"
#include <time.h>
using namespace std;
struct stek
{
int d;
struct stek *next; // указатель на следующий элемент стека
};
void push(stek* &next, int d); // функция будет помещать элемент в стек
// next – указатель на вершину стека
int pop(stek* &next); // функция будет извлекать элемент из стека
// вершина которого - next
void push(stek* &next, int d)
{
stek *pv = new stek; // объявляем новую динамическую переменную типа stek
pv->d = d; // записываем значение, которое помещается в стек
pv->next = next; // связываем новый элемент стека с предыдущим
next = pv; // новый элемент стека становится его вершиной
}
int pop(stek* &next)
{
int temp = next->d; // извлекаем в переменную temp значение в вершине стека
stek *pv = next; // запоминаем указатель на вершину стека, чтобы затем
// освободить выделенную под него память
next = next->next; // вершиной становится предшествующий top элемент
delete pv; // освобождаем память, тем самым удалили вершину
return temp; // возвращаем значение, которое было в вершине
}
int output(stek* &next)
{
int out = next->d;
next = next->next;
return out;
}
void main()
{
srand(time(NULL));
int size, elem, k = 0, k2 = 0, k3 = 0;
stek *s1 = new stek;
stek *s2 = new stek;
stek *s3 = new stek;
cout << "Stack: ";
for (int i = 0; i < 10; i++)
{
elem = rand() % 50;
push(s1, elem);
cout << elem << " ";
k++;
}
cout << endl;
int max, tek;
while (k != 0)
{
max = pop(s1);
k--;
push(s2, max);
k2++;
while (k != 0)
{
tek = pop(s1);
k--;
if (tek > max) { max = tek; }
push(s2, tek);
k2++;
}
while (k2 != 0)
{
tek = pop(s2);
k2--;
if (tek == max){ push(s3, tek); k3++; }
else{ push(s1, tek); k++; }
}
}
cout << "Stack sort: ";
while (k3 != 0){
int o = output(s3);
cout << o << " ";
push(s1, o);
k++;
k3--;
}
k++;
cout << endl;
int el = 0;
cout << "Enter element: ";
cin >> el;
push(s1, el);
k2 = 0; k3 = 0;
while (k != 0)
{
max = pop(s1);
k--;
push(s2, max);
k2++;
while (k != 0)
{
tek = pop(s1);
k--;
if (tek > max) { max = tek; }
push(s2, tek);
k2++;
}
while (k2 != 0)
{
tek = pop(s2);
k2--;
if (tek == max){ push(s3, tek); k3++; }
else{ push(s1, tek); k++; }
}
}
while (k3 != 0){
cout << output(s3) << " ";
k3--;
}
cout << endl;
system("pause");
}
Дата добавления: 2020-04-25; просмотров: 118; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!