Инструменты и приборы для поиска и устранения неисправностей ПК

 

Аннотация

В данной пояснительной  записке содержат 65 страниц, 7 картинок. Программа «Алфавит» занимает 538 байт, «Калькулятор» занимает 535 байт. Данная курсовая  работа раскрывает тему ссылочных данных и динамических переменных. Содержит две главы. В первой главе дается теоретическое объяснение ссылочным данным и динамическим переменным. Во второй главе дает практическое объяснение, которое раскрыто в двух задачах. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тема курсовой работы :Ссылочные типы. Динамические переменные

 

 

 

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

И статические, и динамические переменные вызываются по их адресам. Без адреса не получить доступ к нужной ячейке памяти, но, используя статические переменные, непосредственно адрес не указываете, а обращаетесь к переменной по имени. Компилятор размещает переменные в памяти и подставляет нужные адреса в коды команд.

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

• выделение памяти под динамическую переменную;
• присвоение указателю на динамическую переменную адреса выделенной памяти (инициализация указателя);
• освобождение памяти после использования динамической переменной.

Из этого перечня  видно, что управление памятью касается широкого класса объектов.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

Глава I. Теоретическая часть

1. Указатели. Описание указателей

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

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

1.1. Указатели и адреса

Известно, что адресом  переменной является адрес первого байта ячейки памяти, которая под нее отводится. Для данных структурных типов (массивов и записей) их адресом считается адрес первого байта первого элемента.

В Turbo Pascal существует возможность  прямого доступа к любому байту  оперативной памяти по его адресу при помощи определенных в модуле system массивов Mem, MemW и MemL, которые позволяют записать информацию или прочитать ее непосредственно из ячеек памяти (один, два или четыре байта). Это очень опасные действия, поэтому они исключены в 32- разрядных системах программирования. Все же дадим краткие пояснения для тех, кто работает в среде Borland (Turbo) Pascal.

В качестве индекса в  этих массивах используется адрес, записанный в виде, принятом в DOS: сегмент : Смещение относительно начала сегмента. Такой странный способ записи адреса связан с тем, что в операционной системе DOS вся память разбита на сегменты, размеры которых не превышают 64 Кбайт. Для получения абсолютного адреса из пары сегмент Смещение система прибавляет к сегменту справа шестнадцатеричный ноль (это четыре нуля в двоичной системе), а затем складывает его со смещением. Таким способом можно адресовать 1 Мбайт памяти.

Например, начальный адрес  видеобуфера запишется в виде $B800:$000, а обратиться к самому первому  его байту можно так: Mem[$В800:$0000], к первым двум байтам — MemW[$B800:$0000], к первым четырем байтам — MemL [$B800:$0000]. Абсолютный адрес, соответствующий данной паре, — $B8000.

Еще один пример для любознательных — оператор mem[0:$41C]:=mem[0:$41А]; можно  применить для принудительной очистки буфера клавиатуры. Здесь адрес маркера конца буфера клавиатуры приравнивается к адресу его начала. Конечно, в данном случае лучше воспользоваться средствами модуля crt.

Имеется еще один способ обращения к оперативной памяти — использование служебного слова absolute при описании переменной. В этом случае переменная будет располагаться именно по тому адресу в оперативной памяти, который указан после absolute. Разумеется, использование служебного слова  absolute — столь же опасный способ, как и обращение к памяти через предопределенные массивы.

Однако absolute может использоваться и более безопасным способом, позволяя совмещать в памяти две переменные с разными именами. В языке Pascal есть специальная операция получения  указателя на переменную (или процедуру) — она обозначается как @. Имеется также эквивалентная ей функция addr.

Например, @x или addr(х) —  адрес переменной х.

Имеется и обратная операция получения значения переменной по ее адресу, которая обозначается знаком ^. Например, р^ переменная с адресом р.

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

1.2. Описание указателей

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

Описание двух видов  указателей выполняется по-разному:

