devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：从前慢现在也慢 | 2024-05-28 08:20:42

赞

踩

c语言单链表基本操作

目录

一、单链表

1、单链表的定义：

2、单链表的优缺点：

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

1、宏定义

2、创建结构体

3、初始化

4、插入

4、求长度

5、清空

6、销毁 

7、取值

8、查找

9、删除

10、头插法创建单链表

11、尾插法创建单链表

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

四、运行结果

一、单链表

1、单链表的定义：

 单链表是一种链式存储的线性表，它用一组地址任意的存储单元来存放线性表中的数据元素。每个节点包含两个部分：数据域和指针域。数据域用于存储数据元素，指针域则存储下一个节点的地址。单链表的第一个节点称为头结点，最后一个节点称为尾结点。

单链表是一种链式存取的数据结构，用一组地址任意的存储单元来存放线性表中的数据元素。

每个节点包含两个部分：数据域和指针域。数据域用于存储数据元素，指针域则存储下一个节点的地址。链表中的数据是以结点来表示的，每个结点的构成包括元素（数据元素的映像）和指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。链表中的每个结点在内存中不是按顺序排列的，而是通过指针链接在一起。单链表的第一个节点称为头结点，最后一个节点称为尾结点。

与顺序表相比，单链表的优点在于插入和删除操作方便，时间复杂度较低，但随机访问和空间利用率不如顺序表。在实际应用中，单链表通常作为其他数据结构的子结构，如哈希表的桶、图的邻接表等。

单链表定义了节点的基本结构，包括数据元素和指向下一个节点的指针。节点的插入和删除操作涉及指针的修改，而非直接修改节点内容。由于其非连续性的特性，链表无法像数组一样随机访问任意元素，而只能从头到尾依次访问。因此，对于需要频繁插入和删除元素的应用场景，单链表是一种高效的数据结构。

2、单链表的优缺点：

单链表的优点：

  1. 插入和删除操作方便：只需修改指针即可，不需要移动大量元素。
  2. 动态分配内存：可以根据需要开辟内存空间，避免了顺序表中的空间浪费问题。

单链表的缺点：

  1. 存储密度低：以节点为单位存储，不支持随机访问，查找较为麻烦。
  2. 空间利用率低：每个节点需要额外的空间来存储指针，导致空间浪费。
  3. 查找效率低：由于链表在内存中不连续，需要从头节点开始逐个节点遍历，时间复杂度较高。

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

1、宏定义
  1. #define OK 1
  2. #define ERROR 0
  3.  
  4. typedef char ElemType;
  5. typedef int Status;
2、创建结构体
  1. typedef struct LNode{
  2.     ElemType data;
  3.     struct LNode *next;
  4. }LNode,*LinkList;
3、初始化
  1. //单链表初始化
  2. Status InitList(LinkList &head){
  3.     head=new LNode;
  4.     head->next=NULL;
  5.     return OK;
  6. }
4、插入
  1. 创建一个新的结点。
  2. 将新结点的数据域置为所需插入的数据。
  3. 根据插入位置的不同，将新结点的指针域指向插入位置的后一个结点。如果是头部插入，则将新结点的指针域指向头结点；如果是尾部插入，则将新结点的指针域指向空；如果是中间插入，则将新结点的指针域指向插入位置的后一个结点。
  4. 将插入位置前一个结点的指针域修改为指向新结点。如果是头部插入，则将头结点的指针域修改为指向新结点；如果是尾部插入，则将尾结点的指针域修改为指向新结点；如果是中间插入，则将插入位置前一个结点的指针域修改为指向新结点。
  1. //插入
  2. Status ListInsert(LinkList &head,int i,ElemType e){
  3.     LinkList 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.     LNode *s=new LNode;
  14.     s->data=e;
  15.     s->next=p->next;
  16.     p->next=s;
  17.  
  18.     return OK;
  19. }
4、求长度
  1. //求单链表长度
  2. Status GetLinkListLength(LinkList head){
  3.     LinkList p=head->next;
  4.     int length=0;
  5.     while (p){
  6.         p=p->next;
  7.         length++;
  8.     }
  9.     return length;
  10. }
5、清空
  1.  
  2. //清空
  3. Status ClearLinkList(LinkList &head){
  4.     LinkList p = head->next;
  5.     LinkList q;
  6.     while(p){
  7.         q = p;
  8.         p = p->next;
  9.         delete q;
  10.     }
  11.     head->next = NULL;
  12.     return OK;
  13. }
6、销毁 
  1.  
  2. //销毁
  3. Status DestoryLinkList(LinkList &head){
  4.     LinkList p;
  5.     while(head){
  6.         p = head;
  7.         head = head->next;
  8.         delete p;
  9.     }
  10.     return OK;
  11. }
7、取值
  1. //取值
  2. Status GetLinkList(LinkList head,int i,ElemType &e){
  3.     LinkList p = head->next;
  4.     int j = 0;
  5.     while (p && j<i){
  6.         p=p->next;
  7.         j++;
  8.     }
  9.     if (!p || j>i){
  10.         return ERROR;
  11.     }
  12.     e=p->data;
  13.  
  14.     return OK;
  15. }
8、查找
  1. //查找用函数返回查找元素的位置
  2. int LocateLinkListElem(LinkList head,ElemType e){
  3.     LinkList p=head->next;
  4.     int j=1;
  5.     while (p && (p->data != e)){
  6.         p=p->next;
  7.         j++;
  8.     }
  9.     if(p==NULL){
  10.         return 0;
  11.     }
  12.     return j;
  13. }
9、删除
  1. 找到要删除的结点的前一个结点。
  2. 将前一个结点的指针域修改为指向要删除的结点的下一个结点。
  3. 释放要删除的结点的存储空间。
  1.  
  2. //删除
  3. Status ListDelete(LinkList &head,int i,ElemType &e){
  4.     LinkList p=head;
  5.     int j=0;
  6.     while ((p->next) && (j<i-1)){
  7.         p=p->next;
  8.         ++j;
  9.     }
  10.     if (!(p->next)||j>i-1){
  11.         return ERROR;
  12.     }
  13.     LinkList q=p->next;
  14.     e=q->data;
  15.     p->next=q->next;
  16.     delete q;
  17.     return OK;
  18. }
10、头插法创建单链表
  1. //头插法创建单链表
  2. void CreateList_H(LinkList &head,int n){
  3.     head=new LNode;
  4.     head->next=NULL;
  5.     for(int i=0;i<n;++i){
  6.         LNode *p=new LNode;
  7.         ElemType cin='a';
  8.         cin>>p->data;
  9.         p->next=head->next;
  10.         head->next=p;
  11.     }
  12. }
11、尾插法创建单链表
  1. //尾插法创建单链表
  2. void CreateList_R(LinkList &head,int n){
  3.     head=new LNode;
  4.     head->next=NULL;
  5.     LNode *r=head;
  6.     for(int i=0;i<n;++i){
  7.         LNode *p=new LNode;
  8.         ElemType cin='a';
  9.         cin>>p->data;
  10.         p->next=NULL;
  11.         r->next=p;
  12.         r=p;
  13.     }
  14. }

