Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення icon

Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення




Скачати 373.34 Kb.
НазваДані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення
Сторінка1/2
Дата конвертації20.01.2013
Розмір373.34 Kb.
ТипДокументи
  1   2

  1. Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення.


У інформатиці дані символізують інформацію, що представлена у вигляді необхідному для її опрацювання автоматичними засобами. Для цього інформацію кодують за допомогою знаків (алфавіт) відповідно до правил певного синтаксису. У сучасних машинах використовується двійковий метод запису даних за допомогою 0 та 1 (алфавіт з двох цифр). Для полегшення роботи для людини двійковий код перекодовується у більш зрозумілі числа, букви тощо.

Дані є інформацією лише тоді, коли вони несуть значення у заданому контексті. Наприклад: кодом міжнародного телефонного зв'язку є набір знаків +38, тобто це дані, про інформацію ми можемо говорити лише за наявності відомості про назву країни, що відповідає цьому коду.

Дані розрізняють на: структуровані (наприклад: база даних, XML-документ),

не структуровані (наприклад: текстовий документ),

тимчасові.

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

Важливими проблемами у інформатиці, особливо у розподілених системах,— є синхронізація даних, а в управлінні даними — стрімке зростання кількості даних.

Модифікація даних

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

Структура даних це програмная| еденица| що дозволяє зберігати і обробляти.Для додавання пошуку модифікації даних структура даних надає декілька фкнкций| який є интерфей| структурами даних.Структура даних часто являетса| реалізацією якого або абстрактного типу даних типу.Бінарне дерево простий приклад ветвлящейся| зв'язної структури даних. Структури даних формуються за допомогою типів даних посилань и операций| над ними у выбраном| мову.

Дані це представлення фактів ідей у формализованом| вигляді придатному для придатні для передачі і обробки в інформаційному процесі.


  1. ^ Структура даних мови Object Pascal, коротка характеристика складених типів даних, приклади використання.


Вивчення мови програмування полягає у вивченні властивостей типів даних, структур керування даними, і прикладів застосування до розв’язання практичних задач. Теоретик програмування Дейкстра дав таке визначенням програм: «Програми = алгоритми + структури даних». Брукс «Сутністю програмування є представлення даних».

Поняття типу даних є одним з фундаментальних понять. Введення цього поняття дозволяє абстрагуватися від конкретного представлення даних на рівні машинних кодів. Кожен тип даних визначає множину значень, які можуть приймати об’єкти поданого типу, і множину операцій, які можна до них застосовувати. Якими б складними не були типи даних, що визначаються програмістом, врешті решт всі вони будуються на основі елементарних стандартних типів даних.

Кожна мова програмування має цілком визначену сукупність простих (атомарних) типів, які описують числа, логічні і символьні змінні.

^ Схема Типи Даних

Вбудовані: ординарні, дійсні.

Складені: рядки, множини, масиви, запис.

Списки: Вказівникові, лінійні, кільцеві, двонаправленні.

^ Файли: типізовані,без типу,текстові.

Класи.


  1. Масиви статичні та динамічні, переваги та недоліки. Використання масивів для організації роботи з даними. Заповнення масивів з файлу.

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

Масиви за своєю організацією можуть бути статичними: кількість елементів, а значить і розмір виділеної пам’яті для них визначається під час компіляції програми, а також динамічними: кількість елементів яких визначається і може бути змінена як в одну так і в іншу сторону під час виконання програми. Останній варіант є більш практичним за рахунок суттєвої економії оперативній пам’яті при обробці заздалегідь невизначеної довжини послідовності.

type

^ Приклад опису та використання статичного масиву

type

Person=record

Name:string[15];

YearOfBirth:integer;

end;

Mas1=array[1..3] of Person;

Const M:Mas1=((Name:’Ivanov’; Age:45),(Name:’Петров’; Age:55).

^ Приклад опису та використання динамічного масиву

type

Person=record

Name:string[15];

YearOfBirth:integer;

end;

Mas1=array of Person;

var P:Person; M:Mas1;

begin

SetLength(M,3);


  1. ^ Формування типізованого файлу на базі таблиці Excel. Приклад програми.


Таблиця з Excel зберігається з розширенням "Текстовые файлы(с разделителями

табуляции)*.txt";

