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

线性表的实现（C语言版）——详细代码_c语言实现线性表

作者：盐析白兔 | 2024-04-06 11:54:54

赞

踩

c语言实现线性表

文章目录

前言

      今天对数据结构中的线性表进行了重新的梳理和复盘，有了许多收获，并花了一些时间在Devc++上进行了顺序表的基本操作的实现。本文就介绍一下自己动手过程中的一些心得和这些代码的内容。（本人小白一个，如有不当之处，请各位大佬不吝指教，万分感谢！）

一、线性表是什么？

线性表是具有相同数据类型的n个数据元素的有限序列，分为顺序表和链表。（本文阐述的是顺序表的实现）。

二、实现步骤

1.引入头文件并定义一个宏常量

代码如下（示例）：

  1. #include <stdio.h>
  2. #include <stdlib.h>//malloc()、free()和exit()函数在这个头文件之中
  3. #define Max 10

2.定义顺序表的结构

代码如下（示例）：

  1. typedef struct{
  2.     int *data;//存放存储空间首地址的指针变量
  3.     int length;//线性表当前的元素个数
  4.     int Max_size;//线性表最大能存储的元素个数
  5. }Sqlist;//把该数据类型命名为Sqlist 

该处使用定义结构体的方法 

3.顺序表各种操作的实现（增删改查等）

代码如下（示例）：

  1. //线性表的初始化 
  2. void InitList(Sqlist &L){
  3.     L.data=(int*)malloc(sizeof(int)*Max);
  4.     L.length=0;
  5.     L.Max_size=Max;
  6.     if(L.data!=0)
  7.         printf("初始化成功！\n");
  8.     else     
  9.         printf("初始化失败！\n");
  10. }
  11. //逐一插入线性表元素 
  12. void Insert(Sqlist &L){
  13.     printf("请逐个输入你要插入的元素：\n");
  14.     for(int i=0;i<Max;i++){
  15.         scanf("%d",&L.data[i]);
  16.         L.length++;
  17.     }
  18. } 
  19. //按位置插入元素
  20. bool InsertElem(Sqlist &L){
  21.     int i,e;
  22.     printf("请输入插入位置和数据：\n");
  23.     scanf("%d%d",&i,&e);
  24.     if(i<1 || i>L.length+1)
  25.         return false;
  26.     if(L.length==L.Max_size)
  27.         return false;
  28.     for(int j=L.length;j>=i;j--){
  29.         L.data[j]=L.data[j-1];
  30.     }
  31.     L.data[i-1]=e;
  32.     L.length++;
  33.     return true;
  34. } 
  35. //按元素所在位置删除元素
  36. bool DeleElem(Sqlist &L){
  37.     int i;
  38.     printf("请输入你要删除的元素所在位置：\n");
  39.     scanf("%d",&i);
  40.     if(L.length==0){
  41.         printf("当前线性表为空\n");
  42.         return false;
  43.     }
  44.     if(i>L.length){
  45.         printf("超出当前元素个数！\n");
  46.         return false;
  47.     }
  48.     for(int j=i;j<L.length;j++){
  49.         L.data[j-1]=L.data[j];
  50.     }
  51.     L.length--;
  52.     printf("删除第%d个元素成功！\n",i);
  53.     return true;    
  54. }
  55. //清空线性表
  56. void ClearList(Sqlist &L){
  57.     L.length=0;//直接让当前元素个数为零即可 
  58.     printf("清空成功！\n");
  59. } 
  60. //按元素所在位置修改元素
  61. bool AlterElem(Sqlist &L){
  62.     int i,e;
  63.     printf("请输入你要修改的元素所在位置和新元素：\n");
  64.     scanf("%d%d",&i,&e);
  65.     if(L.length==0){
  66.         printf("当前线性表为空\n");
  67.         return false;
  68.     }
  69.     if(i>L.length){
  70.         printf("超出当前元素个数！\n");
  71.         return false;
  72.     }
  73.     L.data[i-1]=e;
  74.     printf("修改成功！\n");
  75.     return true;
  76. } 
  77. //按元素所在位置查询元素 
  78. bool GetElem(Sqlist &L){
  79.     int i;
  80.     printf("请输入你要查询的元素所在位置：\n");
  81.     scanf("%d",&i);
  82.     if(L.length==0){
  83.         printf("当前线性表为空\n");
  84.         return false;
  85.     }
  86.     if(i>L.length){
  87.         printf("超出当前元素个数！\n");
  88.         return false;
  89.     }
  90.     printf("线性表第%d个元素为：%d\n",i,L.data[i-1]);
  91.     return true;
  92. }
  93. /*扩充空间，第一次初始化的线性表的存储空间是有限的,
  94. 通过这个函数可以在空间不够时进行添加存储空间，
  95. 从而加大线性表的存储量，但需要对之前所有元素进行复制，
  96. 会加大时间复杂度 
  97. */ 
  98. void IncreaseL(Sqlist &L){
  99.     int *p,len;
  100.     printf("请输入你要扩充的存储单元数：\n");
  101.     scanf("%d",&len);
  102.     p=L.data;
  103.     L.data=(int*)malloc(sizeof(int)*(Max+len));
  104.     for(int i=0;i<L.length;i++){
  105.         L.data[i]=p[i];
  106.     }
  107.     L.Max_size+=len;
  108.     free(p);
  109.     printf("存储空间扩充成功！\n");
  110.     printf("当前存储空间为：%d\n",L.Max_size);
  111. }
  112. //打印线性表的元素 
  113. bool Print(Sqlist L){
  114.     if(L.length!=0){
  115.         printf("线性表元素：\n");
  116.         for(int i=0;i<L.length;i++){
  117.             printf("%d\t",L.data[i]);
  118.         }
  119.         printf("\n");
  120.         return true;
  121.     }
  122.     else{
  123.         printf("当前线性表为空！\n");
  124.         return false;
  125.     }    
  126. } 
  127. //菜单
  128. void Menu(){
  129.     printf("=================================\n");
  130.     printf("1.打印线性表\n");
  131.     printf("2.删除元素\n");
  132.     printf("3.插入元素\n");
  133.     printf("4.扩充存储空间\n");
  134.     printf("5.按位置查询数据\n");
  135.     printf("6.逐个插入数据\n");
  136.     printf("7.按位置修改数据\n");
  137.     printf("8.清空线性表\n");
  138.     printf("9.初始化\n");
  139.     printf("0.退出系统\n"); 
  140.     printf("请输入你要进行的操作：\n");
  141. }

