28642

Использование указателей для представления динамически структур данных

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-08-20

59 KB

1 чел.

Лекции 24-25: Использование указателей для представления динамически
структур данных.

1. Тип Pchar и "строки, заканчивающиеся нулем".

2. Линейные списки и очереди.

3. Кольцевые списки.

4. Использование указателей для обработки деревьев.

 

1. Тип Pchar и "строки, заканчивающиеся нулём".

Описанные ранее строки (называемые строками ASCII), как указывалось, могут иметь максимальную длину только 255 символов. В то же время API-функции Windows, а также язык С используют другой тип строк - "строки, заканчивающиеся нулём" (называемые ASCIIZ-строками). Это - строки, которые ꗬÁIЙለ¿ကЀሢ橢橢뎲뎲Й鈰
ጕ
Ɠ￿ 锞锞锞5镓Ô阧Ô電ꄠǴꌔf電हૌ晩嘕|嚑晩晩電изован в версии  Borland Pascal 7.0 специальным модулем Strings, в котором содержатся функции обработки таких строк и преобразований между строками ASCII и строками ASCIIZ.

Тип PChar является указателем на область памяти, где размещена строка, заканчивающаяся символом #0. Сама строка представляет собой массив вида:

array [0..K] of Char; где: K - количество символов строки.

В отличие от строки string в "строке, заканчивающейся нулем" первый символ имеет индекс 0, а последний - K-1. Символ-терминатор #0 размещен в позиции K и недоступен для прикладной программы.

Замечание

Все стандартные процедуры и функции, рассмотренные для типа string, также применимы и для строк типа PChar. Для определения длины такой строки s можно использовать функцию Length(s), но не ord(s[0]).

Функции над ASCIIZ-строками (все они имеют префикс Str) можно разделить на три группы: аналоги функций для ASCII-строк, оригинальные функции (не имеющие аналога среди функций ASCII-строк) и функции преобразования.

Функции - аналоги: StrCopy, StrPos, StrLen, StrCat.

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

Функции преобразования: преобразование из ASCIIZ к ASCII (StrPas), из ASCII к ASCIIZ (StrPCopy).

Чтение и запись ASCIIZ-строк поддерживается обычными стандартными процедурами: read, readln, write, writeln.

2. Линейные списки и очереди.

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

Линейный список - линейная последовательность произвольного числа компонент (элементов списка), каждый из которых непосредственно связан со следующим или/и предшествующим элементом. Список однонаправленный, если в нём имеется только связь с предшествующим или только со следующим элементом. Список двунаправленный, если в нем имеется связь, как с предшествующим, так и со следующим элементом.

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

Линейные списки часто используются для представления и обслуживания очередей. Характерным для очередей является её естественный порядок: каждый новый элемент помещается в "хвост" очереди. Различают две дисциплины обслуживания очередей:

FIFO  (first input first output) - первым пришёл, первым обслуживается.

LIFO  (last input first output) - последним пришёл, первым обслуживается.

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

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

Пример программы создания очереди - FIFO был приведен выше (список телефонов). Аналогичная программа для стека телефонов (имеющая смысл для определения, кто звонил последним) приведена ниже.

       program stack_tel;{создание стека телефонов}

       uses CRT;

       type ref=^inf; {тип - Указатель на запись }

                inf= record name,adr,tel:string;

                                    pred:ref 

                       end;

       var head,p:ref; {указатель на начало стека и текущий}

             s:string;

            procedure write_stack(start:ref);

       {вывод всех элементов стека}

        begin repeat with start^ do

                begin writeln(name); writeln(adr); writeln(tel);

                end; start:=start^.pred

                  until start=nil

       end{write_stack};

        BEGIN TextBackground(cyan);TextColor(white);ClrScr;

                    window(10,5,40,20);TextBackground(green); ClrScr;head:=nil;

             repeat  new(p); with p^ do {заполнение полей записи}

                  begin write('Ф.И.О.:'); readln(name); write('Адрес:'); readln(adr);

                            write('Телефон:');readln(tel);pred:=head;

                  end;  head:=p;readln(s)

             until (s=' '); writeln('Стек телефонов создан');

             write_list(head);  writeln('Конец вывода стека');

        END{list_tel}.

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

3. Кольцевые списки.

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

       program RING_METRO; {Кольцевая линия Московского метро}

       type link=^nest;nest=record forw,back:link;inf:string end;

       var r,r1,start:link;f:text;c,c1,c2:string;dir:Boolean;L:byte;

       procedure insert(el1,el2:link);{вставка el2 после el1}

           begin el2^.forw:=el1^.forw;el2^.back:=el1;el1^.forw^.back:=el2;el1^.forw:=el2;

           end{insert};

       procedure dir_path(var d:Boolean;s1,s2:string);{направление}

       var g:link;j1,j2:byte;er1,er2:Boolean;

           begin j1:=0;j2:=0;g:=start;er1:=false;er2:=false;

            repeat g:=g^.forw;  if g^.inf=s1   then

              repeat g:=g^.forw;j1:=j1+1;er1:=(g^.inf=s1);d:=(2*j1<L);

              until (g^.inf=s2) or (g^.inf=s1)  else  if g^.inf=s2   then

              repeat g:=g^.forw;j2:=j2+1;er2:=(g^.inf=s2);d:=(2*j2>L);

              until (g^.inf=s1) or (g^.inf=s2);

            until (g=start) or (g^.inf=s1) or (g^.inf=s2);if er1 or er2 then

   begin write('Ошибка в названии ');

           if er1  then write('конечной') else write('начальной');writeln(' станции');halt

   end; if j1+j2=0 then begin writeln('Ошибка в названиях станций');halt end

           end {dir_path};

       procedure write_path(d:Boolean;s1,s2:string);{кратчайший путь}

       var p:link;

           begin p:=start; while not(p^.inf=s1) do p:=p^.forw;

             repeat writeln(p^.inf);if d then  p:=p^.forw else p:=p^.back;

             until (p^.inf=s2) ; writeln(p^.inf);

           end {write_path};

       BEGIN writeln('КОЛЬЦЕВАЯ  ЛИНИЯ  МОСКОВСКОГО МЕТРО');

             new(start);r:=start;r^.forw:=r;r^.back:=r;assign(f,'names_st');{$I-}reset(f);{$I+};

            if IOResult<>0 then begin writeln('Не найден файл names_st');halt end;

             L:=1;readln(f,r^.inf);while not eof(f) do{создание кольца }

             begin readln(f,c);new(r1);insert(r,r1);r1^.inf:=c;r:=r1;L:=L+1 end;

             writeln('Задайте начальную и конечную станции:');    readln(c1);readln(c2);            dir_path(dir,c1,c2); writeln('Кратчайший путь:');write_path(dir,c1,c2);

       END{ring_metro}.

4. Использование указателей для обработки деревьев.

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

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

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

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

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

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

 type link =^node; node = record c:char;count:word;left,right:link end;

 Программа имеет следующий вид:

       program frequency_letters; {Частота вхождения  латинских букв в строку}

       type link=^node; {тип - Указатель на запись}

               node=record c:char;count:word;left,right:link end;

      var root:link; {Корень дерева поиска} symb:char;j:word;

             L:set of  char; {множество символов}

             s:string; { вводимая строка }

       procedure insert_tree(var r:link;ch:char);{Вставка ch в дерево}

            begin if r=nil then

                  begin new(r);with r^ do begin c:=ch;count:=1;left:=nil;right:=nil end end

                                  else with r^ do

                if ch<c then insert_tree(left,ch)   else

                if ch>c then insert_tree(right,ch) else count:=count+1;

            end{insert_tree};

      procedure print_tree(r:link); {Печать количества вхождений букв }

            begin if r<>nil then with r^ do

                  begin print_tree(left);writeln(c,':',count); print_tree(right) end

            end{print_tree};

       procedure search_tree(r:link;ch:char); {Поиск ch и печать}

            begin if r=nil then writeln(ch,':0') else with r^ do

               begin if ch<c then search_tree(left,ch)   else

                         if ch>c then search_tree(right,ch) else writeln(ch,':',count)

               end

            end{search_tree};

  BEGIN L:=['A'..'Z']; root:=nil;writeln(' Введите текст:');while not eof do

         begin readln(s);for j:=1 to length(s) do

     begin if upcase(s[j]) in L then insert_tree(root,s[j]) end;

         end; writeln('СПРАВКА ПО ЧАСТОТАМ ЛАТИНСКИХ БУКВ:');

                 while not eof do begin readln(symb);search_tree(root,symb) end;

                   write('Печатать по всем буквам?(Y/N)');readln(symb);

                   if symb<>'N' then print_tree(root);

  END{frequency_letters}.


 

А также другие работы, которые могут Вас заинтересовать

83550. Правовий режим Чорноморських проток 36.39 KB
  Відносно проходу через протоки військових кораблів Конвенція встановила ряд загальних положень: обов\'язкове повідомлення про прохід обмеження кількості та тоннажу кораблів що проходять через протоки та ін. Конвенція проводить чітку різницю між проходом через протоки кораблів чорноморських та нечорноморських держав. Чорноморським державам дозволяється проводити через протоки кораблі будьякого тоннажу а також підводні човни.
83551. Правовий режим міжнародних каналів. Режим Суецького каналу 37.45 KB
  Режим Суецького каналу Міжнародні канали це штучні морські шляхи що поєднують морські простори та використовуються для інтересів морського судноплавства. Особливістю правового режиму міжнародних каналів є те що вони будучи частиною території державивласника каналу підпадають під дію відповідних міжнародних договорів що істотно обмежують правомочність даної держави. До принципів правового режиму міжнародних каналів відносяться: повага суверенних прав власника каналу і невтручання в його внутрішні справи; свобода судноплавства по каналу...
83552. Поняття міжнародно-правової відповідальності 38.1 KB
  Комісія міжнародного права ООН визначила зміст міжнародної відповідальності як ті наслідки які те або інше міжнароднопротиправне діяння може мати відповідно до норм міжнародного права в різних випадках наприклад наслідки діяння в плані відшкодування збитків та відповідних санкцій 1. У науці міжнародного права під міжнародноправовою відповідальністю розуміють конкретні негативні юридичні наслідки що настають для суб\'єкта міжнародного права в результаті порушення ним міжнародноправового зобов\'язання. У цілому можна зазначити що поняття...
83553. Кодифікація норм про відповідальність в міжнародному праві 35.22 KB
  Незважаючи на те інститут міжнародної відповідальності є одним із найдавніших інститутів міжнародного права його норми і досі не кодифіковані. Комісія міжнародного права за дорученням Генасамблеї ООН проводить роботу по укладенню уніфікованої кодексу міжнародноправової відповідальності. Основним джерелом норм які стосуються міжнародноправової відповідальності є звичай крім того різними міжнародними договорами закріплюються норми що стосуються відповідальності за ті чи інші види правопорушень чи регламентують застосування...
83554. Підстави міжнародно-правової відповідальності 36.39 KB
  Підставами міжнародно правової відповідальності є передбачені нормами міжнародного права обєктивні і суб\'єктивні ознаки. Розрізняють такі підстави міжнародно-правової відповідальності: — юридичні; — фактичні; — процесуальні. Під юридичними підставами розуміють міжнародно-правові...
83555. Поняття, ознаки і елементи міжнародного правопорушення 36.89 KB
  Міжнародне правопорушення являє собою складне правове явище. З юридичної точки зору, в якості міжнародного правопорушення розглядається міжнародно-протиправне діяння субєкта міжнародних правовідносин
83556. Види і зміст міжнародно-правової відповідальності 42.93 KB
  Політична відповідальність як правило супроводжується застосуванням у відношенні державипорушниці примусових заходів і сполучається з матеріальною відповідальністю. Сатисфакція задоволення як форма політичної відповідальності припускає обов\'язок державиправопорушниці надати задоволення не матеріального характеру відшкодувати моральну шкоду заподіяну честі і гідності іншої держави. Сатисфакція може виявитися в таких діях державиделіквента винного суб\'єкта що зобов\'язаний відшкодувати шкоду заподіяну правопорушенням: офіційне...
83557. Політична відповідальність і її форми 38.62 KB
  Політична відповідальність як правило супроводжується застосуванням у відношенні державипорушниці примусових заходів і сполучається з матеріальною відповідальністю. Сатисфакція задоволення як форма політичної відповідальності припускає обов\'язок державиправопорушниці надати задоволення не матеріального характеру відшкодувати моральну шкоду заподіяну честі і гідності іншої держави. Сатисфакція може виявитися в таких діях державиделіквента винного суб\'єкта що зобов\'язаний відшкодувати шкоду заподіяну правопорушенням: офіційне...
83558. Матеріальна відповідальність і її форми 37.01 KB
  Історично свій початок репарації беруть від інституту контрибуцій що успішно існували в міжнародному граві з глибокої давнини і до кінця XIX сторіччя і носили характер данини. З метою обмеження таких негативних явищ були розроблені статті 4751 Гаазької конвенції про закони і звичаї сухопутної війни 1907 року що обмежували стягнення контрибуцій. При розробці Версальского мирного договору 1919 року країни Антанти були змушені формально відмовитися від контрибуцій замінивши їх репараціями. Фактично на зміну контрибуцій прийшли усі форми...