顺序表的定义
顺序表也就是用顺序存储的方式实现线性表。 顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表的实现
静态分配
在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。 在使用静态存储时，首先定义一个最大长度，然后声明顺序表，在声明的顺序表中使用数组存放数据元素，定义当前长度length，代码如下。 Sq：sequence（顺序，序列）
代码语言：javascript复制#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;
// 设置顺序表初试长度为0
L.length = 0;
}
}
int main() {
// 声明顺序表
SqList L;
// 初始化顺序表
InitList(L);
return 0;
}注意：
- 使用静态分配时，如果数组存满了，就“放弃治疗”，因为顺序表的表长刚开始确定后就无法更改（存储空间是静态的）。
- 如果刚开始就声明一个很大的内存空间是没有必要的，这样会浪费存储资源。
动态分配
使用动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数组空间占满，就另外开辟一块更大的存储空间，替换原来的存储空间，而不需要为线性表一次性地划分所有空间。 动态分配使用“动态数组”实现，先定义一个初始长度，然后定义顺序表，在顺序表中用指针来动态分配数组，定义顺序表的最大容量和当前长度。
代码语言：javascript复制#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>
代码语言：javascript复制#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);
// 设置顺序表初试长度为0
L.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];
}
// 顺序表的最大长度增加len
L.MaxSize = L.MaxSize len;
// 释放原来的内存空间
free(p);
}
int main() {
// 声明顺序表
SqList L;
// 初始化顺序表
InitList(L);
//插入数据
IncreaseSize(L, 6);
return 0;
}顺序表的特点
顺序表的特点有随机访问，存储密度高，拓展容量不方便，插入和删除数据元素不方便。
