将节点移到单链列表的开头

mirgee 发表于 Dev

米尔吉

在Pascal中，当我有一个带有这样定义的节点的单链接列表时，

pNode = ^Node;
Node = record
    data : data;
    next : pNode;
end;

当我像这样遍历列表时

while y<>z do begin
        if y^.data < x^.data then begin
          { HERE I WOULD LIKE TO MOVE y IN FRONT OF X }
        end;
        y:=y^.next;
end;

其中x是枢轴（列表的开头），y是列表的“索引”，z是列表的尾部（结尾）（是的，我正在尝试对单个链接的列表执行快速排序）。我将如何完成评论中的任务？

我做了程序insertAfter：

procedure List.insertAfter(n : pNode; var what : data);
var newn : pNode;
begin
  new(newn);
  newn^.data := what;
  newn^.next := n^.next;
  n^.next := newn;
end;

和 insertInstead

procedure List.insertInstead(n : pNode; var what : data);
begin
    List.insterAfter(n, n^.data);
    n^.data:=what;
end;

同样 deleteAfter(n : pNode)

procedure List.deleteAfter(n : pNode);
var q : pNode;
begin
    q := n^.next;
    n^.next := n^.next^.next;
    dispose(q);
end;

和 delete(n : pNode)

procedure List.delete(n : pNode);
begin
    if n^.next <> tail then begin
        n^.data := n^.next^.data;
        deleteAfter(n);
    end
    else begin
        dispose(tail);
        tail:=n;
        tail^.next := nil;
    end;
end;

现在，当我放入迭代时，而不是注释中

list.insertInstead(x,y^.data);
list.delete(y);

，它不起作用，大概是因为y^.next现在不指向移动之前的节点。

所以问题是：如何在y^.next仍指向同一节点的情况下将节点移至开头？

PS .：我已经尝试了显而易见的方法：在移动之前使用和辅助变量存储y的实际值，但是它似乎随y一起变化。

这是原始代码：Stack，List，Quicksort。

企鹅岛

我想我可能会看到问题。插入代码的第一行

 list.insertInstead(x,y^.data);

工作正常。它将在x之后紧跟一个新节点，并用y的数据填充它（因此，您现在实际上在节点x之后有一个节点y的副本。

但我不认为第二行

 list.delete(y);

做你想要的。它确实从列表中“删除”了节点y（根据需要），但是这样做是通过将数据从y之后的节点移到y的位置，然后删除该节点来实现的。因此，现在y.next指向原始y之后的节点之后的节点。也许图表会有所帮助。

在list.delete（y）之前

 node:     ... - y - a - b - c - ... - z
 data:     ... - Y - A - B - C - ... - Z
                     ^ 
                     y.next points here (data is A)

在list.delete（y）之后

 node:     ... - y - b - c - ... - z
 data:     ... - A - B - C - ... - Z
                     ^ 
                     y.next points here (data is B)
                 ^
                 y points here (data is A)

因此，如果您像行中那样递增y

 y:=y^.next;

在迭代循环中，您会错过测试数据A。您可以通过删除y：= y ^ .next;来解决此问题。线。但是然后您的while循环仍然会出现问题

 while y<>z do begin

因为指向节点y的指针不再改变（因为您删除了y：= y ^ .next），所以y永远不会等于z。解决此问题的最简单（但可能不是最优雅）的方法可能是用

 while y^.next <>z do begin

并添加最后一个案例以测试最后一个节点。

然后，主循环看起来像（未经测试）：

 while y^.next <> z do begin
         if y^.data < x^.data then begin
                 list.insertInstead(x,y^.data);
                 list.delete(y);
         end;
 end;
 if y^.data < x^.data then begin
         list.insertInstead(x,y^.data);
         list.delete(y);
 end;

或者，通过定义新程序

 procedure list.moveiflessthan(x,y : pnode);
 begin
      if y^.data < x^.data then begin
              list.insertInstead(x,y^.data);
              list.delete(y);
      end;
 end;

你得到

 while y^.next <> z do
         if y^.data < x^.data then 
                 list.moveiflessthan(x,y);
 if y^.data < x^.data then
         list.moveiflessthan(x,y);

如果您到达列表的末尾（我尚未检查），可能仍然会出现最终案例错误，但是我敢肯定您可以解决此问题...

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。