var p1: ^integer; {указатель  на переменную целого типа}

      p2: ^string; {указатель на стоку}

      p3 pointer; {нетипизированный указатель}

Заметим что тип pointer совместим  со всеми типами указателей. В дальнейшем изложении для удобства имена  всех указателей будем начинать с  буквы p (pointer).

Каждый указатель размещается в сегменте данных или в стеке (если он объявлен в подпрограмме) и занимает там 4 байта. Это дополнительные “накладные расходы’ памяти. Поэтому обычные переменные очень редко создают и уничтожают динамически, оставляя эту возможность для больших совокупностей данных.

Чем больше размер динамической переменной, тем меньше доля накладных  расходов. Например, при хранении в  динамической памяти массивов больших  размеров лишние 4 байта, затраченные  на указатель, несущественны.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Списки

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

2.1 Линейные однонаправленные списки

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

type

TypeOfElem= Char;

Assoc= ^DynElem;

DynElem= record  

Elem: TypeOfElem;  

NextElem: Pointer

end;

DynStr= Assoc;

На практике, для обработки динамических строк вводят два указателя: на начало и конец (текущий элемент) цепочки.

var HeadOfStr: Pointer; ElemOfStr: DynStr;

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

new( ElemOfStr ); ElemOfStr^.Elem:= ▒▓; ElemOfStr^.NextElem:= nil; HeadOfStr:= ElemOfStr;

Для создания каждого следующего элемента списка должна быть выполнена следующая  последовательность операторов:

new( ElemOfStr^.NextElem ); ElemOfStr:= ElemOfStr^.NextElem; ElemOfStr^.Elem:= ▒▓;

ElemOfStr^.NextElem:= nil; {признак конца списка}

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

1.    очередной элемент списка содержит заданный элемент; тогда значение функции √ истинно, а также известно значение ссылки на это звено;

2.    список исчерпан и заданное значение информационного поля элемента не найдено; при этом значение функции ложно.

function FoundElem(st: DynStr; Info: TypeOfElem; var Result: Pointer): Boolean;

var q: DynStr;

begin  

FoundElem:= False;  

Result:= nil;  

q:= st^.NextElem;  

while ( q <> nil ) and ( Result= nil ) do begin  

if q^.Elem= Info then begin    

FoundElem:= True;    

Result:= q  

end;  

q:= q^.NextElem

end

end;     

 Операция удаления элемента списка должна решать две задачи:

1.    изменение ссылки предыдущего элемента так, чтобы она указывала на следующий;

2.    уничтожение элемента с помощью функции dispose.

procedure DelElem( ElemOfStr: DynStr );

var q, p: DynStr;

begin  

if ElemOfStr^.NextElem <> nil then begin    

q:= ElemOfStr^.NextElem;    

p:= ElemOfStr^.NextElem;    

ElemOfStr^.NextElem:= p^.NextElem;    

dispose( q );  

 end

end;

Для вставки элемента в список необходимо выполнить следующую  последовательность действий:

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

2.    инициализировать информационное поле нового элемента;

3.    полю ссылки нового элемента присвоить значение поля ссылки того элемента, после которого вставляется новый;

4.    полю ссылки элемента, после которого вставляется новый присвоить значение ссылки на новый элемент.

procedure InclElem( Info: TypeOfElem; ElemOfStr: DynStr );

var q:DynStr;

begin  

if not ( ElemOfStr= nil ) then begin    

new( q );    

q^.NextElem:= ElemOfStr^.NextElem;    

q^.Elem:= Info;    

ElemOfStr^.NextElem:= q  

 end

end;

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

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

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

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

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

Данные четыре операции покроются  тремя вариантами вставки: в начало списка, в конец списка и между  двумя элементами списка. Общий алгоритм процедуры должен выглядеть следующим образом (ниже Тек_Ссылка означает ссылку на текущий элемент, а Пред_Ссылка √ значение ссылки на предшествующий):

