Линейные списки \ Реализация некоторых функции

@hppnd · Регистрация: 27.05.2012

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

Прошу помощи :
Имеется линейный список с последовательным хранением , элементами которого являются окружности.
Для этого списка реализовать функции :
Добавление нового элемента в конец списка
function add_item("новый элемент","список элементов","текущая длина списка"):integer;
Функция выдает в качестве результата новую длину списка или -1 , если операция не удалась ;

Мои безуспешные попытки :

Delphi

  type tpoint=record
       x,y:Double;
       end;
 
  type circle=record
       nach:tpoint;
       Rad:Double;
       end;
 
  type tintitem=record
       val:integer;
       next:^tintitem;
       end;
  pintitem:^tintitem;
 
 
  function add_item(var p:pintitem; item:Integer):Integer;
           var c,r:pintitem;
      begin
          New(c)
          if r=nil then begin result:=-1;
                              exit;
                              end;
          r^.val:=item;
          r^.next:=nil;
      end;

Буду очень признателен.

@Alex_pac · 27.05.2012, 18:33

deleted

@vilag · 28.05.2012, 02:57

Во-первых, type пишется один раз.
Во-вторых, типы создаются с "=" (pIntItem = ^TIntItem).
В-третьих, если список должен хранить окружности, почему вообще value: Integer?
В-четвёртых, r.val , а не r^.val
В-пятых, процедура принимает p, создаёт c, а значение пытается присвоить r. Какой в этом всём смысл?
Ну и наконец, как может не удасться операция добавления элемента в список? Если память, что-ли, закончится?

Delphi

type 
  TCircle = record
    x, y: double;
    r: double;
  end;
 
  pCircleNode = ^TCircleNode;
  TCircleNode = record
    value: TCircle;
    next: pCircleNode;
  end; 
 
function add_item(listStart: pCircleNode; item: TCircle):Integer;
var 
  listEnd: pCircleNode;
  listLength: integer;
begin
  if listStart = nil then
  begin
    new(listStart);
    listStart.next := nil;
    listStart.value := item;
    result := 1;
    exit;
  end;
  
  listLength := 1; 
  listEnd := listStart;
  while (listEnd.next <> nil) do
  begin
    listEnd :=  listEnd.next;
    inc(listLength);
  end;
  new(listEnd.next);
  listEnd := listEnd.next;
  listEnd.next := nil;
  listEnd.value := item;
  result := listLength + 1;
end;

Как-то так. А лучше глобально хранить переменные как для начала списка, так сразу и для конца. Чтобы каждый раз не перебирать весь список.

@hppnd · 28.05.2012, 11:22 **[ТС]**

vilag, огромное Вам спасибо , но появился еще один вопрос :
не могли бы Вы объяснить структуру заполнения списка ?

@vilag · 28.05.2012, 16:32

Структура следующая:
имеем переменную listStart с началом списка:
listStart -> next -> next -> next ... -> next -> nil
А добавлять надо в конец. Который мы и ищем с помощью listEnd:
listStart -> listEnd -> next -> ...
listStart -> next -> listEnd -> next ...
...
listStart -> next -> ... -> next -> listEnd -> nil
После чего создаем еще один элемент
listStart -> next -> ... -> next -> listEnd -> next
и заполняем его.
Вот и всё

@hppnd · 28.05.2012, 18:19 **[ТС]**

vilag, а как вручную заполнить список ?

@vilag · 28.05.2012, 18:52

А не надо его вручную заполнять. В начале listStart := nil; и добавляй себе элементы с помощью этой процедуры.

@burglar · 29.05.2012, 20:24

Имеется линейный список с последовательным хранением, элементами которого являются прямоугольники с параллельными осям координат сторонами.А остальное как у ТС. Подскажите, пожалуйста, как мне в программу "вставить" эти прямоугольники, как их описать?

Delphi

program linelist;
{$APPTYPE CONSOLE}
uses
  SysUtils;
 
const nMaxSize=1000;
type TIntList=array[0..nMaxSize] of integer;
var Initlist:TIntList;
    i,count:integer;
       
procedure intlist(fIntlist:TIntList;count:integer);
  begin
  for i:=0 to count-1 do write(Initlist[i],' ');
  end;
       
function add_item(item:integer;intlist:tintlist;count:integer):integer;
  begin result:=-1;
  if count<nmaxsize then
      begin intlist[count]:=item;
      result:=count+1;
      end;
  end;
       
function insert_item(item,pos:integer;intlist:tintlist;count:integer):integer;
  begin result:=-1;
  if (count<nmaxsize)and(pos>=0)and(pos<count) then
      begin for i:=count downto pos+1 do intlist[i]:=intlist[i-1];
            intlist[pos]:=item;
            result:=count+1;
      end;
  end;
       
function delete_itemAT(pos:integer;intlist:tintlist;count:integer):integer;
  begin result:=-1;
  if (count<nmaxsize)and(pos>=0)and(pos<count) then
      begin for i:=pos to (count-2) do
                intlist[i]:=intlist[i+1];
            result:=count-1;
      end;
  end;
       
function find_item(item:integer;intlist:tintlist;count:integer):integer;
  begin result:=-1;
  if (count<nmaxsize)and(count>0)then
      for i:=0 to (count-1) do
          if intlist[i]=item then
          begin result:=i;
          exit;
          end;
  end;
       
function delete_item(item:integer;intlist:tintlist;tcount:integer):integer;
  var s:integer;
  begin result:=-1; s:=0;
  if (tcount<nmaxsize)and(tcount>0)then
              for i:=0 to tcount-1 do
              if intlist[i]=item then
                  begin result:=delete_itemAT(i,intlist,tcount);
                  s:=s+1;
                  end;
  if s>1 then result:=tcount-s;
  end;
       
function sort_list(intlist:tintlist;count:integer):boolean;
  var t,s:integer;
  begin
  result:=(count<nmaxsize)and(count>1);
  s:=0;
  while result do
      begin result:=false;
      for i:=0 to count-2 do
        if intlist[i]>intlist[i+1] then
            begin t:=intlist[i];
            intlist[i]:=intlist[i+1];
            intlist[i+1]:=t;
            result:=true;
            s:=s+1;
            end;
      end;
  if s>0 then result:=true;
  end;
 
begin
          
  count:=8;
  writeln('massif');
  for i:=0 to count-1 do begin
                      Initlist[i]:=random(100)+1;
                      write(Initlist[i],' ');
                      end;
  writeln;
  intlist(Initlist,count);
         
  writeln;count:=add_item(123,Initlist,count);
  writeln(count); intlist(Initlist,count);
         
  writeln;count:=insert_item(123,3,Initlist,count);
  writeln(count); intlist(Initlist,count);writeln;
          
  writeln;count:=delete_itemAT(4,Initlist,count);
  writeln(count); intlist(Initlist,count);writeln;
          
  writeln;writeln(find_item(17,Initlist,count));
   intlist(Initlist,count);writeln;
          
  writeln;count:=delete_item(17,Initlist,count);
  writeln(count); intlist(Initlist,count);writeln;
          
  writeln;writeln(sort_list(Initlist,count));
  writeln(count); intlist(Initlist,count);writeln;
  
  readln;
end.

Думал, так, но так неверно:

Delphi

1	type Trect=record x,y:double;

@vilag · 29.05.2012, 20:44

burglar, ты явно не вкурил, что такое список. Это тебе не массив.

А прямоугольники (ортогональными их вроде называют) обычно объявляют как-то так:

Delphi

type
  TRectangle = record
    Left, Top, Right, Bottom: integer;
  end;

И потом меняй себе Integer на TRectangle, где речь идёт о данных.

@hppnd · 29.05.2012, 20:45 **[ТС]**

burglar, как я понимаю , должен быть еще один тип :

Delphi

type point=record
x,y:double; end;
treet=record
a,b:tpoint;
end;

Но так же как и тебе не понятны принципы обращения к типу в самой программе ,
а так же принцип заполнения "линейного списка"

Препод говорил , что прямоугольник задается по двум точкам -вершинам , а именно : левой нижней и правой верхней ( если не ошибаюсь )

@vilag · 29.05.2012, 20:55

Delphi

type point=record
x,y:double; end;
treet=record
a,b:tpoint;
end;

Здесь ошибка в том, что создаётся point, а используется TPoint. Плодить типы не надо, достаточно того, что я написал.

Сообщение от hppnd

принцип заполнения "линейного списка"

Что значит "заполнение"? Список это структура, в которую можно добавлять данные, и из которой можно их удалять. Зачем его "заполнять", если можно просто по очереди добавлять элементы?

@burglar · 30.05.2012, 15:51

Сегодня уточнили у препода, что линейный список с последовательным хранением это именно массив!

@vilag · 31.05.2012, 02:32

Не по теме:

А бабушка с причинными местами - дедушка.

@burglar · 31.05.2012, 21:34

Сообщение от vilag

Не по теме:

А бабушка с причинными местами - дедушка.

Вы, должно быть имели в виду, линейный список со связанным хранением, а нам дан массив, ТС, ошибся, когда хотел использовать указатели.

@burglar 5 / 3 / 1 Регистрация: 27.12.2011 Сообщений: 127
	31.05.2012, 21:34	14
	Сообщение от vilag Не по теме: А бабушка с причинными местами - дедушка. Вы, должно быть имели в виду, линейный список со *связанным* хранением, а нам дан массив, ТС, ошибся, когда хотел использовать указатели. 0

@Alex_pac 1301 / 707 / 107 Регистрация: 25.05.2011 Сообщений: 2,158 Записей в блоге: 51
	27.05.2012, 18:33	2
	deleted 1

@hppnd 1 / 1 / 0 Регистрация: 27.05.2012 Сообщений: 19
	28.05.2012, 11:22 [ТС]	4
	vilag, огромное Вам спасибо , но появился еще один вопрос : не могли бы Вы объяснить структуру заполнения списка ? 0

@vilag 70 / 69 / 13 Регистрация: 24.05.2012 Сообщений: 146
	28.05.2012, 16:32	5
	Структура следующая: имеем переменную listStart с началом списка: listStart -> next -> next -> next ... -> next -> nil А добавлять надо в конец. Который мы и ищем с помощью listEnd: listStart -> listEnd -> next -> ... listStart -> next -> listEnd -> next ... ... listStart -> next -> ... -> next -> listEnd -> nil После чего создаем еще один элемент listStart -> next -> ... -> next -> listEnd -> next и заполняем его. Вот и всё 1

@hppnd 1 / 1 / 0 Регистрация: 27.05.2012 Сообщений: 19
	28.05.2012, 18:19 [ТС]	6
	vilag, а как вручную заполнить список ? 0

@vilag 70 / 69 / 13 Регистрация: 24.05.2012 Сообщений: 146
	28.05.2012, 18:52	7
	А не надо его вручную заполнять. В начале listStart := nil; и добавляй себе элементы с помощью этой процедуры. 1

@burglar 5 / 3 / 1 Регистрация: 27.12.2011 Сообщений: 127
	30.05.2012, 15:51	12
	Сегодня уточнили у препода, что линейный список с последовательным хранением это именно массив! 0

@vilag
	31.05.2012, 02:32 #13
	Не по теме: А бабушка с причинными местами - дедушка. 0