双向链表排序练习(C++和Delphi代码).doc

双向链表排序练习(C+和Delphi代码)双向链表排序练习(C+和Delphi代码)2006-12-15 23:28/VC+版本#include #include #include #include typedef struct tagNode tagNode* forward; int data; tagNode* next; Node, *pNode;typedef struct tagHeadLast pNode begin; pNode end; HeadLast;HeadLast CreateList(int n);void InsertListAtLast(HeadLast& list, pNode node);void InsertList(HeadLast& list, pNode node);void DeleteList(HeadLast& list);bool IsBlankHeadLast(HeadLast& list);void DispList(HeadLast& list);void SortList(HeadLast& list);int main(int argc, char *argv) srand(unsigned)time(NULL); HeadLast List = CreateList(108); DispList(List); coutendlforward = NULL; p-next = NULL; p-data = rand() % 100; InsertListAtLast(hl,p); return hl;void InsertList(HeadLast& list, pNode node) if(IsBlankHeadLast(list) node-forward = NULL; node-next = NULL; list.begin = node; list.end = node; return; pNode p = list.begin; while(p != NULL) if(node-data data) if(p = list.begin) node-next = p; p-forward = node; node-forward = NULL; list.begin = node; return; node-next = p; node-forward = p-forward; p-forward = node; node-forward-next = node; return; p = p-next; InsertListAtLast(list, node);void InsertListAtLast(HeadLast& list, pNode node) if(IsBlankHeadLast(list) list.begin = node; list.end = node; node-forward = NULL; node-next = NULL; else list.end-next = node; node-forward = list.end; node-next = NULL; list.end = node; void DeleteList(HeadLast& list) if(IsBlankHeadLast(list) return; pNode p; p = list.begin-next; if(p = NULL) delete list.begin; list.begin = NULL; list.end = NULL; return; while(p != list.end) delete p-forward; p = p-next; delete p-forward; delete p;bool IsBlankHeadLast(HeadLast& list) if(list.begin = NULL) return true; return false;void DispList(HeadLast& list) int index = 1; pNode p; p = list.begin; while(p != NULL) coutsetw(5)setiosflags(ios:left)index+datanext; void SortList(HeadLast& list) if(list.begin = list.end) return; pNode p, oldp; p = list.begin; list.begin = NULL; list.end = NULL; while(p != NULL) oldp = p; p = p-next; InsertList(list, oldp); /DevC+版本#include #include #include using namespace std;typedef struct tagNode tagNode* forward; int data; tagNode* next; Node, *pNode;typedef struct tagHeadLast pNode begin; pNode end; HeadLast;HeadLast CreateList(int n);void InsertListAtLast(HeadLast& list, pNode node);void InsertList(HeadLast& list, pNode node);void DeleteList(HeadLast& list);bool IsBlankHeadLast(HeadLast& list);void DispList(HeadLast& list);void SortList(HeadLast& list);int main(int argc, char *argv) srand(unsigned)time(NULL); HeadLast List = CreateList(108); DispList(List); coutendlforward = NULL; p-next = NULL; p-data = rand() % 100; InsertListAtLast(hl,p); return hl;void InsertList(HeadLast& list, pNode node) if(IsBlankHeadLast(list) node-forward = NULL; node-next = NULL; list.begin = node; list.end = node; return; pNode p = list.begin; while(p != NULL) if(node-data data) if(p = list.begin) /插在最前 node-next = p; p-forward = node; node-forward = NULL; list.begin = node; return; node-next = p; /插在中间 node-forward = p-forward; p-forward = node; node-forward-next = node; return; p = p-next; InsertListAtLast(list, node);void InsertListAtLast(HeadLast& list, pNode node) if(IsBlankHeadLast(list) list.begin = node; list.end = node; node-forward = NULL; node-next = NULL; else list.end-next = node; node-forward = list.end; node-next = NULL; list.end = node; void DeleteList(HeadLast& list) if(IsBlankHeadLast(list) return; pNode p; p = list.begin-next; if(p = NULL) delete list.begin; list.begin = NULL; list.end = NULL; return; while(p != list.end) delete p-forward; p = p-next; delete p-forward; delete p;bool IsBlankHeadLast(HeadLast& list) if(list.begin = NULL) return true; return false;void DispList(HeadLast& list) int index = 1; pNode p; p = list.begin; while(p != NULL) coutsetw(5)setiosflags(ios:left)index+datanext; void SortList(HeadLast& list) if(list.begin = list.end) return; pNode p, oldp; p = list.begin; list.begin = NULL; list.end = NULL; while(p != NULL) oldp = p; p = p-next; InsertList(list, oldp); /Delphi版本program Doub;$APPTYPE CONSOLEuses SysUtils;type pNode = Node; Node = record forw: pNode; data: integer; next: pNode; end; HeadLast = record head: pNode; last: pNode; end;function IsBlankHeadLast(list: HeadLast): boolean;begin result := false; if list.head = nil then result := true;end;procedure InsertListAtLast(var list: HeadLast; node: pNode);begin if IsBlankHeadLast(list) then begin list.head := node; list.last := node; node.forw := nil; node.next := nil; end else begin list.last.next := node; node.forw := list.last; node.next := nil; list.last := node; end;end;function CreateList(n: integer): HeadLast;var p: pNode;begin result.head := nil; result.last := nil; while true do begin if n = 0 then break; new(p); p.forw := nil; p.next := nil; p.data := Random(100); InsertListAtLast(result, p); dec(n); end;end;procedure InsertList(var list: HeadLast; node: pNode);var p: pNode;begin if IsBlankHeadLast(list) then begin node.forw := nil; node.next := nil; list.head := node; list.last := node; exit; end; p := list.head; while p nil do begin if node.data p.data then begin if p = list.head then begin node.next := p; p.forw := node; node.forw := nil; list.head := node; exit; end; node.next := p; node.forw := p.forw; p.forw := node; node.forw.next := node; exit; end; p := p.next; end; InsertListAtLast(list, node);end;procedure DeleteList(var list: HeadLast);var p: pNode;begin if IsBlankHeadLast(list) then exit; p := list.head.next; if p = nil then begin Dispose(list.head); list.head := nil; list.last := nil; exit; end; while p list.last do begin Dispose(p.forw); p := p.next; end; Dispose(p.forw); Dispose(p);end;function setw(str: string; width: integer): string;begin result := str; while