三、单链表的全部代码（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 LNode{
  10.     ElemType data;
  11.     struct LNode *next;
  12. }LNode,*LinkList;
  13.  
  14. //单链表初始化
  15. Status InitList(LinkList &head){
  16.     head=new LNode;
  17.     head->next=NULL;
  18.     return OK;
  19. }
  20.  
  21. //功能菜单
  22. int choice() {
  23.     printf("==================================\n");
  24.     printf("         单链表操作功能菜单          \n");
  25.     printf("1、插入元素  2、查询表长  3、按位查找\n");
  26.     printf("4、按值查找  5、删除元素  6、销毁链表\n");
  27.     printf("7、清空链表  8、批量插入  9、结束程序\n");
  28.     printf("10、头插法创建单链表11、尾插法创建单链表\n");
  29.     printf("==================================\n");
  30.     return 0;
  31. }
  32.  
  33.  
  34. //插入
  35. Status ListInsert(LinkList &head,int i,ElemType e){
  36.     LinkList 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.     LNode *s=new LNode;
  47.     s->data=e;
  48.     s->next=p->next;
  49.     p->next=s;
  50.  
  51.     return OK;
  52. }
  53.  
  54. //求单链表长度
  55. Status GetLinkListLength(LinkList head){
  56.     LinkList p=head->next;
  57.     int length=0;
  58.     while (p){
  59.         p=p->next;
  60.         length++;
  61.     }
  62.     return length;
  63. }
  64.  
  65. //销毁
  66. Status DestoryLinkList(LinkList &head){
  67.     LinkList p;
  68.     while(head){
  69.         p = head;
  70.         head = head->next;
  71.         delete p;
  72.     }
  73.     return OK;
  74. }
  75.  
  76. //清空
  77. Status ClearLinkList(LinkList &head){
  78.     LinkList p = head->next;
  79.     LinkList q;
  80.     while(p){
  81.         q = p;
  82.         p = p->next;
  83.         delete q;
  84.     }
  85.     head->next = NULL;
  86.     return OK;
  87. }
  88.  
  89. //取值
  90. Status GetLinkList(LinkList head,int i,ElemType &e){
  91.     LinkList p = head->next;
  92.     int j = 0;
  93.     while (p && j<i){
  94.         p=p->next;
  95.         j++;
  96.     }
  97.     if (!p || j>i){
  98.         return ERROR;
  99.     }
  100.     e=p->data;
  101.  
  102.     return OK;
  103. }
  104.  
  105.  
  106. //查找用引用型参数返回查找元素的位置
  107. //LNode *LocateLinkList(LinkList head,ElemType e,Status &j){
  108. //    LinkList p=head->next;
  109. //    j=1;
  110. //    while (p && p->data!=e){
  111. //        p=p->next;
  112. //        j++;
  113. //    }
  114. //    return p;
  115. //}
  116. //查找用函数返回查找元素的位置
  117. int LocateLinkListElem(LinkList head,ElemType e){
  118.     LinkList p=head->next;
  119.     int j=1;
  120.     while (p && (p->data != e)){
  121.         p=p->next;
  122.         j++;
  123.     }
  124.     if(p==NULL){
  125.         return 0;
  126.     }
  127.     return j;
  128. }
  129.  
  130. //删除
  131. Status ListDelete(LinkList &head,int i,ElemType &e){
  132.    LinkList p=head;
  133.     int j=0;
  134.    while ((p->next) && (j<i-1)){
  135.        p=p->next;
  136.        ++j;
  137.     }
  138.  
  139.     if (!(p->next)||j>i-1){
  140.         return ERROR;
  141.     }
  142.     LinkList q=p->next;
  143.     e=q->data;
  144.     p->next=q->next;
  145.     delete q;
  146.     return OK;
  147. }
  148.  
  149. //头插法创建单链表
  150. void CreateList_H(LinkList &head,int n){
  151.     head=new LNode;
  152.     head->next=NULL;
  153.     for(int i=0;i<n;++i){
  154.         LNode *p=new LNode;
  155.         ElemType cin='a';
  156.         cin>>p->data;
  157.         p->next=head->next;
  158.         head->next=p;
  159.     }
  160. }
  161.  
  162.  
  163. //尾插法创建单链表
  164. void CreateList_R(LinkList &head,int n){
  165.     head=new LNode;
  166.     head->next=NULL;
  167.     LNode *r=head;
  168.     for(int i=0;i<n;++i){
  169.         LNode *p=new LNode;
  170.         ElemType cin='a';
  171.         cin>>p->data;
  172.         p->next=NULL;
  173.         r->next=p;
  174.         r=p;
  175.     }
  176. }
  177.  
  178. int main()
  179. {
  180.     LinkList list;
  181.  
  182.     //初始化
  183.     printf("单链表正在初始化....\n");
  184.     int InitStatus=InitList(list);
  185.     if (InitStatus=OK){
  186.         printf("单链表初始化成功！\n");
  187.     }else{
  188.         printf("单链表初始化失败！\n");
  189.     }
  190.  
  191.     choice();    //调用功能菜单函数
  192.     int temp=1;  //通过改变temp的值来跳出while循环
  193.  
  194.     while(temp) {
  195.         int flag;
  196.         printf("请输入所需的功能编号：\n");
  197.         scanf("%d",&flag);
  198.  
  199.         switch (flag) {//通过开关进行功能选择
  200.             case 1:{//插入元素
  201.                 int insertIndex;
  202.                 ElemType inserElem;
  203.                 printf("请输入插入元素位置及插入元素(请在英文状态下输入): \n");
  204.                 scanf("%d,%c",&insertIndex,&inserElem);
  205.                 Status InsertS = ListInsert(list, insertIndex, inserElem);
  206.                 if(InsertS ==OK){
  207.                     printf("向单链表%d个位置,插入元素为%c成功！\n",insertIndex,inserElem);
  208.                     printf("======================================\n\n");
  209.                 }else{
  210.                     printf("向单链表插入元素失败！\n");
  211.                     printf("======================================\n\n");
  212.                 }
  213.             }
  214.                 break;
  215.             case 2:{//求单链表的长度
  216.                 int length=GetLinkListLength(list);
  217.                 printf("单链表的长度为:%d。 \n",length);
  218.             }
  219.                 break;
  220.             case 3:{//取值
  221.                 Status GetIndex;
  222.                 printf("请输入需要查询的元素的位置：\n");
  223.                 scanf("%d",&GetIndex);
  224.                 ElemType GetElem;
  225.                 int GetStatus=GetLinkList(list,GetIndex, GetElem);
  226.                 if (GetStatus=OK){
  227.                     printf("从单链表中获取第%d位置元素成功，所获取到的元素为：%c。\n",GetIndex,GetElem);
  228.                 }else{
  229.                     printf("从单链表中获取第%d位置元素失败！\n",GetIndex);
  230.                 }
  231.             }
  232.                 break;
  233.             case 4:{//查找
  234.                 //查找用引用型参数返回查找元素的位置
  235. //                Status LocateIndex;
  236. //                ElemType LocateElem;
  237. //                printf("请输入想要查找元素：\n");
  238. //                scanf("%c",&LocateElem);
  239. //                LNode *LocateStatus = LocateLinkList(list,LocateElem,LocateIndex);
  240. //                //printf("%d",LocateStatus);
  241. //                if (LocateStatus == NULL) {
  242. //                    printf("未查找到需要查找元素！\n");
  243. //                } else {
  244. //                    printf("查找到单链表中第%d元素为%c！\n",LocateIndex, LocateStatus->data);
  245. //                }
  246.                 //查找用函数返回查找元素的位置
  247.                 ElemType LocateElem;
  248.                 printf("请输入想要查找元素：\n");
  249.                 getchar();    //用于接收回车
  250.                 scanf("%c",&LocateElem);
  251.                 Status LocateIndex = LocateLinkListElem(list,LocateElem);
  252.                 if (LocateIndex > 0) {
  253.                     printf("从单链表中查找元素%c成功，它在单链表中的位置为第%d个！\n",LocateElem,LocateIndex);
  254.                 } else {
  255.                     printf("从单链表中查找元素%c失败！\n",LocateElem);
  256.                 }
  257.             }
  258.                 break;
  259.             case 5:{//删除
  260.                 Status DeleteIndex;
  261.                 printf("请输入想要删除元素的位置：\n");
  262.                 scanf("%d",&DeleteIndex);
  263.                 ElemType DeleteElem;
  264.                 ElemType DeleteStatus = ListDelete(list,DeleteIndex,DeleteElem);
  265.                 if (DeleteStatus=OK){
  266.                     printf("删除单链表第%d个位置的元素成功，删除的元素为：%c。\n",DeleteIndex,DeleteElem);
  267.                 }else{
  268.                     printf("删除单链表第%d个位置的元素失败！\n",DeleteIndex);
  269.                 }
  270.             }
  271.                 break;
  272.             case 6:{//销毁
  273.                 Status DestoryStatus = DestoryLinkList(list);
  274.                 if (DestoryStatus == OK){
  275.                     printf("单链表销毁成功！\n");
  276.                 }else{
  277.                     printf("单链表销毁失败！\n");
  278.                 }
  279.             }
  280.                 break;
  281.             case 7:{//清空
  282.                 Status ClearStatus = ClearLinkList(list);
  283.                 if (ClearStatus == OK){
  284.                     printf("单链表清空成功！\n");
  285.                 }else{
  286.                     printf("单链表清空失败！\n");
  287.                 }
  288.             }
  289.                 break;
  290.             case 8:{//批量插入
  291.                 int on;
  292.                 printf("请输入想要插入的元素个数：\n");
  293.                 scanf("%d", &on);
  294.                 ElemType array[on];
  295.                 for (int i = 1; i <= on; i++) {
  296.                     getchar();
  297.                     printf("向单链表第%d个位置插入元素为:", (i));
  298.                     scanf("%c", &array[i]);
  299.                 }
  300.  
  301.                 for (int i = 1; i <= on; i++){
  302.                     Status InsertStatus = ListInsert(list,i,array[i]);
  303.                     if (InsertStatus=OK){
  304.                         printf("向单链表第%d个位置插入元素%c成功！\n",i,array[i]);
  305.                     }else{
  306.                         printf("向单链表第%d个位置插入元素%c失败！\n",i,array[i]);
  307.                     }
  308.                 }
  309.             }
  310.                 break;
  311.             case 9:{//退出程序
  312.                 temp=0;
  313. //               return 0;
  314.             }
  315.                 break;
  316.             case 10:{//头插法创建单链表
  317. //                ElemType EnterElement='e';
  318. //                CreateList_H(list,EnterElement);
  319. //                printf("前插法插入%c元素成功！\n",EnterElement);
  320.             }
  321.                 break;
  322.             case 11:{//尾插法创建单链表
  323. //                ElemType EnterElem='a';
  324. //                CreateList_R(list,EnterElem);
  325. //                printf("后插法插入%c元素成功！\n",EnterElem);
  326.             }
  327.                 break;
  328.             default:
  329.                 printf("输入错误，无此功能，请检查输入:\n");
  330.         }
  331.     }
  332.  
  333. }

四、运行结果

 

 

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

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

  

闽ICP备14008679号