Однонаправленный список, Memo

@knopick · Регистрация: 01.05.2011

Author24 — интернет-сервис помощи студентам

Можно ли сделать однонаправленный список из данных (чисел), которые вводятся в поле Memo? Каждое новое число в Memo начинается с новой строки)

@mss · 22.11.2012, 22:39

Можно.

@knopick · 22.11.2012, 22:44 **[ТС]**

как

хотя бы на словах?

@mss · 22.11.2012, 22:46

точно так же как из данных (чисел), которые вводятся в поле ListBox

@knopick · 23.11.2012, 00:11 **[ТС]**

помогите, пожалуйста, изменить тип , который использует процедура добавления элемента

Delphi

type
  TData = Integer;
  TPElem = ^TElem;
  TElem = record
    Data : TData;
    PNext : TPElem;
  end;
 
 
procedure AddL(var aPList, aPElem : TPElem);
begin
  if aPElem = nil then Exit;
 
  if aPList = nil then
    aPElem^.PNext := aPElem
  else begin
    aPElem^.PNext := aPList^.PNext;
    aPList^.PNext := aPElem;
  end;
   aPList := aPElem;
end;

под тип, который необходим для другой важной процедуры. Числа типа не Integer, а Byte.

Delphi

type
  PDElem = ^TDElem;
  TDElem = record
    Key: LongWord;
    Item: Pointer;
    Next: PDElem;
  end;

@Mawrat · 23.11.2012, 02:18

Односвязанный список. Основные данные типа Integer. Заполнение из Memo.

Delphi

type
  //Тип основных данных списка.
  TData = Integer;
  //Тип указателя на элемент списка.
  TPElem = ^TElem;
  //Тип элемента списка.
  TElem = record
    Data : TData;
    PNext : TPElem;
  end;
  //Тип, описывающий однонаправленный список.
  TList = record
    PFirst : TPElem; //Указатель на первый элемент списка.
    PLast : TPElem; //Указатель на последний элемент списка.
  end;
 
//Инициализация списка. Внимание! Эту процедуру можно выполнять только
//в отношении пустого списка. Иначе - будут утечки памяти.
procedure Init(var aList : TList);
begin
  aList.PFirst := nil;
  aList.PLast := nil;
end;
 
//Добавление элемента в конец однонаправленного списка.
procedure AddL(var aList : TList; const aData : TData);
var
  PElem : TPElem;
begin
  New(PElem);
  PElem^.Data := aData;
  PElem^.PNext := nil;
  if aList.PFirst = nil then
    aList.PFirst := PElem
  else
    aList.PLast^.PNext := PElem;
  aList.PLast := PElem;
end;
 
//Удаление однонаправленного списка из памяти и инициализация.
procedure ListFree(var aList : TList);
var
  PNext, PDel : TPElem;
begin
  if aList.PFirst = nil then Exit;
 
  PNext := aList.PFirst;
  while PNext <> nil do begin
    PDel := PNext;
    PNext := PNext^.PNext;
    Dispose(PDel);
  end;
  Init(aList);
end;
 
//Распечатка однонаправленного списка.
function ListToStr(const aList : TList) : String;
var
  PElem : TPElem;
  i : Integer;
begin
  Result := '';
  if aList.PFirst = nil then begin
    Result := 'Список пуст.';
    Exit;
  end;
 
  PElem := aList.PFirst;
  i := 0;
  while PElem <> nil do begin
    Inc(i);
    if i > 1 then Result := Result + ', ';
    Result := Result + IntToStr(PElem^.Data);
    PElem := PElem^.PNext;
  end;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  List : TList;
  PElem : TPElem;
  i : Integer;
  S : String;
  BRes : Boolean;
begin
  //Начальная инициализация списка.
  Init(List);
 
  //Читаем числа из Мемо и добавляем их в список.
  //Предполагается, что каждое число в Мемо расположено на отдельной строке.
  for i := 0 to Memo1.Lines.Count - 1 do begin
    S := Memo1.Lines[i];
    if S <> '' then AddL(List, StrToIntDef(S, 0));
  end;
 
  Memo2.Lines.Add('--------------------------------------------------');
  Memo2.Lines.Add('Составлен список:');
  Memo2.Lines.Add(ListToStr(List));
 
  //Работа со списком.
  ...
  ...
  ...
 
  //Удаление списка из памяти.
  ListFree(List);
end;

Чтобы изменить тип основных данных на Byte достаточно изменить определение типа TData:

Delphi

1
2
3

