Б С Бусигін - Прикладна інформатика - страница 51

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83 

Рис. 8.101. Перестановка двох сусідніх елементів у середині списку

В алгоритмі перестановки в однозв'язному списку (рис. 8.101) виходимо з того, що відомо адресу елемента, що передує парі, у якій виробляється перестановка. У приведеному алгоритмі також не враховується випадок перестановки першого і другого елементів.

{ Перестановка двох сусідніх елементів в однозв'язному списку }

Procedure ExchangeSll(prev :   sllptr {Указник на елемент, що передує парі, що переставляється} );

Var

pi, p2  :  sllptr; {Указники на елементи пари}

Begin

pi:=prevA.next;    {Указник на 1-й елемент пари} p2:=piA.next;       {Указник на 2-й елемент пари}

piA.next:=p2A.next; {1-й елемент пари тепер указує на наступний за

парою}

p2A.next:=pi;      {1-й елемент пари тепер випливає за 2-им } prevA.next:=p2;    {2-й елемент пари тепер стає 1-им } End;  {Proc ExchangeSll}

8.27.17. Рішення задачі по створенню черги

і реалізація операцій з нею

Тепер Ви добре себе уявляєте, що лінійні списки можна застосовувати у додатках, де непередбачені вимоги на розмір пам'яті, необхідної для збереження даних, а також велике число складних операцій над даними, особливо включень і виключень.

Стек - це такий послідовний список з перемінною довжиною, включення і виключення елементів у який виконуються тільки з однієї сторони списку, називаного вершиною стека. Існують й інші назви стека - магазин, а також черга, що функціонує за принципом LIFO (Last-In-First-Out - "останнім прийшов - першим виключається"). Прикладом стека може бути обойма у пістолеті.

Основні операції над стеком - це включення нового елемента (англійська назва push - заштовхувати) і виключення елемента зі стека (англ. pop -вискакувати).

Відомо, що стек може бути представлений як лінійний список, у якому включення елементів завжди провадиться з початки списку, а виключення -також з початку. Для представлення його Вам досить мати один показник - top, що завжди вказує на останній записаний у стек елемент. У вихідному стані (при порожньому стеці) покажчик top - порожній. Головні процедури StackPush і StackPop зводяться відповідно до включення елемента у початок списку і виключення з початку ж списку.

Зверніть увагу на те, що при включенні елемента для нього виділяється пам'ять, а при виключенні - звільняється. Перед включенням елемента перевіряється доступний обсяг пам'яті, і якщо він не дозволяє виділити пам'ять для нового елемента, стек вважається заповненим. При очищенні стека послідовно проглядається весь список і знищуються його елементи. При списковому представленні стека виявляється непросто визначити розмір стека. Ця операція могла б зажадати від Вас перебору всього списку для підрахунку числа елементів. Щоб уникнути послідовного перебору всього списку Ви повинні ввести додаткову перемінну stsize, що відбиває поточне число елементів у стеці і коректується при кожнім включенні/виключенні:

{Стек на 1 -зв'язному лінійному списку}

unit Stack; Interface

type data = {Елементи можуть мати будь-як тип}

Procedure StackInit; Procedure StackClr;

Function StackPush(a  :  data)   : boolean; Function StackPop(Var a  :  data)   : boolean; Function StackSize  : integer;

Implementation

type stptr = Astit; {Показник на елемент списку}

stit = record {Елемент списку} inf : data; {Дані}

next:  stptr; {Покажчик на наступний елемент}

end;

Var top :  stptr; {Покажчик на вершину стека}

stsize  :  longint; {Розмір стека} {** Ініціалізація - список порожній }

Procedure Stacklnit;

begin      top:=nil;  stsize:=0;    end;  {ProcStacklnit} {**Очищення - звільнення всієї пам'яті}

Procedure StackClr; var x  : stptr; begin {Перебір елементів до кінця списку і їхнє знищення}

while top<>nil do

begin    x:=top;  top:=topA.next;  Dispose(x); end; stsize:=0; end; {Proc StackClr}

Function StackPush(a: data)   : boolean;   {Занесення в стек} var x  : stptr; begin    {Якщо немає більше вільної пам'яті - відмовлення} if MaxAvail < SizeOf(stit)   then StackPush:=false else  {Виділення пам'яті для елементу і заповнення інф. частини} begin    New(x); xA.inf:=a;

{Новий елемент міститься у голові списку} xA.next:=top; top:=x; stsize:=stsize+i; {Корекція розміру} StackPush:=true; end;

end; {Func StackPush}

Function StackPop(var a:  data)   : boolean;  {Вибірка зі стека} var x  : stptr;

begin

{Список порожній - стек порожній}

if top=nil then StackPop:=false else begin

a:=topA.inf;  {Вибірка інформації з 1-го елементу списку} {1-й елемент виключається зі списку, звільняється пам'ять}

x:=top;  top:=topA.next; Dispose(top); stsize:=stsize-i; {Корекція розміру}

StackPop:=true; end;    end;   {  StackPop }

Function StackSize  :  integer; {Визначення розміру стека}

begin     StackSize:=stsize;      end; {Func StackSize}

END.

Програмний приклад для організація на однозв'язному лінійному списку черги FIFO розробіть самостійно. Для лінійного списку, що представляє чергу, Вам необхідно буде зберігати: top - указник на перший елемент списку, і bottom - указник на останній елемент.

Вправи

1. Для яких цілей використовується оператор With?

2. У часовій майстерні всі замовлення, що надходять, реєструються в комп'ютері. Про кожне замовлення зберігається наступна інформація:

- номер замовлення;

- прізвище замовника;

- тип годинника (механічні, електронно-механічні, електронні);

- марка годинника;

- термін виконання і вартість замовлення.

Годинники різних типів ремонтуються різними майстрами. Видати завдання кожному майстру в порядку терміновості замовлень, а також указати загальну суму замовлень.

3. Написати програму для обробки інформації про товари, що зберігаються на складі. Інформація містить у собі:

- найменування товару.

- вартість товару.

- країна-виробник товару.

- кінцевий термін реалізації товару.

- кількість товару, що мається у наявності.

Програма повинна дозволяти користувачу зчитувати дані з клавіатури і заносити їх у необхідний запис, а також зчитувати дані із заданого запису й виводити на екран список товарів, з терміном реалізації, що минає (менше місяця).

4. Створити модуль для роботи з комплексними числами і програму, що його викликає, для перевірки правильності роботи модуля.

5. Додати в кінець не порожньої черги всі її елементи, розташовуючи їх у зворотному порядку.

6. Інформаційне поле елемента черги - рядок. Підрахувати кількість слів черги, що збігаються з останнім рядком.

7. Інформаційне поле елемента черги - числове. Підрахувати і вивести на екран елементи черги, не рівні нулю.

Додаток І

Преподавание информатики: потерянная дорога

Никлаус Вирт

Приветствие на открытии Международной конференции по преподаванию информатики ITiCSE г. Аархус (Дания), 24 июня 2002 г.

Всего через пару дней после получения приглашения выступить на открытии данной Конференции по преподаванию информатики, я прочел доклад коллеги из США. Доклад достигает кульминации в следующем абзаце о преподавании:

Поучительно сравнить учебники для средней школы по математике и по информатике. Я имел несчастье проделать это довольно внимательно, и вот мое заключение: мы ни на что не годимся <we suck>. Похоже, мы заставляем студентов сделать вывод, что серьезно думать о карьере в информатике могут только мазохисты.

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

Как профессионалы в информатике, мы обязаны поднять свои голоса против традиции, приравнявшей компьютерную грамотность к знанию темных деталей языка программирования, используемого в индустрии. Мне вспоминается рассказ Э. Дейкстры о его ночном кошмаре после чтения спецификаций нового языка программирования PL/1 в 1965 г. Ему представилось, что в будущем программирование приравняют к выучиванию PL/1, а информатику - к овладению JCL к OS/360 (речь идет о языке программирования и языке управления заданиями для компьютеров фирмы IBM, печально известных своим крайне неудачным дизайном; российские программисты старшего поколения помнят, что это такое, по опыту работ на ЕС ЭВМ - прим. перев.). Достаточно заменить PL/1 на C++ или Java, а JCL - на Windows или Linux, и вы чудесным образом перенесетесь в настоящее.

Тогда я написал своему коллеге о полном согласии с ним. Он ответил следующим разъяснением:

Мои резкие замечания о преподавании - результат полного провала попыток помочь сыну, ученику старших классов, освоить C++. Дизайн языка чудовищен, а учебник написан отвратительно. Мой сын не мог понять, почему x = y должно отличаться от y = x. Дейкстра также жаловался мне, что важная книга по языку Java не содержала формальной грамматики.

http://www.inr.ac.ru/~info21/greetings/wirth_doklad_rus.htm

361

Действительно, формальные правила синтаксиса были заданы лишь в четвертой версии языка! Но позвольте мне продолжить цитату:

Я был разочарован не только таким положением вещей, но и тем, что серьезные специалисты по информатике воспринимают его как совершенно нормальное. Мне еще ни разу не попадался учебник по иЫ1ХЮ++Мача, который я мог бы освоить за неделю. Их учебники невозможно читать, они предполагают, что читатель принадлежит какой-то секте, чьи заклинания должны оставаться тайной для публики, и читателю не следует ожидать многого в плане надежности, связности или общей элегантности. Мое отчаяние достигло апогея, когда я пытался научить своего сына программировать на С++ - факультативный курс в средней школе! После полугода агонии - как для отца, так и для сына - я посоветовал сыну бросить этот курс.

Чего я не понимаю, так это отсутствия возмущения среди ученых, специалистов по информатике. Когда управляющий совет колледжа решил включить в программу С++ в середине 90-х гг., я письменно выразил им свое возмущение. Но я не в счет.

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

Интересно, что курс в лицее помогает лучше понять как само программирование, так и то, как его нужно преподавать. Примерно половина улучшений в моем университетском курсе будет сделана благодаря опыту, полученному в лицее. Кроме того, я почувствовал, в каком ужасном состоянии находится преподавание программирования - как на уровне средней школы, так и университета.

Слова резкие, но они не преувеличение. В чем же ошибка? Что можно сделать? Вспоминается смиренное: "Я не в счет" - из процитированного выше письма. Мы чувствуем себя беспомощными. Кое-кто чувствует себя обреченным на жалобы, а большинство решают примириться с очевидными фактами и кое-как приСпошбиться к ним. Но вряд ли подобную позицию интеллектуальных лидеров можно оправдать. Посмотрим правде в глаза: разве большинство учреждений образования не оказалось заложниками горстки компаний, чья профессиональная цель состоит в повышении доходов - идет ли речь о производителях оборудования, программного обеспечения или об издательствах? Университеты, которые могли бы оказывать хоть какое-то корректирующее влияние, и чьи преподаватели числятся среди авторов популярных учебников, на самом деле больше заинтересованы в том, чтобыдемонстрировать свое участие в модных исследованиях, оставляя преподавание ассистентам.

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

Слова резкие. Что же можно сделать? Ведь и в самом деле индивидууму очень трудно противостоять глобальной тенденции. Я имею в виду тенденцию перехода от долгосрочного планирования к немедленному извлечению доходов, от учения с целью понимания к применению навыков непосредственного действия. Что касается нашего предмета -информатики и программирования для компьютеров, - то конечная цель учреждения образования должна быть гораздо шире, чем овладение каким-либо языком программирования. Это должно быть никак не менее, чем искусство проектирования артефактов для решения сложных задач. Иногда это называют искусством конструктивного мышления. Именно в таком контексте становится важным наличие подходящего инструмента, хорошо спроектированного языка программирования. Он играет роль теории, на которой основываются наши методы. Как можно научиться хорошему и эффективному проектированию, если базовый формализм, само основание представляет собой ошеломляющую, непостижимую путаницу? Как можно освоить такое искусство без образцовых примеров, достойных изучения и подражания? Конечно, не все равно одарены в том, что касается хорошего проектирования, и все же надлежащее обучение, инструменты и примеры играют важнейшую роль.

Конечной целью образования должно быть искусство конструктивного мышления. Именно в таком контексте становится важным наличие хорошо спроектированного языка программирования.

Люди по ошибке принимают сложность за изощренность.

Я говорил о проектировании сложных артефактов. Очевиден факт, что наши артефакты становятся все сложнее. Например, автомобиль это уже не просто двигатель и четыре колеса. В нем еще есть компьютер для определения оптимального количества впрыскиваемого топлива в самые подходящие моменты времени. Это нужно, чтобы снизить затраты топлива, чтобы сберечь энергию. Но современный автомобиль еще содержит с десяток (или больше) хорошо спрятанных электромоторов для управления окнами и антеннами, радар для определения расстояния до опасных объектов, системную шину для связи всех этих устройств, а также компьютер для управления ими. Эти вещи не слишком способствуют истинному назначению автомобиля, но они добавляют сложность, затрудняют обслуживание и повышают стоимость. Это мнение было выражено в недавней статье о "совершеннейшем автомобиле" в газете Нью-Йорк Таймс (озаглавленной За рулем, BMW 745i, технический нокаут):

"Люди по ошибке принимают сложность за изощренность," сказал однажды Никлаус Вирт, швейцарский ученый, специалист по информатике. В роскошных автомобилях, напичканных новейшими технологиями, прибамбасами и завлекалками, уже трудно увидеть эту разницу - так же как трудно определить ту точку, за которой техника, целью которой была помощь водителю, становится помехой вождению ... Достаточно сказать, что семерка, несомненно, самый «продвинутый» седан в мире, но отнюдь не самый легкий в управлении.

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

-надежности. Но обманутый клиент понимает

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

времени, чтобы самодельная сложность порождает множество

спроектировать экономную, проблем. Главное, она размывает различием простую и эффективную между    тем,    что    действительно важно

систему, нежели сложную и (оптимальное впрыскивание топлива), и тем, громоздкую. что эфемерно (моторчики для закрытия окон).

-Беда в том, что требуется гораздо больше

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

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83 


Похожие статьи

Б С Бусигін - Прикладна інформатика