68987

Динамічні рядки символів

Лекция

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

На підставі вивчених типів можна одержувати різні структури даних, яких у мові Паскаль у явному вигляді немає. Прикладом такої структури є рядки - впорядковані послідовності символів. Рядки можна відображати за допомогою векторного зображення, коли послідовність символів - це послідовність компонентів вектора...

Украинкский

2014-09-28

47 KB

1 чел.

Лекція № 16

Тема: Динамічні рядки символів

План заняття:

  1.  Рядки символів
  2.  Динамічні рядки символів

Рядки символів

На підставі вивчених типів можна одержувати різні структури даних, яких у мові Паскаль у явному вигляді немає. Прикладом такої структури є рядки - впорядковані послідовності символів. Рядки можна відображати за допомогою векторного зображення, коли послідовність символів - це послідовність компонентів вектора, тобто компонентів одновимірного масиву типу char. Таке відображення рядків має свої переваги і недоліки. Головною перевагою є простота доступу до будь-якого елемента рядка: індекс елемента масиву визначає доступ до самого елемента. Недоліки векторного зображення виявляються під час перетворення рядків, наприклад, коли треба вставити або вилучити символ - елемент рядка. Для вставляння потрібно розсунути рядок, тобто змістити всі елементи після того, який вставляють, праворуч. У випадку вилучення - ліворуч. Ці операції досить трудомісткі.

Недоліки векторного зображення виникають і в разі запам'ятовування рядків. Оскільки довжина рядка наперед невідома, доводиться резервувати масив з розрахунку на максимальний його розмір. По-перше, це веде до неефективного використання пам'яті. По-друге, для виявлення кінця рядка треба виконати велику кількість операцій з перебирання всіх елементів масиву.

Динамічні рядки символів

Розглянемо інший спосіб зображення рядків - за допомогою комбінованого і вказівного типів. У цьому випадку кожний елемент рядка складається з двох полів: перше містить власне

символ (літеру) рядка, а друге - вказівку на наступний елемент. Розміщення елементів рядка в пам'яті у цьому разі може бути довільним, а впорядкованість визначена якраз за допомогою другого поля, що містить вказівку на наступний елемент. За цими вказівками всі пари, що називають ланками, утворюють один ланцюг. Спосіб зображення, коли кожна ланка містить сам елемент послідовності і довідкову частину, використовують для зображення не тільки рядків, а й списків, дерев тощо.

За допомогою типів мови Паскаль створимо структуру, яка визначатиме рядок у вигляді ланцюга. Це буде запис, що містить два поля: саму літеру і вказівник на наступну ланку:

type

Link=^LRiad; LRiad=record

Elem: Char;

Next: Link;

end;

