devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】 双链表的基本操作 （C语言版）_双链表操作

作者：人工智能uu | 2024-07-14 21:30:36

赞

踩

双链表操作

目录

一、双链表

1、双链表的定义：

2、双链表表的优缺点： 

二、双链表的基本操作算法（C语言）

 1、宏定义

 2、创建结构体

3、双链表的初始化 

4、双链表表插入

5、双链表的查找

6、双链表的取值

7、求双链表长度

8、双链表的删除

9、双链表的清空

10、双链表的销毁

11、输出链表元素

三、双链表的全部代码（C语言）

四、运行结果

一、双链表

1、双链表的定义：

双链表也叫双向链表，是一种链表数据结构。它的每个数据结点包含两个指针，一个指向前一个结点，另一个指向后一个结点。这意味着从双向链表的任何节点都可以方便地访问其前驱或后继节点。通常，我们构造双向循环链表，它的特点是尾节点的指针域指向头结点，整个链表形成一个环。

 

2、双链表表的优缺点： 

双链表的优点：

  1. 可以方便地访问前驱和后继节点，既可以向前也可以向后遍历链表。
  2. 在某些情况下，双链表比单链表更节省空间，因为它不需要额外的指针来存储前驱和后继节点的信息。

双链表的缺点：

  1. 插入和删除节点相对复杂，需要更多的时间来调整指针。
  2. 双链表需要更多的存储空间，因为每个节点都需要额外的指针来存储前驱和后继节点的信息。

二、双链表的基本操作算法（C语言）

 1、宏定义
  1. #define OK 1
  2. #define ERROR 0
  3.  
  4. typedef char ElemType;
  5. typedef int Status;
 2、创建结构体
  1. typedef struct DuLNode {
  2.     ElemType data;
  3.     struct DuLNode *prior;
  4.     struct DuLNode *next;
  5. } DuLNode, *DuLinkList;
3、双链表的初始化 
  1. //双链表初始化
  2. Status DInitList(DuLinkList &head) {
  3.     head = new DuLNode;
  4.     head->prior = NULL;
  5.     head->next = NULL;
  6.     return OK;
  7. }
4、双链表表插入
  1. //插入
  2. Status DListInsert(DuLinkList &head, int i, ElemType e) {
  3.     DuLinkList p = head;
  4.     int j = 0;
  5.     while (p && (j < i - 1)) {
  6.         p = p->next;
  7.         ++j;
  8.     }
  9.     if (!p || j > i - 1) {
  10.         return ERROR;
  11.     }
  12.  
  13.     DuLNode *s = new DuLNode;
  14.     s->data = e;
  15.     s->next = p->next;
  16.     if(p->next != NULL){
  17.       p->next->prior = s;	
  18.     }
  19.     p->next = s;
  20.     s->prior = p;
  21.  
  22.     return OK;
  23. }
5、双链表的查找
  1.  
  2. //查找
  3. int DLocateLinkListElem(DuLinkList head, ElemType e) {
  4.     DuLinkList p = head->next;
  5.     int j = 1;
  6.     while (p && (p->data != e)) {
  7.         p = p->next;
  8.         j++;
  9.     }
  10.     if (p == NULL) { 
  11.         return 0;
  12.     }
  13.     return j;
  14. }
6、双链表的取值
  1. //取值
  2. Status DGetLinkList(DuLinkList head, int i, ElemType &e) {
  3.     DuLinkList p = head->next;
  4.     int j = 1;
  5.     while (p && j < i) {
  6.         p = p->next;
  7.         ++j;
  8.     }
  9.     if (p == NULL) {
  10.         return ERROR;
  11.     }
  12.     e = p->data;
  13.  
  14.     return OK;
  15. }
7、求双链表长度
  1. //求双链表长度
  2. Status DGetLinkListLength(DuLinkList head) {
  3.     DuLinkList p = head->next;
  4.     int length = 0;
  5.     while (p!=NULL) {            //单链表不为空表时
  6.         length++;
  7.         p = p->next;
  8.     }
  9.     return length;
  10. }
8、双链表的删除
  1. //删除
  2. Status DListDelete(DuLinkList &head, int i, ElemType &e) {
  3.     DuLinkList p = head;
  4.     int j = 0;
  5.     while (p && j < i - 1) {
  6.         p = p->next;
  7.         j++;
  8.     }
  9.  
  10.     if (!p) {
  11.         return ERROR;
  12.     }
  13.     DuLinkList q = p->next;
  14.     e = q->data;
  15. 	p->next = q->next;
  16.     if(q->next != NULL){
  17.     	q->next->prior=p;
  18.     }
  19.     delete q;
  20.     return OK;
  21. }
9、双链表的清空
  1. //清空
  2. Status DClearLinkList(DuLinkList &head) {
  3.     DuLinkList p = head->next;
  4.     DuLinkList q;
  5.     while (p) {
  6.         q = p;
  7.         p = p->next;
  8.         delete q;
  9.     }
  10.     head->next = NULL;
  11.     return OK;
  12. }
10、双链表的销毁
  1. //销毁
  2. Status DestoryDLinkList(DuLinkList &head) {
  3.     DuLinkList p;
  4.     while (head) {
  5.         p = head;
  6.         head = head->next;
  7.         delete p;
  8.     }
  9.     return OK;
  10. }
11、输出链表元素
  1. //输出链表元素
  2. void DprintLinkList(DuLinkList head) {
  3.     DuLinkList p = head->next;
  4.     while (p) {
  5.         printf("%c", p->data);
  6.         p = p->next;
  7.     }
  8.     printf("\n");
  9. }

