DOS Pascal

← →
Nick Denry (2004-01-17 13:13) [0]

Народ, очень надо несколько ворпросов по теме "Структуры и алгоритмы обработки данных" утрясти.

1.Вопрос Unit STKOBJ;
Interface

type
TValue = array [1..3] of Real;
PValue = ^TValue;
PItem = ^TItem;
TItem = record
Value : PValue;
Next : PItem;
end;
PStack = ^TStack;
TStack = object
fHead : PItem;
procedure Push (V : TValue);
function Pop : PValue;
function Empty : boolean;
function TopValue : PValue;
function Size : WORD;
function Peep (K: WORD): PValue;
procedure Change(K:Word; V:PValue);
procedure Clear;
constructor Create;
destructor Destroy;
end;
PQueue = ^TQueue;
TQueue = Object(TStack)
fRear : PItem;
procedure Insert(V : TValue);
function Remove : PValue;
function PeepHead : PValue;
function PeepRear : PValue;
constructor create;
end;
PDEQ = ^TDEQ;
TDEQ = Object(TQueue)
procedure push (v : TValue);
function Delete : PValue;
function Pop : PValue;
end;
Implementation
procedure TStack.Push(v : TValue);
var NewItem : PItem;
begin
NewItem := New(PItem);
NewItem^.Value^ := v;
NewItem^.Next := fHead;
fHead := NewItem;
end;
function TStack.Pop : PValue;
var DisItem : PItem;
begin
if not (TStack.empty) then
begin
pop := fHead^.Value;
DisItem := fHead;
fHead := fHead^.Next;
Dispose(DisItem);
end
else WriteLN("Can""t pop value. Stack is empty");
end;
function TStack.Empty : boolean;
begin
empty := fHead = nil;
end;
function TStack.TopValue : PValue;
begin
TopValue := fHead^.Value;
end;
function TStack.Size : WORD;
begin
end;
function TStack.Peep (K: WORD): PValue;
begin
end;
procedure TStack.Change(K:Word; V:PValue);
begin
end;
procedure TStack.Clear;
begin
end;
constructor TStack.Create;
begin
{fHead := nil;}
end;
destructor TStack.Destroy;
begin
end;
{TQueue methods}
procedure TQueue.Insert (V : TValue);
var NewItem : PItem;
begin
NewItem := New(PItem);
NewItem^.Value^ := v;
NewItem^.Next := nil;
if fRear <> nil
then fREar^.Next := NewItem
else fHead:= NewItem;
fRear := NewItem;
end;
function TQueue.remove : PValue;
begin
Remove := Pop;
if fHead = nil then fRear := nil;
end;
function TQueue.PeepHead : PValue;
begin
end;
function TQueue.PeepRear : PValue;
begin
end;
constructor TQueue.Create;
begin
end;
{TDEQ methods}
Procedure TDEQ.Push (V : TValue);
begin
inherited Push(v);
if fRear = nil then fRear := fHead;
end;
function TDEQ.delete : PValue;
var DisItem, Item : PItem;
begin
Delete := fRear^.Value;
DisItem := fRear;
if fHead <> fRear then begin
Item := fHead;
while Item^.Next <> fRear do Item := Item^.Next;
fRear := Item;
fRear^.Next := nil;
end
else begin
fHead := nil;
fRear := nil;
end;
end;
function TDEQ.Pop : PValue;
begin
inherited Pop;{(v);}
end;
Begin
End.

Это частична реализация ДЕКА (Очередь с двумя концами). Если кто сталкивался, пришлите пример плиз...

2. Нужен пример (если есть у кого) метод пойска в массиве - "расстановка методом свертки" и при этом нужно пользоваться алгоритмом "внутреннее сцепление" для устранения кофликтов при расстановке. Никогда с этим не сталкивался и описания алгоритмов нет.

3. Сортировка в массиве - быстрая сортировка (тоже прример , если можно)

← →
Nick Denry (2004-01-17 14:20) [1]

Никто не сталкивался?

← →
Nick Denry (2004-01-17 14:42) [2]

Задания

1. Создать ДЕК, каждаый элемент которого представляет собой совокупность 3-х вещественных значений. Исключить из ДЕКа все элементы, у которых каждое из 3-х значений превышает заданное. Вывести длинну получившегося ДЕКа (???? вообще не представляю) и значение его первого и последнего элементов.

2. Составить программу формирования заданным методом таблицы поиска и последующего поиска в этой таблице элементов из входной последовательности. Программу необходимо реализовать с двумя вариантами исходных данных: - отладочный (10- элементов) демонстрирующий работу алгоритма поиска; рабочий - (50 элементов) в результате обработки которого выводятся значения параметров эффективности (число сравнения ключей), определенных для данного метода поиска. Исходные данные и результаты обработки разместить в текст. файлах.

Метод поиска - расстановка методом свертки...

Метод устранения конфликтов при расстановке - внутреннее сцепление.

3. Составить программу сртировки заданной последовательности .Программу необходимо реализовать с двумя вариантами исходных данных: - отладочный (10- элементов) демонстрирующий рез-ты всех проходов алгоритма сортировки; рабочий - (50 элементов) в результате обработки которого выводятся значения параметров эффективности (число сравнения ключей С и число перестановок эл-тов Р) и отсортированная последовательность, определенных для данного метода сртировки.

Метод сртировки - быстрая сортировка.

← →
DrPass (2004-01-17 16:22) [3]

Конечно, все программисты это проходили в институте. Ну и что? Лабы тебе делать, что ли?

← →
Nick Denry (2004-01-17 16:25) [4]

Поверь, другого я и не ожидал.

Я просил пример реализации определенных алгоритмов. Это конечно лабы, но они не мне....

← →
Nick Denry (2004-01-17 16:47) [5]

2>DrPass

И еще. Где ты увидел строку "ПОМОГИТЕ МНЕ СДЕЛАТЬ ЛАБЫ"??

← →
Nelud (2004-01-17 18:00) [6]

Const
MaxM = 3; {Количество "маленьких массивов" - 1}
SizeOfArray = 10000; {Размер "маленького массива"}

Type
PArray = ^TArray; {Указатель на "маленький" массив}
TArray = Array [0..9999] Of LongInt; {Маленький массив}

TLargeArray = Array [0..MaxM] Of PArray; {Большой массив}

Var
A: TLargeArray; {Создаем переменную типа большой массив}

Procedure Put(Index, What: LongInt);
Var
NumOfArray, {Номер маленького массива}
IndexInArray: Word; {Индекс в маленьком массиве}
Begin
NumOfArray := Index Div SizeOfArray; {Вычисляем номер маленького массива}
IndexInArray := Index Mod SizeOfArray; {и номер элемента в нем}
A[NumOfArray]^[IndexInArray] := What; {затем устанавливаем нужное значение}
End;

Function Get(Index: LongInt): LongInt;
Var
NumOfArray, {Номер маленького массива}
IndexInArray: Word; {Индекс в маленьком массиве}
Begin
NumOfArray := Index Div SizeOfArray; {Вычисляем номер маленького массива}
IndexInArray := Index Mod SizeOfArray; {и номер элемента в нем}
Get := A[NumOfArray]^[IndexInArray]; {затем возвращаем нужное значение}
End;

Procedure QuickSort(L, R: Word);
{Сортировка методом Хоара или "быстрая" сортировка,
адаптированная к большому массиву}
Var
X, Y, I, J: LongInt;
Begin
I := L;
J := R;
X := Get((L + R) Div 2);
Repeat
While Get(I) < X Do Inc(I);
While Get(J) > X Do Dec(J);
If I <= J Then
Begin
Y := Get(I);
Put(I, Get(J));
Put(J, Y);
Inc(I);
Dec(J);
End;
Until I > J;
If L < J Then QuickSort(L, J);
If R > I Then QuickSort(I, R);
End;

Var
Cur, Max, T, N, I: LongInt;

Begin
Assign(Input, "Input.Txt");
ReSet(Input);
Assign(Output, "Output.Txt");
ReWrite(Output);
Writeln;
For I := 0 To MaxM Do A[I] := New(PArray); {Деинициализация}
Readln(N); {Чтение данных из файла}
For I := 1 To N Do
Begin
ReadLn(T);
Put(I, T);
End;
QuickSort(1, N); {Сортировка методом Хоара}
Max := 0; {Находим нужное нам число}
Cur := 1;
For I := 0 To N Do
If Get(I) <> Get(I+1) Then
Begin
If Cur > Max Then
Begin
Max := Cur;
T := Get(I);
End;
Cur := 1;
End
Else Inc(Cur);
Writeln("Число "", T, "" встречается ", Max, " раз(а)"); {Выводим ответ}
For I := 0 To MaxM Do Dispose(A[I]); {Деинициализация}
Close(Output);
End.

решение одной задачи. использует QS.

← →
Nick Denry (2004-01-17 20:16) [7]

DOS Pascal Найти похожие ветки