4.主函数调用实现

代码如下（示例）：

  1. int main(){
  2.     Sqlist L;//声明一个线性表
  3.     InitList(L);//线性表的第一次初始化，为线性表分配存储空间 
  4.     int Choice; //定义与菜单相匹配的选择变量Choice 
  5.     while(1){//对菜单栏的打印和用户要做的选择进行循环更新 
  6.         Menu();//打印菜单 
  7.         scanf("%d",&Choice);//从键盘获取用户的选择 
  8.         switch(Choice){        //使用switch函数进行操作匹配 
  9.         case 1:Print(L);break; //打印线性表 
  10.         case 2:DeleElem(L);break;//删除一个元素 
  11.         case 3:InsertElem(L);break;//在指定位置插入元素 
  12.         case 4:IncreaseL(L);break;//增加指定数量的存储空间 
  13.         case 5:GetElem(L);break;//按位置查询线性表元素 
  14.         case 6:Insert(L);break;//按顺序逐个对线性表进行插入 
  15.         case 7:AlterElem(L);break;//修改指定位置元素 
  16.         case 8:ClearList(L);break;//一键清空线性表 
  17.         case 9:InitList(L);break;//对线性表进行初始化操作 
  18.         case 0:exit(0);//退出系统 
  19.         }
  20.     }
  21.     return 0;
  22. } 

该处使用switch()函数对每个函数方法进行调用以实现对应操作。

5.完整代码

