Сортировка методом сцепления очередей. Поиск методом составных атрибутов (стр. 1 из 2)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра “Комплексная Защита Информационных Систем”
Специальность 090104 “Комплексная Защита Объектов Информатизации”
КУРСОВАЯ РАБОТА
по Методам Программирования и Прикладным Алгоритмам
(дисциплина)
"Сортировка методом сцепления очередей. Поиск методом составных атрибутов"
(тема КР)
Допустить к защите
И.О. Зав. кафедрой д.ф-м.н. Добрица В.П.
Выполнил ______________________
(Ф.И.О. студента)
Студент __________________________
(курс, группа)
Работа защищена _________________
(дата)
Оценка ____________________________
Руководитель к.т.н. С.С.Шевелев
(подпись, Ф.И.О. преподавателя) Курск 2009 г.
Содержание
1 Введение ………………………………….…………………………………………..3
2 Теоретическая часть………………………………….…………………………….5
3. Практическая часть………………………………….………………………..…...7
3.1. Листинг………………………………….……………………………..…...7
3.2. Блок-схема………………………………….……………………………..10
3.3. Описание переменных………………………………….………………..17
3.4. Внешний вид формы…………………………………………………….17
3.5. Результаты выполнения программы…………………………………18
4. Заключение……………………………………..………………………………….21
5. Список используемой литературы……………………………………………..22
1. Введение
Наиболее частый вопрос, который возникает в программировании: переразмещение элементов в возрастающем или убывающем порядке. Представьте, насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит скорость и простота алгоритмов, предназначенных для их обработки.
Хотя в словарях слово "сортировка" (sorting) определяется как "распределение, отбор по сортам; деление на категории, сорта, разряды", программисты традиционно используют это слово в гораздо более узком смысле, обозначая им сортировку предметов в возрастающем или убывающем порядке. Этот процесс, пожалуй, следовало бы назвать не сортировкой, а упорядочением (ordering), но использование этого слова привело бы к путанице из-за перегруженности значениями слова "порядок". В математической терминологии это слово также изобилует значениями (порядок группы, порядок перестановки, порядок точки ветвления, отношение порядка и т. п.). Итак, слово "порядок" приводит к хаосу.
В качестве обозначения для процесса упорядочения предлагалось также слово "ранжирование", но оно во многих случаях, по-видимому, не вполне отражает суть дела, особенно если присутствуют равные элементы, и, кроме того, иногда не согласуется с другими терминами. Конечно, слово "сортировка" и само имеет довольно много значений, но оно прочно вошло в программистский жаргон. Поэтому мы без дальнейших извинений будем использовать слово "сортировка" в узком смысле "сортировка по порядку".
Вот некоторые из наиболее важных применений сортировки:
Решение задачи "группировки", когда нужно собрать вместе все элементы с одинаковым значением некоторого признака. Допустим, имеется 10000 элементов, расположенных в случайном порядке, причем значения многих из них равны; и предположим, нам нужно переупорядочить файл так, чтобы элементы с равными значениями занимали соседние позиции в файле. Это, по существу, задача "сортировки" в широком смысле слова, и она легко может быть решена путем сортировки файла в узком смысле слова, а именно расположением элементов в неубывающем порядке v1 v2 ... v10000. Эффективностью, которая может быть достигнута в этой процедуре, и объясняется изменение первоначального смысла слова "сортировка".
Если два или более файла отсортировать в одном и том же порядке, то можно отыскать в них все общие элементы за один последовательный просмотр всех файлов, без возвратов. Оказывается, что, как правило, гораздо экономнее просматривать список последовательно, а не перескакивая с места на место случайным образом, если только список не настолько мал, что он целиком помещается в оперативной памяти. Сортировка позволяет использовать последовательный доступ к большим файлам в качестве приемлемой замены прямой адресации.
Сортировка помогает и при поиске, с ее помощью можно сделать выдачи ЭВМ более удобными для человеческого восприятия. В самом деле, листинг (напечатанный машиной документ), отсортированный в алфавитном порядке, зачастую выглядит весьма внушительно, даже если соответствующие числовые данные были рассчитаны неверно.
Хотя сортировка традиционно и большей частью использовалась для обработки коммерческих данных, на самом деле она является инструментом, полезным в самых разных ситуациях, и поэтому о нем не следует забывать.
2. Теоретическая часть
Сортировка
Поиск
3. Практическая часть
3.1. Листинг
unit Unit1;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;
type
FindRec = record
count:Integer;
dats:array of integer;
end;
put = record
ind:array of integer;
col_vo:Integer; end;
TForm1 = class(TForm)
StringGrid1: TStringGrid;
StringGrid2: TStringGrid;
StringGrid3: TStringGrid;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Edit4: TEdit;
Edit5: TEdit;
Edit6: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
Label8: TLabel;
Label9: TLabel;
Label10: TLabel;
Edit7: TEdit;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
a,b:array of integer;
implementation
uses Math, DateUtils;
{$R *.dfm}
function obmen(i:integer;j:integer):Boolean;
var
p:integer;
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
Result:=true;
end;
function Zameni(x:integer;y:integer):Integer;
var
i,j:Integer;
pr:boolean;
begin
i:=x;
j:=y;
pr:=false;
while i<j do begin
if a[i]>a[j] then
begin
if pr= false then
i:=i+1
else
j:=j-1;
end;
end;
end;
procedure ScepOch(l, t: integer);
var i: integer;
begin
if l<t then begin
i:=Zameni(l, t);
ScepOch(l,i-1);
ScepOch(i+1,t);
end;
end;
function SostAtr(obr:Integer;kol:Integer):FindRec;
var
sr,j:integer;
n,v:Integer;
founded:Boolean;
rez:FindRec;
tree:put;
begin
n:=0;
v:=kol-1;
founded:=false;
rez.count:=0;
SetLength(rez.dats,0);
tree.col_vo:=0;
while (n<=v) and (founded=false) do
begin
sr:=(n+v) div 2;
SetLength(tree.ind,tree.col_vo+1);
tree.ind[tree.col_vo]:=sr;
inc(tree.col_vo);
if a[sr]=obr then
begin
for j:=n to v do begin
if a[j]=obr then begin
inc(rez.count);
SetLength(rez.dats,rez.count);
rez.dats[rez.count-1]:=j;
end;
end;
end;
Result:=rez;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i,k:Integer;
t1,t2:integer;
r:TTimeStamp;
begin
t1:=MilliSecondOfTheMinute(time);
k:=0;
while k<=100 do
begin
a:=b;
ScepOch(0,StrToInt(Edit2.Text)-1);
k:=k+1;
end;
t2:=MilliSecondOfTheMinute(Time);
for i:=0 to StrToInt(Edit2.Text)-1 do
begin
StringGrid2.Cells[i,0]:=IntToStr(a[i]);
end;
Edit3.Text:=FloatToStr(abs(t1-t2)/1000);
end;
procedure TForm1.Button2Click(Sender: TObject);
var i:Integer;
begin
SetLength(b,StrToInt(Edit2.Text));
for i:=0 to StrToInt(Edit2.Text)-1 do begin
b[i]:=Random(StrToInt(Edit1.Text));
StringGrid1.Cells[i,0]:=IntToStr(b[i]);
end;
StringGrid1.ColCount:=StrToInt(Edit2.Text);
StringGrid2.ColCount:=StrToInt(Edit2.Text);
Button1Click(Sender);
StringGrid3.ColCount:=StrToInt(Edit2.Text);
for i:=0 to StrToInt(Edit2.Text)-1 do
StringGrid3.Cells[i,0]:=StringGrid2.Cells[StrToInt(Edit2.Text)-1-i,0];
end;
procedure TForm1.Button3Click(Sender: TObject);
var obr,i,k:integer;
f:FindRec;
t1,t2:Integer;
begin
obr:=StrToInt(Edit4.Text);
t1:=MilliSecondOfTheMinute(time); k:=0;
while k<=10000 do begin
f:=SostAtr(obr,StrToInt(Edit2.Text));
inc(k); end;
t2:=MilliSecondOfTheMinute(time);
if f.count<>0 then begin for i:=0 to f.count-1 do begin
Edit5.Text:=Edit5.Text+IntToStr(f.dats[i]+1)+';';
Edit7.Text:=Edit7.Text+IntToStr(StrToInt(Edit2.Text) - f.dats[i])+';';
end; end
else begin
Edit5.Text:='нет такого элемента';
Edit7.Text:='нет такого элемента'; end;
Edit6.Text:=FloatToStr(abs(t1-t2)/10000);
end; end.
3.2. Блок-схема:
procedure ScepOch (l, t: integer);
function Zameni(x:integer;y:integer):Integer;
function Obmen(i:integer;j:integer):Boolean;
procedure TForm1.Button1Click(Sender: TObject);
procedure TForm1.Button2Click(Sender: TObject);