отриманий файл відкрити у Word'і як текстовий, та за допомогою команди "Пошук та заміна"

замінити знаки табуляції на проміжки;

проміжки у значеннях полів замінити на підкреслення (наприклад, назва кафедри:

"Інтелектуальні інформацйні системи" замінити на "Інтелектуальні_інформацйні_системи"

проміжків у атрибутах записів не повинно бути, це пов'язано з тим, що значення

атрибута читається з рядка до першого проміжка;

кому в дійсних числах замінити на крапку.

Треба мати на увазі, що код програми необхідно пристосовувати до особливостей

типів та імен атрибутів записів

begin

DecimalSeparator:='.';

assignfile(Excel_txt,'Клієнти_tab.txt'); assignfile(Ft,'Client.typ');

reset(Excel_txt); rewrite(Ft);

while not Eof(Excel_txt) do

begin

readln(Excel_txt,St);

Memo1.Lines.Add(St);

end; reset(Excel_txt); readln(Excel_txt,St);

while not Eof(Excel_txt) do

begin readln(Excel_txt,St);

St:=St+' '; I:=1; St1:='';

while St[I] <> ' ' do

begin St1:=St1+St[I];

Inc(I);end;

P.Name_ID:=StrToInt(St1);

while St[I] = ' ' do Inc(I);



  1. ^ Масиви статичні та динамічні. Додавання, видалення та модифікація даних (робота із даними). Приклад програмного коду.


Масив – це упорядкована послідовність однотипних елементів, кожен з яких має один і той же тип. Тип елементів зветься базовим і може бути будь-яким, навіть структурованим, наприклад, запис (record), який має заздалегідь визначений об’єм пам’яті. Масиви зберігаються в оперативній пам’яті комп’ютера. Елементи масиву розміщені впорядковано, кожен має свій номер, який називається індексом. Доступ до елементів масиву відбувається шляхом вказування імені масиву та його порядкового номера у послідовності, тобто використовується прямий метод доступу. Індексом може бути будь-який арифметичний вираз ординального типу.

Масиви за своєю організацією можуть бути статичними: кількість елементів, а значить і розмір виділеної пам’яті для них визначається під час компіляції програми, а також динамічними: кількість елементів яких визначається і може бути змінена як в одну так і в іншу сторону під час виконання програми. Останній варіант є більш практичним за рахунок суттєвої економії оперативній пам’яті при обробці заздалегідь невизначеної довжини послідовності.

^ Видалення даних з масиву. Це набагато складніша операція, тому що вона складається із певної низки доволі довгих операцій з масивом, які виконуються за наступним алгоритмом:

Виконати пошук елементу, який потрібно видалити.

Якщо його знайдено, то можна застосувати два шляхи:

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

2)У структурі елементу заздалегідь необхідно передбачити поле, яке буде означати: дійсний це елемент або виключений із послідовності. У знайденому елементі робиться помітка про його виключення із послідовності. Перевага цього підходу полягає в тому, що уникається така довготривала операція, як переміщення елементів. Цей алгоритм можна застосовувати як для несортованих масивів, так і для сортованих. Недоліком є те, що залишаються „дірки” у масиві, якщо їх буде багато, то обробка масиву суттєво уповільнеться.

^ Додавання даних у масив. Якщо масив невідсортований і динамічний, то додавання нового елементу зводиться до збільшення кількості елементів на одиницю (1) і додаванню його у кінець. Для статичного масиву додавання нового елементу можливо тільки у випадку, якщо є вільні порожні елементи масиву у кінці, або „дірки” при попередньому видаленні елементу шляхом помітки його як недійсного.

Якщо масив відсортований, то можна застосувати два підходи:

1)Знайти місце вставки, зсунути елементи праворуч на 1, записати новий елемент на звільнене місце.

