Связанные списки, очереди, стеки, кольца

Лабораторная работа №10

Список – это набор элементов (чаще всего структурных переменных) размещаемых в динамической памяти и связанных между собой с использованием указателей на эти элементы. Применяемый способ связывания элементов определяет тип списка.

Списки бывают линейными и кольцевыми, односвязными и двусвязными. Элемент односвязного списка содержит кроме непосредственно «полезной» информации также информацию о следующем либо предыдущем элементе списка. Соответственно элемент двусвязного списка содержит информацию, как о следующем, так и о предыдущем элементах. Последний элемент кольцевого списка содержит указатель на первый элемент списка.

Графическое изображение списков показано на рис. 1.1.

Односвязный линейный список	Двусвязный линейный список	Односвязный кольцевой список

Рис. 1.1. Графическое изображение списков

Самыми распространёнными случаями линейного односвязного списка служат стек и очередь.

Очередь – это список с таким способом связи между элементами, при котором новые элементы добавляются строго в конец списка, а извлекаются для обработки строго из начала.

Стек – это список с таким способом связи между элементами, при котором новые элементы добавляются строго в начало списка и извлекаются для обработки также строго из начала списка, т.е. первый занесённый в стек элемент будет обработан последним).

Кольцо – это список, элементы которого образуют замкнутую круговую систему, т.е. последний созданный элемент должен содержать указатель на первый элемент.

Списки могут быть двунаправленными, что даёт возможность обхода списков в двух направлениях. У линейных списков в первых элементах указатель на предыдущий элемент, как правило, равен нулю. У двунаправленного кольца первый элемент указывает на последний, а последний – на первый.

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

struct node

{

int data;

structnode *nextPtr;

};

описывает тип struct node. Структура типа struct node состоит из двух элементов — целого data и указателя nextPtr. Элемент nextPtr указывает на структуру типа struct node — структуру того же самого типа, что и только что объявленная, отсюда и термин «структура, ссылающаяся на себя». Элемент nextPtr иногда называют связкой, т.е. nextPtr можно использовать для того, чтобы связать структуру типа struct node с другой структурой того же типа. Структуры, ссылающиеся на себя, могут связываться вместе для образования других структур данных, таких как списки, очереди, стеки и деревья.

Рис. 1.2. Графическая иллюстрация двух, ссылающихся на себя структур, связанных друг с другом

Графическая иллюстрация двух структур, ссылающиеся на себя, связанных друг с другом и образующих список приведена на рис. 3.20. На рис. 1.2 в связывающем элементе второй структуры нарисована, представляющая указатель NULL, косая черта, чтобы показать, что этот элемент не указывает на другую структуру. Косая черта используется исключительно для иллюстрации и не имеет никакого отношения к символу обратной дробной черты языка Си. Указатель NULL обычно обозначает конец структуры данных, так же как символ NULL обозначает конец строки.

Связанный список — это линейный набор ссылающихся на себя структур, называемых узлами, и объединенных указателем-связкой, отсюда и название — «связанный» список. Доступ к связанному списку обеспечивается указателем на первый узел списка. Доступ к следующим узлам производится через связывающий указатель, хранящийся в каждом узле. По общему соглашению связывающий указатель в последнем узле списка устанавливается в NULL, отмечая конец списка. Данные хранятся в связанном списке динамически — каждый узел создается по мере необходимости. Узел может содержать данные любого типа, включая другие структуры. Стеки и очереди также принадлежат к линейным структурам данных, и являются специальными вариантами связанных списков. Деревья же являются нелинейными структурами данных.

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

Связанные списки могут содержаться в сортированном виде, если помещать каждый новый элемент в соответствующую позицию списка.

Узлы связанных списков, как правило, не располагаются в памяти в виде одной сплошной области. Логически связанный список представляется непрерывным. Графическая иллюстрация иллюстрирует связанного списока с несколькими узлами приведена на рис. 1.3.

Рис. 1.3. Графическая иллюстрация связанного списка
с несколькими узлами.

Стек — это упрощенный вариант связанного списка. Новые узлы могут добавляться в стек и удаляться из стека только сверху. По этой причине, стек часто называют структурой вида последним пришел — первым обслужился (LIFO). На стек ссылаются через указатель на верхний элемент стека. Связывающий элемент в последнем узле стека установлен равным NULL,чтобы пометить границу стека.

Графическое представление стека с несколькими узлами показано на рис. 1.4. Следует отметить, что стеки и связанные списки представляются идентично. Разница между стеком и связанными списками в том, что вставку и удаление в связанных списках можно выполнять в любом месте, а в стеке только сверху.

Рис. 1.4. Графическая иллюстрация стека

Примеры. Программа работает с простым стеком целых чисел. Программа выполняет три действия на выбор: 1) помещает значение в стек (функция push), 2) извлекает значение из стека (функция pop), и 3) завершает работу.

#include "stdafx.h"

#include<stdlib.h>

#include<malloc.h>

#include<stdio.h>

struct stackNode

{

int data;

struct stackNode *nextPrt;

};

typedef struct stackNode STACKNODE;

typedef STACKNODE * STACKNODEPTR;

void push(STACKNODEPTR *, int);

int pop(STACKNODEPTR *);

int isEmpty(STACKNODEPTR);

void printStack(STACKNODEPTR);

void instruc(void);

void main()

{

STACKNODEPTR stackPtr = NULL;

int choice, value;

instruc();

printf("? ");

scanf("%d", &choice);

while (choice !=3)

{

switch (choice)

{

case 1:

printf("Enter an integer >> ");

scanf("%d", &value);

push (&stackPtr, value);

printStack(stackPtr);

break;

case 2:

if (!isEmpty(stackPtr))

printf("the popped value is %d \n", pop(&stackPtr));

printStack(stackPtr);

break;

default:

printf("Error enter\n");

instruc();

break;

}

printf("? ");

scanf("%d", &choice);

}

printf("End \n");

}

void instruc(void)

{

printf("1 - dobavit\n");

printf("2 - delete\n");

printf("3 - exit\n");

}

void push(STACKNODEPTR *topPtr, int info)

{

STACKNODEPTR newPtr;

newPtr = new STACKNODE;

if (newPtr != NULL)

{

newPtr ->data = info;

newPtr ->nextPrt = * topPtr;

*topPtr = newPtr;

}

else

printf("%d Error not memori\n", info);

}

int pop(STACKNODEPTR *topPtr)

{

STACKNODEPTR tempPtr;

int popValue;

tempPtr = *topPtr;

popValue = (*topPtr) ->data;

*topPtr = (*topPtr) ->nextPrt;

free(tempPtr);

return popValue;

}

void printStack(STACKNODEPTR currentPtr)

{

if (currentPtr == NULL)

printf("Error not stack\n\n");

else

{

printf("Stack is :>> \n");

while (currentPtr != NULL )

{

printf("%d -> ", currentPtr ->data);

currentPtr = currentPtr ->nextPrt;

}

printf("\n");

}

}

int isEmpty (STACKNODEPTR topPtr)

{

return topPtr == NULL;

}

В данном примере основные функции, используемые при работе со стеками — push и pop. Функция push создает новый узел и помещает его на вершину стека. Функция pop удаляет верхний узел стека, освобождает память, которая была выделена изъятому узлу, и возвращает изъятое значение.

Программа работает с простым стеком целых чисел. Программа выполняет три действия на выбор: 1) помещает значение в стек (функция push), 2) изымает значение из стека (функция pop), и 3) завершает работу.

Функция push помещает новый узел на вершину стека. В выполнении функции можно выделить три этапа:

1. Создание нового узла посредством вызова malloc, при этом указателю newPtr присваивается адрес блока выделенной памяти; переменной newPtr -> data присваивается значение, которое необходимо поместить в стек; и указателю newPtr->nextPtr присваивается NULL.

2. Указателю newPtr->nextPtr присваивается *topPtr (указатель на вершину стека); связывающий элемент newPtr теперь указывает на узел, который был верхним до этого.

3. *topPtr присваивается значение newPtr; *topPtr теперь указывает на новую вершину стека. Операции, включающие в себя *topPtr,меняют значение stackPtrв main.

а)
б)

Рис. 1.5. Графическая иллюстрация выполнения функции push

Наглядное представление о том, как происходит выполнение функции push показано на рис. 1.5. На рис. 1.5, а изображен стек и новый узел перед выполнением функции push. Пунктирные линии на рис. 1.5, б иллюстрируют шаги 2 и 3 выполнения функции push, в результате которых узел, содержащий 12, становится новой вершиной стека.

Функция pop удаляет верхний узел стека. Отметим, что перед тем как вызвать функцию pop, функция main определяет, не пуст ли стек. В выполнении функции pop можно выделить пять основных этапов:

1. Указателю tempPtr присваивается *topPtr (tempPtr будет использован для освобождения ненужной памяти).

2. Переменной popValue присваивается значение (*topPtr)->data (сохраняется значение, находившееся в верхнем узле).

3. *topPtr присваивается (*topPtr)->nextPtr (*topPtr присваивается адрес нового верхнего узла).

4. Освобождается память, на которую указывает tempPtr.

5. Вызывающей функции возвращается значение popValue (в примере программы это функция — main).

Выполнение функции pop проиллюстрировано на рис. 1.6. На рис. 1.6, а показано состояния стека после предыдущей операции push. На рис. 1.6, б выделены указатели tempPtr, указывающий на первый узел стека, и *topPtr, указывающий на второй узел. Для освобождения указанной tempPtr памяти вызывается функция free.

а)
б)

Рис. 1.6. Графическая иллюстрация выполнения функции pop

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

На стеке выделяется пространство для автоматических переменных при каждом вызове функции. Когда происходит возврат от вызванной функции к вызывающей, пространство автоматических переменных функции удаляется из стека, и эти переменные становятся для программы неизвестными.

Компиляторы используют стеки в процессе вычисления выражений и создания кода машинного языка.