Chinaunix首页 | 论坛 | 博客
  • 博客访问: 81778
  • 博文数量: 30
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2016-09-23 20:18
个人简介

linux 嵌入式 物联网 驱动 ARM-A9

文章分类

全部博文(30)

文章存档

2016年(30)

我的朋友

分类: C/C++

2016-09-24 20:26:26

原文地址:双链表操作 作者:Mrt-l

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

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

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

  16.     return rootp;
  17. }

  18. /*
  19.  * 把一个值插入到一个双链表中,rootp 是一个指向根节点的指针,value 是欲插入的新值。
  20.  * 返回值:如果 value 已在链表中,返回0;内存不足,返回-1;插入成功,返回1。
  21.  */

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

  33.     newnode = (Node *)malloc(sizeof(Node));
  34.     if (newnode == NULL)
  35.         return -1;
  36.     newnode->value = value;

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

  66. /*
  67.  * 从双链表中移除一个节点。
  68.  *
  69.  * rootp :包含链表根指针的节点的指针。
  70.  * delete:要删除的节点的指针。
  71.  */

  72. int dou_remove(Node *rootp, Node *delete)
  73. {
  74.     register Node *this;
  75.     assert(delete != NULL);

  76.     for (this = rootp; this != NULL; this = this->link)
  77.         if (this == delete)
  78.             break;

  79.     if (this == delete) {
  80.         // 更新 delete 节点的前面那个节点的 fwd 字段
  81.         if (this->bwd == NULL)
  82.             rootp->fwd = this->fwd;
  83.         else
  84.             this->bwd-fwd = this->fwd;

  85.         // 更新 delete 节点的后面那个节点的 bwd 字段
  86.         if (this->fwd == NULL)
  87.             rootp->bwd = this->bwd;
  88.         else
  89.             this->fwd->bwd = this->bwd;

  90.         free(this);
  91.         return TRUE;
  92.     }
  93.     else
  94.         return    FALSE;
  95. }

  96. int main()
  97. {
  98.     Node *rootp, *ptr;

  99.     // test function dll_insert1
  100.     rootp = creat_root();
  101.     dll_insert1(rootp, 10);
  102.     dll_insert1(rootp, 20);
  103.     dll_insert1(rootp, 30);

  104.     printf("the dou_link contains :");
  105.     for (ptr = rootp->fwd; ptr != NULL ; ptr = ptr->fwd) {
  106.             printf("%4d", ptr->value);
  107.     }    
  108.     printf("\n");

  109.     exit(0);    
  110. }
阅读(1079) | 评论(0) | 转发(0) |
0

上一篇:一个均匀绑定cpu的shell

下一篇:堆栈操作

给主人留下些什么吧!~~