[C语言] 双向链表操作

[复制链接]
1112|1
 楼主| 一路向北lm 发表于 2018-10-21 18:49 | 显示全部楼层 |阅读模式
  1. /*******************************双链表**************************/
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>

  5. #define  FALSE    0
  6. #define  TRUE     1
  7. // 双链表声明
  8. typedef struct NODE
  9. {
  10.    struct  NODE  *fwd;
  11.    struct  NODE  *bwd;
  12.    int     value;
  13. }Node;

  14. // 双链表的创建,返回头指针
  15. Node *CreatList(int n)
  16. {
  17.     Node *head,*pNode,*sNode;
  18.     int i;
  19.     head=(Node *)malloc(sizeof(Node));
  20.         head->bwd=NULL;
  21.         head->fwd=NULL;
  22.     pNode=head;
  23.     for(i=1;i<=n;i++)
  24.     {
  25.         sNode=(Node *)malloc(sizeof(Node));
  26.                 sNode->value=i;
  27.                 sNode->bwd = NULL;
  28.                 sNode->fwd = NULL;

  29.                 pNode->fwd=sNode;
  30.                 sNode->bwd=pNode;
  31.         pNode=sNode;
  32.     }
  33.     return(head);
  34. }

  35. // 打印双链表数据(传递双向链表头head)
  36. void print_link(Node *head)
  37. {
  38.         Node *pNode=head->fwd;
  39.     while(pNode!=NULL)
  40.     {
  41.                 printf("%d\n",pNode->value);
  42.                 pNode=pNode->fwd;
  43.     }
  44. }

  45. /*双链表的插入
  46. ** 把一个值插入到双链表,rootp是一个指向根节点的指针
  47. ** value 是欲插入的新值
  48. ** 返回值:如果欲插入的值已存在链表中,函数返回0;
  49. ** 如果内存不足导致无法插入,函数返回-1;,如果插入成功,函数返回1;
  50. */

  51. int dll_insert(Node *rootp,int value)
  52. {
  53.     Node *thist;
  54.         Node *next;
  55.         Node *newnode;
  56.         /*查看value是否存在链表中,有就返回,
  57.         ** 否则为新值创建一个新的节点
  58.         **  thist 指向新节点之前那个节点
  59.         **  next  指向新节点之后那个节点
  60.         */
  61.         for(thist = rootp;(next = thist->fwd) != NULL;thist = next)
  62.         {
  63.                 if (next->value == value)
  64.                         return 0;
  65.                 if (next->value > value)
  66.                         break;
  67.         }
  68.         newnode = (Node *)malloc(sizeof(Node));
  69.         if(newnode == NULL)
  70.                 return -1;
  71.         newnode->value = value;

  72.         /*
  73.         ** 把新值添加到链表中
  74.         */

  75. /*
  76. **最初版,分析了四种不同情况。
  77. */
  78. /*
  79.         if(next != NULL)
  80.         {
  81.                // 情况1或者2:并非位于链表尾部
  82.                    if(thist!=rootp)         //情况1:并非位于链表的起始位置
  83.                    {
  84.                            newnode->fwd = next;
  85.                            thist->fwd = newnode;
  86.                            newnode->bwd = thist;
  87.                            next->bwd = newnode;
  88.                    }
  89.                    else                     //情况2:位于链表的起始位置
  90.                    {
  91.                            newnode->fwd = next;
  92.                            rootp->fwd = newnode;
  93.                            newnode->bwd = NULL;
  94.                            next->bwd = newnode;
  95.                    }
  96.         }
  97.         else    //情况3或者4:位于链表尾部
  98.         {
  99.              if(thist != rootp)   //情况3:并非位于链表的起始位置
  100.                  {
  101.                          newnode->fwd = NULL;
  102.                          thist->fwd = newnode;
  103.                          newnode->bwd = thist;
  104.                          rootp->bwd = newnode;
  105.                  }
  106.                  else                 //情况4:位于链表的起始位置
  107.                  {
  108.                          newnode->fwd = NULL;
  109.                          rootp->fwd = newnode;
  110.                          newnode->bwd = NULL;
  111.                          rootp->bwd = newnode;
  112.                  }
  113.         }
  114. */

  115. /*
  116. **简化版,对比上面可读性不强,运行速度并不比前面的快。
  117. */
  118.          newnode->fwd = next;
  119.      thist->fwd = newnode;
  120.         if(thist!=rootp)         
  121.             newnode->bwd = thist;
  122.         else                     
  123.                 newnode->bwd = NULL;       
  124.         if(next != NULL)   
  125.             next->bwd = newnode;
  126.         else   
  127.             rootp->bwd = newnode;

  128.   return 1;  
  129. }

  130. /*双链表的删除
  131. ** 把一个值插入到双链表,rootp是一个指向根节点的指针
  132. ** del 是指向欲移除节点的指针
  133. ** 返回值:
  134. ** 如果链表不包含移除的节点,函数就返回假,否则返回真。
  135. */
  136. int dll_remove(Node *rootp, Node *del)
  137. {
  138.     register  Node  *thist;
  139.         assert( del != NULL);
  140.         for(thist=rootp->fwd; thist != NULL; thist = thist->fwd)
  141.             if(thist == del)
  142.                       break;
  143.         if(thist == del)
  144.         {
  145.                 /*
  146.         ** Update fwd pointer of the previous node.
  147.         */
  148.         if( thist->bwd == NULL )
  149.                         rootp->fwd = thist->fwd;
  150.         else
  151.            thist->bwd->fwd = thist->fwd;
  152.          /*
  153.          ** Update bwd pointer of the next node.
  154.          */
  155.         if( thist->fwd == NULL )
  156.             rootp->bwd = thist->bwd;
  157.        else
  158.            thist->fwd->bwd = thist->bwd;
  159.         free( thist );
  160.         return TRUE;
  161.         }
  162.         else
  163.                 return FALSE;
  164.        
  165. }


airwill 发表于 2018-10-23 07:14 | 显示全部楼层
双向链表作为一种数据结构, 确实很常用. 比如 UCOS 也用这个来管理任务.
不过让单片机处理这个还是有点麻烦, 特别是8位机要尽量避免
您需要登录后才可以回帖 登录 | 注册

本版积分规则

293

主题

3837

帖子

81

粉丝
快速回复 在线客服 返回列表 返回顶部