0 
for (size_t i = 0; i < n; ++i) {
    while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
    H[k++] = P[i];

for (size_t i = n-1, t = k+1; i > 0; --i) {
    while (k >= t && cross(H[k-2], H[k-1], P[i-1]) <= 0) k--;
    H[k++] = P[i-1];

我在 wikipedia 上找到了它的代码，但由于某些原因，我更喜欢使用双向链表作为数据结构
问题在于 while 循环 while(k>=2&&...) 和 while(k>=t && ...）
如何在链表上重写这些 while 循环

4

1 回答 1

0 
unit DoublyLinkedList;
interface
const NULL = NIL;
type TPoint = record
                x,y:longint;
              end;
     PLink = ^TLink;
     TLink = record
                point:TPoint;
                next:PLink;
                prev:PLink;
             end;
    TList = record
                first:PLink;
                last:PLink;
            end;
    TFunc = function(A,B:TPoint):integer;

procedure ListInit(var L:TList);
function  ListFind(L:TList;key:TPoint):PLink;
function  ListIsEmpty(L:TList):boolean;
procedure ListInsertFirst(var L:TList;dd:TPoint);
procedure ListInsertLast(var L:TList;dd:TPoint);
procedure ListDeleteFirst(var L:TList);
procedure ListDeleteLast(var L:TList);
procedure ListInsert(var L:TList;dd:TPoint);
function ListInsertAfter(var L:TList;key,dd:TPoint):boolean;
procedure ListDeleteKey(var L:TList;key:TPoint);
procedure ListDisplayForward(L:TList);
procedure ListDisplayBackward(L:TList);
procedure BSTsort(var L:TList);

implementation
function equals(p1,p2:TPoint):boolean;
begin
  equals:=(p1.x = p2.x) and (p1.y = p2.y);
end;
function compare(A,B:TPoint):integer;
var t:integer;
begin
  t := 1;
  if(A.x < B.x)or((A.x = B.x)and(A.y < B.y))then
        t := -1;
  if(A.x = B.x)and(A.y = B.y)then
        t := 0;
  compare := t;
end;
procedure BSTinsert(var root:PLink;x:PLink);
begin
        if root = NULL then
        begin
        root := x;
                x^.prev := NULL;
                x^.next := NULL;
        end
    else if compare(root^.point,x^.point) = 0 then
        BSTinsert(root^.prev,x)
    else if compare(root^.point,x^.point) < 0 then
                BSTinsert(root^.next,x)
    else
                BSTinsert(root^.prev,x);
end;
procedure BSTtoDLL(root:PLink;var L:TList);
begin
  if root <> NULL then
  begin
    BSTtoDLL(root^.prev,L);
    if ListIsEmpty(L) then
        L.first := root
    else
        L.last^.next := root;
    root^.prev := L.last;
    L.last := root;
    BSTtoDLL(root^.next,L);
  end;
end;
procedure BSTsort(var L:TList);
var root,temp:PLink;
begin
  root := NULL; (*This instruction was missing in the code *)
  while not ListIsEmpty(L)do
  begin
    temp := L.first;
    if L.first^.next = NULL then
        L.last := NULL
    else
        L.first^.next^.prev := NULL;
    L.first := L.first^.next;
        BSTinsert(root,temp);
  end;
  BSTtoDLL(root,L);
end;
procedure ListInit(var L:TList);
begin
  L.first := NULL;
  L.last := NULL;
end;
function  ListFind(L:TList;key:TPoint):PLink;
var p:PLink;
begin
  p := L.first;
  while(p <> NULL)and(not equals(key,p^.point))do
    p := p^.next;
  ListFind := p;
end;
function  ListIsEmpty(L:TList):boolean;
begin
  ListIsEmpty := L.first = NULL;
end;
procedure ListInsertFirst(var L:TList;dd:TPoint);
var newLink:PLink;
begin
  new(newLink);
  newLink^.point.x := dd.x;
  newLink^.point.y := dd.y;
  newLink^.next := NULL;
  newLink^.prev := NULL;
  if ListIsEmpty(L) then
     L.last := newLink
  else
    L.first^.prev := newLink;
  newLink^.next := L.first;
  L.first := newLink;   
end;
procedure ListInsertLast(var L:TList;dd:TPoint);
var newLink:PLink;
begin
  new(newLink);
  newLink^.point.x := dd.x;
  newLink^.point.y := dd.y;
  newLink^.next := NULL;
  newLink^.prev := NULL;
  if ListIsEmpty(L) then
     L.first := newLink
  else
  begin
    L.last^.next := newLink;
    newLink^.prev := L.last;
  end;
  L.last := newLink;
end;
procedure ListDeleteFirst(var L:TList);
var temp:PLink;
begin
  if not ListIsEmpty(L) then
  begin
    temp := L.first;
    if L.first^.next = NULL then
        L.last := NULL
    else
        L.first^.next^.prev := NULL;
    L.first := L.first^.next;
    dispose(temp);
  end;  
end;
procedure ListDeleteLast(var L:TList);
var temp:PLink;
begin
  if not ListIsEmpty(L) then
  begin
    temp := L.last;
    if L.first^.next = NULL then
        L.first := NULL
    else
        L.last^.prev^.next := NULL;
    L.last := L.last^.prev;
    dispose(temp);
  end;
end;
procedure ListInsert(var L:TList;dd:TPoint);
var newLink,current:PLink;
begin
  new(newLink);
  newLink^.point.x := dd.x;
  newLink^.point.y := dd.y;
  newLink^.next := NULL;
  newLink^.prev := NULL;
  current := L.first;
  while(current <> NULL)and(compare(newLink^.point,current^.point) > 0)do
     current := current^.next;
  if current = NULL then
  begin
    if ListIsEmpty(L)then
        L.first := newLink
    else
    begin
        L.last^.next := newLink;
        newLink^.prev := L.last;
    end;
    L.last := newLink;
  end
  else if current^.prev = NULL then
  begin
    L.first := newLink;
    newLink^.next := current;
    current^.prev := newLink;
    newLink^.prev := NULL;
    current := newLink;
  end
  else
  begin
     current^.prev^.next := newLink;
     newLink^.next := current;
     newLink^.prev := current^.prev;
     current^.prev := newLink;
  end;
end;
function ListInsertAfter(var L:TList;key,dd:TPoint):boolean;
var newLink,current:PLink;
    found:boolean;
begin
  current := ListFind(L,key);
  found := current <> NULL;
  if found then
  begin
    new(newLink);
    newLink^.point.x := dd.x;
    newLink^.point.y := dd.y;
    newLink^.next := NULL;
    newLink^.prev := NULL;
    if current^.next = NULL then
    begin
      newLink^.next := NULL;
      L.last := newLink;    
    end
    else
    begin
      newLink^.next := current^.next;
      current^.next^.prev := newLink;   
    end;
    newLink^.prev := current;
    current^.next := newLink;
  end;
  ListInsertAfter:= found;  
end;
procedure ListDeleteKey(var L:TList;key:TPoint);
var current:PLink;
begin
  current := ListFind(L,key);
  if current <> NULL then
  begin
    if current^.prev = NULL then
        L.first := current^.next
    else
        current^.prev^.next := current^.next;
    if current^.next = NULL then
        L.last := current^.prev
    else
        current^.next^.prev := current^.prev;
    dispose(current);
  end;
end;
procedure ListDisplayForward(L:TList);
var current :PLink;
begin
  write('List (first-->last): ');
  current := L.first;
  while current <> NIL do
  begin
    write('(',current^.point.x,',',current^.point.y,') -> ');
    current := current^.next;
  end;
  writeln('NULL');  
end;
procedure ListDisplayBackward(L:TList);
var current :PLink;
begin
  write('List (last-->first): ');
  current := L.last;
  while current <> NIL do
  begin
    write('(',current^.point.x,',',current^.point.y,') -> ');
    current := current^.prev;
  end;
  writeln('NULL');  
end;

begin

end.


program MonotoneChain;

uses crt,doublylinkedlist;

function equals(a,b:TPoint):boolean;
begin
  equals := (a.x = b.x) and (a.y = b.y)
end;

function vect(a1,a2,b1,b2:TPoint):longint;
begin
  vect := (a2.x - a1.x) * (b2.y - b1.y) - (b2.x - b1.x) * (a2.y - a1.y)
end;

function dist2(a1,a2:TPoint):longint;
begin
  dist2 := sqr(a2.x - a1.x) + sqr(a2.y-a1.y)
end;

procedure Solve(var A,B:TList);
var k,t:longint;
    pt:PLink;
begin
  ListInit(B);
  if not ListIsEmpty(A)then
  begin
    k := 0;
    pt := A.first;
    while pt <> NULL do
    begin
      while(k >= 2)and(vect(B.last^.prev^.point,B.last^.point,B.last^.prev^.point,pt^.point) <= 0)do
      begin
        ListDeleteLast(B);
        k := k - 1;
      end;
      ListInsertLast(B,pt^.point);
      k := k + 1;
      pt := pt^.next;
    end;
    t := k + 1;
    pt := A.last;
    while pt <> NULL do
    begin
      while(k >= t)and(vect(B.last^.prev^.point,B.last^.point,B.last^.prev^.point,pt^.point) <= 0)do
      begin
        ListDeleteLast(B);
        k := k - 1;
      end;
      ListInsertLast(B,pt^.point);
      k := k + 1;
      pt := pt^.prev;
    end;
    ListDeleteLast(B);
  end;
end;



procedure main;
var A,B:TList;
    input:text;
    p:TPoint;
    path:string;
begin
  ListInit(A);
  writeln('Podaj sciezke do pliku z danymi do wczytania');
  readln(path);
  path := 'F:\fpc\3.0.4\bin\i386-win32\monotonechain\' + path;
  assign(input,path);
  {$I-}
  reset(input);
  {$I+}
  if IOResult <> 0 then
     writeln('Pliku nie udalo sie wczytac')
  else
  begin
  while not eof(input) do
  begin
    while not eoln(input) do
    begin
      read(input,p.x,p.y);
      ListInsertLast(A,p);
    end;
    readln(input);
    writeln('List A');
    ListDisplayForward(A);
    ListDisplayBackward(A);
    BSTsort(A);
    Solve(A,B);
    writeln('List A');
    ListDisplayForward(A);
    ListDisplayBackward(A);
    writeln('List B');
    ListDisplayForward(B);
    ListDisplayBackward(B);
    while not ListIsEmpty(A) do
       ListDeleteFirst(A);
   while not ListIsEmpty(B) do
       ListDeleteFirst(B);
  end;
  close(input);
  end;
  readkey;
end;


BEGIN
  main;
END.

这是代码

当我尝试使用 BST 对列表进行排序时出现分段错误
可能当我尝试将从列表头部删除的节点插入 BST
分段错误仅在我从找到凸包的过程中调用它时出现
当我从 main 调用它时代码块一切似乎都正常
分段错误的一种情况是取消引用空指针，但我不知道这个分段错误是由取消引用空指针引起的
我很奇怪，在主代码块中调用的 BSTsort 工作正常，但调用了 BSTsort在解决过程中导致分段错误

我想我知道如何纠正这个排序过程
，但我想知道为什么会发生分段错误以及为什么只在解决过程中

于 2020-07-11T22:56:11.350 回答