type
  //Тип основных данных списка.
  TData = Byte;

@knopick · 23.11.2012, 09:31 **[ТС]**

Выдает несоответствие типов TList и PDElem.

Delphi

type
  PDElem = ^TDElem;
  TDElem = record
    Key: LongWord;
    Item: Pointer;
    Next: PDElem;
  end;

а этот тип необходим для

Delphi

type
  TBucket = array [byte] of TDElem;
  TBucketTail = array [byte] of PDElem;
 
var
  Bucket: TBucket;
  BucketTail: TBucketTail;
 
procedure RadixSort(DList: PDElem);
var
  i, j: integer;
  KeyIndex: byte;
  ListElem, lastElem: PDElem;
  firstElem: TDElem;
begin
  if not assigned(DList) then exit;
  //íà÷àëüíûå óñòàíîâêè
  //ýëåìåíòû Bucket èìåþò òèï çàïèñè, äëÿ îäíîîáðàçèÿ â öèêëå
  for i := 0 to sizeOf(LongWord) - 1 do
  begin
    for j := 0 to High(byte) do
      BucketTail[j] := @Bucket[j];
    //Èäåì ïî ñïèñêó
    ListElem := DList;
    repeat
      //i óêàçûâàåò íîìåð îáðàáàòûâàåìîãî áàéòà, ñäâèãàåì âïðàâî íà i*8
      //è áåðåì ìëàäøèé áàéò, îí êàê ðàç è íóæåí
      KeyIndex := byte(ListElem^.Key shr (i shl 3));
      //Âñòàâëÿòü íàäî â êîíåö ñïèñêà
      BucketTail[KeyIndex]^.Next := ListElem;
      //è íå çàáûòü ïåðåìåñòèòü õâîñò
      BucketTail[KeyIndex] := ListElem;
      //Òåïåðü ìîæíî âçÿòü ñëåäóþùèé ýëåìåíò
      ListElem := ListElem^.Next;
    until not assigned(ListElem);
 
    //Âñå, òåïåðü äëÿ ñëåäóþùåé èòåðàöèè íàäî âíîâü ñðàñòèòü ñïèñîê
    firstElem.Next := nil;
    lastElem := @firstElem;
    for j := 0 to High(byte) do
      //Åñëè â ÿ÷åéêå åñòü ñïèñîê
      if BucketTail[j] <> @Bucket[j] then  //äîáàâëÿåì åãî â õâîñò
      begin
        lastElem^.Next := Bucket[j].Next;
        lastElem := BucketTail[j];
      end;
      //îñòàëîñü ïðèñâîèòü ñïèñîê è îáíóëèòü åãî õâîñò
      DList := firstElem.Next;
      lastElem^.Next := nil;
  end;
end;

@Mawrat · 23.11.2012, 10:00

Тип TList описывает сам список - это запись, содержащая указатели на первый и на последний элементы списка.
А типы TElem и TPElem можно привести в соответствие с типами TDElem и PDElem. И понадобится ещё немного подправить процедуры для работы со списком - в соответствие со структурой TDElem.

Добавлено через 49 секунд
Я могу подправить код со списком таким образом, чтобы TElem и TPElem полностью соответствовали типам TDElem и PDElem.

Добавлено через 19 минут
Процедуры для работы со списком будут выглядеть так:

Delphi

type
  //Тип основных данных списка.
  TData = record
    Key : Longword;
    Item : Pointer;
  end;
  //Тип указателя на элемент списка.
  TPElem = ^TElem;
  //Тип элемента списка.
  TElem = record
    Data : TData;
    PNext : TPElem;
  end;
  //Тип, описывающий однонаправленный список.
  TList = record
    PFirst : TPElem; //Указатель на первый элемент списка.
    PLast : TPElem; //Указатель на последний элемент списка.
  end;
 
//Инициализация списка. Внимание! Эту процедуру можно выполнять только
//в отношении пустого списка. Иначе - будут утечки памяти.
procedure Init(var aList : TList);
begin
  aList.PFirst := nil;
  aList.PLast := nil;
end;
 
//Добавление элемента в конец однонаправленного списка.
procedure AddL(var aList : TList; const aData : TData);
var
  PElem : TPElem;
begin
  New(PElem);
  PElem^.Data := aData;
  PElem^.PNext := nil;
  if aList.PFirst = nil then
    aList.PFirst := PElem
  else
    aList.PLast^.PNext := PElem;
  aList.PLast := PElem;
end;
 
//Удаление элемента однонаправленного списка по указателю
//на предыдущий элемент. Если указатель на предыдущий элемент равен NIL,
//то удаляется первый элемент списка.
procedure Del(var aList : TList; var aPPrev : TPElem);
var
  PElem : TPElem;
begin
  if aList.PFirst = nil then Exit;
 
  if aPPrev = nil then begin
    PElem := aList.PFirst;
    aList.PFirst := PElem^.PNext;
  end else begin
    PElem := aPPrev^.PNext;
    if PElem <> nil then aPPrev^.PNext := PElem^.PNext;
  end;
  if aList.PLast = PElem then aList.PLast := aPPrev;
  if PElem <> nil then begin
 
    //--------------------------------------------------
    //Внимание! Если требуется освобождать память, занаятую объектами,
    //на которые ссылается поле TData.Item, то здесь надо написать код
    //для освобождения этой памяти. Для этого требуется знать размер
    //объекта, на который ссылается TData.Item.
    //...
    //...
    //...
    //--------------------------------------------------
 
    //Освобождение памяти, занятой элементом.
    Dispose(PElem);
  end;
end;
 
//Удаление однонаправленного списка из памяти и инициализация.
procedure ListFree(var aList : TList);
var
  PNext, PDel : TPElem;
begin
  if aList.PFirst = nil then Exit;
 
  PNext := aList.PFirst;
  while PNext <> nil do begin
    PDel := PNext;
    PNext := PNext^.PNext;
 
    //--------------------------------------------------
    //Внимание! Если требуется освобождать память, занаятую объектами,
    //на которые ссылается поле TData.Item, то здесь надо написать код
    //для освобождения этой памяти. Для этого требуется знать размер
    //объекта, на который ссылается TData.Item.
    //...
    //...
    //...
    //--------------------------------------------------
 
    //Освобождение памяти, занятой элементом.
    Dispose(PDel);
  end;
  Init(aList);
end;
 
//Распечатка однонаправленного списка.
function ListToStr(const aList : TList) : String;
var
  PElem : TPElem;
  i : Integer;
begin
  Result := '';
  if aList.PFirst = nil then begin
    Result := 'Список пуст.';
    Exit;
  end;
 
  PElem := aList.PFirst;
  i := 0;
  while PElem <> nil do begin
    Inc(i);
    if i > 1 then Result := Result + ', ';
    Result := Result + '(Key=' + IntToStr(PElem^.Data.Key)
      + '; Item=' + IntToStr(Integer(PElem^.Data.Item)) + ')';
    PElem := PElem^.PNext;
  end;
end;

Здесь основные данные оформлены в виде записи (Record).
Дальше уже надо этот код надо приспособить в соответствие со смыслом задачи.

@knopick · 24.11.2012, 13:26 **[ТС]**

что-то не получается разобраться (или чуть не ту информацию смотрю по спискам). как под процедуру AddL изменить:

Delphi

for i := 0 to Memo1.Lines.Count - 1 do
  begin
    S := Memo1.Lines[i];
    if S <> '' then AddL(List, StrToIntDef(S, 0));
end;

Добавлено через 13 часов 34 минуты
что-то не получается разобраться (или чуть не ту информацию смотрю по спискам). как под процедуру AddL изменить:

Delphi

for i := 0 to Memo1.Lines.Count - 1 do
  begin
    S := Memo1.Lines[i];
    if S <> '' then AddL(List, StrToIntDef(S, 0));
end;

@Mawrat · 24.11.2012, 14:57

Если тип TData определён так:

Delphi

1	TData = Integer; //Или так: TData = Longword;

То загрузка из Мемо будет такой:

Delphi

for i := 0 to Memo1.Lines.Count - 1 do begin
  S := Memo1.Lines[i];
  if S <> '' then AddL(List, StrToIntDef(S, 0));
end;

А если TData определён так:

Delphi

TData = record
  Key : Longword;
  Item : Pointer;
end;

то здесь надо для каждого элемента иметь значение Key и Item. Возможно, сначала из Мемо должны грузиться ключи (Key). А потом, по ходу алгоритма, уже определяются и устанавливаются значения Item (адреса)? Хотя может и не так - это только предположение. Я же не знаю, как организована программа, где этот список используется.
В общем, для TData с полями Key и Item код загрузки из Мемо будет таким:

Delphi