三、双链表的全部代码（C语言）

  1. #include <stdio.h>
  2.  
  3. #define OK 1
  4. #define ERROR 0
  5.  
  6. typedef char ElemType;
  7. typedef int Status;
  8.  
  9. typedef struct DuLNode {
  10.     ElemType data;
  11.     struct DuLNode *prior;
  12.     struct DuLNode *next;
  13. } DuLNode, *DuLinkList;
  14.  
  15. //双链表初始化
  16. Status DInitList(DuLinkList &head) {
  17.     head = new DuLNode;
  18.     head->prior = NULL;
  19.     head->next = NULL;
  20.     return OK;
  21. }
  22.  
  23. //功能菜单
  24. int choice() {
  25.     printf("==================================\n");
  26.     printf("         双链表操作功能菜单        \n");
  27.     printf("1、插入元素  2、查询表长  3、按位查找\n");
  28.     printf("4、按值查找  5、删除元素  6、销毁链表\n");
  29.     printf("7、清空链表  8、批量插入  9、链表元素\n");
  30.     printf("==================================\n");
  31.     return 0;
  32. }
  33.  
  34. //插入
  35. Status DListInsert(DuLinkList &head, int i, ElemType e) {
  36.     DuLinkList p = head;
  37.     int j = 0;
  38.     while (p && (j < i - 1)) {
  39.         p = p->next;
  40.         ++j;
  41.     }
  42.     if (!p || j > i - 1) {
  43.         return ERROR;
  44.     }
  45.  
  46.     DuLNode *s = new DuLNode;
  47.     s->data = e;
  48.     s->next = p->next;
  49.     if(p->next != NULL){
  50.       p->next->prior = s;	
  51.     }
  52.     p->next = s;
  53.     s->prior = p;
  54.  
  55.     return OK;
  56. }
  57.  
  58. //查找
  59. int DLocateLinkListElem(DuLinkList head, ElemType e) {
  60.     DuLinkList p = head->next;
  61.     int j = 1;
  62.     while (p && (p->data != e)) {
  63.         p = p->next;
  64.         j++;
  65.     }
  66.     if (p == NULL) { 
  67.         return 0;
  68.     }
  69.     return j;
  70. }
  71.  
  72. //取值
  73. Status DGetLinkList(DuLinkList head, int i, ElemType &e) {
  74.     DuLinkList p = head->next;
  75.     int j = 1;
  76.     while (p && j < i) {
  77.         p = p->next;
  78.         ++j;
  79.     }
  80.     if (p == NULL) {
  81.         return ERROR;
  82.     }
  83.     e = p->data;
  84.  
  85.     return OK;
  86. }
  87.  
  88. //求双链表长度
  89. Status DGetLinkListLength(DuLinkList head) {
  90.     DuLinkList p = head->next;
  91.     int length = 0;
  92.     while (p!=NULL) {            //单链表不为空表时
  93.         length++;
  94.         p = p->next;
  95.     }
  96.     return length;
  97. }
  98.  
  99.  
  100. //删除
  101. Status DListDelete(DuLinkList &head, int i, ElemType &e) {
  102.     DuLinkList p = head;
  103.     int j = 0;
  104.     while (p && j < i - 1) {
  105.         p = p->next;
  106.         j++;
  107.     }
  108.  
  109.     if (!p) {
  110.         return ERROR;
  111.     }
  112.     DuLinkList q = p->next;
  113.     e = q->data;
  114. 	p->next = q->next;
  115.     if(q->next != NULL){
  116.     	q->next->prior=p;
  117.     }
  118.     delete q;
  119.     return OK;
  120. }
  121.  
  122.  
  123. //清空
  124. Status DClearLinkList(DuLinkList &head) {
  125.     DuLinkList p = head->next;
  126.     DuLinkList q;
  127.     while (p) {
  128.         q = p;
  129.         p = p->next;
  130.         delete q;
  131.     }
  132.     head->next = NULL;
  133.     return OK;
  134. }
  135.  
  136. //销毁
  137. Status DestoryDLinkList(DuLinkList &head) {
  138.     DuLinkList p;
  139.     while (head) {
  140.         p = head;
  141.         head = head->next;
  142.         delete p;
  143.     }
  144.     return OK;
  145. }
  146.  
  147. //输出链表元素
  148. void DprintLinkList(DuLinkList head) {
  149.     DuLinkList p = head->next;
  150.     while (p) {
  151.         printf("%c", p->data);
  152.         p = p->next;
  153.     }
  154.     printf("\n");
  155. }
  156.  
  157. int main() {
  158.  
  159.     DuLinkList Dlist;
  160.  
  161.     printf("双链表正在初始化....\n");
  162.     int InitStatus = DInitList(Dlist);
  163.     if (InitStatus == OK) {
  164.         printf("双链表初始化成功！\n");
  165.     } else {
  166.         printf("双链表初始化失败！\n");
  167.     }
  168.  
  169.     choice();
  170.  
  171.     while (1) {
  172.         int flag;
  173.         printf("请输入所需的功能编号：\n");
  174.         scanf("%d", &flag);
  175.  
  176.         switch (flag) {//通过开关进行功能选择
  177.             case 1: {//插入元素
  178.                 //ListInsert_Dul(Dlist,1,'a');
  179.                 int insertIndex;
  180.                 ElemType inserElem;
  181.                 printf("请输入插入元素位置及插入元素(请在英文状态下输入例如:1,a): \n");
  182.                 scanf("%d,%c", &insertIndex, &inserElem);
  183.                 Status InsertS = DListInsert(Dlist, insertIndex, inserElem);
  184.                 if (InsertS == OK) {
  185.                     printf("向双链表%d个位置,插入元素为%c成功！\n\n", insertIndex, inserElem);
  186.                 } else {
  187.                     printf("向双链表插入元素失败！\n\n");
  188.                 }
  189.             }
  190.                 break;
  191.             case 2: {//求单链表的长度
  192.                 int length = DGetLinkListLength(Dlist);
  193.                 printf("循环双链表的长度为:%d。 \n\n", length);
  194.             }
  195.                 break;
  196.             case 3: {//取值
  197.                 Status GetIndex;
  198.                 printf("请输入需要查询的元素的位置：\n");
  199.                 scanf("%d", &GetIndex);
  200.                 ElemType GetElem;
  201.                 int GetStatus = DGetLinkList(Dlist, GetIndex, GetElem);
  202.                 if (GetStatus == OK) {
  203.                     printf("从单链表中获取第%d位置元素成功，所获取到的元素为：%c。\n\n", GetIndex, GetElem);
  204.                 } else {
  205.                     printf("从单链表中获取第%d位置元素失败！\n\n", GetIndex);
  206.                 }
  207.             }
  208.                 break;
  209.             case 4: {//查找
  210.                 ElemType LocateElem;
  211.                 printf("请输入想要查找元素：\n");
  212.                 getchar();    //用于接收回车
  213.                 scanf("%c", &LocateElem);
  214.                 Status LocateIndex = DLocateLinkListElem(Dlist, LocateElem);
  215.                 if (LocateIndex > 0) {
  216.                     printf("从双链表中查找元素%c成功，它在循环链表中的位置为第%d个！\n\n", LocateElem, LocateIndex);
  217.                 } else {
  218.                     printf("从双链表中查找元素%c失败！\n\n", LocateElem);
  219.                 }
  220.             }
  221.                 break;
  222.             case 5: {//删除
  223.                 //ListDelete_DuL(list,1);
  224.                 Status DeleteIndex;
  225.                 printf("请输入想要删除元素的位置：\n");
  226.                 scanf("%d", &DeleteIndex);
  227.                 ElemType DeleteElem;
  228.                 ElemType DeleteStatus = DListDelete(Dlist, DeleteIndex, DeleteElem);
  229.                 if (DeleteStatus == OK) {
  230.                     printf("删除双链表第%d个位置的元素成功，删除的元素为：%c。\n\n", DeleteIndex, DeleteElem);
  231.                 } else {
  232.                     printf("删除双链表第%d个位置的元素失败！\n\n", DeleteIndex);
  233.                 }
  234.             }
  235.                 break;
  236.             case 6: {//销毁
  237.                 Status DestoryStatus = DestoryDLinkList(Dlist);
  238.                 if (DestoryStatus == OK) {
  239.                     printf("双环链表销毁成功！\n\n");
  240.                 } else {
  241.                     printf("双链表销毁失败！\n\n");
  242.                 }
  243.             }
  244.                 break;
  245.             case 7: {//清空
  246.                 Status ClearStatus = DClearLinkList(Dlist);
  247.                 if (ClearStatus == OK) {
  248.                     printf("双链表清空成功！\n\n");
  249.                 } else {
  250.                     printf("双链表清空失败！\n\n");
  251.                 }
  252.             }
  253.                 break;
  254.             case 8: {//批量插入
  255.                 int on;
  256.                 printf("请输入想要插入的元素个数：\n");
  257.                 scanf("%d", &on);
  258.                 ElemType array[on];
  259.                 for (int i = 1; i <= on; i++) {
  260.                     getchar();
  261.                     printf("向双链表第%d个位置插入元素为:", (i));
  262.                     scanf("%c", &array[i]);
  263.                 }
  264.  
  265.                 for (int i = 1; i <= on; i++) {
  266.                     Status InsertStatus = DListInsert(Dlist, i, array[i]);
  267.                     if (InsertStatus == OK) {
  268.                         printf("向双链表第%d个位置插入元素%c成功！\n", i, array[i]);
  269.                     } else {
  270.                         printf("向双链表第%d个位置插入元素%c失败！\n", i, array[i]);
  271.                     }
  272.                 }
  273.             }
  274.                 break;
  275.             case 9: {//输出链表元素
  276.                 DprintLinkList(Dlist);
  277.             }
  278.                 break;
  279.                
  280.             default: {
  281.                 printf("输入错误，无此功能，请检查输入:\n\n");
  282.             }
  283.         }
  284.     }
  285.  
  286.     return 1;
  287.  
  288. }

四、运行结果

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/826358
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号