КУРСОВАЯ  РАБОТА

По дисциплине: «ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ»

ТЕМА: «Указатель и динамическая память в Турбо  Паскаль» 
 
 

Выполнила: 

Проверил: 
 
 
 
 
 
 
 

2011

Содержание:

Введение

    Даже  при наличии десятков тысяч программ для IBM PC пользователям может потребоваться  что-то такое, чего не делают (или делают, но не так) имеющиеся программы. В этих случаях следует использовать системы программирования, т.е. системы для разработки новых программ.

    История искусства программирования насчитывает  уже десятки лет. И языков программирования уже становится чуть больше, чем хотелось бы. Из универсальных языков программирования сегодня наиболее популярны следующие: Бейсик (Basic); Паскаль (Pascal); Си++ (C++), Ява (Java).

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

    Концепция Паскаля была разработана Н. Виртом примерно в 1970 году и Паскаль быстро получил широкое распространение  благодаря легкости его изучения, наглядности составленных на нем текстов программ.

    Система программирования Турбо Паскаль, разработанная  американской корпорацией Borland, остается одной из самых популярных систем программирования в мире. Этому способствуют, с одной стороны, простота лежащего в ее основе языка программирования Паскаль, а с другой - труд и талант сотрудников Borland во главе с идеологом и создателем Турбо Паскаля Андерсом Хейлсбергом, приложивших немало усилий к ее совершенствованию. Придуманный швейцарским ученым Никласом Виртом как средство для обучения студентов программированию, язык Паскаль стараниями А.Хейлсберга превратился в мощную современную профессиональную систему программирования, которой по плечу любые задачи – от создания простых программ, предназначенных для решения несложных вычислительных задач, до разработки сложнейших реляциооных систем управления базами данных. Появление Windows и инструментальных средств Borland Pascal with Objects и Delphi для разработки программ в среде Windows лишний раз показало, какие поистине неисчерпаемые возможности таит он в себе: и Borland Pascal, и используемый в Delphi язык Objects Pascal основываются на Турбо Паскале и развивают его идеи.

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

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

    Для достижения поставленной цели необходимо решить следующие задачи:

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

    Актуальностью выбранной темы в настоящее время является то, что современные системы программирования являются неотъемлемой частью компьютерных технологий.

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

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

    - изучение и анализ научной литературы;

    - изучение и обобщение отечественной и зарубежной практики;

    -  сравнение, анализ и т.д. 

1. Понятие указателей и динамической памяти.

    1.1 Понятие динамической памяти.

    Все переменные, объявленные в программе, размещаются в одной непрерывной  области оперативной памяти, которая  называется сегментом данных. Длина  сегмента данных определяется архитектурой микропроцессоров 80x86 и составляет 65536 байт, что может вызвать известные затруднения при обработке больших массивов данных. С другой стороны, объем памяти ПК (обычно не менее 640 Кбайт) достаточен для успешного решения задач с большой размерностью данных. Выходом из положения может служить использование так называемой динамической памяти.

    Динамическая  память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайт), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти можно варьировать в широких пределах (см. прил.1). По умолчанию этот размер определяется всей доступней памятью ПК и, как правило, составляет не менее 200...300 Кбайт.

    Динамическая  память - это фактически единственная возможность обработки массивов данных большой размерности. Многие практические задачи трудно или невозможно решить без использования динамической памяти. Такая необходимость возникает, например, при разработке систем автоматизированного проектирования (САПР): размерность математических моделей, используемых в САПР, может значительно отличаться в разных проектах; статическое (т.е. на этапе разработки САПР) распределение памяти в этом случае, как правило, невозможно. Наконец, динамическая память широко используется для временного запоминания данных при работе с графическими и звуковыми средствами ПК.

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

    Динамическую  память обычно используют при:

1. обработке больших массивов данных;
2. разработке САПР;
3. временном запоминании данных при работе с графическими и звуковыми средствами ЭВМ.

    Размещение  статических переменных в памяти осуществляется компилятором в процессе компиляции.

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

    1.2 Адреса и указатели.

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

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

    В ПК адреса задаются совокупностью двух шестнадцатиразрядных слов, которые  называются сегментом и смещением. Сегмент - это участок памяти, имеющий  длину 65536 байт (64 Кбайт) и начинающийся с физического адреса, кратного 16 (т.е. О, 16, 32, 48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу.

    Адресное  пространство ПК составляет 1 Мбайт (речь идет о так называемой стандартной  памяти ПК; на современных компьютерах  с процессорами 80386 и выше адресное пространство составляет 4 Гбайт, однако в Турбо Паскале нет средств, поддерживающих работу с дополнительной памятью; при использовании среды Borland Pascal with Objects 7.0 такая возможность имеется). Для адресации в пределах 1 Мбайта нужно 20 двоичных разрядов, которые получаются из двух шестнадцатиразрядных слов (сегмента и смещения) следующим образом (рис.1): содержимое сегмента смещается влево на 4 разряда, освободившиеся правые разряды заполняются нулями, результат складывается с содержимым смещения.

Рисунок 1 Схема формирования адреса в ПК 

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

    Таким образом, по своей внутренней структуре  любой указатель представляет собой  совокупность двух слов (данных типа WORD), трактуемых как сегмент и смещение. С помощью указателей можно размещать  в динамической памяти любой из известных  в Турбо Паскале типов данных. Лишь некоторые из них (BYTE, CHAR, SHORTINT, BOOLEAN) занимают во внутреннем представлении один байт, остальные - несколько смежных. Поэтому на самом деле указатель адресует лишь первый байт данных.

    1.3 Объявление указателей.

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

    var

    P1 :^Integer; 

    р2 :^Real; 

    type

    PerconPointer = PerconRecord; 

    PerconRecord = record

    Name : String;

    Job : String;

    Next : PerconPointer 

    end;

    Следует обратить внимание, что при объявлении типа PerconPointer была ссылка на тип PerconRecord, который предварительно в программе объявлен не был. Как уже отмечалось, в Турбо Паскале последовательно проводится в жизнь принцип, в соответствии с которым перед использованием какого-либо идентификатора он должен быть описан. Исключение сделано только для указателей, которые могут ссылаться на еще не объявленный тип данных. Это исключение сделано не случайно. Динамическая память дает возможность реализовать широко используемую в некоторых программах организацию данных в виде списков. Каждый элемент списка имеет в своем составе указатель на соседний элемент (рис. 2), что обеспечивает возможность просмотра и коррекции списка. Если бы в Турбо Паскале не было этого исключения, реализация списков была бы значительно затруднена.

Рисунок 2 Списочная структура данных 

    В Турбо Паскале можно объявлять  указатель и не связывать его  при этом с каким-либо конкретным типом данных. Для этого служит стандартный тип POINTER, например:

    var

    р: pointer;

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

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

    var

    p1,p2: integer; 

    р3 : Rеа1; 

    рр : pointer;

    то  присваивание

    p1 := р2;

    вполне  допустимо, в то время как

    р1 := р3;

    запрещено, поскольку Р1 и Р3 указывают на разные типы данных. Это ограничение, однако, не распространяется на нетипизированные указатели, поэтому мы могли бы записать

    pp := p3; 

    p1 := pp;

    и тем самым достичь нужного  результата.

2. Выделение и освобождение динамической памяти.

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

    Начало  кучи хранится в стандартной переменной HEAPORG (рис.3), конец - в временной HEAPEND. Текущую границу незанятой динамической памяти указывает указатель HEAPPTR.

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

    var

    i, j : Integer; 

    r : Real; 

    begin 

    New(i) ;

    .......

    end.

    После выполнения этого фрагмента указатель / приобретет значение, которое перед  этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличит свое значение на 2, так как длина внутреннего представления типа INTEGER, с которым связан указатель I, составляет 2 байта (на самом деле это не совсем так: память под любую переменную выделяется порциями, кратными 8 байтам. Оператор

    new(r);

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

Рисунок 3 Расположение кучи в памяти ПК

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

    i := 2; {B область памяти i помещено значение 2} 

    r := 2*pi; {В область памяти r помещено  значение 6.28}

    Таким образом, значение, на которое указывает  указатель, т.е. собственно данные, размещенные в куче, обозначаются значком ^, который ставится сразу за указателем. Если за указателем нет значка ^, то имеется в виду адрес, по которому размещены данные.

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

    r := sqr(r) + i - 17;

    Разумеется, совершенно недопустим оператор

    r := sqr(r) + i - 17;

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

    r := sqr(r) ;

    поскольку значением указателя R является адрес, и его (в отличие от того значения, которое размещено по этому адресу) нельзя возводить в квадрат. Ошибочным  будет и такое присваивание:

    r :=i;

    так как вещественным данным, на которые указывает R, нельзя присвоить значение указателя (адрес).

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

    dispose (r) ; 

    dispose (i) ;

    вернут  в кучу 8 байт, которые ранее были выделены указателям I и R.

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

    const

    p:  Real = NIL;

    begin

    .......

    if p = NIL then

    new(p);

    .......

    dispose(p); 

    p := NIL;

    .......

    end.

    Никакие другие операции сравнения над указателями  не разрешены.

    Приведенный выше фрагмент иллюстрирует предпочтительный способ объявления указателя в виде типизированной константы с одновременным присвоением ему значения NIL. Следует учесть, что начальное значение указателя (при его объявлении в разделе переменных) может быть произвольным. Использование указателей, которым не присвоено значение процедурой NEW или другим способом, не контролируется системой и может привести к непредсказуемым результатам.

    Чередование обращений к процедурам NEW и DISPOSE обычно приводит к «ячеистой» структуре  памяти. Дело в том, что все операции с кучей выполняются под управлением  особой подпрограммы, которая называется администратором кучи. Она автоматически пристыковывается к Вашей программе компоновщиком Турбо Паскаля и ведет учет всех свободных фрагментов в куче. При очередном обращении к процедуре NEW эта подпрограмма отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи.

    Другая  возможность состоит в освобождении целого фрагмента кучи. С этой целью  перед началом выделения динамической памяти текущее значение указателя HEAPPTR запоминается в переменной-указателе с помощью процедуры MARK. Теперь можно в любой момент освободить фрагмент кучи, начиная от того адреса, который запомнила процедура MARK, и до конца динамической памяти. Для этого используется процедура RELEASE. Например:

    var

    p,p1,p2,

    рЗ,р4,р5 : Integer; 

    begin

    new(p1);

    new(p2) ;

    mark(p); .

    new(p3);

    new(p4);

    new(p5)

    ......

    release(p); 

    end.

    В этом примере процедурой MARK(P) в указатель  Р было помещено текущее значение HEAPPTR, однако память под переменную не резервировалась. Обращение RELEASE(P) освободило динамическую память от помеченного места до конца кучи. Рисунок 4 иллюстрирует механизм работы процедур NEW-DISPOSE и NEW-MARK-RELEASE для рассмотренного примера и для случая, когда вместо оператора RELEASE(P) используется, например, DISPOSE(P3).

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

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

    GETMEM (P, SIZE) - резервирование памяти; 

    FREEMEM(P, SIZE) - освобождение памяти.

    Здесь Р - нетипизированный указатель;

    SIZE - размер в байтах требуемой  или освобождаемой части кучи.

Рисунок 4 Состояние динамической памяти: а) перед освобождением; б) после Dispose(p3); в) после Release(p) 

    За  одно обращение к куче процедурой GETMEM можно зарезервировать до 65521 байта динамической памяти.

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

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

    var

    i,j : Integer; 

    r : Real; 

    begin

    new(i); {i := HeapOrg; HeapPtr:= HeapOrg + 2}

    j := i; {j := HeapOrg} 

    j := 2;

    dispose(i); {HeapPtr := HeapOrg} 

    new(r); {r := HeapOrg; HeapPtr:= HeapOrg + 6}

    r := pi; 

    WriteLn(j) 

    end.

    Перед исполнением программы этот указатель  имел значение адреса начала кучи HEAPORG, которое и было передано указателю I, а затем и J. После выполнения DISPOSE(I) указатель кучи вновь приобрел значение HEAPORG, этот адрес передан указателю R в процедуре NEW(R). После того как по адресу R разместилось вещественное число pi=3.14159, первые 2 байта кучи оказались заняты под часть внутреннего представления этого числа. В то же время J все еще сохраняет адрес HEAPORG, поэтому оператор WRITELN(J^) будет рассматривать 2 байта числа pi как внутреннее представление целого числа (ведь J - это указатель на тип INTEGER) и выведет 8578.

    2.1 Использование указателей.

    Исходя  из выше изложенного, можно сделать вывод, что динамическая память составляет 200...300 Кбайт или больше, ее начало хранится в переменной HEAPORG, а конец соответствует адресу переменной HEAPEND. Текущий адрес свободного участка динамической памяти хранится в указателе HEAPPTR.

    Можно посмотреть, как можно использовать динамическую память для размещения крупных массивов данных. Пусть, например, требуется обеспечить доступ к элементам прямоугольной матрицы 100x200 типа EXTENDED. Для размещения такого массива требуется память 200000 байт (100*200*10).

    Казалось  бы, эту проблему можно решить следующим  образом:

    var

    i,j : Integer;

    PtrArr : array [1..100, 1...200] of  Real; 

    begin

    for i := 1 to 100 do 

    for j := 1 to 200 do

    new(PtrArr[i,j]);

    .......

    end.

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

    PtrArr[1,1] := 0;

    if PtrArr[i,j*2] > 1 then ......

    Однако, что длина внутреннего представления указателя составляет 4 байта, поэтому для размещения массива PTRARR потребуется 100*200*4 = 80000 байт, что превышает размер сегмента данных (65536 байт), доступный, как уже отмечалось, программе для статического размещения данных.

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

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

    SEG(X) - возвращает сегментную часть  адреса; 

    OFS(X) - возвращает смещение.

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

    var

    р : Real; 

    begin

    ......

    new(p);

    р := 3.14;

    .......

    end.

    то  функция SEG(P) вернет сегментную часть  адреса, по которому располагается 4-байтный  указатель Р, в то время как SEG(P^) - сегмент 6-байтного участка кучи, в  котором хранится число 3.14 .

    С другой стороны, с помощью встроенной функции

    PTR(SEG,OFS: WORD): POINTER

    можно создать значение указателя, совместимое  с указателями любого типа. Таким  образом возможна такая последовательность действий. Вначале процедурой GETMEM из кучи забираются несколько фрагментов подходящей длины. Для рассматриваемого примера удобно резервировать фрагменты такой длины, чтобы в них могли, например, разместиться строки прямоугольной матрицы, т.е. 100 * 10 = 2000 байт. Начало каждого фрагмента, т.е. фактически начало размещения в памяти каждой строки, запоминается в массиве PTRSTR, состоящем из 100 указателей, теперь для доступа к любому элементу строки нужно вычислить смещение этого элемента от начала строки и сформировать соответствующий указатель: