AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

双向链表

2017-09-11 980
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

 

来源：http://blog.csdn.net/hopeyouknow/article/details/6716177

首先编写头文件，头文件里做相关的定义和声明，DList.h内容如下：

[cpp]  view plain copy
  1. #ifndef DList_H  
  2. #define DList_H  
  3. typedef  int Item;  
  4. typedef struct Node * PNode;  
  5. typedef PNode Position;  
  6. /*定义节点类型*/  
  7. typedef struct Node  
  8. {  
  9.     Item data;      /*数据域*/  
  10.     PNode previous; /*指向前驱*/  
  11.     PNode next;     /*指向后继*/  
  12. }Node;  
  13. /*定义链表类型*/  
  14. typedef struct  
  15. {  
  16.     PNode head;     /*指向头节点*/  
  17.     PNode tail;     /*指向尾节点*/  
  18.     int size;  
  19. }DList;  
  20.   
  21. /*分配值为i的节点，并返回节点地址*/  
  22. Position MakeNode(Item i);  
  23.   
  24. /*释放p所指的节点*/  
  25. void FreeNode(PNode p);  
  26.   
  27. /*构造一个空的双向链表*/  
  28. DList* InitList();  
  29.   
  30. /*摧毁一个双向链表*/  
  31. void DestroyList(DList *plist);  
  32.   
  33. /*将一个链表置为空表，释放原链表节点空间*/  
  34. void ClearList(DList *plist);  
  35.   
  36. /*返回头节点地址*/  
  37. Position GetHead(DList *plist);  
  38.   
  39. /*返回尾节点地址*/  
  40. Position GetTail(DList *plist);  
  41.   
  42. /*返回链表大小*/  
  43. int GetSize(DList *plist);  
  44.   
  45. /*返回p的直接后继位置*/  
  46. Position GetNext(Position p);  
  47.   
  48. /*返回p的直接前驱位置*/  
  49. Position GetPrevious(Position p);  
  50.   
  51. /*将pnode所指节点插入第一个节点之前*/  
  52. PNode InsFirst(DList *plist,PNode pnode);  
  53.   
  54. /*将链表第一个节点删除并返回其地址*/  
  55. PNode DelFirst(DList *plist);  
  56.   
  57. /*获得节点的数据项*/  
  58. Item GetItem(Position p);  
  59.   
  60. /*设置节点的数据项*/  
  61. void SetItem(Position p,Item i);  
  62.   
  63. /*删除链表中的尾节点并返回其地址，改变链表的尾指针指向新的尾节点*/  
  64. PNode Remove(DList *plist);  
  65.   
  66. /*在链表中p位置之前插入新节点S*/  
  67. PNode InsBefore(DList *plist,Position p,PNode s);  
  68.   
  69. /*在链表中p位置之后插入新节点s*/  
  70. PNode InsAfter(DList *plist,Position p,PNode s);  
  71.   
  72. /*返回在链表中第i个节点的位置*/  
  73. PNode LocatePos(DList *plist,int i);  
  74.   
  75. /*依次对链表中每个元素调用函数visit()*/  
  76. void ListTraverse(DList *plist,void (*visit)());  
  77. #endif  


接下来逐个实现其功能，DList.c内容如下：

