GAECHKA
Твоя помощница в решении задач

Линейные односвязные списки

Задача: Написать программу,которая копирует в список М,по каждому вхождению заданного элемента K,все элементы списка М2.

Подскажите,пожалуйста,как можно реализовать вставку одного списка в другой? В конце программы я попытался это сделать,но чёт совсем запутался.


program spisok;
uses
crt;
 
type   
oc=^st;      {список М2}
st=record
inf:integer;
link:oc;
end;
 
oc1=^st1;     {список М}
st1=record   
inf1:integer;
link1:oc1;
end;
 
var
p,top,endl:oc;
top1,end1,p1:oc1;
i,j,n,m,k,t:integer;
begin
top:=nil;
endl:=nil;
top1:=nil;
end1:=nil;
 
new(p);
writeln('first element in first list: ');
readln(p^.inf);
p^.link:=nil;
top:=p;endl:=p;
 
writeln('n= ');
readln(n);
 
for i:=2 to n do
Begin
new(p);
Write('next element in first list: ');
Readln(p^.inf);
p^.link:=nil;
endl^.link:=p;
endl:=p;
End;
 
clrscr;
 
p:=top;
writeln('first list : ');
While pnil do
Begin
Write(p^.inf,' ');
p:=p^.link;
End;
 
writeln;
new(p1);
writeln('first element in second list: ');
readln(p1^.inf1);
p1^.link1:=nil;
top1:=p1;end1:=p1;
 
for i:=2 to n do
Begin
new(p1);
Write('next element in second list : ');
Readln(p1^.inf1);
p1^.link1:=nil;
end1^.link1:=p1;
end1:=p1;
End;
clrscr;
writeln('second list : ');
p1:=top1;
While p1nil do
Begin
Write(p1^.inf1,' ');
p1:=p1^.link1;
end;
 
writeln;
writeln;
writeln('num :');
readln(k);
 
 
p:=top;
p1:=top1;
for i:=1 to n do
if k=p^.inf then
begin 
for j:=1 to n do
begin
new(p);
p:=p^.link;
p^.inf:=p1^.inf1;
end;
end;
 
p:=top;
While pnil do
Begin
Write(p^.inf,' ');
p:=p^.link;
end;
end.
0
вопрос задан

Источник


2 ответа
Для начала, вам нужно выкинуть объявление oc1=^st1; {список М} из вашей программы.
И привести оба списка к одному типу данных.

Затем прочитать статью на офф-сайте: Связанные списки - новый стиль

type   
  tList = class
    inf : Integer;
    next : tList;
    
    constructor (inf : Integer);
    begin
      Self.inf := inf; next := nil;
    end;
    
    procedure Add(inf : Integer);
    begin
      var cur := Self;
      while cur.next  nil do cur := cur.next;
      cur.next := New tList(inf);
    end;
    
    procedure Add(List : tList);
    begin
      var cur := Self;
      while cur.next  nil do cur := cur.next;
      cur.next := List;
    end;
    
    procedure Out(msg : String := '');
    begin
      if msg.Length > 0 then Write(msg);
      var cur := Self;
      repeat
        Write(#32,cur.inf); cur := cur.next;
      until cur = nil;
      WriteLn;
    end;
  end;
 
begin
  var List1 : tList := nil;
  for var i := 1 to ReadInteger('n =') do
    if List1 = nil then
      List1 := New tList(ReadInteger($'List1({i}) ='))
    else
      List1.Add(ReadInteger($'List1({i}) ='));
  List1.Out('List1 :');
 
  var List2 : tList := nil;
  for var i := 1 to ReadInteger('n =') do
    if List2 = nil then
      List2 := New tList(ReadInteger($'List2({i}) ='))
    else
      List2.Add(ReadInteger($'List2({i}) ='));
  List2.Out('List2 :');
  
  List1.Add(List2);
  Write('Результат (два списка в одном):'); List1.Out;
end.
JuriiMW, надо не 1 раз складывать списки, а вставлять второй в первый, при каждом вхождении элемента K.
И чтение можно ускорить, не перебирая весь список для вставки каждого 1 элемента.

type   
  tList = class
    inf: Integer;
    next: tList;
    
    constructor (inf : Integer);
    begin
      Self.inf := inf;
    end;
    
    static function ReadNew(count: integer): tList;
    begin
      if count1 then exit;
      
      Result := new tList(ReadInteger);
      
      var last := Result;
      loop count-1 do
      begin
        last.next := new tList(ReadInteger);
        last := last.next;
      end;
      
    end;
    
    function Enmr: sequence of tList;
    begin
      var curr := self;
      
      while curr  nil do
      begin
        yield curr;
        curr := curr.next;
      end;
      
    end;
    
    function Copy: tList;
    begin
      Result := new tList(self.inf);
      var last := Result;
      
      foreach var curr in self.Enmr.Skip(1) do
      begin
        last.next := new tList(curr.inf);
        last := last.next;
      end;
      
    end;
    
    procedure Insert(other: tList);
    begin
      other.Enmr.Last.next := self.next;
      self.next := other;
    end;
    
    function Out(msg: String := ''): tList;
    begin
      if msg  '' then Print(msg);
      self.Enmr.Println;
      Result := self;
    end;
    
    public function ToString: string; override := inf.ToString;
    
  end;
 
begin
  var List1 := tList.ReadNew(ReadInteger('N1 =')).Out('List1 :');
  var List2 := tList.ReadNew(ReadInteger('N2 =')).Out('List2 :');
  var K := ReadInteger('K =');
  
  // .Pairwise надо чтоб следующий элемент вычислялся перед тем как вставится List2
  // иначе элементы List2 будет тоже проверять на =K, и если хоть 1 совпадёт - получаем бесконечный цикл
  foreach var el: tList in List1.Enmr.Append(nil).Pairwise((el1,el2)->el1) do
    if el.inf=K then
      el.Insert(List2.Copy);
  
  List1.Out('Получившийся список :');
end.