type
  //Тип основных данных списка.
  TData = record
    Key : Longword;
    Item : Pointer;
  end;
  //Тип указателя на элемент списка.
  TPElem = ^TElem;
  //Тип элемента списка.
  TElem = record
    Data : TData;
    PNext : TPElem;
  end;
  //Тип, описывающий однонаправленный список.
  TList = record
    PFirst : TPElem; //Указатель на первый элемент списка.
    PLast : TPElem; //Указатель на последний элемент списка.
  end;
 
...
 
var
  List : TList;
 
procedure TForm1.Button1Click(Sender: TObject);
const
  //Запись с обнулёнными полями.
  Data0 : TData = (Key : 0; Item : nil);
var
  Data : TData;
  S : String;
  i : Integer;
  Sl : TStringList;
begin
  ListFree(List);
 
  Sl := TStringList.Create;
  for i := 0 to Memo1.Lines.Count - 1 do begin
    S := Memo1.Lines[i];
    if S <> '' then begin
      //Разделяем строку на подстроки по положению разделителей [',', ';'].
      ExtractStrings([',', ';'], [' ', #9, #10, #13], PChar(S), Sl);
      Sl.Clear; //Очистка списка.
      Data := Data0; //Обнуляем поля записи.
      if Sl.Count > 0 then begin
        Data.Key := StrToIntDef(Sl[0], 0);
        if Sl.Count > 1 then
          Data.Item := Pointer( StrToIntDef(Sl[1], 0) );
        AddL(List, Data);
      end;
    end;
  end;
  FreeAndNil(Sl);
 
...
end;

Чтобы конкретнее сказать, мне нужно больше знать о задаче.

@knopick · 24.11.2012, 22:32 **[ТС]**

Сама задача:
Структура данных содержит записи фиксированного размера (200 байт). Одно из полей записи содержит ключ (ключи могут повторяться). Количество записей допускает их размещение в оперативной памяти.
Нужно разработать программы, осуществляющие сортировку предложенными методами. Оценить сложность алгоритмов по количеству операций сравнения и перестановки записей, проверить полученные результаты экспериментально.

Обсуждение в данной теме: делаю пирамидальную сортировку. числа заносятся в поле Memo (с помощью Random и с помощью с клавиатуры). но как я поняла для пирамидальной сортировки нужна работать со списком, который как раз считывает данные из поля Memo.

Добавлено через 22 минуты
извиняюсь, не пирамидальную сортировку делаю, а сортировку стопками

@knopick · 25.11.2012, 18:55 **[ТС]**

пишет что список пуст

@knopick · 12.12.2012, 23:58 **[ТС]**

Тема закрыта

@knopick 6 / 3 / 2 Регистрация: 01.05.2011 Сообщений: 73
		1
	Однонаправленный список, Memo 22.11.2012, 22:31. Показов 2199. Ответов 12 Метки нет (Все метки) Можно ли сделать однонаправленный список из данных (чисел), которые вводятся в поле Memo? Каждое новое число в Memo начинается с новой строки) 0

@mss 3530 / 2270 / 279 Регистрация: 24.12.2010 Сообщений: 13,723
	22.11.2012, 22:39	2
	Можно. 0

@knopick 6 / 3 / 2 Регистрация: 01.05.2011 Сообщений: 73
	22.11.2012, 22:44 [ТС]	3
	как хотя бы на словах? 0

@mss 3530 / 2270 / 279 Регистрация: 24.12.2010 Сообщений: 13,723
	22.11.2012, 22:46	4
	точно так же как из данных (чисел), которые вводятся в поле ListBox 0

@knopick 6 / 3 / 2 Регистрация: 01.05.2011 Сообщений: 73
	24.11.2012, 22:32 [ТС]	11
	Сама задача: Структура данных содержит записи фиксированного размера (200 байт). Одно из полей записи содержит ключ (ключи могут повторяться). Количество записей допускает их размещение в оперативной памяти. Нужно разработать программы, осуществляющие сортировку предложенными методами. Оценить сложность алгоритмов по количеству операций сравнения и перестановки записей, проверить полученные результаты экспериментально. Обсуждение в данной теме: делаю пирамидальную сортировку. числа заносятся в поле Memo (с помощью Random и с помощью с клавиатуры). но как я поняла для пирамидальной сортировки нужна работать со списком, который как раз считывает данные из поля Memo. Добавлено через 22 минуты извиняюсь, не пирамидальную сортировку делаю, а сортировку стопками 0

@knopick 6 / 3 / 2 Регистрация: 01.05.2011 Сообщений: 73
	12.12.2012, 23:58 [ТС]	13
	Тема закрыта 0