[cpp]  view plain copy
  1. #include"DList.h"  
  2. #include<malloc.h>  
  3. #include<stdlib.h>  
  4. /*分配值为i的节点，并返回节点地址*/  
  5. Position MakeNode(Item i)  
  6. {  
  7.     PNode p = NULL;   
  8.     p = (PNode)malloc(sizeof(Node));  
  9.     if(p!=NULL)  
  10.     {  
  11.         p->data = i;  
  12.         p->previous = NULL;  
  13.         p->next = NULL;  
  14.     }     
  15.     return p;  
  16. }  
  17. /*释放p所指的节点*/  
  18. void FreeNode(PNode p)  
  19. {  
  20.      free(p);  
  21. }  
  22. /*构造一个空的双向链表*/  
  23. DList * InitList()  
  24. {  
  25.     DList *plist = (DList *)malloc(sizeof(DList));  
  26.     PNode head = MakeNode(0);   
  27.     if(plist!=NULL)  
  28.     {  
  29.         if(head!=NULL)  
  30.         {  
  31.             plist->head = head;  
  32.             plist->tail = head;  
  33.             plist->size = 0;  
  34.         }  
  35.         else  
  36.             return NULL;  
  37.     }  
  38.     return plist;  
  39. }  
  40.   
  41. /*摧毁一个双向链表*/  
  42. void DestroyList(DList *plist)  
  43. {  
  44.     ClearList(plist);  
  45.     free(GetHead(plist));  
  46.     free(plist);  
  47. }  
  48.   
  49. /*判断链表是否为空表*/  
  50. int IsEmpty(DList *plist)  
  51. {  
  52.     if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist))  
  53.         return 1;  
  54.     else  
  55.         return 0;  
  56. }  
  57. /*将一个链表置为空表，释放原链表节点空间*/  
  58. void ClearList(DList *plist)  
  59. {  
  60.     PNode temp,p;  
  61.     p = GetTail(plist);  
  62.     while(!IsEmpty(plist))  
  63.     {     
  64.         temp = GetPrevious(p);  
  65.         FreeNode(p);  
  66.         p = temp;  
  67.         plist->tail = temp;  
  68.         plist->size--;  
  69.     }  
  70. }  
  71.   
  72. /*返回头节点地址*/  
  73. Position GetHead(DList *plist)  
  74. {  
  75.     return plist->head;  
  76. }  
  77.   
  78. /*返回尾节点地址*/  
  79. Position GetTail(DList *plist)  
  80. {  
  81.     return plist->tail;  
  82. }  
  83.   
  84. /*返回链表大小*/  
  85. int GetSize(DList *plist)  
  86. {  
  87.     return plist->size;  
  88. }  
  89.   
  90. /*返回p的直接后继位置*/  
  91. Position GetNext(Position p)  
  92. {  
  93.     return p->next;  
  94. }  
  95.   
  96. /*返回p的直接前驱位置*/  
  97. Position GetPrevious(Position p)  
  98. {  
  99.     return p->previous;  
  100. }  
  101.   
  102. /*将pnode所指节点插入第一个节点之前*/  
  103. PNode InsFirst(DList *plist,PNode pnode)  
  104. {  
  105.     Position head = GetHead(plist);  
  106.   
  107.     if(IsEmpty(plist))  
  108.         plist->tail = pnode;  
  109.     plist->size++;  
  110.   
  111.     pnode->next = head->next;  
  112.     pnode->previous = head;  
  113.   
  114.     if(head->next!=NULL)  
  115.         head->next->previous = pnode;  
  116.     head->next = pnode;  
  117.       
  118.     return pnode;   
  119. }  
  120.   
  121. /*将链表第一个节点删除,返回该节点的地址*/  
  122. PNode DelFirst(DList *plist)  
  123. {  
  124.     Position head = GetHead(plist);  
  125.     Position p=head->next;  
  126.     if(p!=NULL)  
  127.     {  
  128.         if(p==GetTail(plist))  
  129.             plist->tail = p->previous;  
  130.         head->next = p->next;  
  131.         head->next->previous = head;  
  132.         plist->size--;  
  133.           
  134.     }     
  135.     return p;  
  136. }  
  137.   
  138. /*获得节点的数据项*/  
  139. Item GetItem(Position p)  
  140. {  
  141.     return p->data;  
  142. }  
  143.   
  144. /*设置节点的数据项*/  
  145. void SetItem(Position p,Item i)  
  146. {  
  147.     p->data = i;  
  148. }  
  149.   
  150. /*删除链表中的尾节点并返回地址，改变链表的尾指针指向新的尾节点*/  
  151. PNode Remove(DList *plist)  
  152. {  
  153.     Position p=NULL;  
  154.     if(IsEmpty(plist))  
  155.         return NULL;  
  156.     else  
  157.     {  
  158.         p = GetTail(plist);  
  159.         p->previous->next = p->next;  
  160.         plist->tail = p->previous;  
  161.         plist->size--;  
  162.         return p;  
  163.     }  
  164. }  
  165. /*在链表中p位置之前插入新节点s*/  
  166. PNode InsBefore(DList *plist,Position p,PNode s)  
  167. {  
  168.     s->previous = p->previous;  
  169.     s->next = p;  
  170.     p->previous->next = s;      
  171.     p->previous = s;  
  172.   
  173.     plist->size++;  
  174.     return s;  
  175. }  
  176. /*在链表中p位置之后插入新节点s*/  
  177. PNode InsAfter(DList *plist,Position p,PNode s)  
  178. {  
  179.     s->next = p->next;  
  180.     s->previous = p;  
  181.       
  182.     if(p->next != NULL)  
  183.         p->next->previous = s;  
  184.     p->next = s;  
  185.       
  186.     if(p = GetTail(plist))  
  187.         plist->tail = s;  
  188.       
  189.     plist->size++;  
  190.     return s;  
  191. }  
  192.   
  193. /*返回在链表中第i个节点的位置*/  
  194. PNode LocatePos(DList *plist,int i)  
  195. {  
  196.     int cnt = 0;  
  197.     Position p = GetHead(plist);  
  198.     if(i>GetSize(plist)||i<1)  
  199.         return NULL;  
  200.   
  201.     while(++cnt<=i)  
  202.     {  
  203.         p=p->next;  
  204.     }  
  205.   
  206.     return p;  
  207. }  
  208.   
  209. /*依次对链表中每个元素调用函数visit()*/  
  210. void ListTraverse(DList *plist,void (*visit)())  
  211. {  
  212.     Position p = GetHead(plist);  
  213.     if(IsEmpty(plist))  
  214.         exit(0);  
  215.     else  
  216.     {  
  217.           
  218.         while(p->next!=NULL)  
  219.         {  
  220.             p = p->next;  
  221.             visit(p->data);            
  222.         }         
  223.     }  
  224. }  