Звернемо увагу на одну особливість: вказівний тип Link визначено за допомогою типу LRiad (тип динамічного об'єкта), описаного далі. Тобто тут порушене головне правило мови Паскаль про те, що всі програмні об'єкти можна використати тільки після того, як їх описано у відповідному розділі. Однак для вказівного типу в мові Паскаль зроблено виняток: для опису вказівних типів можна використовувати імена, які описані після цього опису.

Отже, ми описали структуру для зображення окремих ланок. Тепер формуватимемо ланцюг. З цією метою введемо деякі змінні. Для вказівника на весь ланцюг (тобто на першу ланку цього ланцюга, бо всі інші ланки містять вказівники на наступну ланку) введемо вказівну змінну

var RefRjad: Link;

Для формування ланцюга потрібний буде ще вказівник Reflan: Link;

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

new (RefRjad ); RefRjad^.elem:=sym; RefRjad^.next:=nil;

Останній з цих операторів відображає те, що на кожному етапі формування ланцюга остання сформована ланка як вказівку на наступну ланку буде містити nil, тобто це буде порожня вказівка; sym - це черговий символ, який уводять у рядок символів. Отже, за допомогою наведених операторів відводиться місце в пам'яті для першої ланки; вказівній змінній буде присвоєне значення вказівки на цю ланку (оператор new(RefRjad)), а також поля цієї ланки одержать свої значення. Матимемо ситуацію, показану на рис. 1.

  Refrjad nil

Рис. 1. Формування першої ланки.

Для формування наступної ланки використаємо допоміжну змінну RefLan, яка повинна вказувати на останню сформовану ланку. Тому

RefLan:=RefRjad; Тепер можна сформувати наступну ланку:

new(RefLan^.next); RefLan:=RefLan^.next; RefLan^.elem:=sym; RefLan^.next:=nil;

Усі наступні ланки формуватимуться за цією ж схемою і за допомогою цих же операторів. Запишемо програму формування рядка із символів, що вводяться із файлу input доти, доки не трапиться крапка в послідовності символів. Дещо модифікуємо наведену схему так, щоб перша ланка формувалася за тією ж схемою, що й наступні. Для цього введемо так звану нульову ланку, яка в полі .next міститиме вказівник на першу ланку, а в полі .elem може містити деяку додаткову інформацію про рядок. Перший символ формованого рядка (слова) помістимо в першу ланку (її поле .elem), другий - у другу і так далі. Програма формування рядка у вигляді ланцюга з використанням вказівних змінних і записів буде мати такий вигляд:

program Form1;

type

Link=^LRiad;

LRiad=Record

Elem: Char;

Next: Link;

end;

var

refRjad,RefLan: Link;

sym: Char;

begin

New(RefRjad);

RefLan:=RefRjad;

RefLan^.Next:=nil;

read(sym);

while sym<>'.' do

begin

New(RefLan^.Next);

RefLan:=RefLan^.Next;

RefLan^.EIem:=sym;

RefLan^.Next:=nil;

Read(sym);

end;

end.

У результаті одержимо структуру, показану на рис. 2.

   RefRjad

RefLan

Рис. 2. Сформований динамічний рядок символів.


*

S1

*

*

sym

*

*

sym

sym

*

*


 

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

26601. СТАНДАРТНАЯ СОРТИРОВКА ТУШ ПО УПИТАННОСТИ 15.96 KB
  Говядину взрослого скота молодняка а также баранину и козлятину подразделяют на 1ю и 2ю категории. Говядина 1й категории должна иметь как минимум удовлетворительное развитие мускулатуры; остистые отростки позвонков седалищные бугры и маклоки не должны резко выступать жировые отложения должны быть заметны в виде небольших участков на шее лопатках бедрах в тазовой полости и в области паха; слои подкожного жира от 8го ребра к седалищным буграм могут иметь значительные просветы. Говядина 2й категории характеризуется менее...
26602. СУЩНОСТЬ «ЗАГАРА» МЯСА. САНИТАРНАЯ ОЦЕНКА МЯСА ПРИ «ЗАГАРЕ». ЗАГАР 2.3 KB
  СУЩНОСТЬ ЗАГАРА МЯСА. САНИТАРНАЯ ОЦЕНКА МЯСА ПРИ ЗАГАРЕ. Это особый вид порчи мяса в первые сутки после убоя животного. Наблюдают его при недостаточно интенсивном охлаждении парного мяса а также при слабой аэрации если туши в парном состоянии плотно укладывают или тесно подвешивают одна к другой в душных помещениях при температуре выше 1520 С.
26603. СУЩНОСТЬ ПОНЯТИЙ «УСЛОВНО ГОДНОЕ МЯСО», «МЯСО ВЫНУЖДЕННО УБИТЫХ ЖИВОТНЫХ» 878 Bytes
  СУЩНОСТЬ ПОНЯТИЙ УСЛОВНО ГОДНОЕ МЯСО МЯСО ВЫНУЖДЕННО УБИТЫХ ЖИВОТНЫХ. Мясо вынужденно убитых животных мясо от больных животных лишенных жизни ввиду нецелесообразности или неэффективности дальнейшего лечения с целью недопущения падежа. Условногодное мясо мясо использование которого для пищевых целей допускается после обеззараживания.
26604. СУЩНОСТЬ ПРОЦЕССА ПОСОЛКИ И ГИГИЕНА ПОСОЛКИ МЯСА. ЗНАЧЕНИЕ И СУЩНОСТЬ ПОСОЛА 6.28 KB
  СУЩНОСТЬ ПРОЦЕССА ПОСОЛКИ И ГИГИЕНА ПОСОЛКИ МЯСА. Посол мяса один из самых древних ранее широко распространенных и доступных методов консервирования. В связи с развитием холодильной техники использованием высоких температур для консервирования мяса и мясопродуктов развитием колбасного производства посол уступил первое место этим методам консервирования. Однако и сейчас в сельской местности в личном хозяйстве он находит и будет находить применение как самостоятельный метод консервирования мяса н мясопродуктов.
26605. СХЕМА ИССЛЕДОВАНИЯ МЯСА НА ОБСЕМЕНЕННОСТЬ ВОЗБУДИТЕЛЯМИ ТОКСИКОИНФЕКЦИЙ 1.54 KB
  СХЕМА ИССЛЕДОВАНИЯ МЯСА НА ОБСЕМЕНЕННОСТЬ ВОЗБУДИТЕЛЯМИ ТОКСИКОИНФЕКЦИЙ. Схема бактериологического исследования мяса и мясопродуктов по ГОСТ 2123775.
26606. ТЕХНОЛОГИЯ УБОЯ КРС И ПЕРВИЧНАЯ ПЕРЕРАБОТКА ТУШ. ОГЛУШЕНИЕ. 22.62 KB
  ТЕХНОЛОГИЯ УБОЯ КРС И ПЕРВИЧНАЯ ПЕРЕРАБОТКА ТУШ. Чтобы предотвратить загрязнение туш и крови содержимым преджелудков на пищевод животным перед их обескровливанием накладывают лигатуру. Во избежание попадания крови от больных животных емкости нумеруют соответствующими номерами туш от которых собрана кровь. После этого полый нож извлекают из туши.
26607. ТЕХНОЛОГИЯ УБОЯ СВИНЕЙ И ПЕРВИЧНАЯ ПЕРЕРАБОТКА ТУШ. УБОЙ. ОГЛУШЕНИЕ 22.1 KB
  При сборе крови только для технических целей обычным боенским ножом производят глубокий разрез тканей в месте соединения шеи с грудной частью туши и направляя лезвие ножа вверх перерезают кровеносные сосуды у правого предсердия. Зачистка этих участков приводит к потерям массы туши и снижению ее товарного вида. Как указано выше свиные туши обрабатывают со съемкой шкур со съемкой крупонов и со шпаркой туш без съемки шкур. На конвейере вручную кольцеобразно подрезают гузенки снимают шкуру с бедер голяшек и паховой части от туш самцов...
26608. ТРАНСПОРТИРОВКА СКОРОПОРТЯЩИХСЯ ПРОДУКТОВ 8.39 KB
  ТРАНСПОРТИРОВКА СКОРОПОРТЯЩИХСЯ ПРОДУКТОВ. Главными задачами транспортировки являются быстрая доставка продуктов к местам назначения и сохранение их первоначальных качеств. Температурный режим при перевозке скоропортящихся продуктов В рефрижераторных поездах и секциях устанавливается в зависимости от температуры груза в момент погрузки. Совместная перевозка в одном вагоне разных видов скоропортящихся продуктов допускается при условии одинакового способа их обслуживания и на срок не превышающий установленного для наименее стойкого груза.
26609. ТРАНСПОРТИРОВКА СКОТА АВТОМОБИЛЬНЫМ ТРАНСПОРТОМ, ПО ЖЕЛЕЗНЫМ ДОРОГАМ И ВОДНЫМ ПУТЯМ. АВТОМОБИЛЬНЫЙ ТРАНСПОРТ 9.12 KB
  В 23 раза по сравнению с железнодорожным транспортом автомобильные перевозки ускоряют доставку животных на убой. В них не должно быть торчащих предметов дыр в полу и других неисправностей которые могли бы травмировать животных. Для предохранения животных от перегрева и охлаждения кузова покрывают брезентом. Крупных животных размещают в кузове на привязи головами вперед или к боковой стенке овец свиней и молодняк крупного рогатого скота перевозят без привязи.