1.    Установить значение Тек_Ссылка так, чтобы оно указывало на начало списка, положить значение Пред_Ссылка = nil и установить признак того, что положение вставляемого элемента не определено.

2.    Пока в списке остаются еще не просмотренные элементы и положение нового элемента не определено выполнять следующее: - если новый элемент следует за тем, на который указывает Тек_Ссылка, то положить значение Пред_Ссылка равным Тек_Ссылка и изменить значение Тек_Ссылка так, чтобы оно указывало на следующий элемент; - иначе установить признак того, что положение вставляемого элемента не определено.

3.    Если Пред_Ссылка= nil, то вставить элемент в начало списка. Если и Пред_Ссылка и Тек_Ссылка не равны nil, то вставить новый элемент между теми элементами, на которые указывают Пред_Ссылка и Тек_Ссылка. Если Пред_Ссылка не равна nil, а Тек_Ссылка= nil, то вставить новый элемент в конец списка.

procedure InclWithSort( NewElem: DynStr; var HeadOfStr: Pointer);

var

CurrAssoc, PredAssoc: DynStr; {соответственно Тек_Ссылка и Пред_Ссылка}  

IsFounded: Boolean;

begin  

CurrAssoc:= HeadOfStr;  

PredAssoc:= nil;  

IsFounded:= False;  

while ( CurrAssoc <> nil ) and not IsFounded do begin    

if NewElem^.Elem > CurrAssoc^.Elem then begin      

 {перейти к следующему элементу}      

PredAssoc:= CurrAssoc;      

 CurrAssoc:= CurrAssoc^.NextElem    

end      

else IsFounded:= True  

 end;  

{позиция вставки нового элемента  найдена}  

if PredAssoc= nil then begin    

{вставка нового элемента в  начало списка}    

 NewElem^.NextElem:= HeadOfStr;    

HeadOfStr:= NewElem  

end;  

if ( PredAssoc <> nil ) and ( CurrAssoc <> nil ) then begin    

 {вставка элемента между элементами, на которые указывают ссылки PredAssoc      

 CurrAssoc}    

NewElem^.NextElem:= PredAssoc^.NextElem;    

PredAssoc^.NextElem:= NewElem  

end;  

if ( PredAssoc <> nil ) and ( CurrAssoc= nil ) then begin    

{вставка в конец списка}    

PredAssoc^.NextElem:= NewElem;    

NewElem^.NextElem:= nil  

end

end;

2.2 Двунаправленные списки

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

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

2.3 Циклические списки

Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей (см. рис 3).

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

В двунаправленном циклическом  списке система указателей аналогична системе указателей двунаправленного линейного списка (см. рис 4).

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

Разберем решение типичной задачи, связанной с обработкой списков.

Текст задания

С использованием списков, заданный во входном файле текст (за которым  следует точка) распечатать в  обратном порядке.

Решение

program reverse;

type   List= ^Elem;  

Elem= record    

Info: Char;    

Next: List  

end;

var  

L, p: List;  

 c: char;

begin  

{ввод литер текста  и запись их в обратном порядке  в список L (без заглавного звена)}  

L:= nil; {ссылка на построенную  часть списка}  

 read( c );  

while c <> '.' do begin    

 {добавить с в начало списка}    

 new( p );    

p^.Info:= c;    

p^.Next:= L;    

L:= p;    

read( c )  

end;  

{печать литер из L}  

 while L <> nil do begin    

write( L^.Info );    

L:= L^.Next  

end;  

writeln

end.

 

 

 

 

 

 

3. Очереди и стеки

Очередь и стек представляют собой структуры данных с фиксированными механизмами занесения и выбора элементов. Возможны реализации очереди и стека на базе регулярных или списковых структур данных. Соответственно представлению изменяется реализация механизмов обработки структур. Однако определяющими являются следующие принципы: очередь предполагает занесение нового элемента в конец, а выбор с начала списка (FIFO √ First In First Out); в стек элемент заносится в начало и выбирается также сначала (LIFO √ Last In First Out).