接下来进行测试，Test.h内容如下：

[cpp]  view plain copy
  1. #include"DList.h"  
  2. #include<stdio.h>  
  3. void print(Item i)  
  4. {  
  5.     printf("数据项为%d \n",i);  
  6. }  
  7. main()  
  8. {  
  9.     DList *plist = NULL;  
  10.     PNode p = NULL;  
  11.       
  12.     plist = InitList();  
  13.     p = InsFirst(plist,MakeNode(1));  
  14.     InsBefore(plist,p,MakeNode(2));  
  15.     InsAfter(plist,p,MakeNode(3));  
  16.   
  17.     printf("p前驱位置的值为%d\n",GetItem(GetPrevious(p)));  
  18.     printf("p位置的值为%d\n",GetItem(p));  
  19.     printf("p后继位置的值为%d\n",GetItem(GetNext(p)));  
  20.       
  21.       
  22.     printf("遍历输出各节点数据项:\n");  
  23.     ListTraverse(plist,print);  
  24.     printf("除了头节点该链表共有%d个节点\n",GetSize(plist));  
  25.     FreeNode(DelFirst(plist));  
  26.     printf("删除第一个节点后重新遍历输出为:\n");  
  27.     ListTraverse(plist,print);  
  28.     printf("除了头节点该链表共有%d个节点\n",GetSize(plist));  
  29.     DestroyList(plist);  
  30.     printf("链表已被销毁\n");  
  31. }  

 





本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3272639.html，如需转载请自行联系原作者

