链表模板

  1 //LinkedList API
  2 typedef struct ListNode {
  3     int key;
  4     struct ListNode * next;
  5     struct ListNode * prev;
  6 }ListNode;
  7  
  8 ListNode ListNodePool[LISTSIZE];
  9 int NodeNum = 0;
 10  
 11 ListNode NIL;
 12  
 13 ListNode * getNewNode(){
 14     return &ListNodePool[NodeNum++];
 15 }
 16  
 17 void listInit(){
 18     NIL.next = &NIL;
 19     NIL.prev = &NIL;
 20     NIL.key = 0;
 21 }
 22  
 23 void listInsertAtFront(ListNode * node){
 24     node->next = NIL.next;
 25     node->prev = &NIL;
 26     NIL.next->prev = node;
 27     NIL.next = node;
 28 }
 29  
 30 void listInsertAfter(ListNode * dstNode, ListNode * NewNode){
 31     NewNode->next = dstNode->next;
 32     NewNode->prev = dstNode;
 33     dstNode->next->prev = NewNode;
 34     dstNode->next = NewNode;
 35 }
 36  
 37 void listDelete(ListNode * node){
 38     node->prev->next = node->next;
 39     node->next->prev = node->prev;
 40 }
 41  
 42 ListNode * listSearch(int k){
 43     ListNode * x = NIL.next;
 44     while (x != &NIL && x->key != k){
 45         x = x->next;
 46     }
 47     return x;
 48 }
 49  
 50 //end of LinkedList API
 51  
 52 void showList(){
 53     ListNode * curNode = NIL.next;
 54     while (curNode != &NIL){
 55         cout << curNode->key << " ";
 56         curNode = curNode->next;
 57     }
 58     cout << endl;
 59 }
 60  
 61 void listInsertSort(){
 62     ListNode * curNode = NIL.next->next;
 63     ListNode * tmpNode;
 64     while (curNode != &NIL){
 65         //cout << curNode->key << " " << endl;
 66         ListNode * dstNode = NIL.next;
 67         while (dstNode != curNode && dstNode->key < curNode->key){
 68             dstNode = dstNode->next;
 69         }
 70  
 71         dstNode = dstNode->prev;
 72         tmpNode = curNode->next;
 73         listDelete(curNode);
 74         listInsertAfter(dstNode, curNode);
 75  
 76         curNode = tmpNode;
 77     }
 78 }
 79  
 80 void main(){
 81     cin >> N;
 82  
 83     listInit();
 84     ListNode * dstNode = &NIL;
 85     for (int i = 0; i < N; i++){
 86         ListNode * node = getNewNode();
 87         node->key = data[i];
 88  
 89         listInsertAfter(dstNode, node);
 90         dstNode = dstNode->next;
 91     }
 92  
 93     ListNode * curNode = NIL.next;
 94     while (curNode != &NIL){
 95         cout << curNode->key << " ";
 96         curNode = curNode->next;
 97     }
 98     cout << endl;
 99  
100     insertSort(data, N);
101     showData(N);
102  
103     listInsertSort();
104     showList();
105 }
106