2)Дописати новий елемент в окремий додатковий масив. При необхідності пошуку спочатку виконати пошук в основному масиві бінарним алгоритмом, а потім у додатковому - звичайним послідовним. Якщо об’єм основного масиву достатньо велекий, а додаткового – навпаки, то цей підхід може суттєво зменшити час роботи програми. Через певний відрізок часу звичайно ці два масиви об’єднують в один масив та знову відсортувують його.



  1. ^ Стек: призначення, приклади, застосування. Організація та робота стеку на базі масиву. Приклад програмного коду.


Стек, це динамічний список, дані у який вставляються у «хвіст», вибір даних теж виконуються із «хвоста». Мнемонічна назва цієї структури: «останнім прийшов – першим вийшов». Якщо записати у стек якусь послідовність даних, а потім її вибрати із стеку, то отримаємо інвертовану структуру (переписану с кінця). Нижче наведено процедури додавання та вибору елементів із стеку.

const

M:Mas1=((p:3; q:2),(p:1; q:5),(p:1; q:2),(p:2; q:3),(p:2; q:1),

(p:4; q:4),(p:4; q:2),(p:3; q:1),(p:2; q:1),(p:4; q:5),(p:0; q:5));


procedure InsertNodeStack(var First:TNode; Info:Node);

{Вставка одного елемента у стек }

var

NewP:TNode;

begin

New(NewP); // формування елементу стеку і вставка його у стек

NewP^.q:=Info.q; NewP^.p:=Info.p; NewP^.Next:=nil;

if First=nil then

begin //якщо стек порожній

NewP^.Next:=nil; First:=NewP;

end

else

begin //якщо стек не порожній

NewP^.Next:=First First:=NewP;

end;;// procedure InsertNodeStack


  1. ^ Черга: призначення, приклади , застосування. Організація та робота черги на базі масиву. Приклад програмного коду.


Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.


Процедура вставки чергового елементу у хвіст черги.

procedure InsertNodeLine(var:TNode; Info:Node);

{Додавання елементу у чергу, якщо черга порожня, то First:= nil

First – адреса «хвоста» списку, Info – інформаційна частина елементу списку, тип даних - record}

var

NewP:TNode;

begin

New(NewP); // виділення пам’яті під елемент черги

NewP^.q:=Info.q; // заповнення інформаційної частини елементу

NewP^.p:=Info.p;

NewP^.Next:=nil;

if First=nil then

begin // якщо черга порожня

NewP^.Next:=nil;

First:=NewP;

end

else

begin //якщо в черзі є хоча б один елемент

NewP^.Next:=First;

First:=NewP;

end;

end;// procedure InsertNodeLine



  1. ^ Пошук даних в масиві. Послідовний та бінарний методи пошуку. Переваги та недоліки. Приклад програмного коду.

Бинарный поиск:

Для того, чтобы найти нужную запись в таблице, в худшем случае требуется log2(N) сравнений. Это значительно лучше, чем при последовательном поиске.

BinarySeekMassiv(Left,Right, Number:integer;

var Index,Quant:integer;

M:group):boolean;

begin

BinarySeekMassiv:=false; Quant:=0;

while Left <= Right do

begin

Middle:=(Left+Right) div 2;

if M[Middle].NomKaf < Number then

begin

Left:=Middle+1;

Inc(Quant);

end

else

if M[Middle].NomKaf > Number then

begin

Right:=Middle-1;

Inc(Quant);

end

else

//інакше ми найшли елемент, що шукали

begin

BinarySeekMassiv:=true;

Index:=Middle;

//виходимо із процедури

Exit;

end;

end;

end;

Последовательный

Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма - линейный - O(N).

//шукаємо елемент із кодом 2 послідовним пошуком

J:=0;

while G[J].NomKaf <>2 do

Inc(J);

  1. ^ Сортування масивів на місці, прості та складні алгоритми сортування. Приклад програмного коду (але не бульбашкою).