代码如下（示例）：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define Max 10
  4. //定义线性表数据类型 
  5. typedef struct{
  6.     int *data;
  7.     int length;
  8.     int Max_size;
  9. }Sqlist;//把该数据类型命名为Sqlist 
  10. //线性表的初始化 
  11. void InitList(Sqlist &L){
  12.     L.data=(int*)malloc(sizeof(int)*Max);
  13.     L.length=0;
  14.     L.Max_size=Max;
  15.     if(L.data!=0)
  16.         printf("初始化成功！\n");
  17.     else     
  18.         printf("初始化失败！\n");
  19. }
  20. //逐一插入线性表元素 
  21. void Insert(Sqlist &L){
  22.     printf("请逐个输入你要插入的元素：\n");
  23.     for(int i=0;i<Max;i++){
  24.         scanf("%d",&L.data[i]);
  25.         L.length++;
  26.     }
  27. } 
  28. //按位置插入元素
  29. bool InsertElem(Sqlist &L){
  30.     int i,e;
  31.     printf("请输入插入位置和数据：\n");
  32.     scanf("%d%d",&i,&e);
  33.     if(i<1 || i>L.length+1)
  34.         return false;
  35.     if(L.length==L.Max_size)
  36.         return false;
  37.     for(int j=L.length;j>=i;j--){
  38.         L.data[j]=L.data[j-1];
  39.     }
  40.     L.data[i-1]=e;
  41.     L.length++;
  42.     return true;
  43. } 
  44. //按元素所在位置删除元素
  45. bool DeleElem(Sqlist &L){
  46.     int i;
  47.     printf("请输入你要删除的元素所在位置：\n");
  48.     scanf("%d",&i);
  49.     if(L.length==0){
  50.         printf("当前线性表为空\n");
  51.         return false;
  52.     }
  53.     if(i>L.length){
  54.         printf("超出当前元素个数！\n");
  55.         return false;
  56.     }
  57.     for(int j=i;j<L.length;j++){
  58.         L.data[j-1]=L.data[j];
  59.     }
  60.     L.length--;
  61.     printf("删除第%d个元素成功！\n",i);
  62.     return true;    
  63. }
  64. //清空线性表
  65. void ClearList(Sqlist &L){
  66.     L.length=0;//直接让当前元素个数为零即可 
  67.     printf("清空成功！\n");
  68. } 
  69. //按元素所在位置修改元素
  70. bool AlterElem(Sqlist &L){
  71.     int i,e;
  72.     printf("请输入你要修改的元素所在位置和新元素：\n");
  73.     scanf("%d%d",&i,&e);
  74.     if(L.length==0){
  75.         printf("当前线性表为空\n");
  76.         return false;
  77.     }
  78.     if(i>L.length){
  79.         printf("超出当前元素个数！\n");
  80.         return false;
  81.     }
  82.     L.data[i-1]=e;
  83.     printf("修改成功！\n");
  84.     return true;
  85. } 
  86. //按元素所在位置查询元素 
  87. bool GetElem(Sqlist &L){
  88.     int i;
  89.     printf("请输入你要查询的元素所在位置：\n");
  90.     scanf("%d",&i);
  91.     if(L.length==0){
  92.         printf("当前线性表为空\n");
  93.         return false;
  94.     }
  95.     if(i>L.length){
  96.         printf("超出当前元素个数！\n");
  97.         return false;
  98.     }
  99.     printf("线性表第%d个元素为：%d\n",i,L.data[i-1]);
  100.     return true;
  101. }
  102. /*扩充空间，第一次初始化的线性表的存储空间是有限的,
  103. 通过这个函数可以在空间不够时进行添加存储空间，
  104. 从而加大线性表的存储量，但需要对之前所有元素进行复制，
  105. 会加大时间复杂度 
  106. */ 
  107. void IncreaseL(Sqlist &L){
  108.     int *p,len;
  109.     printf("请输入你要扩充的存储单元数：\n");
  110.     scanf("%d",&len);
  111.     p=L.data;
  112.     L.data=(int*)malloc(sizeof(int)*(Max+len));
  113.     for(int i=0;i<L.length;i++){
  114.         L.data[i]=p[i];
  115.     }
  116.     L.Max_size+=len;
  117.     free(p);
  118.     printf("存储空间扩充成功！\n");
  119.     printf("当前存储空间为：%d\n",L.Max_size);
  120. }
  121. //打印线性表的元素 
  122. bool Print(Sqlist L){
  123.     if(L.length!=0){
  124.         printf("线性表元素：\n");
  125.         for(int i=0;i<L.length;i++){
  126.             printf("%d\t",L.data[i]);
  127.         }
  128.         printf("\n");
  129.         return true;
  130.     }
  131.     else{
  132.         printf("当前线性表为空！\n");
  133.         return false;
  134.     }    
  135. } 
  136. //菜单
  137. void Menu(){
  138.     printf("=================================\n");
  139.     printf("1.打印线性表\n");
  140.     printf("2.删除元素\n");
  141.     printf("3.插入元素\n");
  142.     printf("4.扩充存储空间\n");
  143.     printf("5.按位置查询数据\n");
  144.     printf("6.逐个插入数据\n");
  145.     printf("7.按位置修改数据\n");
  146.     printf("8.清空线性表\n");
  147.     printf("9.初始化\n");
  148.     printf("0.退出系统\n"); 
  149.     printf("请输入你要进行的操作：\n");
  150. } 
  151. //主函数 
  152. int main(){
  153.     Sqlist L;//声明一个线性表
  154.     InitList(L);//线性表的第一次初始化，为线性表分配存储空间 
  155.     int Choice; //定义与菜单相匹配的选择变量Choice 
  156.     while(1){//对菜单栏的打印和用户要做的选择进行循环更新 
  157.         Menu();//打印菜单 
  158.         scanf("%d",&Choice);//从键盘获取用户的选择 
  159.         switch(Choice){        //使用switch函数进行操作匹配 
  160.         case 1:Print(L);break; //打印线性表 
  161.         case 2:DeleElem(L);break;//删除一个元素 
  162.         case 3:InsertElem(L);break;//在指定位置插入元素 
  163.         case 4:IncreaseL(L);break;//增加指定数量的存储空间 
  164.         case 5:GetElem(L);break;//按位置查询线性表元素 
  165.         case 6:Insert(L);break;//按顺序逐个对线性表进行插入 
  166.         case 7:AlterElem(L);break;//修改指定位置元素 
  167.         case 8:ClearList(L);break;//一键清空线性表 
  168.         case 9:InitList(L);break;//对线性表进行初始化操作 
  169.         case 0:exit(0);//退出系统 
  170.         }
  171.     }
  172.     return 0;
  173. }

总结

以上就是今天要讲的内容，笔者认为，线性表的实现主要是对指针的理解，如果能够理解代码中线性表L中的data指针变量和初始化函数中malloc()函数所开辟的空间之间的关系，那么理解上面的代码将容易很多。本文仅仅简单介绍了顺序表的实现方法，希望对读者朋友有所帮助。

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

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

  

闽ICP备14008679号