Смекни!
smekni.com

Сортировка методом сцепления очередей. Поиск методом составных атрибутов (стр. 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);