Методи сортування можна розбити у відповідності до визначаючих їх принципів на три основні групи:
    1. Сортування за допомогою вставки (by Insertion) або за допомогою включення.
    2. Сортування за допомогою вибору (by Selection) або за допомогою виділення.
    3. Сортування за допомогою обміну (by Exchange) або бульбашкове.
  Кожна група має прямий метод (самий простий) і покращені(ускладнені) методи сортування.
^ Сортування за допомогою вставки.

procedure sortd; {Файл процедуры метода c:\f1\s_dir.pas}

var i,j,x:integer;

begin

for i:=2 to N do

begin x:=a[i]; a[0]:=x; {stop} j:=i;

while x
begin

a[j]:=a[j-1]; j:=j-1

end;

a[j]:=x {Вставка}

end

end;


  1. ^ Сортування масивів на місці, метод вставок.


  Принцип сортування: масив розподіляється на відсортовану та невідсортовану частини. На першому кроці за відсортовану частину (послідовність) приймається перший елемент масиву. Кожний наступний елемент з невідсортованої частини вставляємо в заздалегідь відсортовану послідовність так, щоб ця послідовність залишалась відсортованою.
При цьому треба:
    1. Знайти місце, куди потрібно вставити цей елемент.
    2. Зсунути елементи, що стоять справа у відсортованій частині, на одну позицію вправо.
    3. На звільнене місце поставити елемент, що аналізується(вставляється).
  Два способи виконання цих дій:
    1) кожний наступний елемент порівнюється з елементами у відсортованій частині, знаходиться місце вставки, всі наступні елементи зсуваються на одну позицію вправо і після цього вставляється елемент;
    2) елемент, що вставляється, послідовно, зліва направо, порівнюється з кожним із елементів у відсортованій частині. Якщо потрібно, елемент у відсортованій частині одразу зсувається на одну позицію вправо. Як тільки знайдено потрібне місце вставки, елемент, що аналізується, вставляється на потрібну позицїю.

procedure sortd; {Файл процедуры метода c:\f1\s_dir.pas}

var i,j,x:integer;

begin

for i:=2 to N do

begin x:=a[i]; a[0]:=x; {stop} j:=i;

while x
begin

a[j]:=a[j-1]; j:=j-1

end;

a[j]:=x {Вставка}

end

end;



  1. ^ Сортування масивів на місці, метод простого вибору.


Реализация данного метода не требует дополнительной памяти.

Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами.

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

а потому следующий раз достаточно просматривать уже меньшее количество элементов.

Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма. Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N - количество элементов.

Вот как это можно реализовать:

Program BubbleSort;

Var A : array[1..1000] of integer;

N,i,j,p : integer;

Begin

for i:=1 to n do

for j:=1 to n-i do

if A[j]>A[j+1] then

begin {Обмен элементов}

p:=A[j];

A[j]:=A[j+1];

A[j+1]:=P;

end;



End.


  1. ^ Сортування масивів на місці, метод Shaker (одночасний пошук мінімального та максимального елементів.


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

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

Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N - количество элементов. Реализация данного алгоритма выглядит так:

Var A : array[1..1000] of integer;

N,i,j,p : integer;

Min, Max : integer;

Begin

{Определение размера массива A - N) и его заполнение}



{сортировка данных}

for i:=1 to n div 2 do

begin

if A[i]>A[i+1] then

begin

Min:=i+1; Max:=i;

end

else begin

Min:=i;Max:=i+1;

end;

for j:=i+2 to n-i+1 do

if A[j]>A[Max] then Max:=j

else

if A[j]
Min:=j; P:=A[i];

A[i]:=A[min]; A[min]:=P;

if max=i then

max:=min; P:=A[N-i+1];

A[N-i+1]:=A[max]; A[max]:=P; end; … End

  1. Динамічний розподіл оперативній пам’яті (виділення, ініціалізація даних, звільнення пам’яті). Лінійні, кільцеві та двонаправлені динамічні списки, переваги та недоліки. Загальна характеристика. Приклад програмного коду.

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

^ Данные динамической структуры:

Файлы:Текстовые , типизированные, не типезированные

Связанные и несвязанные динамические структуры:

Линейной структуры: односвязные(очередь, стек, Дек, список) и многосвязные.

^ Кольцевой структуры: односвязный кольцевой список и многосвязный кольцевой спосок.

Разветвленной структры: Деревья(Бинарные, Разветвленные) Графы.


  1. ^ Динамічний список: призначення, організація, формування, ініціалізація, наприклад з файлу. Переваги та недоліки порівняно з масивами. Приклад програмного коду.


Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Nil).

Схематически это выглядит так:





Просмотр списка

Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р поочередно устанавливается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция вывода поля данных на экран. Начальное значение р – адрес первого элемента списка p^. Если р указывает на конец списка, то его значение равно Nil, то есть while p<>Nil do

Begin

Write(p^.Data, ' ');

p := p^.Next;

End



  1. ^ Лінійний динамічний список: додавання, видалення та модифікація даних (робота з даними, порівняти із масивами). Приклад програмного коду.

Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной px, второй – в dх), после чего установить новые связи с элементом, в котором хранится значение Digit.

Операторы, выполняющие данную задачу, будут следующими:New(x);

x^.Data := Digit;

px^.Next := x;

x^.Next := dx;

Приведем процедуру InsInto, которая ищет место в списке и вставляет элемент, переданный ей как параметр. В результате сразу получается упорядоченный список. Адрес первого элемента списка передается параметром Head.

Procedure InsInto(Digit : integer; Var Head : Ukazatel );

Var

dx, px, x : Ukazatel ;

Begin

New(x);

x^.Data := Digit; x^.Next := Nil; if Head = Nil

then Head := x

else Begin dx := Head; px := Head;

while (dx<>Nil) and (dx^.Data<=Digit) do

Begin px := dx; dx :=dx^.Next;

End if dx=Nil

then {Пройден весь список}

px^.Next := x else Begin x^.Next := dx;

if dx=Head then

Head := x else

px^.Next := x; End; End; End;

Удаление элемента из конца списка производится, когда указатель dx показывает на предпоследний элемент списка, а х – на последний.

Изобразим удаление графически:

{Найдем предпоследний элемент}

x := Head;

dx :=Head;

while x^.Next<>Nil do

Begin

dx := x;

x := x^.Next;

End;

{Удаляем элемент x^ из списка и освобождаем занимаемую им память}

dx^.Next := Nil;

Dispose(x);

^ Процедура просмотра:

Begin

Write(p^.Data, ' ');

p := p^.Next;

End



  1. Кільцевий динамічний список: переваги та недоліки порівняно з лінійним. Додавання, видалення та модифікація даних (робота із даними). Порівняти з лінійним. Приклад програмного коду.

Структура кольцевого двухсвязного списка

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

Koльцо - это вид связанного списка, в котором указатель последнего элемента ссылается на первый элемент.

К кольцу применим обход элементов, доступ возможен к любому элементу структуры.

Кольцо является динамической структурой – может изменяется и количество, и набор составляющих его элементов.

Опишем кольцо на языке программирования:Type

TypeCircle = ^K;

K = record

Data : integer;

Next : TypeCircle;

End;

Var

Circle1 : TypeCircle;

Обход кольца

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

Рассмотрите процедуру обхода кольца. Procedure PrintК(u : TypeCircle);

Var

x : TypeCircle;

Begin

x := u;

repeat

write(x^.Data,' ');

x := x^.Next;

until x = u;

readln;

End;


  1. ^ Сортування даних у динамічних списках по одному та декільком полях. Приклад програмного коду.

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

{ Сортировка выборкой на 1-связном списке }

Function Sort(head : lptr) : lptr;

var newh, max, prev, pmax, cur : lptr;

begin newh:=nil; while head<>nil do

begin max:=head; prev:=head; cur:=head^.next; while cur<>nil do begin

if cur^.key>max^.key then begin

max:=cur; pmax:=prev;

end; prev:=cur; cur:=cur^.next end;

if max=head then head:=head^.next

else pmax^.next:=max^.next;

max^.next:=newh; newh:=max;

end; Sort:=newh;

