ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.11.2019
Просмотров: 462
Скачиваний: 1
Списком називається структура даних, до якої елементи можуть додаватись (або вилучатись з нього) в довільному місці. Списки поділяються на однозв’язні та двозв’язні. Елемент однозв’язного списку складається з одного інформаційного поля ( або кількох ) та вказівника на наступний елемент. Елемент двозв’язного списку крім того містить ще й вказівник на попередній елемент.
3.2. Опис алгоритму.
В даному алгоритмі ми використовуємо однонаправлений лінійний список в якому кожен елемент має вказівник на наступний елемент, а також три інформаційних поля. Алгоритм обчислення базується на тому що ми за один цикл, переглядаючи список від початку, знайшовши знак операції та два операнди, виконуємо одну операцію і вносимо відповідні зміни в список.
3.3. Текст програми.
Для реалізації цього алгоритму потрібно ініціалізувати список. Це виконує процедура Init ( L ) . Після ініціалізації виконуємо ввід виразу в список. Для запису введених операцій та операндів у список використовується перевірка чи введений елемент є одним з чотирьох знаків арифметичних дій, чи числом чи символом закінчення вводу вираза. На основі цього, якщо введений знак, то в поле typ записується true, в поле znak – відповідний знак, а якщо введене число, то в поле typ записується false, а в num – значення числа. Ми переглядаємо список від початку, і коли зустрічається знак і два числа, слідуючих за ним, ми виконуємо відповідну операцію над операндами, зберігаємо результат в елементі списку, де був знак і видаляємо елементи списку де знаходились операнди за допомогою процедури Delete ( L , I ). Знову повторюємо перегляд, аж поки в списку не залишиться один елемент, значення інформаційного поля якого і буде результатом обчислення введеного арифметичного виразу.
3.4. Тестування.
Для тестування введемо наступний вираз, натискаючи Enter після вводу кожної операції та операнда : / + - * 15 2 37 19 + 7 1. Після вводу виразу у префіксній формі вводимо q, що означає кінець вводу. Отримаємо результат : 1.5 .
Висновки.
Під час виконання курсової роботи “Структури даних та алгоритми” я ознайомився з основними та базовими типами і структурами даних. Також я ознайомився з основними алгоритмами роботи з масивами та списками. Я розробив та протестував ряд програм та алгоритмів, які були використані при виконанні поставлених задач. Мною були розроблені програми, які представляли дані у вигляді, у якому вони зберігаються у пам’яті комп’ютера, виконували сортування елементів, пошук елемента у списку, реалізовували однонаправлений список, обчислювали арифметичний виразу, записаний у префіксній формі. Також я набув навичок розробки програмних продуктів, їх тестування, а також навиків виконання та оформлення технічної документації.
Список використаної літератури:
1. Методичні вказівки і завдання до курсової роботи „Структури даних та алгоритми” з курсу „Основи інформатики, алгоритмізації та мов програмування” для студентів спеціальності
7.091502
"Технологія проблемного та системного програмування" / Укл. Лисак Т.А. – Львів: ІППТ, 2002. – 50 с.
2. Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. –М.: Изд.дом „Вильямс”, 2001. – 832 с.
Додаток 1.
Представлення даних в пам’яті комп’ютера.
Текст програми.
program Kursova;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
zz1=02;
zz2=85;
zz3=zz2-30;
var
b1 : boolean;
b2 : Wordbool;
b3 : Longbool;
ch : Char;
i1 : Byte;
i2 : Shortint;
i3 : Word;
i4 : Integer;
i5 : Longint;
r1 : Real;
r2 : Single;
r3 : Double;
r4 : Extended;
r5 : Comp;
str : String [15];
p : String;
d : zz1..zz2;
m : array [1..2, 1..5] of char;
rec : record
a1, a2 : string[15];
b1, b2, b3 : char;
c1, c2 : integer
end;
s : set of
zz1 .. zz3 ;
f : text;
procedure BooleanTP(b1:boolean);
const b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..1] of byte absolute b1;
begin
b1:=(i1 mod 2)=0;
write('Predstavlennya typu Boolean: ');
for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16]);
writeln
end;
procedure WordBooleanTP(b2:WordBool);
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer; a:array[1..2] of byte absolute b2;
begin
b2:=succ(b1);
write('Predstavlennya typu Word Boolean: ');
for i:=1 to 2 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure LongBooleanTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..4] of byte absolute b3;
begin
b2:=pred(pred(b1));
write('Predstavlennya typu Long Boolean: ');
for i:=1 to 4 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure CharTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..1] of byte absolute ch;
begin
write('Ch = ', ch, '
');
write('Predstavlennya typu Char: ');
for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure ByteTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..1] of byte absolute i1;
begin
write('I1 = ',i1,'
');
write('Predstavlennya typu Byte: ');
for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure ShortIntegerTP;
const b:array[0..15] of char='0123456789ABCDEF';
var i:integer;
a:array[1..1] of byte absolute i2;
begin
write('I2 = ',i2,'
');
write('Predstavlennya typu Short integer: ');
for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16]);
writeln
end;
procedure WordTP;
const b:array[0..15] of char='0123456789ABCDEF';
var i:integer;
a:array[1..2] of byte absolute i3;
begin
write('I3 = ',i3,'
');
write('Predstavlennya typu Word: ');
for i:=1 to 2 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure IntegerTP;
const b:array[0..15] of char='0123456789ABCDEF';
var i:integer;
a:array[1..2] of byte absolute i4;
begin
write('I4 = ',i4,'
');
write('Predstavlennya typu Integer: ');
for i:=1 to 2 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure LongIntegerTP;
const b:array[0..15] of char='0123456789ABCDEF';
var i:integer;
a:array[1..4] of byte absolute i5;
begin
write('I5 = ',i5,'
');
write('Predstavlennya typu Long Integer: ');
for i:=1 to 4 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure RealTP;
const b:array[0..15] of char='0123456789ABCDEF';
var i:integer;
a:array[1..6] of byte absolute r1;
begin
write('R1 = ',r1:4:2,'
');
write('Predstavlennya typu Real: ');
for i:=1 to 6 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure SingleTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..4] of byte absolute r2;
begin
write('R2 = ',r2:6:2,' ');
write('Predstavlennya typu Single: ');
for i:=1 to 4 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure DoubleTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..8] of byte absolute r3;
begin
write('R3 = ',r3:6:2,' ');
write('Predstavlennya typu Double: ');
for i:=1 to 8 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure ExtendedTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..10] of byte absolute r4;
begin
write('R4 = ',r4:6:2,' ');
write('Predstavlennya typu Extended: ');
for i:=1 to 10 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure CompTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..8] of byte absolute r5;
begin
write('R5 = ',r5:4:0,'
');
write('Predstavlennya typu Comp: ');
for i:=1 to 8 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure StringTP;
const b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..13] of byte absolute str;
begin
write('Str = ',str,'
');
write('Predstavlennya typu String: ');
for i:=1 to 12 do write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure CountingTP;
const b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..1] of byte absolute p;
begin
write('P = ',p,'
');
write('Predstavlennya typu Counting: ');
for i:=1 to 1 do
write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure DiapasonTP;
const b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..1] of byte absolute d;
begin
write('D = ',d,'
');
write('Predstavlennya typu Diapason: ');
for i:=1 to 1 do
write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure MasyvTP;
const b:array[0..15] of char='0123456789ABCDEF';
var
i,j:integer;
a:array[1..10] of byte absolute m;
begin
write('M = ');
for i:=1 to 2 do
for j:=1 to 5 do write(m[i,j],' ');
writeln;
write('
Predstavlennya typu Masyv: ');
for i:=1 to 10 do
write(b[a[i] div 16], b[a[i] mod 16],' ');
writeln
end;
procedure RecordTP;
const
b:array[0..15] of char='0123456789ABCDEF';
var
i:integer;
a:array[1..39] of byte absolute rec;
begin
write('Rec = ',rec.a1,rec.b1,' ',rec.a2,rec.b2,' ',rec.c1,
rec.b3,rec.c2,'
' );
writeln;
write('
Predstavlennya typu Record: ');
for i:=1 to 39 do begin
write(b[a[i] div 16], b[a[i] mod 16],' ');
if (i=10) or (i=20) or (i=30) then begin
writeln; write('
')
end;
end;
writeln
end;
begin
writeln('Vvedit pershu literu prizvushca (velyku)');
readln(ch);
writeln('Vvedit den narodzhennja');
readln(i1);
{День народження}
i2:=-i1;
{-i1}
i3:=i1*125;
{i1*125}
i4:=-i3;
{-i3}
i5:=-i3;
{-i3}
writeln('Vvedit drobove chyslo:cila chastyna-misjatc narodzh, drobova-rik');
readln(r1);
{дробове число:ціла частина-місяць народження,
дробова частина-рік народження}
r2:=r1*125;
{r1*125}
r3:=-r2;
{-r2}
r4:=r2;
{r2}
r5:=i5;
{i5}
writeln('Vvedit prizvyshce z velykoi litery');
readln(str);
{Прізвище}
writeln('Vvedit imja z velykoi litery');
readln(p);
{Ім'я}
d:=i1+15;
{День народження + 15}
m[1,1]:='3';
m[1,2]:='9';
m[1,3]:='0';
m[1,4]:='8';
m[1,5]:='0';
m[2,1]:='0';
m[2,2]:='1';
m[2,3]:='0';
m[2,4]:='9';
m[2,5]:='6';
writeln('Vvedit misto');
readln(rec.a1);
{назва міста в адресі прописки}
writeln('Vvedit vulytcju');
readln(rec.a2); {назва вулиці в адресі прописки}
writeln('Vvedit nomer budynku');
readln(rec.c1);
{номер будинку в адресі прописки}
writeln('Vvedit nomer kvartyry');
readln(rec.c2);
{номер квартири в адресі прописки}
rec.b1:= ',';
rec.b2:= ',';
rec.b3:= '/';
if (i1 mod 2)=0
then b1:=true
else b1:=false;
write('B1 = ',b1,'
');
BooleanTP(b1);
b2:=succ(b1);
write('B2 = ',b2,'
');
WordBooleanTP(b2);
b3:=pred(pred(b1));
write('B3 = ',b3,'
');
LongBooleanTP;
CharTP;
ByteTP;
ShortIntegerTP;
WordTP;
IntegerTP;
LongIntegerTP;
RealTP;
SingleTP;
DoubleTP;
ExtendedTP;
CompTP;
StringTP;
CountingTP;
DiapasonTP;
MasyvTP;
RecordTP;
readln
end.
Додаток 2.
Сортування і пошук.
Порозрядне сортування.
program PorozrSort;
{$APPTYPE CONSOLE}
uses
SysUtils;
const n=10; h=32;
type
TElem=record
dec:integer;
bin:array [1..h] of char;
end;
TSpysok=array[1..n] of TElem;
var
i,j,k,p,a_or_b:integer; {a_or_b: 0 - a, 1 - b}
a,b:TSpysok;
c:TElem;
procedure Dec2Bin(var z:TElem; x:integer);
var
k,l:byte;
b:string[2];
y:integer;
begin
b:='01';
k:=h;
y:=abs(x);
while y>=2 do begin
z.bin[k]:=b[(y mod 2)+1];
y:=y div 2;
k:=k-1
end;
z.bin[k]:=b[y+1];
for l:=k-1 downto 1 do z.bin[l]:='0';
if x>=0
then z.bin[1]:='1' {1 - chyslo dodatnie}
else z.bin[1]:='0' {0 - chyslo vidjemne}
end;
procedure Vvid(var z:TSpysok);
var sign,i,choice:integer;
begin
Randomize;
writeln('1 - Vypadkovi chysla');
writeln('2 - Vvesty chysla');
readln(choice);
while (choice1) and (choice2) do begin
writeln('!!! Nevirnyj vybir. Vvedit'' 1 abo 2');
readln(choice);
end;
if choice=1 then begin
sign:=1;
for i:=1 to n do begin
a[i].dec:=Random(1000)*sign;
sign:=-sign;
Dec2Bin(a[i], a[i].dec)
end;
end
else if choice=2 then begin
writeln('Vvedit'' 10 chysel');
for i:=1 to n do begin
readln(a[i].dec);
Dec2Bin(a[i], a[i].dec)
end;
end;
writeln('---===||| Vhidna poslidovnist''');
for i:=1 to n do writeln(a[i].dec,'
',a[i].bin)
end;
procedure SortVidjem(w:TSpysok; var z:TSpysok; k:integer);
var i,j:integer;
begin
j:=1;
if p>=2 then begin
for i:=1 to p do begin
if w[i].bin[k]='1' then begin
z[j]:=w[i];
j:=j+1
end;
end;
for i:=1 to p do begin
if w[i].bin[k]='0' then begin
z[j]:=w[i];
j:=j+1
end;
end;
end;
end;
procedure SortDodat(w:TSpysok; var z:TSpysok; k:integer);
var i,j:integer;
begin
j:=n;
if n-p>=2 then begin
for i:=n downto p+1 do begin
if w[i].bin[k]='1' then begin
z[j]:=w[i];
j:=j-1
end;
end;
for i:=n downto p+1 do begin
if w[i].bin[k]='0' then begin
z[j]:=w[i];
j:=j-1
end;
end;
end;
end;
procedure Vyvid(z,w:TSpysok);
var i: byte;
begin
writeln('---===||| Vidsortovana poslidovnist''');
if a_or_b=0
then for i:=1 to n do writeln(z[i].dec,'
',z[i].bin)
else for i:=1 to n do writeln(w[i].dec,'
',w[i].bin);
end;
begin
Vvid(a);
for i:=n downto 2 do
for j:=1 to i-1 do
if a[j].bin[1]>a[j+1].bin[1] then begin
c:=a[j+1];
a[j+1]:=a[j];
a[j]:=c
end;
p:=0;
while a[p+1].bin[1]='0' do p:=p+1; {p - kil''kist'' vidjemnyh chysel}
if p=1 then b[1]:=a[1];
if p=n-1 then b[n]:=a[n];
k:=h;
while k>=2 do begin
SortVidjem(b,a,k);
SortDodat(b,a,k);
a_or_b:=0;
k:=k-1;
if k>=2 then begin
SortVidjem(a,b,k); SortDodat(a,b,k);
a_or_b:=1;
k:=k-1
end;
end;
Vyvid(a,b);
readln
end.
Пошук Фібоначчі
program FiboSearch;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
n=12;
type
TSpysok=array[1..n] of integer;
Var
K,i:integer;
a:TSpysok;
error:boolean;
porivn:integer;
procedure Vvid(var z:TSpysok);
var sign,i,choice:integer;
begin
Randomize;
writeln('1 - Vypadkovi chysla');
writeln('2 - Vvesty chysla');
readln(choice);
while (choice1) and (choice2) do begin
writeln('!!! Nevirnyj vybir. Vvedit'' 1 abo 2');
readln(choice);
end;
if choice=1 then begin
sign:=1;
for i:=1 to n do begin
a[i]:=Random(1000)*sign;
sign:=-sign;
end;
end
else if choice=2 then begin
writeln('Vvedit'' 12 chysel');
for i:=1 to n do readln(a[i])
end
end;
procedure Sort(var z:TSpysok);
var i,j,x:integer;
begin
for i:=n downto 2 do
for j:=1 to i-1 do
if a[j]>a[j+1] then begin
x:=a[j+1];
a[j+1]:=a[j];
a[j]:=x
end
end;
function Find(z:TSpysok; x:integer):integer;
var i,p,q,p1:integer;
found:boolean;
begin
Find:=0;
error:=false;
found:=false;
i:=8; p:=5; q:=3;
repeat
porivn:=porivn+1;
if xthen
if q0 then begin
i:=i-q;
p1:=p;
p:=q; q:=p1-q
end
else begin
writeln('!Nema takogo elementa v masyvi!');
readln; halt
end
else begin
porivn:=porivn+1;
if x>a[i] then
if p1 then begin
i:=i+q;
p:=p-q; q:=q-p
end
else begin
writeln('!Nema takogo elementa v masyvi.!');
readln; halt
end
else begin
Find:=i;
found:=true
end
end
until found;
end;
begin
porivn:=0;
writeln('*** Poshuk Fibonacci ***');
Vvid(a);
Sort(a);
writeln('
Vhidna poslidovnist''');
for i:=1 to n do writeln(i,')
',a[i]);
write('Vvedit'' element, jakyy treba znaity: ');
readln(K);
writeln('Poriadkovyi nomer chysla ',K,': ',Find(a,K),'.');
writeln('Kil''kist'' porivnian'' : ',porivn,'.');
readln
end.
Додаток 3.
Обчислення арифметичного виразу, записаного у префіксній формі.
program spysok_masyv;
{$APPTYPE CONSOLE}
uses SysUtils, A_list;
begin
Init(L);
writeln('** Obchyslennia vyrazy, zapysanogo v prefiksnij formi **');
Vvid(L,Free,Space);
writeln('** Rezultat obchyslennia : ',PrefixCalculate(L):10:4,'**');
readln
end.
unit A_List;
interface
const N=100;
type
IndexType=0..N;
InfoType=real;
ElemType=record
typ:boolean;
num:InfoType;
znak:char;
next:IndexType;
end;
ListType=IndexType;
SpaceType=array [0..N] of ElemType;
var L:ListType;
Free:IndexType;
Space:SpaceType;
procedure Init (var L:ListType);
function Empty (L:ListType):boolean;
function Full (L:ListType):boolean;
function FindLast (L:ListType):IndexType;
function FindBefore (L:ListType; K:IndexType):IndexType;
procedure Delete (var L:ListType;K:IndexType);
procedure AddElem (var L:ListType; t:boolean; x:InfoType; c:char);
procedure Vvid(var L:ListType;var Free:IndexType;var Space:SpaceType);
function PrefixCalculate (L:ListType):real;
implementation
procedure Init (var L:ListType);
var i:IndexType;
begin
for i:=1 to N-1 do space[i].Next:=i+1;
Space[0].next:=0;
Space[N].next:=0;
L:=0;
Free:=1
end;
function Empty (L:ListType):boolean;
begin
Empty:=L=0
end;
function Full (L:ListType):boolean;
begin
Full:=Free=0
end;
function FindLast (L:ListType):IndexType;
var i:IndexType;
begin
i:=L;
while Space[i].Next0 do i:=space[i].Next;
FindLast:=i
end;
function FindBefore (L:ListType; K:IndexType):IndexType;
var i:IndexType;
begin
i:=L;
FindBefore:=0;
while Space[i].NextK do i:=Space[i].Next;
FindBefore:=i
end;
procedure Delete (var L:ListType;K:IndexType);
var i,j:IndexType;
begin
i:=K;
if Space[i].Next=0
then begin
j:=FindBefore(L,i); Space[j].Next:=0;
end
else begin
j:=Space[i].Next;
Space[i]:=Space[j]; i:=j;
end;
Space[FindLast(Free)].Next:=i;
Space[i].Next:=0
end;
procedure AddElem (var L:ListType; t:boolean; x:InfoType; c:char);
var i,j:IndexType;
begin
if not Full(L) then begin
i:=Free;
Free:=Space[Free].next;
space[i].typ:=t; space[i].num:=x; space[i].znak:=c;
space[i].next:=0;
j:=FindLast(L);
space[j].Next:=i;
end
else writeln('Error: List is Full')
end;
procedure Vvid(var L:ListType;var Free:IndexType;var Space:SpaceType);
var i:integer; s:string; x:InfoType;
begin
writeln('- Vvedit vyraz v prefiksnij formi, natyskajuchy "Enter"');
writeln('
pislia kozhnogo operatora ta operanda');
writeln('
(dlia zakinchennia vvodu vyraza vvedit'' q)');
repeat
readln(s);
if (s[1]='+')or(s[1]='-')or(s[1]='*')or(s[1]='/')or(s[1]='.')
or(s[1]='1')or(s[1]='2')or(s[1]='3')or(s[1]='4')or(s[1]='5')
or(s[1]='6')or(s[1]='7')or(s[1]='8')or(s[1]='9')or(s[1]='0')
then if (s[1]='+')or(s[1]='-')or(s[1]='*')or(s[1]='/')
then AddElem(L,true,0,s[1])
else begin
Val(s,x,i); AddElem(L,false,x,' ');
end
else if s[1]='q'
then writeln('- vvid zakincheno')
until s[1]='q';
end;
function PrefixCalculate (L:ListType):real;
var i,j:IndexType;
z:char;
calc:0..2;
a:array[1..2] of InfoType;
begin
PrefixCalculate:=0;
calc:=0;
z:=' ';
while FindLast(L)>1 do begin
i:=L;
repeat
i:=Space[i].next;
if Space[i].typ=true
then begin
calc:=0;
z:=Space[i].znak
end
else begin
calc:=calc+1; a[calc]:=Space[i].num
end;
until calc=2;
j:=FindBefore(L,i);
Delete(L,i);
i:=FindBefore(L,j);
Delete(L,j);
Space[i].typ:=false;
Space[i].znak:=' ';
case z of
'+': Space[i].num:=a[1]+a[2];
'-': Space[i].num:=a[1]-a[2];
'*': Space[i].num:=a[1]*a[2];
'/': Space[i].num:=a[1]/a[2];
end;
end;
i:=Space[L].next;
if Space[i].next=0
then PrefixCalculate:=Space[i].num
else writeln('Error - je > 1 elem')
end;
end.
Ключові слова:
Курсова робота , Структури даних та алгоритми
Коментарі
Залишити коментар »
Ви не можете залишити коментар.
Для цього, будь ласка, увійдіть або зареєструйтесь.
Завантаження файлу
поділитись
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
детальніше
і отримай привілеї у користуванні архівом! детальніше
Вхід
увійти
реєстрація
забули пароль?
запам'ятати мене
Партнери сайту
© 2012 antibotan.com - Навчатись легко!