数据结构之顺序表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

顺序表

顺序表的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列

顺序表 ---用顺序存储的方式实现线性表。顺序存储---把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

如何知道一个数据元素大小？ sizeof(ElemType) ,ElemType 是顺序表中存放的数据元素类型。Eg: sizeof(int) = 4B,4字节

顺序表有两种实现方式 ---- 静态分配和动态分配。

静态分配申请固定大小的内存空间，大小一旦确定就无法改变，存在比较严重的缺陷，在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。

动态分配是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不像数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。C语言动态申请和释放内存空间的函数是 malloc，free 函数。它们的头文件是 #include <stdlib.h>。malloc 函数的参数，指明要分配多大的连续内存空间。

malloc的全称是memory allocation，malloc函数原型是 void * malloc(unsigned int size)；void 中文翻译为无类型，void * 就是无类型指针，可以指向任何类型的地址。malloc函数返回开辟空间的首地址，只接收一个形参，malloc函数是为了在内存的动态存储区中分配一个长度为size的连续空间。

接着看这句代码： int *p = (int *)malloc(sizeof(int));

其中的解释是：int *p代表一个以int类型地址为内容的指针变量，（int *) 是让计算机知道怎么去划分开辟的空间，就是以几个字节为单元去划分，int占4个字节。如果实在理解不了的话，先记住就行。

接下来就是如何用代码实现顺序表啦。

大概思路：首先先去了解一个顺序表里有什么属性，还可以设置一个表的初始长度（也可以反映出动态分配的内存空间大小）。顺序表的属性有顺序表的最大容量，以及目前顺序表的实际长度（顺序表的数据个数），从这些属性出发，用代码定义一个顺序表（假装先告诉计算机，我在你内部有了一个顺序表）。然后我们还要真正地创建出一个顺序表（动态分配的方式），再对顺序表的属性进行初始化，刚开始的顺序表肯定为空表，即实际长度为0，最大容量等于表的初始长度。

关于顺序表的增删改查操作，画图的话，很好理解，建议在网上找相关视频，自己再画图理解。代码刚开始先慢慢理解了，再模仿着，带着记忆，独立敲出来。

 1 #include <stdio.h>
 2 #include <malloc.h>
 3 #define InitSize 10  //表的初始长度
 4 typedef struct 
 5 {
 6     int *data;
 7     int MaxSize;//顺序表的最大容量
 8     int length; //顺序表的实际长度
 9 }SeqList;
10 void InitList(SeqList &L)//初始化函数的定义，引用做函数参数，可以简化指针修饰实参，就是在函数体内能直接改变实参的值
11 {
12     L.data = (int *)malloc(InitSize * sizeof(int));
13     L.length = 0;
14     L.MaxSize = InitSize;
15 }
16 bool InsertList(SeqList &L, int i, int e) //在L的位序 i 处插入元素e,用bool类型是为了给用户一个反馈
17 {
18     if(i < 1 || i > L.length+1) //判断插入的位置是否越界，length从0开始的，i是位序，位序比length大1，
19                                  //所以当i=length+1是临界值
20         return false;
21     if(L.length >= L.MaxSize) //判断顺序表是否已满
22         return false;
23     for(int j = L.length; j >= i; j--)//用for循环将第i个元素及之后的元素后移，这样才能把e放进去，自己画图能很好理解
24     {
25         L.data[j] = L.data[j-1]; //后移数据覆盖,等号是从右到左赋值
26     }
27     L.data[i-1] = e; //在位置i处放入e
28     L.length++; //更新当前长度
29     return true;
30 }
31 bool ShowList(SeqList &L) //显示出顺序表中的数据
32 {
33     if(L.length == 0)
34        return false;
35     for(int i = 0; i < L.length; i++)
36     {
37         printf("%d",L.data[i]);
38         printf(" ");
39     }
40     printf("\n");
41     return true;
42 }
43 bool DeleteList(SeqList &L, int i, int &e) //在L的位序 i 处删除元素e
44 {
45     if(i < 1 || i > L.length)//判断是否越界
46         return false;
47     e = L.data[i-1];//将被删除的元素赋值给e
48     for(int j = i; j < L.length; j++)//用for循环将第i个位置后的元素前移，自己画图理解
49     {
50         L.data[j-1] = L.data[j]; //前移数据覆盖
51     }
52     L.length--; //更新当前长度
53     return true;
54 }
55 int UpdateList(SeqList &L, int i, int num)//把位序为i的数修改为num
56 {
57     L.data[i-1] = num;
58     return L.data[i-1];
59 }
60 int GetList(SeqList &L, int i)//按位查找操作。获取表L中第 i 个位置的元素的值。
61 {
62     return L.data[i-1];//和访问普通数组的方法一样
63 }
64 int main()
65 {
66     SeqList L;//声明一个顺序表
67     InitList(L); //初始化函数的调用
68     InsertList(L,1,1);
69     InsertList(L,2,2);
70     InsertList(L,3,3);
71     InsertList(L,4,4);
72     InsertList(L,5,5);
73     printf("顺序表内的数据是：");
74     ShowList(L);
75     int e;
76     if(DeleteList(L,3,e)) //删除第3个位置上的数，并把这个数返回
77     {
78         printf("删除的数是：%d\n",e);
79     }
80     printf("顺序表内的数据是：");
81     ShowList(L);
82     printf("查找的数是：%d\n",GetList(L,1));//查找第1个位置上的数，并返回
83     printf("修改成功的数是：%d\n",UpdateList(L,1,0));//修改第1个位置上的数为0，并返回
84     printf("顺序表内的数据是：");
85     ShowList(L);    
86     
87     
88     return 0;
89 }