Сортировка методом сцепления очередей. Поиск методом составных атрибутов

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ  И  НАУКИ  РОССИЙСКОЙ  ФЕДЕРАЦИИ 
 

КУРСКИЙ  ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ 
 
 
 
 
 

Кафедра  “Комплексная  Защита  Информационных  Систем”

Специальность  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