Структуры и алгоритмы обработки данных
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
тора theArray с размером SIZE}
Procedure Vector (SIZE, MAX: integer; var theArray:arrayType);;i:=1 to SIZE do[i]:=random(MAX);
{Writeln('Исходный массив: ');i:=1 to Size do(theArray[i],' ');};QSort (SIZE:integer; var theArray:arrayType; var time:real);, min, sec, hund: word;_time, finish_time: real;sort (L,R:integer);, Tmp: Integer;:=L;:=R;:=theArray[(L+R) div 2];i<=j dotheArray[i]<B do i:=i+1;B<theArray[j] do j:=j-1;i<=j then:=theArray[i];[i]:=theArray[j];[j]:=Tmp;:=i+1;:=j-1;;;L<j then sort(L,j);i<R then sort(i,R);;(hour,min,sec,hund);_time:=sec+hund*0.01+min*60+hour*3600;(1,Size);(hour,min,sec,hund);_time:=sec+hund*0.01+min*60+hour*3600;:= finish_time - start_time;
end;
{главная программа};
assign (f, 'd:\Work\Ann\tp71\BIN\Serik');
rewrite (f);('Введите необходимое количество точек для построения графики: ');
Readln(point);:=round(ARRAYSIZE/point);
Writeln ('Введите количество экспериментов: ');(exp);(f, ' Среднее время сортировки элементов ');(f, ' кол-во ',' обратно- ',' сортированные');(f, 'элементов сортированные ');
for k:=1 to point do:=step*k;i:=1 to 3 do_time[i]:=0.0;j:=1 to exp do(n,ARRAYSIZE,a);(n,a,t);_time[i]:=aver_time[1]+t;i:=1 to n div 2 do:=a[i];[i]:=a[n-i+1];[n-i+1]:=c;;(n,a,t);_time[2]:=aver_time[2]+t;(n,a,t);_time[3]:=aver_time[3]+t;;i:=1 to 3 do_time[i]:=aver_time[i]/exp;(f,n:7,' ');i:=1 to 3 do(f, aver_time[i]:7:2,' ');(f);;(f);
end.
Задача 3. Циклические списки
Задание:
Описать указанный абстрактный тип данных и основные функции работы с ним на абстрактном уровне. Реализовать процедуры необходимые для вставки, удаления элемента в указанный вид АТД, процедуру печати содержимого АТД, а также дополнительно реализовать процедуру указанную в варианте, на конкретном языке программирования.
Для варианта №10: Однонаправленный циклический список символов. Реализовать процедуру подсчета суммы элементов.
Решение:
Теоретическое введение
Циклически связанный список (сокращенно - циклический список) обладает той особенностью, что связь его последнего узла не равна Л, а идет назад к первому узлу списка. В этом случае можно получить доступ к любому элементу, находящемуся в списке, отправляясь от любой заданной точки; одновременно мы достигаем также полной симметрии, и теперь нам уже не приходится различать в списке "последний" или "первый" узел. Типичная ситуация выглядит следующим образом:
Предположим, в узлах имеется два поля: INFO и LINK. Переменная связи PTR указывает на самый правый узел списка, a LINK (PTR) является адресом самого левого узла.
Рис. 1
Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент.
Листинг программыlist;CRT;pt = ^elem;= record: byte;: pt;;getprelastel (list:pt):pt;nextel:pt;(listNIL) then
nextel:=list^.next;(nextel^.next=NIL); (* Пока следующий за данным элемент списка не будет последним *):=list; (* Вернуть найденный элемент *)(* Иначе, если список пуст *):=NIL; (* Вернуть указатель на пустой список *)
end;getlastel (list:pt):pt;(listNIL) do (*Пока текущий элемент списка не последний*)
list:=list^.next; (*Перейти к следующему элементу *):=list; (* Вернуть найденный элемент *)(* Иначе *):=NIL; (* Вернуть указатель на пустой список *)
end;searchel (list:pt;info:byte):pt;(listinfo)) do (* Пока текущий элемент не последний и не искомый *):=list^.next; (* Переходить к следующему элементу списка *)
if (list^.info<>info) then (* если искомый элемент не найден *):=NIL (*вернуть указатель на пустой список *)(* Иначе *):=list; (*Вернуть указатель на этот элемент*)(* Иначе *):=NIL; (* Вернуть указатель на пустой список *)
end;;searchpreel (list:pt;info:byte):pt;nextel:pt;(listNIL) then:=list^.next;((nextel^.next=NIL) or (nextel^.info=info)); (* пока следующий за текущим элемент - не последний или искомый*)
if (nextel^.info<>info) or (nextel=list) then (* Если нужный нам элемент не найден или в списке 1 элемент *):=NIL (* Вернуть указатель на пустой список *)(* Иначе *):=list; (* Вернуть указатель на найденный элемент *)(* Иначе, если список пуст *):=NIL; (* Вернуть указатель на пустой список *)
end;;getelem(elname:string):byte;ret:byte;('Введите ',elname,': ');(ret);:=ret;;addtobegin (var list:pt;info:byte);newelem:pt;(newelem); (* создать в памяти новый элемент *)^.info:=info;^.next:=list; (* Присоединить к этому элементу спиоск *)
list:=newelem; (* Вернуть его, как начало нового списка *)
end;addafter (listel:pt;info:byte);newelem:pt;(listel<>NIL) then (* Если список не пуст *)
begin(newelem); (* Создать в памяти новый элемент *)^.info:=info;^.next:=listel^.next; (*Вставить элемент между заданным элементом и следующим *)
listel^.next:=newelem;;;addtoend (var list:pt;info:byte);(list=NIL) then(*Если список пуст*)
addtobegin(list,info)(*Добавить элемент в начало, создав новый список *)(*Иначе*)(getlastel(list),info); (*Добавить элемент после последнего *)
end;addbefore (listel:pt;info:byte);newelem:pt;(listel<>NIL) then (* Если список не пуст *)
begin(newelem); (* Создать в памяти новый элемент *)^.info:=listel^.info; (*Скопировать в него заданный элемент списка*)^.info:=info; (*Записать в заданный элемент списка после добавленного*)^.next:=listel^.next; (*Вставить заданный элемент списка после добавленного*)
listel^.next:=newelem;;;delfirstel(var list:pt);temp:pt;(list<>NIL) then (*Если список не пуст*)
begin:=list; (*Сохранит в памяти адрес первого элемента*):=list^.next; (*Отрезать от списка первый элемент*)(temp); (*Убрать первый элемент из памяти*)
end;;dellastel(var list:pt);temp:pt;(list<>NIL) then (* Если список не пуст, то *)
if (list^.next=NIL) then (* Если в списке один элемент *)
delfirstel(list) (* Удалить его *)(* иначе *)
temp:=getprelastel(list); (* Найти предпоследний элемент списка*)(temp^.next); (* Удалить следующий за ним *)
temp^.next:=NIL;;;delel(var list:pt;el:pt);temp:pt;((listNIL)) then (* Если дан элемент для удаления и список не пуст *)
begin(el^.next=NIL) then (* Если элемент, который нужно удалить - последний в списке *)(list^.next=NIL) then (* И если он еще и единственный *)(list) (* Уд?/p>