Сортировки, Помогите решить задачу Опции

[*alt]

Задача.
Дан список морфем, в котором указана сама морфема и её тип (приставка, корень, суффикс или окончание). В списке могут встречаться повторяющиеся морфемы.
Написать программу, результатом работы которой должен быть список морфем, разбитый на группы для каждого типа. Внутри этих групп морфемы должны быть упорядочены в лексикографическом порядке. В группе корней одна и таже морфема может встречаться несколько раз, а в других группах морфемы должны быть уникальными.


С чего начать???
Что сделать???
Как сделать???
Помогите.....

[klem4]

{$B-}

uses crt;

{
  функция сравнения 2-х строк в лексикографическом порядке
}
function CmpStr(const a, b: string): integer;
var
  i, lenA, lenB: byte;

begin
  lenA := length(a);
  lenB := length(b);

  i := 1;
  while (i <= lenA) and (i <= lenB) and (a[i] = b[i]) do
    inc(i);

  if (i > lenA) and (i > lenB) then
    CmpStr := 0
  else if (i > lenA) or ((i <= lenB) and (a[i] < b[i])) then
    CmpStr := -1
  else if (i > lenB) or ((i <= lenA) and (a[i] > b[i])) then
    CmpStr := 1;
end;

type
  { возможные виды морфем: приставка, корень, суффикс, окончание }
  MorphemeType = (
    PREFIX,
    ROOT,
    SUFFIX,
    TERMINATION
  );

  MorphPtr = ^Morpheme;
  
  { структура, хранящая информацию о морфеме в списке морфем }
  Morpheme = record
    _type: MorphemeType; { вид морфемы }
    _value: string;              { значение морфемы }
    next: MorphPtr;            { указатель на следующую морфему в списке }
  end;

  { объект - список морфем, фактически обычный однонаправленный список, вот только элементы 
    добавляются не в начало или конец списка, а добавляются таким образом, чтобы после добавления
    очередного элемента в список, он (список) был упорядочен по полям _value в лексикографическом порядке
  }
  MorphemList = object
    first: MorphPtr; // указатель на первый элемент списка

    constructor Create; // создание пустого списка
    destructor Free; // уничтожение списка

    procedure Add(const mType: MorphemeType; const value: string); {
       добавление морфемы в список (mType - тип морфемы), value - значение
   }
    procedure Print; // печать списка морфем 
  end;

constructor MorphemList .Create;
begin
  first := nil;
end;

destructor MorphemList.Free;
var
  head: MorphPtr;

begin
  while first <> nil do begin
    head := first;
    first := first^.next;
    dispose(head);
  end;
end;

procedure MorphemList.Add(const mType: MorphemeType; const value: string);
var
  p, prev, next: MorphPtr;
  cmp: integer;
begin
  new(p);

  p^._type  := mType;
  p^._value := value;

  if first = nil then begin
    p^.next := nil;
    first := p;
  end else begin

    prev := nil;
    next := first;
    cmp := CmpStr(next^._value, value);

    while (next <> nil) and (cmp < 0) do begin
      prev := next;
      next := next^.next;

      if next <> nil then
        cmp := CmpStr(next^._value, value);
    end;

    if (cmp <> 0) or (mType = ROOT) then begin
      if (prev = nil) then begin
        p^.next := first;
        first := p;
      end else if (next = nil) then begin
        p^.next := nil;
        prev^.next := p
      end else begin
        p^.next := next;
        prev^.next := p;
     end;
    end else dispose(p);

  end;

end;

procedure MorphemList.Print;
var
  p: MorphPtr;
begin
  p := first;
  while p <> nil do begin
    writeln(p^._value);
    p := p^.next;
  end;
end;

{
  в результате работы процедуры, на вход которой поступает строка S вида
  <название_морфемы тип_морфемы>
  будет запись типа_морфемы в переменную mType и самой морфемы в переменную value
}
procedure GetMorphemInfo(const s: string;
                        var mType: MorphemeType;
                        var value: string);
var
  temp: string;
begin
  temp := copy(s, pos(' ', s) + 1, 255);

  if temp = 'ROOT' then
    mType := ROOT
  else if temp = 'PREFIX' then
    mType := PREFIX
  else if temp = 'SUFFIX' then
    mType := SUFFIX
  else mType := TERMINATION;

  value := copy(s, 1, pos(' ', s) - 1);
end;


const
  // символьное отображение названий видов морфем
  // szMotphTypes[PREFIX] == "PREFIX" и т.д.
  szMorphTypes: array [ MorphemeType ] of string =
    ('PREFIX',
     'ROOT',
     'SUFFIX',
     'TERMINATION'
    );

var
  // массив списков морфем, каждый элемент массива - список морфем определенного вида,
  // например mList[ROOT] - список корней
  mList: array [ MorphemeType ] of ^MorphemList;
  mt: MorphemeType; // дополнительная переменная
  morphFile: Text; // текстовый файл с морфемами (пример содержания файла я привел)
  temp, value: string; // дополнительный переменные

begin
  clrscr;

  assign( morphFile, 'c:\morphems.txt' ); 
   reset( morphFIle ); // открываем файл с морфемами для чтения

  for mt := PREFIX to TERMINATION do
    new( mList[ mt ], Create ); // создаем все списки морфем

  while not eof ( morphFile ) do begin // читаем строки из файла
    readln( morphFIle, temp );
    GetMorphemInfo(temp, mt, value); // выдергиваем из строки информацию о морфеме
    mList[mt]^.Add(mt, value); // заносим морфему в соответствующий список
  end;

  for mt := PREFIX to TERMINATION do begin
    writeln( szMorphTypes[ mt ], '''s:'); // подсказка показывает список какой из морфем сейчас будет выведен
    mList[ mt ]^.Print; // печать очередного списка списка
    writeln;
    dispose( mList[ mt ], Free ); // удаление списка
  end;

  close( morphFile ); // не забываем закрыть файл
end.

root1 ROOT
suffix1 SUFFIX
root2 ROOT
termination1 TERMINATION
root3 ROOT
prefix1 PREFIX
termination2 TERMINATION

Сообщение отредактировано: klem4 - 8.05.2008 22:24