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

*

*


 

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

31802. Понятие риска, составляющие и источники рисков в управлении 26 KB
  Понятие риска составляющие и источники рисков в управлении. Риск [греч. Риск предполагает неуверенность либо невозможность получения достоверного знания о благоприятном исходе в заданных внешних обстоятельствах; Риск в узком смысле измеряемая или рассчитываемая вероятность неблагоприятного исхода что подразумевает наличие статистических данных. Риск принято рассматривать как историческую и экономическую категории.
31803. Стратегии управления риском 24.5 KB
  При принятии страт решений необходимо проводить анализ рисков: 1Качественный анализ – определение факторов риска и обстоятельств приводящих к рискованным ситуациям. 2Количественный анализ – позволяет вычислить величину отдельных рисков и риска проекта в целом. Способы измерения риска: 1Стаитстическая оценка 2Экспертаная 3Оценка на основе моделей принятия решений.избежание риска.
31804. Технология принятия решений в условиях стохастического риска 24 KB
  Изменение величины риска или степени риска: Среднее ожидаемое значение. Среднее значение: 1Средневзвешенное для всех возможных резв где вероятность каждого реза используется в качестве частоты или вес соотвго значения. 2Дисперсия представляет собой среднее взвешенное из квадратов отклонений действующих результатов от средних ожиданий 3Среднее ожидаемое значение отклонений прибыли от ее средне ожидаемых значений или среднеквадратическое отклонение рассчитывается по формуле.
31805. Технология принятия решений в условиях поведенческого риска 23 KB
  Формируется когда существуют др лица принимающие решение и основное ЛПР опасается их т.к либо интересы основного ЛПР столкнулись с интересами др ЛПР либо сущ различия в позициях точках зрения традиций основного лица и др ЛПР либо ЛПР считает природу в кот принимаемое решение неопределенной непредсказуемой и поэтому агрессивной.
31806. Формы разработки и реализации управленческих решений 36.5 KB
  Указание решение носящее методический технологический характер. Акт решение широкого круга государственных и общественных организаций. Приказ письменный или устный это решение руководителя обличенного властью в организации или крупном ее подразделении. Распоряжение это решение руководителя не наделенного административными функциями.
31807. Сущность, функции, виды и методы контроля управленческого решения 30 KB
  Контроль организации исполнения УР – система наблюдения проверки оценки и коррекции положения дел на основе критерия. Виды контроля: 1Постоянный – ежедневно 2Регулярный – еженедельно 3Промежуточный – ежемесячно 4Переодический – составление отчета 5Детальный 6Факторный Контроль как функция управления. Контроль УР как на стадии разработки так и на стадии реализации является важнейшей функцией управления. Контроль может осуществляться в двух вариантах: по результатам и по упреждению.
31808. Сущность и виды ответственности руководителей за принятие управленческого решения 30.5 KB
  Ответственность – мера соответствия действий человека групп людей или обва взаимным требованиям нормам. Ответственность это необходимость обязанность отдавать комулибо отчет в своих действиях поступках. Ответственность может быть официальная и личная чувство ответственности как черта характера. Виды ответственности: 1Внутрифирменная: аадминистративная выговор бэкономическая лишение премии впрофессиональная понижение в должности 2Внешняя: аюридическая арест бсоциальная вморальная Юридическая ответственность частично или...
31809. Планирование и прогнозирование в процессе принятия управленческих решений 25 KB
  Метод прогнозирования – способ исследования объекта прогноза направленный на разработку прогнозов. Состояние объекта в будущем определяется закономерностями выявленным по частным результатам опыта его проведения в прошлом и настоящем. Осущся от имеющегося уровня знаний а конечные результаты развития объекта составляют содержание прогноза. Ориентирован на то что задается цель развития объекта в будущем а содержанием прогнозов становится определение частных путей.
31810. Экспертные методы прогнозирования решения 27 KB
  Экспертные методы базируются на информации которую поставляют специалистыэксперты в процессе систематизированных процедур выявления и обобщения этого мнения. Например при проведении экспертного опроса участникам представляют цифровую информацию об объекте или фактографические прогнозы либо наоборот при экстраполяции тенденции наряду с фактическими данными используют экспертные оценки. Экспертные методы разделяются на два подкласса. Прямые экспертные оценки строятся по принципу получения и обработки независимого обобщенного мнения...