|
Структури даних для обробки інформац |
Структури даних для обробки інформац
26 - Зміст
- Вступ
- РОЗДІЛ І. ДИНАМІЧНІ СТРУКТУРИ ДАНИХ
- 1.1 ЗМІННІ-ВКАЗІВНИКИ
- 1.2. ЗВ'ЯЗАНИЙ СПИСОК. СТЕК
- 1.3. ЗВ'ЯЗАНИЙ СПИСОК. ЧЕРГА
- РОЗДІЛ ІІ. ДЕРЕВА. БІНАРНЕ ДЕРЕВО
- 2.1. РЕАЛІЗАЦІЯ БІНАРНОГО ДЕРЕВА ЗА ДОПОМОГОЮ ДИНАМІЧНИХ ЗМІННИХ
- ВИСНОВКИ
- СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
- Вступ
- Сучасні алгоритми працюють з великим обсягом інформації, і тому час пошуку у таких алгоритмах є критичним. Таким чином, актуальним є розроблення структур даних для ефективного зберігання та обробки інформації.
- Однією з таких структур є бінарне дерево. Це динамічна структура даних, розмір якої обмежується тільки розміром віртуальної пам'яті комп'ютера. Бінарні дерева забезпечують пошук конкретного значення, максимуму, мінімуму, попереднього, наступного, операції вставки та видалення елемента.
- Пошук у збалансованому дереві виконується за час O(log2n), але звичайні бінарні дерева можуть вироджуватись у список, при цьому пошук вже триватиме O(n) часу.
- У повсякденному житті ми дуже часто зустрічаємо приклади дерев. Наприклад, люди часто використовують генеалогічне дерево для зображення структури свого роду; як ми побачимо, багато термінів, пов'язаних з деревами, узято саме звідси.
- Другий приклад - це структура великої організації; використання деревоподібної структури для представлення її "ієрархічної структури" нині широко використовується в багатьох комп'ютерних завданнях.
- Третій приклад - це граматичне дерево; спочатку воно служило для граматичного аналізу комп'ютерних програм, а нині широко використовується і для граматичного аналізу літературної мови.
РОЗДІЛ І. ДИНАМІЧНІ СТРУКТУРИ ДАНИХПід час роботи довільної програми значення деякої статичної змінної може змінюватися, але власне кількість оголошених статичних змінних не змінюється. Це не завжди зручно. Наприклад, якщо програма призначена для введення та обробки даних про учнів класу, а для збереження цих даних використовується звичайний масив, то визначаючи розмір масиву, приходиться орієнтуватися на деяке, як здається програмісту, граничне значення учнів в класі. При цьому якщо реально учнів в класі менше цього граничного значення, то пам'ять ПК використовується неефективно. Якщо ж учнів більше - то таку програму використовувати взагалі неможна. В таких задачах зручно використовувати структури (подібні до масивів) в яких кількість елементів може змінюватися. Такими структурами є зв'язані список. Зв'язаний список нагадує масив, в якому кількість елементів змінюється під час роботи програми.Зв'язаний список можна побудувати використовуючи динамічні змінні. Динамічні змінні можна створювати під час роботи програми («на ходу») за допомогою так званих змінних-вказівників.1.1 ЗМІННІ-ВКАЗІВНИКИЗмінну-вказівник можна уявити як звичайну статичну змінну, але таку, в якій зберігається не деяке конкретне значення (наприклад типу integer, real, …), а адрес іншої змінної.Змінна-вказівник (р) нагадує конверт, який містить лише адресу квартири Петрова, а не її вміст. Можна сказати, що змінна-вказівник р вказує на іншу змінну, яка знаходиться за адресою вул.. 1-го Травня, 58.Вміст змінної-вказівника р: Вул. 1 Травня, 58Вміст змінної за адресою «Вул. 1 Травня, 58» (ця змінна не має імені):Квартира ПетроваЗмінна, що містить значення Квартира Петрова не є звичайною статичною змінною - вона динамічна. <Ім'я змінної-вказівника>:^тип динамічної змінноїНаприклад, a:^integer; b:^real;Щоб змінити значення динамічній змінній, на яку вказує деяка змінна-вказівник z, необхідно виконати команду:z^:=<значення> (z - це змінна вказівник, а z^ - динамічна змінна, на яку вказує вказівник z).Щоб змінити значення змінної-вказівника z (направити її на іншу динамічну змінну) необхідно:z:=<деякий вказівник нв іншу динамічну змінну>Оскільки динамічна змінна не має імені (а отже не описується в блоці var), то на початку роботи програми пам'ять під дану змінну не виділяється. А відповідна змінна-вказівник ні нащо не вказує. Коли змінна-вказівник ні нащо не вказує, то говорять, що вона вказує на nil. Щоб виділити пам'ять, необхідно виконати процедуру new(x), де х - змінна-вказівник.Після виконання даної процедури (new(x)) вказівник x буде вказувати на комірку пам'яті відповідного типу.Нехай на якомусь етапі роботи програми вказівник a вказує на деяку динамічну змінну, що містить число 5, а b на іншу змінну, що містить число 10 (мал.1)Після виконання вказівки a^:=10 (або a^:=b^) напрям вказівника a не змінюється, змінюється значення динамічної змінної (в нашому випадку зміниться значення змінної за адресою 1: замість 5 там буде міститися 10) Якщо ж замість a^:=b^ записати a:=b, то напрям вказівника a змінюється. Змінна-вказівник a буде вказувати на ту ж змінну, що і вказівник b.(мал 3). Тепер значення динамічної змінної, що знаходиться за адресою 2 можна змінити двома способами: використовуючи вказівник a та вказівник b.Після виконання вказівок: a:=b; a^:=100; b^:=15; writeln(a^); на екрані буде число 15 (а не 100)Приклад.1 Демонструє зміну напрямків вказівників на дві незалежні динамічні змінні.var a,b,c:^byte;begin new(a); new(b); read(a^,b^); c:=a; a:=b; b:=c; writeln(a^,' ',b^);end.Результат роботи програми:1 22 1В даній програмі використовується лише дві динамічні змінні (дві комірки пам'яті)Приклад 2 Демонструє перестановку двох динамічних змінних з використанням третьої.var a,b,c:^byte;begin new(a); new(b); new(с); read(a^,b^); c^:=a^; a^:=b^; b^:=c^; writeln(a^,' ',b^);end.Результат роботи програми:1 22 1В даній програмі використовується три динамічні змінні (три комірки пам'яті). Вона працює повністю аналогічно як у випадку із звичайними статичними змінними.Приклад 1 ефективніший за приклад 2, бо:По-перше, використовується дві комірки пам'яті;По-друге, вміст комірок пам'яті не змінюється.1.2. ЗВ'ЯЗАНИЙ СПИСОК. СТЕКВказівники та динамічні змінні дозволяють створювати складні динамічні структури.Найпростішою з них є зв'язаний список.Схематично зв'язаний список можна зобразити так:a1 - змінна-вказівникЕлемент списку a1^- це динамічна змінна (наприклад типу zapis=record), яка в найпростішому випадку складається з двох полів: інформаційного (наприклад, name:string) та змінної-вказівника на наступний елемент списку (next:^zapis). Тобто, динамічна змінна - елемент списку - крім деякого значення містить адресу (змінну-вказівник) наступного елемента списку.Спробуємо описати тип динамічної змінної. Якщо ми назвали тип динамічної змінної zapis, то, здавалося б, цей тип має виглядати так:typezapis=record name:string; next:^zapis;end;Щоб вийти з цієї ситуації оголосимо спочатку «тип-вказівник» elem на тип zapis:typeelem=^zapis;zapis=recordname:string;next:elem;end;Список, кожен елемент якого містять вказівник лише на наступний елемент називається однозв'язним.Список, що містить два вказівники (на попередній та на наступний елементи) - двозвязний.Формування стеку.Формувати список можна добавляючи елементи як на початок списку (стек), як в кінець (черга), так і в довільне місце списку.Приклад 1. Наступна програма демонструє добавляння елемента на початок списку.type elem=^zapis; zapis=record name:string; next:elem; end;var a1,a:elem;begin new(a1); a1^.name:='Иванов'; a1^.next:=nil; writeln(a1^.name); {Добавимо елемент 'Петров' на початок} writeln('Формування стеку:'); new(a); a^.name:='Петров'; a^.next:=a1; write(a^.name,' '); a:=a^.next; writeln(a^.name);end.Результат роботи програми:ИвановФормування стеку:Петров ИвановПриклад 2. Наступна програма демонструє формування безкінечного стеку.type elem=^zapis; zapis=record name:string; next:elem; end;var a1,a:elem; name:string;begin repeat readln(name); if name<>'' then begin new(a); a^.name:=name; a^.next:=a1; a1:=a; end; until name=''; while a<>nil do begin writeln(a^.name); a:=a^.next; end;end.Результат роботи програми:елемент1елемент2елемент3елемент4елемент5елемент6елемент6елемент5елемент4елемент3елемент2елемент1Розглянемо докладніше як працює з попереднього прикладу структура: new(a); a^.name:=name; a^.next:=a1; a1:=a;При повторному виконанні вказівок: new(a); a^.name:=name; a^.next:=a1; a1:=a;в пам'яті ПК відбудуться наступні перетворення:Бачимо, що кожен наступний елемент (Name2) встановлюється на початок списку. Останній елемент, який увійде у стек - перший з нього виходить (він буде на першому місці, тобто при читанні стеку, буде першим).1.3. ЗВ'ЯЗАНИЙ СПИСОК. ЧЕРГА.Формування черги (вставка елементів в кінець списку).Після створення динамічної змінної s^,поміщаємо в неї «Ільчук». Потім необхідно на цей елемент «напрямити» вказівник елемента sn^ (динамічна змінна sn^ містить вказівник next . А отже, sn^.next:=s;). Після цього елемент «Ільчук» добавиться в кінець списку. Але вказівник sn ще вказує на попередньо останній елемент (тобто на «Сидоров»). Напрямимо його на «Ільчук» (на «Ільчук вказує s. Отже, sn:=s).Розглянемо схематично дію програмного коду вставки елемента в чергу.type elem=^zapis; zapis=record name:string; next:elem; end;var s1, s, sn:elem;begin new(s); readln(name); s^.name:=name; s^.next:=nil; if s1=nil then s1:=s else sn^.next:=s; sn:=s; end.В результаті роботи такої програми три вказівника будуть вказувати на перший елемент черги.При повторному виконанні вказівок new(s); readln(name); s^.name:=name; s^.next:=nil; if s1=nil then s1:=s else sn^.next:=s; sn:=s; новий елемент s^ буде добавлено в кінець списку. При цьому s1 буде вказувати на перший елемент списку, а s та sn - на добавлений елемент списку (останній елемент).Розглянемо на схемі повторну дію згаданих вище вказівок: ТЕКСТ ПРОГРАМИ ФОРМУВАННЯ ЧЕРГИ:type elem=^zapis; zapis=record name:string; next:elem; end;var s1, s, sn:elem; name:string;BEGIN s1:=nil; s:=nil; repeat new(s); readln(name); if name<>'' then begin s^.name:=name; s^.next:=nil; if s1=nil then s1:=s; else sn^.next:=s; sn:=s; end; until name=''; while s1<>nil do begin writeln('--',s1^.name); s1:=s1^.next; end;END.ФОРМУВАННЯ ВПОРЯДКОВАНОГО СПИСКУ.S1 - вказівник на перший елемент спискуS_new - вказівник на новий елемент спискуS_p - вказівник на елемент, після якого необхідно здійснити вставку нового елементаBuf - деякий допоміжний вказівник на елемент, який проглядається в процесі пошуку місця для вставки нового елемента.typeelem=^spisok;spisok=recordname:string;next:elem;end;vars1,s_new,buf,s_p:elem;BEGINs1:=nil;s_new:=nil;buf:=nil;repeatnew(s_new);readln(s_new^.name);s_p:=nil;buf:=s1;if s_new^.name<>'' thenbeginwhile (buf^.name<s_new^.name)and(buf<>nil) dobegins_p:=buf;buf:=buf^.next;if s_p=nil thenbegins_new^.next:=s1;s1:=s_new;endelsebegins_new^.next:=s_p^.next;_p^.next:=s_new;end;end;until s_new^.name='';while s1<>nil dobeginwriteln('--',s1^.name);s1:=s1^.next;end;END.ВИДАЛЕННЯ ЕЛЕМЕНТА ЗІ СПИСКУЯкщо у деякому сформованому списку вказівник s_1 вказує на перший елемент списка, то програмний код знищення елементів, що вводяться з клавіатури (якщо він присутній у списку, то нехай buf - це вказівник на елемент, що знаходиться перед ним) , може мати наступний вигляд:{Формування списку}repeatwriteln('Введите элемент, который хотите уничтожить со списка:');readln(name);if name<>'' thenbeginif s1^.name=name then s1:=s1^.nextelsebeginbuf:=s1;while (buf^.next^.name<>name)and(buf^.next<>nil) do buf:=buf^.next;if buf^.next^.name=name then buf^.next:=buf^.next^.next;end;end;until name='';ОБЕРНЕННЯ ЕЛЕМЕНТІВ СПИСКУ (ЗМІНЕННЯ НАПРЯМКІВ УСІХ ВКАЗІВНИКІВ НА ПРОТИЛЕЖНИЙ)1 спосіб (шляхом «переміщення» кожного елемента списку, починаючи з другого, на його початок)
Страницы: 1, 2
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|