文章标签：
C++
长征4号
目录
相关文章
叫个什么名字
|
算法 JavaScript 前端开发
编码之舞：我的技术感悟之旅
在编程的世界里，代码不仅仅是冷冰冰的文字排列，它们更像是一种艺术的表达。本文通过个人的技术成长经历，探讨如何将编程转化为一种创造性的活动，以及在技术探索中如何找到乐趣和成就感。文章旨在分享从初学者到资深开发者的转变过程中的心得体会，鼓励读者以积极的心态面对技术挑战，享受编程带来的乐趣。
叫个什么名字
90 1
开发者小助理
|
人工智能 Kubernetes 小程序
开发者社区精选直播合集（二十七）| HaaS物联网最佳实践
HaaS（Hardware as a Service）物联网设备云端一体开发框架，整合阿里云、达摩院、平头哥技术，基于数亿物联网设备接入经验，提供积木式硬件开发能力，实现低代码快速开发，帮助中小开发者聚焦业务，实现设备安全上云，加速设备创新迭代。
开发者小助理
424 4
开发者社区精选直播合集（二十七）| HaaS物联网最佳实践
YOLO创新改进大师
|
移动开发
数字三角形-动态规划-无
数字三角形-动态规划-无
YOLO创新改进大师
159 0
bbskkb
|
Linux 弹性计算 数据库
基于阿里云产品的服务器演进-单机
公司创办初期，基于成本，以及用户访问量的因素，需要选择合适的云产品搭建应用。本文基于阿里云现有云产品进行分析，提供合理的选型建议。
bbskkb
502 0
基于阿里云产品的服务器演进-单机
2025「AI安全」全球攻防赛小编
|
4天前
|
人工智能 运维 安全
亚太厂商唯一！阿里云以应用身份服务IDaaS入选全球 Gartner Access Management 魔力象限
中国厂商0→1突破
2025「AI安全」全球攻防赛小编
1477 11
2025「AI安全」全球攻防赛小编
|
11天前
|
人工智能 自然语言处理 安全
双第一！阿里云领跑安全运营智能体
喜报～
2025「AI安全」全球攻防赛小编
2148 8
游客geb4fgnutonte
|
5天前
|
搜索推荐 编译器 Linux
一个可用于企业开发及通用跨平台的Makefile文件
一款适用于企业级开发的通用跨平台Makefile，支持C/C++混合编译、多目标输出（可执行文件、静态/动态库）、Release/Debug版本管理。配置简洁，仅需修改带`MF_CONFIGURE_`前缀的变量，支持脚本化配置与子Makefile管理，具备完善日志、错误提示和跨平台兼容性，附详细文档与示例，便于学习与集成。
游客geb4fgnutonte
307 116
阿里云万网官方
|
20天前
|
域名解析 人工智能
【实操攻略】手把手教学，免费领取.CN域名
即日起至2025年12月31日，购买万小智AI建站或云·企业官网，每单可免费领1个.CN域名首年！跟我了解领取攻略吧~
阿里云万网官方
2289 9
modelscope
|
7天前
|
数据采集 人工智能 自然语言处理
Meta SAM3开源：让图像分割，听懂你的话
Meta发布并开源SAM 3，首个支持文本或视觉提示的统一图像视频分割模型，可精准分割“红色条纹伞”等开放词汇概念，覆盖400万独特概念，性能达人类水平75%–80%，推动视觉分割新突破。
modelscope
504 45
Meta SAM3开源：让图像分割，听懂你的话

热门文章

最新文章

  • 1
    java实现图片与base64转换
  • 2
    OpenSearch大模型实践之Havenask篇
  • 3
    Pycharm2022最新版安装破解与激活教程，亲测可用
  • 4
    阿里云内网可用的dns
  • 5
    Linux的root账号忘记密码怎么办？看这一篇就够了！
  • 6
    使用阿里云容器服务Jenkins 2.0实现持续集成之the tag you want篇(updated on 2017.09.06)
  • 7
    Skia深入分析8——Skia的GPU绘图
  • 8
    1918年就诞生了比Zoom酷太多的视频聊天设想！而那时才刚有无线电
  • 9
    Windows Phone 7 网络编程之留言板应用
  • 10
    Linux驱动 读写文件【转】
  • 1
    构建AI智能体：三十八、告别“冷启动”：看大模型如何解决推荐系统的世纪难题
    53
  • 2
    HTML文档的基本结构：构建网页的基石
    62
  • 3
    BipedalWalker实战：SAC算法如何让机器人学会稳定行走
    158
  • 4
    快速恢复ie浏览器的正常使用
    57
  • 5
    云原生日志监控体系怎么做才不崩？一篇给你讲透采集、存储、分析、告警的最佳实践
    44
  • 6
    Prometheus 撑不住了？上 Thanos、Cortex、M3！一篇给你讲明白大规模监控的江湖
    48
  • 7
    ETL vs ELT：到底谁更牛？别被名字骗了，这俩是两种世界观
    45
  • 8
    告别繁琐判断：用PHP 8的匹配表达式优雅你的代码
    34
  • 9
    告别繁琐include！PHP自动加载优化全攻略
    145
  • 10
    告别混乱：用PHP 8的Match表达式优雅地简化你的条件逻辑
    24

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云负载均衡收费标准：ALB、NLB和CLB价格，包括LCU费用、实例费和公网带宽价格