Линейный односвязный список

Методическое руководство и задания

(для студентов 3-го курса заочного факультета,

направление 050102 – компьютерная инженерия)

Профессор Ляхов А.Л.

ЦЕЛИ И ЗАДАЧИ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ

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

Изучение курса «Структуры и алгоритмы обработки данных в ЭВМ» опирается на знания, умения и навыки, которые студенты должны получить при изучении дисциплин: «Математический анализ», «Линейная алгебра и аналитическая геометрия», «Информатика», «Программирование», «Дискретная математика».

Целью изучения курса «Структуры и алгоритмы обработки данных в ЭВМ» является глубокое освоение студентами методов представления данных в памяти ЭВМ и основных алгоритмов, оперирующих с ними.

Студент должен иметь представление:

· об основных структурах представления данных в ЭВМ;

· об алгоритмах, оперирующих со структурами;

· об использовании структур представления данных для решения возникающих задач;

· знать и уметь использовать:

· основные понятия алгоритмических структур для построения алгоритмов и задач по их математическим моделям;

· должен приобрести навыки:

· грамотной постановки задач, возникающих в практической деятельности для их решения с помощью ЭВМ;

· разработки оптимальных алгоритмов для решения поставленных задач;

· формализованного описания поставленных задач.

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

Неотъемлемой частью курса является лабораторный практикум, при прохождении которого студентами приобретаются навыки программирования в интегрированной среде Turbo Pascal 7.0 или WS C++ (по желанию).

ТЕМЫ

Для самостоятельного изучения

Очереди

Списки - Динамические структуры данных.

Очередь - линейный список, доступ к элементам которого происходит по принципу FIFO (First In and First Out - первым пришел и первым ушел).

Для очереди характерны две операции - Занесение элемента в очередь и выбор элемента из очереди. В очереди доступны две позиции - начало (из этой позиции происходит выбор) и конец (в эту позицию заносится входящий элемент).

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

Применение:

диспетчеризация задач операционной системой (системная задача);

буферизация ввода/вывода (системная задача);

моделирование процессов (прикладная задача).

Пример программы с процедурами постановки и выбора из очереди - Queue_Test.

Функция qretrieve() извлекает из очереди первый элемент; хранившиеся в этом элементе данные разрушаются. Если из очереди удалены все элементы, она становится пустой. На самом деле qretrieve() в этом примере не разрушает информацию, но информацию можно считать удаленной, так как дальнейший доступ к ней невозможен.

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

// 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

qnext:=qnext+1;

q[qnext]:=i

end

else

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

end;function qretrieve():Integer;

begin

if qindex=qnext then

begin

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

qretrieve:=0;

end

else

begin

qindex:=qindex+1;

qretrieve:=q[qindex]

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.

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

Программа 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.

Стеки

Стек - разновидность очереди, но с противоположным по смыслу методом доступа - LIFO (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;

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.

Программа Stack_Test.

Pos - индекс следующей открытой позиции - вершины стека.

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

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

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;

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;

begin

push(p,43);

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

push(p,726,54);

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

readln;

end.

Программа Stack_Test.

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

Каждое звено цепочки содержит указатель на следующее звено, "дно" стека - элемент, занесенный первым имеет этот указатель равным nil.

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

Может быть несколько стеков: push(var st:stack, ... ).

Если стек P пуст, то значение указателя P равно nil.

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

Списки

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

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

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

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

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

По направлению связей связные списки бывают односвязными (однонаправленными) и двусвязными (двунаправленными).

По способу организации связей связные списки могут быть линейными и кольцевыми (циклическими).

Линейный односвязный список

Как следует из названия, каждый элемент такого списка содержит указатель на следующий элемент. Таким образом, тип информации элемента должен быть записью (структурой). Односвязный список можно определить с помощью описаний типов (см. пример 1).

В списке предусмотрено заглавное звено. Указатель списка (l1), значение которого - адрес заглавного звена, представляет список как единый объект.

Указатель на следующий элемент в последнем звене списка имеет значение nil (NULL).

Недостаток: По односвязному списку можно двигаться только от заглавного звена к последнему. Начинать можно с любого звена в списке, но если вдруг возникнет необходимость обратиться к предшествующим элементам, придется начинать с заглавного звена, что неудобно, нерационально и усложняет алгоритм обработки.

Для списков, кроме операций, рассмотренных ранее для очередей и стеков, существуют операции:

создание заглавного звена;

вставка;

удаление;

поиск.

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

rel=^elem;

elem=record

next:rel1;

data:<Тип хранимых данных>

end;

list1=rel1;