Динамични списъци паскал-Паскал - Паскал - Програмиране - членове Directory
Динамични структури от данни (около могат да бъдат намерени на форума)
Обектът на данни е с динамична структура, ако размерът му варира по време на изпълнението на програмата или е потенциално безкрайна.
Класификация на структурите от данни
Използва се, за да програмирате данните могат да бъдат разделени на две основни групи:
Това статична структура - тези данни, относителните позиции и отношения на елементи, които винаги остават постоянни.
Динамична структура на данни - тези данни, вътрешната структура на което се формира от който и да е закон, но броя на елементите, а относителният им отношения може да бъде променян динамично по време на изпълнение на програмата, в съответствие със закона на формиране.
Динамична структура на данните:
Чрез динамичното структурата на файловете с данни включват, независими и свързани динамични данни.
Имайте предвид, че файловете в класирането, възложени на динамични структури от данни. Това се прави въз основа на горното определение. Въпреки премахване и поставяне елементи в средата на файла не е позволено, но дължината на файла в програмата подлежи на промяна - увеличаване или намаляване до нула. И това е най-динамичните свойства на файла като структура от данни.
Статични и динамични променливи в Паскал
Динамична памет (ДП) - PC памет, предоставена от програмата по време на работа, по-малко данни сегмент (64K), стека (16 Kb) и част от самия текст на програмата. динамична памет размер може да варира. По подразбиране DP - цялата налична памет на компютъра.
DP - това е всъщност единствената възможност за обработка на големи масиви от данни за величините. Много практически проблеми са трудно или невъзможно да се реши без да се използва ДП. Така например, в развитието на CAD разпределение статична памет е невъзможно, тъй като измерение на математически модели в различни проекти, може да варира значително.
За да работите с динамични променливи в програмата трябва да се следват следните стъпки:
- заделяне на памет за динамична променлива;
- Инициализиране на показалеца;
- Освобождаване памет след използване на динамична променлива.
Програмистът трябва сам да запазите място, за да се определи стойността на показалеца, освободете ДП.
Вместо това, можете да използвате всеки статична променлива динамика, но без реална нужда от това не си струва да правиш.
Стрелката е свързан с някои определен вид данни, наречена написали показалка. Неговото описание е както следва:
А указател, който не е свързан с нито един вид данни се нарича типизиран указател. За да се опише нетипизирани указатели в Pascal има стандартен тип показалка. Описание на индикатора е следното:
Използване на указатели, която е типизиран динамично разпределяне на структурата на данните и вида на които варира по време на изпълнението на програмата.
Можеше да се очаква, че стойността на показалеца може да бъде прехвърлено в друга. Всъщност, можете да въведете стойности само между указатели, свързани с един тип данни. Указатели към различните видове данни са от различни видове, както и на тези видове не са съвместими.
Това ограничение обаче не се отнася за един типизиран указател. В програмата са включени следните действия ще бъдат разрешени:
Разпределение и освобождаването на динамичната памет
Всички ДП се счита за непрекъснат масив от байтове, който се нарича купчина.
Местоположение купчина в паметта на компютър.
- Heaporg - началото на куп;
- Heapend - края на куп;
- Heapptr - сегашната граница на незаета DP.
разпределение на паметта се извършва по динамична променлива процедура:
Графично, новите процедури за действие, могат да бъдат представени, както следва:
Освобождаване на процедурата по купчина се извършва:
Пример процедура програма фрагмент изхвърли
Имайте предвид, че нееднократно прилагане на процедури, които да се разпореждат свободно показалеца може да доведе до грешка.
разпорежда процедура освобождава паметта взета от динамична променлива. В този случай показалеца е неопределено.
Всяко действие на показалеца в програмата са разположени между новите процедури и да се разпорежда.
При използване на динамично разпределени променливи често възниква проблем от общ характер, наречена динамична памет течове. теч памет - това е ситуация, в която пространството е разпределена в купа, а след това загуби - по някаква причина, курсора не посочва повече от отпуснатите зона, така че не може да освободи място. Често срещана причина за изтичане на памет е rebindings динамични променливи без предварително освобождаване. Най-простият случай е следната:
Пример програма фрагмент
Var IntPointer: ^ цяло число;
започвам
New (IntPointer);
New (IntPointer);
край.
Първото повикване в Новия купчина отпуснати 2 байта, а те определят IntPointer показалка. Втората покана Нови акценти други 2 байта, а IntPointer инсталирани върху тях. Сега не е нужно указател сочи към първите 2 байта, така че не можете да ги освободи. Програмата на тези байтове, ще бъдат загубени.
Принадлежността към показалеца
За да нулирате указатели има няколко възможности.
операция показалка
За съвети как да се определят само оператор задача, и проверка за равенство или неравенство. В Pascal забранява всякакви аритметични операции върху указатели, тяхната вход-изход и сравнение с по--малко.
Още веднъж стрелките правилата за присвояване:
- Вие може да бъде назначен някой индекс нула стандарт постоянно, което означава, че индексът не се отнася за всеки конкретен клетки на паметта;
- стандартни тип показалеца показалки указатели, съвместими с всякакъв вид;
- указател към определен тип данни може да се определи само стойността указател от същия тип данни или стандарт.
Показалки могат да се сравняват за равенство или неравенство, например:
Ако p1 = p2 след това ... ..
Ако p1<>p2 след това ... ..
стандартните функции са определени в Pascal за указатели:
Задаването на стойности на динамичните променливи
Динамични данни за разпределение могат да се използват навсякъде в програмата, която позволява използването на подходящи видове изрази.
R ^: = пл (R ^) + I ^ -17;
р ^: = 2; Inc (р ^); writeln (р ^)
Недопустимо е да се използват изрази като следните:
Вземем примера на работа с указатели:
динамични структури
Линейни списъци (еднопосочен верига).
Списък е структура от данни, където всеки елемент чрез указател, свързани с следващия елемент.
Всеки елемент от свързан списък, на първо място, поддържа някаква информация, и второ сочи към следващия елемент. Тъй като елемент от списък съхранява различни видове (съхранява информация и показалеца), тогава е естествено да представлява рекорд в който се намира на полето в един обект, а другият - указател към следващия запис от същия тип. Този запис се нарича връзка. и структурата на тези записи се нарича списък, или верига.
Само при първия елемент в списъка (главата), отделен индекс. Последният елемент в списъка, няма да се посочи.
Описание списък
Пример списък описание
Тип ukazat = ^ S;
S = запис
Inf: цяло число;
Next: ukazat;
Край;
В Pascal има основно правило, че тя трябва да бъде описано, преди да използвате на всеки обект. Изключение се прави само за насоки, които могат да се обръщат към все още не е обявена тип.
Създаване на списък
За списък съществува, то е необходимо да се дефинира указател към неговото начало.
Пример списък описание
Тип ukazat = ^ S;
S = запис
Inf: цяло число;
Next: ukazat;
Край;
Нека създадем първия елемент от списъка:
Ние продължаваме да създадете списък. За да направите това, добавяне на елемент към двата края на списъка, или в главата.
А) Добавяне на елементи към списък глава. За да направите това, трябва да извършите поредица от действия:
- получите памет за новия елемент;
- се връща на информацията;
- закрепване на елемент към списъка с глава.
Докато ф<> нула правя
започвам
Writeln (ф ^ .inf);
ф: = ф ^ .next;>
приключи;
Премахването на елемента от списъка
А) Отстраняване на първият член. За тази цел във вторичната индекса ще помня първия елемент, указател към началото на списъка, за да преминете към следващата точка от списъка и да освободи района на куп, което показва, под-индекс.
х: = ф;
а (х<> нула) и (х ^. INF<> цифра) направи
започвам
DX: = х;
х: = х ^ .next;
приключи;
DX: = х ^ .next:
разпорежда (х);
Б) премахване на края на списъка. За да направите това, вие трябва да намерите предпоследния елемент.
х: = ф; DX: = ф;
а х ^ .next<> нула правя
започвам
DX: = х; х: = х ^ .next;
приключи;
DX ^ .next: = нула;
разпорежда (х);
Преминаването на списъка. Важно е да бъде в състояние да се справи елементи от списъка, изпълнете с всяка операция. Да предположим, че искате да се намери сумата от списък с елементи.
Сума: = 0;
х: = ф;
докато х<> нула правя
започвам
Сума: = Сума + х ^ .inf;
х: = х ^ .next;
приключи;
Динамични обекти на сложна структура
Използването на еднопосочни списъци може да доведе до някои трудности при решаването на редица проблеми. Фактът, че списъкът на приносител може да се движи само в една посока, от началото на списъка на последното звено. В същото време често е необходимо да се направи операция с елемента, предхождащ елемент с желаните свойства. Въпреки това, след намиране на елемент с даден имот по еднопосочен списък, ние нямаме начин да получите бърз и удобен начин за достъп до предишния елемент.
Тип ukazat = ^ S;
S = запис
Inf: цяло число;
Next: ukazat;
Pred: ukazat;
Край;
Динамична структура, състояща се от единици от вида, наречен двупосочен списък. който може да бъде представен схематично както следва:
В програмирането, двойно свързани списъци често са генерализирани, както следва: като ценност поле на последното звено от Next вземе препратка към елемент заглавие, и като стойност на полето Pred Заглавие на връзката - линк към последното звено:
Има различни методи за използване на динамични списъци:
- Стек - специален вид на списък, достъпът до която е само указател към първия елемент. Ако искате да добавите към елемента на комин, тя се добавя в предната част на първия елемент, показалеца към върха на стека е включен в новия елемент. Алгоритъмът на стека се характеризира с правилото "последен в - първа изходяща".
- Опашка - изглед на списък, който има две указатели към първия и последния елемент на веригата. Новите елементи са написани след последния, и компонентите на пробата е първата. Алгоритъмът на принципа "пръв влязъл - първи навън".
- Възможност за организиране на списъци с произволен достъп до елементите. В този случай имате нужда от допълнителен указател към текущия елемент.
При един текстов файл, а не по-голям от 64 Kb, включващи реални числа, по един във всеки ред. Презаписване на съдържанието на даден файл в масив, което я поставя в купчина. Изчислява се средната стойност на елементите на масива. Изчистване на купчина. Създаване на цяла поредица от размер 10 000, го напълни с произволни числа в интервала от -100 до 100, и се изчислява средната стойност.
? 200 '200px': '' + (this.scrollHeight + 5) + 'пиксела ");">
Програма Srednee;
Строителство Nmax = 10000;
Въведете Diapazon = 1..NMax;
MasInt = Array # 91; Diapazon] От цяло число;
MasReal = Array # 91; Diapazon] От Real;
Var PIint. ^ MasInt; PReal. ^ MasReal;
I, Midint. longInt; MidReal. Реал; Т. Текст; S. низ;
започвам
Напишете ( "Въведете името на файла: '# 41 ;; ReadLn (S # 41 ;;
Задаване (T, S # 41 ;; Reset (Т # 41 ;; MidReal: = 0; MidInt: = 0;
Случаен;
NEW (PReal # 41 ;;
Макар и да не EOF (T # 41; Do
Започнете ReadLn (T, PReal # 91; I] # 41 ;; MidReal: = MidReal + PReal # 91; I] Край;
ПРЕМАХВАТЕ (PReal # 41 ;;
NEW (пинта # 41 ;;
Защото: = 1 За да Nmax Do
Започнете пинта # 91; I]: = -100 + Произволни (41 # 201 ;; MidInt: = MidInt + пинта # 91; I] Край;
WriteLn ( "средно число, равно на: ', MidInt Div Nmax # 41 ;;
WriteLn ( "средният реален и:., (MidReal / Nmax # 41; 10 6 No. 41;
Край.
// C ++ език
#include
#include
#include
#include
#define Nmax 10000
typedef Int MasInt;
typedef поплавък MasReal;
MasInt * пинта; MasReal * PReal;
Int I, п, MidInt; поплавък MidReal; овъгляване S # 91; 255];
FILE * т; знак * endptr;
невалидни основни (# 41;
Т = fopen (S, "R" # 41 ;;
MidReal = 0; MidInt = 0;
случайност (# 41 ;; I = 0;
/ * Памет за недвижими масив * /
PReal = (MasReal * # 41; изчистване (sizeof (MasReal # 41; # 41 ;;
/ * Input и сумиране недвижими масив * /
докато (feof (т # 41;! # 41;
PReal # 91; I] = strtod (S, endptr # 41 ;; // конвертира входния низ на реално число
MidReal + = PReal # 91; I]; I ++;>
п = I + 1;
безплатно (PReal # 41 ;; / * Изтриване на недвижими масив * /
Пинта = (MasInt * # 41; изчистване (sizeof (MasInt # 41; # 41 ;; / * достатъчно памет масив под * /
/ * Изчисляване на сумата на целия масив * /
за (I = 0; I
/ * Посочете средните стойности * /
Cout <<"\nсреднее целое равно " <
>
Създаване на програма, която въз основа на списък с предварително определен формира други двама, поставянето на първата от тях положително, а вторият - отрицателни оригинални елементи от списъка.
? 200 '200px': '' + (this.scrollHeight + 5) + 'пиксела ");">
Програма Ex_sp_1;
Използва Spisok;
Var S1, S2, S3, V1, V2, V3. U; А. BT; I, Н. Байт;
започвам
Случаен;
N: = 1 + Произволни (20 # 41 ;;
S1: = Nil; A: = -100 + Произволни (41 # 201 ;;
V_Nachalo (S1, A # 41 ;; V1: = S1;
За I: = 2 до N Do
Започнете А: = -100 + Произволни (41 # 201 ;; V_Spisok (V1, A # 41 ;; V1: = V1 ^ .Next край;
WriteLn ( "списък спусъка '# 41 ;; Print (S1 # 41 ;;
V1: = s1; S2: = Nil; S3: = Nil;
Докато V1 <> нула Do
започвам
Ако V1 ^ .inf> 0
Тогава Ако S2 = Nil
След това започва V_Nachalo (S2, V1 ^ .inf # 41 ;; V2: = S2 Край
Друго Започнете V_Spisok (V2, V1 ^ .inf # 41 ;; V2: = V2 ^ .Next край;
Ако V1 ^ .inf <0
Тогава Ако S3 = Nil
След това започва V_Nachalo (s3, V1 ^ .inf # 41 ;; V3: = S3 Край
Друго Започнете V_Spisok (V3, V1 ^ .inf # 41 ;; V3: = V3 ^ .Next край;
V1: = V1 ^ .Next
Край;
WriteLn ( "Получената списъка на положителните елементи: '# 41 ;; Print (S2 # 41 ;;
WriteLn ( "Получената списъка с отрицателни елементи: '# 41 ;; Print (S3 # 41 ;;
Ochistka (S1 # 41 ;; Ochistka (S2 # 41 ;; Ochistka (S3 # 41 ;;
Край.