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

*

*


 

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

44117. Технология изготовления отливки «Обечайка» массой 47 т из стали 10ГН2МФАЛ 1.72 MB
  Этапы формирования отливки. Технологические приёмы воздействия на процессы затвердевания и охлаждения отливки в литейной форме. Способы воздействия на характер формирования отливки на этапе охлаждения расплава до температуры кристаллизации. Получение заданных свойств для отливок ответственного назначения. Проектирование технологии изготовления отливки Обечайки парогенератора ПГВ1000 в литейных формах с дифференцированным отводом тепла.
44118. Модель создания единого информационного пространства образовательного учреждения с применением сетевых информационных технологий 1.25 MB
  Особую роль в данной форме самообразования могут занять социальные сети и социальные сообщества функционирующие в Интернете. Все больше преподавателей осваивают работу в Сети и начинают использовать ее в образовательном процессе. При условии создания в учебном заведении Интернет-системы следующим шагом становится выход на более высокий уровень функционирования информационного пространства Интернет предусматривающий создание и открытие доступа всем непосредственным участникам учебного процесса и внешним посетителям к сайту учебного...
44119. Технологический процесса производства сборной жестяной консервной тары 4.79 MB
  В некоторых случаях можно отказаться от применения пайки продольного шва. Продольный шов можно соединять с помощью клеящего устройства и герметизировать уплотняющими средствами. Благодаря этому становиться возможным изготовление герметичных сборных жестяных банок из неподдающихся пайки исходных материалов.
44120. Разработка способов сжигания твердого топлива ОАО «Экспериментальная ТЭС» 1.73 MB
  Расчет мощности на перекачку воды Расчет деаэратора питательной воды ДПВ до реконструкции на каждый котел установлен один деаэратор. Расчет теплового баланса деаэратора питательной воды ДПВ. Выбор деаэратора питательной воды ДПВ.
44121. Транспортировка грузов 1.01 MB
  Поэтому для обеспечения высоких эксплуатационных характеристик грузоподъемных кранов и их безаварийной работы машинист крана крановщик и обслуживающий персонал должны знать хорошо назначение область применения и устройство кранов их конструктивные особенности технические характеристики устройство и работу крановых механизмов электрооборудования приборов и устройств безопасности. Кроме того машинист крана должен знать правила безопасной эксплуатации кранов их технического обслуживания и ремонта современную прогрессивную технологию и...
44122. МОТИВАЦИИ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ ПЕРВОКЛАССНИКОВ С ЗАДЕРЖКОЙ ПСИХИЧЕСКОГО РАЗВИТИЯ 588.5 KB
  Мотивационную сферу человека с точки зрения ее развитости можно оценивать по следующим параметрам: широта, гибкость и иерархизированность. Под широтой мотивационной сферы понимается качественное разнообразие мотивационных факторов — диспозиций (мотивов), потребностей и целей, представленных на каждом из уровней.
44123. Формирование и развитие рынка речных круизов в Перми и Пермском крае на примере туристической фирмы ООО «Кубань» 838 KB
  Основные понятия рынка и государственное регулирование сферы туризма в России Переход страны к рыночной экономике сопровождается постепенным созданием конкурентной среды во всех отраслях современного туризма в том числе и в сфере речного круизного туризма. В российской экономической литературе вопросам туризма посвящено немало научных исследований. Таким образом планируется рассмотреть проблемы и сформировать программы развития туризма регионального муниципального уровней в которых предстоит разработать и реализовать комплекс мер...
44124. Проектирование районной понизительной подстанции 356.24 KB
  На данной подстанции по ПУЭ устанавливается 2 трансформатора, это делается из-за того что на ней присутствуют потребители I и II категории. Перерыв в электроснабжение которых для I категории допускается лишь на время автоматического восстановления питания, а для II категории – на время
44125. Оценка стоимости недвижимости. Анализ ипотеки в Барнауле и Алтайском крае 1.09 MB
  Мне было дано провести анализ по оценки объекта недвижимости в городе Барнаулея взял как примержилой дом находящегося по адресу: г. Оценка стоимости недвижимости процесс определения рыночной стоимости объекта или отдельных прав в отношении оцениваемого объекта недвижимости. Оценка стоимости недвижимости включает: определение стоимости права собственности или иных прав например права аренды права пользования и т. в отношении различных объектов недвижимости.