双链表操作

2939阅读　0评论2011-05-12　Mrt-l
分类：C/C++

/*
 * 该例程实现了双链表的声明，创建，插入，删除等功能。
 */
 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include<assert.h>

  5. typedef struct NODE {
  6.     struct NODE *fwd;
  7.     struct NODE *bwd;
  8.     int value;
  9. }Node;

  11. struct NODE *creat_root()
  12. {
  13.     Node *rootp;
  14.     rootp = (Node *)malloc(sizeof(Node));
  15.     rootp->fwd = NULL;
  16.     rootp->bwd = NULL;
  17.     rootp->value = 0;

  19.     return rootp;
  20. }

  22. /*
  23.  * 把一个值插入到一个双链表中，rootp 是一个指向根节点的指针，value 是欲插入的新值。
  24.  * 返回值：如果 value 已在链表中，返回0;内存不足，返回-1;插入成功，返回1。
  25.  */

  27. int dll_insert1(Node *rootp, int value)
  28. {
  29.     Node *this, *next, *newnode;
  30.     
  31.     /* this 首先指向跟节点，根节点只用两个指针字段，值字段不用 */
  32.     for (this = rootp; (next = this->fwd) != NULL; this = next) {
  33.         if (next->value == value)
  34.             return 0;
  35.         if (next->value > value)
  36.             break;
  37.     }    

  39.     newnode = (Node *)malloc(sizeof(Node));
  40.     if (newnode == NULL)
  41.         return -1;
  42.     newnode->value = value;

  44.     if (next != NULL) {/* 情况1或2:不是位于链表的尾部 */
  45.         if (this != rootp) {/* 情况1:不是位于链表的起始位置，即在第一个节点跟最后一个节点之间 */
  46.             newnode->fwd = next;
  47.             this->fwd = newnode;
  48.             newnode->bwd = this;
  49.             next->bwd = newnode;
  50.         }
  51.         else {/* 情况2:位于链表的起始位置，即第一个节点且后面还要节点 */
  52.             newnode->fwd = next;
  53.             rootp->fwd = newnode;
  54.             newnode->bwd = NULL;
  55.             next->bwd = newnode;
  56.         }    
  57.     }
  58.     else {/* 情况3或4:位于链表的尾部 */
  59.         if (this != rootp) {/* 情况3:不是位于链表的起始位置，即最后一个节点的后面 */
  60.             newnode->fwd = NULL;
  61.             this->fwd = newnode;
  62.             newnode->bwd = this;
  63.             rootp->bwd = newnode;
  64.         }    
  65.         else {/* 情况4:位于链表的起始位置，即是第一个节点也是最后一个节点*/
  66.             newnode->fwd = NULL;
  67.             rootp->fwd = newnode;
  68.             newnode->bwd = NULL;
  69.             rootp->bwd = newnode;
  70.         }
  71.     }
  72. }

  74. /*
  75.  * 从双链表中移除一个节点。
  76.  *
  77.  * rootp :包含链表根指针的节点的指针。
  78.  * delete:要删除的节点的指针。
  79.  */

  81. int dou_remove(Node *rootp, Node *delete)
  82. {
  83.     register Node *this;
  84.     assert(delete != NULL);

  86.     for (this = rootp; this != NULL; this = this->link)
  87.         if (this == delete)
  88.             break;

  90.     if (this == delete) {
  91.         // 更新 delete 节点的前面那个节点的 fwd 字段
  92.         if (this->bwd == NULL)
  93.             rootp->fwd = this->fwd;
  94.         else
  95.             this->bwd-fwd = this->fwd;

  97.         // 更新 delete 节点的后面那个节点的 bwd 字段
  98.         if (this->fwd == NULL)
  99.             rootp->bwd = this->bwd;
  100.         else
  101.             this->fwd->bwd = this->bwd;

  103.         free(this);
  104.         return TRUE;
  105.     }
  106.     else
  107.         return    FALSE;
  108. }

  110. int main()
  111. {
  112.     Node *rootp, *ptr;

  114.     // test function dll_insert1
  115.     rootp = creat_root();
  116.     dll_insert1(rootp, 10);
  117.     dll_insert1(rootp, 20);
  118.     dll_insert1(rootp, 30);

  120.     printf("the dou_link contains :");
  121.     for (ptr = rootp->fwd; ptr != NULL ; ptr = ptr->fwd) {
  122.             printf("%4d", ptr->value);
  123.     }    
  124.     printf("\n");

  126.     exit(0);    
  127. }
上一篇：单链表操作
下一篇：堆栈操作