end;


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

{ Сортировка вставками на 1-связном списке }

type data = integer;

Function Sort(head : lptr) : lptr;

var newh, cur, sel : lptr;

begin

newh:=nil;

while head <> nil do begin sel:=head;

head:=head^.next

if (newh=nil) or (sel^.key < newh^.key) then begin

sel^.next:=newh; newh:=sel; end

else begin

cur:=newh;

while (cur^.next <> nil) and (cur^.next^.key < sel^.key) do

cur:=cur^.next;

sel^.next:=cur^.next; cur^.next:=sel;

end; end; Sort:=newh;

end;


  1. ^ Стек: призначення, приклади , застосування. Організація стеку за допомогою лінійного динамічного списку. Приклад програмного коду.


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

Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека.

Изобразим стек графически:

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

Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.

Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.

Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.

Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, "нижний" элемент.

Таким образом, описать стек можно следующим образом:Type

EXST = ^ST;

ST = record

Data : integer;

Next : EXST;

end;

Var

Stack : EXST; {Текущая переменная} Если стек пуст, то значение указателя равно Nil.


  1. ^ Включення/забирання елемента до/з стеку. Приклад програмного коду.


Занесение элемента в стек

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

Процедура формирования стека будет иметь следующий вид:

Procedure add(Pn:Tperson;var First:Tperson);

Begin if First <>nill then

Begin

Pn^.Next = First; First :=Pn; end

Else begin Pn^.Next=nil; First:=Pn;end

End;

Извлечение элемента из стека

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

Procedure Extract(First:Tperson;var Pold:Tperson);

Begin

if First <>nill then

Begin Pold:=First; First:=Pold.Next; end

Else begin Pold:=nil;end;

End;

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



  1. ^ Включення/забирання елемента до/з черги. Приклад програмного коду.

Черга – структура яка э звичайною чергою.

Занесение элемента в очередь

Занесение элемента в очередь реализуется как добавлению элемента в конец списка. Рассмотрите процедуру, описанную ниже.

Procedure Add(Last:Tperson; var Pnew:Tperson);

Begin if Last <>nil then

Begin Pnew^.Next: = Last;Last:=Pnew; end

Else begin Pnew^.Next = nil;Last:=Pnew;end

End;

Извлечение элемента из очереди

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

Procedure Extract(Last:Tperson; var Pold:Tperson);

Var P:TPerson;

Begin if Last <> nil then

Begin P:=Last;

While P^.Next^.Next<>nil do P:=P^.Next;Pold:= P^.Next;P^.Next:=nil;

end;

Else Pold:= nil;

End;



  1. Черга: призначення, приклади застосування. Організація черги за допомогою лінійного динамічного списку. Приклад програмного коду.

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

Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.

Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.


Для работы с очередью используются указатели на ее начало и конец, а также вспомогательный указатель. По отношению к очередям может использоваться специальная терминология, например, начало (front) и конец (rear) очереди. Объекты вставляются в конце очереди и проталкиваются по ней до тех пор, пока не достигнут начала очереди.



Для работы с очередями используются следующие действия:

  • Очистка очереди;

  • Считывание первого элемента очереди;

  • Вставка элемента в конец очереди;

  • Удаление первого элемента очереди;

  • Проверка, является ли очередь пустой.
  1   2



Схожі:

Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconКонцепція типу даних
Структура даних, прості і складені типи даних, схема, приклади деяких простих типів, призначення
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформації про особу (персональних даних) потребує неабиякої уваги, передусім з точки зору змісту таких понять, як персональні дані, ідентифікаційний номер та ідентифікація даних
Прогрес в галузі інформаційних технологій, зокрема, в сфері розробки та впровадження програмного забезпечення, активність у формуванні...
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа х  Резидент х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа х  Резидент х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа х  Резидент х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа х  Резидент х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа х  Резидент х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа х  Резидент х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа  Резидент
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення iconІнформація про володільця бази персональних даних  Юридична особа Х  Резидент Х
Прошу зареєструвати базу персональних даних у Державному реєстрі баз персональних даних
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи