русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Связные списки


Дата добавления: 2013-12-23; просмотров: 1284; Нарушение авторских прав


Стеки

Циклическая очередь

 

 

Программа Queue_Test останавливается, когда будет достигнут определенный размер массива, используемого для хранения очереди.

 

В циклической очереди используется массив, в котором хранятся элементы очереди как циклический список, а не линейный.

 

Индексы сохранения qnext и извлечения qindex циклически возвращаются к началу массива (0). В такую очередь можно поместить любое количество элементов (если они не только помещаются, но и извлекаются из очереди).

 

Если qindex на 1 больше qnext - очередь заполнена и запись новых элементов невозможна, пока не будут прочитаны элементы, хранящиеся в очереди в данный момент. Если qindex=qnext - очередь пуста. В остальных случаях существует место для помещения по крайней мере еще одного элемента.

Программа создания циклической очереди на языке "Паскаль"

 

// FIFO First In - First Out Очередь

// Queue

 

Programm Queue_Test;

var

q:array[0..30] of Integer;

qnext,qindex,qlength:Integer;

procedure qstore(i:Integer);

begin

if (qnext+1)<>qlength then

begin

q[qnext]:=i;

qnext:=qnext+1;

if qnext=qlength then

qnext:=0 {Циклический переход}

end

else

writeln('Мест нет')

end;function qretrieve():Integer;

begin

if qindex=qlength then

qindex:=0; {Циклический переход}

if qindex=qnext then

begin

writeln('Очередь пуста');

qretrieve:=0;

end

else

begin

qretrieve:=q[qindex];

qindex:=qindex+1

end;

end;begin Содержимое очереди

qlength:=30;

qnext:=0;

qindex:=0;

qstore(1); 1

qstore(2); 1 2

qstore(3); 1 2 3

qretrieve(); {возвращает 1} 2 3

qstore(4); 2 3 4

qretrieve(); {возвращает 2} 3 4

qretrieve(); {возвращает 3} 4



qretrieve(); {возвращает 4} Очередь пуста

end.

 

Стек - разновидность очереди (а значит и разновидность списка), но с другим правилом доступа - L I F O (Last In and First Out - последним пришел и первым ушел). Ещё один термин (редко используемый) для обозначения этой структуры данных - магазин.

 

В стеке доступна единственная позиция - та, в которой находится последний введённый элемент - вершина. Иногда позицию, от которой стек начал заполняться данными, называют дном стека (хотя особого применения этот термин не имеет, поскольку дно стека, в котором содержится хотя бы один элемент данных, недоступно. Одно из немногих рациональных применений термина "дно" - признак пустого стека, когда дно и вершина совпадают).

 

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

 

Области применения стеков такие же, как и у очередей:

 

Системные - передача процедурам и функциям аргументов по значению;

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

 

Прикладные - стековая (магазинная) память, например в языке программирования Forth; вспомогательные структуры данных (например, при поиске в графе).

 

Примеры стеков. Второе название стека - магазин, - приводит к механическому примеру стека - магазин стрелкового оружия. Ещё один простой пример - стакан.

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

 

Ниже приведёны примеры процедур занесения и извлечения данных для стека на основе массива на языках Паскаль и Си++.

Программа работы со стеком на языке Паскаль

Programm Stack_Test;

const

N=30;

var

stack:array[0..N] of char;

slen,pos:integer;

 

procedure push(i:char);

begin

if pos<slen then

begin

stack[pos]:=i;

pos:=pos+1

end

else

writeln('Стек полон.');

end;

 

function pop():char;

begin

if pos=0 then

begin

writeln('Стек пуст.');

pop:=0

end

else

begin

pos:=pos-1;

pop:=stack[pos]

end;

end;

 

Pos - индекс следующей открытой позиции - вершины стека. Если Pos больше индекса последнего сохранения, значит стек заполнен; если Pos=0 - стек пуст.

begin Содержимое стека

slen:=N;

pos:=0;

push('A'); A

push('B'); B A

push('C'); C B A

pop(); {Возвращает C} B A

push('D'); D B A

pop(); {Возвращает D} B A

pop(); {Возвращает B} A

pop(); {Возвращает A} Стек пуст

end.

 

 

Аналогичная программа на языке Си++

 

#include <iostream>

using namespace std;

 

const int N=30;

char stack[N];

int pos=0,slen=N;

 

// Занесение элемента в стек.

void Push(char i)

{

if(pos==slen)

{

cout<<"Стек полон!\n";

return;

}

stack[pos]=i;

pos++;

}

 

// Извлечение элемента из стека.

char Pop()

{

if(pos==0)

{

cout<<"Стек пуст.\n";

return 0;

}

pos--;

return stack[pos];

}

 

void main() Содержимое

{

Push(‘A’); A

Push(‘B’); B A

Push(‘C’); C B A

cout>>Pop()>>endl; // Возвр. C B A

Push(‘F’); F B A

cout>>Pop()>>'\n'; // Возвр. F B A

cout>>Pop()>>endl; // Возвр. B A

}

 

Представим стек, как динамическую цепочку звеньев, т.е. связный список. Первое звено - вершина. Так как доступна только вершина, то в таком списке главное звено становится излишним. Стек как единый объект представляет указатель, значение его - адрес вершины стека. Каждое звено цепочки содержит указатель на следующее звено, "дно" стека - элемент, занесенный первым, имеет этот указатель равным nil.

Программа работы с динамическим стеком на языке Паскаль

 

Programm Stack_Test;

 

Стек, как структура данных, задается набором типов.

 

type (* Секция описания типов *)

stype=real;

next=^elem;

elem=record (* Запись *)

dr:next;

data:stype

end;

stack=next;

var

p:stack;

procedure push(var st:stack; newl:stype);

var

q:next;

begin

new(q);

q^.data:=newl; (* новое звено *)

q^.dr:=st;

st:=q; (* новое звено - вершина *)

end;

 

 

Наличие у процедуры аргумента push(var st:stack, ... ) позволяет работать с несколькими стеками.

 

function pop(var st:stack):stype;

var

q:next;

begin

if st=nil then

writeln('Стек пуст.')

else

begin

pop:=st^.data;

q:=st;

st:=st^.dr;

dispose(q)

end;

end;

 

var P: stack;

 

Если стек пуст, то значение указателя P равно nil. К началу использования стека его нужно сделать пустым при помощи оператора p := nil;

 

begin

p := nil;

push(p,43);

writeln(pop(p):3:9);

push(p,54);

writeln(pop(p):3:9);

readln;

end.

Аналогичные процедуры на языке Си++

 

typedef float stype; /* Необязательное переименование типа float (может использоваться любой тип) в имя stype */

struct elem

{

elem* dr; // указатель на другой такой же элемент

stype data; // хранимые в стеке данные

};

 

void Push(elem*& st,stype newel)

{

elem* q=new elem;

q->data=newel; // Новое звено

q->dr=st;

st=q; // Новое звено становится вершиной стека.

}

 

stype Pop(elem*& st)

{

stype a;

elem *q;

if(st==NULL)

{

cout<<"Стек пуст.\n";

return;

}

a=st->data;

q=st;

st=st->dr;

delete q;

return a;

}

 

Понятие "списки" включает в себя самые разные структуры данных. Это могут быть и массивы, в том числе массивы записей, и специальные динамические структуры данных, и даже деревья. Общим для них является то, что они содержат набор записей одного вида, ограниченный по размеру или неограниченный, упорядоченный или неупорядоченный. Данные, хранящиеся в этих записях, обычно логически связаны между собой, например, фамилии студентов одной группы и т.п. В тексте программы такая связь может выражаться в том, что все такие элементы хранятся в одном и том же массиве как непрерывном блоке памяти. Но кроме общего имени массива (и адреса его начала) между этими элементами никакой другой физической связи нет, и на физическом уровне подобные списки могут быть названы "несвязными" (или, что (почти) то же самое, "несвязанными"). Т.е. внутри них нет связей (их элементы не связаны друг с другом физически).

 

Типичным примером несвязного (физически) списка является массив. В этой главе мы рассмотрим те самые "специальные динамические структуры данных", которые и получили название связных списков.

 

 

Вспомним общие черты очередей и стеков:

Строгие правила доступа к данным;

Операции извлечения (считывания) данных являются разрушающими.

 

Связные списки свободны от этих ограничений. Они допускают гибкие методы доступа; извлечение (чтение) элемента из списка не приводит к удалению его из списка и потере данных. Для фактического удаления элемента из связного списка требуется специальная процедура.

 

Связные списки представляют собой (как уже было сказано) динамические (фактически, линейные!) структуры данных (динамические цепочки звеньев), в которых однотипные элементы (звенья) каким-либо образом связаны между собой, обычно на физическом уровне. Связь между элементами можно осуществить за счёт хранения в одном элементе адреса другого такого же элемента (того же типа). Т.е. каждый информационный элемент содержит внутри себя указатель на собственный тип. Учитывая, что кроме этого указателя должны присутствовать полезные данные, тип информационного элемента оказывается записью. Например, для простейшего вида списка этот тип может быть следующим (на языках Си/Си++):

 

struct Link1

{

int data;

Link1* next;

};

 

Классификация связных списков. По числу связей (и одновременно, направлению) списки бывают односвязными (однонаправленными), двусвязными (двунаправленными) и многосвязными.

 

По способу организации связей (или по архитектуре) списки могут быть линейными и кольцевыми (циклическими). (Если список не является ни линейным, ни кольцевым, то остаётся единственный вариант - ветвящийся список, фактически являющийся одной из древовидных структур данных.)

 

По степени упорядоченности хранимых данных списки могут быть упорядоченными и неупорядоченными. Такое разделение иногда бывает удобно на практике, но для поддержания упорядоченности списков приходится прибегать к специальным мерам.

 

Для списков, по сравнению с очередями и стеками, имеется значительно больше операций, которые включают в себя:

- добавление нового звена списка (вставка звена);

- удаление звена;

- просмотр (или прохождение) списка;

- поиск данных в списке;

- создание ведущего (заглавного) звена (при необходимости);

- сортировка списка;

- обращение (реверсирование) списка, т.е. перестановка всех его звеньев в обратном порядке.

 

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

 

 



<== предыдущая лекция | следующая лекция ==>
Машина Тьюринга | Линейный односвязный список


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.011 сек.