线性表的实现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.  
     }

总结

这篇好文章是转载于：学新通技术网