3.1 Очередь на базе списка 

Из механизма FIFO следует, что в очереди доступны два элемента √ первый и последний простая очередь (см. рис. 5).

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

type 

TypeOfElem= {}; 

Assoc= ^ElementOfQueue; 

ElementOfQueue= record   

Elem: TypeOfElem;   

NextElem: Pointer 

end; 

 Queue= Assoc;

3.2 Создание (очистка) очереди

Для создания новой пустой или очистки существующей очереди  достаточно присвоить  указателям на первый и последний элементы значение nil.

procedure CreateQueue ( var FirstElem, LastElem: Queue);

begin 

FirstElem:= nil; 

LastElem:= nil

end;

3.3 Проверка очереди на пустоту

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

function QueueIsClear( var FirstElem, LastElem: Queue ): Boolean;

begin 

QueueIsClear:= ( FirstElem= nil ) and ( LastElem= nil )

end;

3.4 Включение элемента в очередь

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

procedure IncludeInQueue( var FirstElem, LastElem: Queue; NewElem: TypeOfElem);

var  

ServiceVar: Queue;

begin  

{создание нового элемента}  

new( ServiceVar );  

ServiceVar^.Elem:= NewElem;  

ServiceVar^.NextElem:= nil;  

if ( FirstElem= nil ) and ( LastElem= nil ) then begin    

 {создать очередь из одного элемента}    

 FirstElem:= ServiceVar;    

LastElem:= ServiceVar  

end    

else begin      

 {созданный элемент поместить в конец очереди}      

 LastElem^.NextElem:= ServiceVar;      

LastElem:= ServiceVar    

end

end;

3.5 Выбор элемента из очереди

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

procedure SelectFromQueue( var FirstElem, LastElem: Queue; var Result: TypeOfElem);

var  

ServiceVar: Queue;

begin  

if not ( ( FirstElem= nil ) and ( LastElem= nil ) ) then begin    

Result:= FirstElem^.Elem;    

ServiceVar:= FirstElem;    

 {убираем 1-ый элемент из очереди}    

 FirstElem:= FirstElem^.NextElem;    

{был ли это последний элемент}    

if FirstElem= nil then      

LastElem:= nil;    

dispose( ServiceVar )  

end

end;

3.6 Стек на базе списка

Из механизма LIFO следует, что в стеке доступен только последний занесенный его элемент √ так называемая вершина стека. Главный элемент, представляющий весь список как единый объект, в случае стека оказывается лишним, его роль выполняет вершина стека. Элемент, занесенный в стек раньше других имеет ссылку nil (см. рис. 6).

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

type  

TypeOfElem= {};  

Assoc= ^ElementOfStack;  

ElementOfStack= record    

Elem: TypeOfElem;    

NextElem: Pointer  

end;  

 Stack= Assoc;     

 Рассмотрим реализацию  основных операций над стеком.

3.7 Создание (очистка) стека

Для создания нового пустого  или очистки существующего стека  достаточно присвоить  указателю на первый его элемент (вершину) значение nil.

procedure CreateStack ( var StackHead: Stack);

begin  

StackHead:= nil

end;

3.8 Проверка стека на пустоту

Условием пустоты стека  является значение его вершины, равное nil.

function StackIsClear( var StackHead: Stack ): Boolean;

begin  

StackIsClear:= ( StackHead= nil )

end;

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

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

procedure IncludeInStack( var StackHead: Stack; NewElem: TypeOfElem );

var  

ServiceVar: Stack;

begin  

{создание нового элемента}

&nbspnew( ServiceVar );  

 ServiceVar^.Elem:= NewElem;  

{созданный элемент  сделать вершиной стека}  

 ServiceVar^.NextElem:= StackHead;  

StackHead:= ServiceVar

end;

3.10 Выбор элемента из стека

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