Линейный односвязный список
Методическое руководство и задания
(для студентов 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;
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;
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;
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;
var
l1:list1;
procedure insert1(link:rel1;info:<Тип>);
var
q:elem1;
begin
new(q);
q^.data:=info;
q^.next:=link^.next;
link^.next:=q
end;
procedure delete1(link:rel1);
var
q:rel1;
begin
if link^.next<>nil then
begin
q:=link^.next;
link^.next:=link^.next^.next;
dispose(q);
end
end;
function search1(l:list1;info:<Тип>;var r:rel1):boolean;
var
q:rel1;
begin
search1:=false;
r:=nil;
q:=l^.next;
while (q<>nil) and (r<>nil) do
begin
if q^.data=info then
begin
search:=true;
r:=q
end;
q:=q^.next
end
end;