【数据结构】顺序表的定义及实现方式

---

顺序表的定义

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

---

顺序表的实现

静态分配

在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。
在使用静态存储时，首先定义一个最大长度，然后声明顺序表，在声明的顺序表中使用数组存放数据元素，定义当前长度length，代码如下。
Sq：sequence（顺序，序列）

#include <stdio.h>// 静态存储
// 定义最大长度,最大为10个,所以只能存放10个
#define MaxSize 10
// 声明顺序表
typedef struct {// 用静态的数组存放数据元素int data[MaxSize];// 顺序表的当前长度int length;
}SqList; // 顺序表的类型定义

初始化顺序表
声明顺序表后，需要初始化顺序表，将所有数据元素设置为默认初始值，顺序表的初试长度设置为0（这一步必须做！！！）
如果没有初始化顺序表，则内存中会有遗留的脏数据，所以将length的值设置为0这一步必须做！！！
初始化代码如下：

#include <stdio.h>// 静态存储
// 定义最大长度,最大为10个,所以只能存放10个
#define MaxSize 10
// 声明顺序表
typedef struct {// 用静态的数组存放数据元素int data[MaxSize];// 顺序表的当前长度int length;
}SqList; // 顺序表的类型定义// 初始化顺序表
void InitList(SqList& L){for (int i = 0; i < MaxSize; i++) {// 将所有数据元素设置为默认初始值L.data[i] = 0;// 设置顺序表初试长度为0L.length = 0;}
}int main() {// 声明顺序表SqList L;// 初始化顺序表InitList(L);return 0;
}

注意：

• 使用静态分配时，如果数组存满了，就“放弃治疗”，因为顺序表的表长刚开始确定后就无法更改（存储空间是静态的）。
• 如果刚开始就声明一个很大的内存空间是没有必要的，这样会浪费存储资源。

动态分配

使用动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数组空间占满，就另外开辟一块更大的存储空间，替换原来的存储空间，而不需要为线性表一次性地划分所有空间。
动态分配使用“动态数组”实现，先定义一个初始长度，然后定义顺序表，在顺序表中用指针来动态分配数组，定义顺序表的最大容量和当前长度。

#include <stdio.h>
// 初始长度
#define InitSize 10
typedef struct {// 动态分配数组的指针ElemType *data;// 顺序表的最大容量int MaxSize;// 顺序表的当前长度int length;
}SeqList;

动态申请内存空间，动态释放内存空间（malloc，free）

初始动态分配内存语句： L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize)

• L.data：指向一整片连续的存储空间的起始地址。
• (ElemType *)：malloc 函数返回一个指针， 需要强制转型为你定义的数据元素类型指针。
• malloc：动态申请内存空间。
• InitSize：malloc 函数的参数，指明要分配多大的连续内存空间。

注意：使用malloc和free函数需要引入头文件 #include <stdlib.h>

#include <stdio.h>
#include <stdlib.h>
// 初始长度
#define InitSize 10
typedef struct {// 动态分配数组的指针int *data;// 顺序表的最大容量int MaxSize;// 顺序表的当前长度int length;
}SqList;
// 初始化顺序表
void InitList(SqList& L) {//申请一片连续的存储空间L.data = (int *)malloc(sizeof(int) * InitSize);// 设置顺序表初试长度为0L.length = 0;L.MaxSize = InitSize;
}
//动态插入数据，增加长度
void IncreaseSize(SqList& L, int len) {int* p = L.data;L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));for (int i = 0; i < L.length;i++) {// 将数据复制到新区域，但是这样使用时间开销大L.data[i] = p[i];}// 顺序表的最大长度增加lenL.MaxSize = L.MaxSize + len;// 释放原来的内存空间free(p);
}
int main() {// 声明顺序表SqList L;// 初始化顺序表InitList(L);//插入数据IncreaseSize(L, 6);return 0;
}

顺序表的特点

顺序表的特点有随机访问，存储密度高，拓展容量不方便，插入和删除数据元素不方便。

---

总结

以上就是今天的学习内容啦~
如果有兴趣的话可以订阅专栏，持续更新呢~
咱们下期再见~