顺序表的定义
顺序表：用顺序存储的方式来实现线性表
顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
如何知道一个数据元素的大小？
- C语言：sizeof(ElemType)
sizeof(int) = 4B
顺序表的实现方式
静态分配
#define MaxSize 10 // 定义最大长度
typedef struct{
ElemType data[MaxSize];// 用静态的“数组”存放数据元素
int length;// 顺序表的当前长度
}SqList;// 顺序表的类型定义（静态分配的方式）当定义了数组的长度就无法改变
Q：如果“数组”中数据存满了怎么办？
A：可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的）
Q：如果刚开始就声明一个很大的内存空间呢？
A：会存在很浪费的问题
#include <stdio.h>
#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; // 将所有数据元素设置为默认初始值
}
L.length = 0; // 顺序表的初始长度为0
}
int main(){
SqList L; // 声明一个顺序表
InitList(L);// 初始化顺序表
// ... 未完待续，后续操作
return 0;
}动态分配
#define InitSize 10 //顺序表的初始长度
typedef struct{ //指示动态分配数组的指针
ELemType *data; //顺序表的最大容量
int MaxSize; // 顺序表的当前长度
int length; // 顺序表的类型定义（动态分配的方式）
} SqList;
- C语言中 分别使用 --
malloc和free函数。malloc函数返回一个指针需要强制转型为你定义的数据元素的类型指针
L.data = (ElemType *) malloc (sizeof(ElemType*) * InitSize);
ElemType *表示你要申请的内存的数据类型sizeof(ElemType*) * InitSize表示的是申请的内存空间大小
- C++中使用
new和delete关键字
#include <stdlib.h>
#define InitSize 10 //默认的最大长度
typedef struct{
int *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的当前长度
}SeqList;
void InitList(SeqList &L){
// 用malloc函数申请一片连续的存储空间
L.data=(int *) malloc(InitSize * sizeof(int));
L.length =0;
L.MaxSize =InitSize;
}
// 增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int *)malloc ((L.MaxSize+len)*sizeof(int));
// 上面的malloc返回一个指针，需要强制转换
for(int i=0;i<L.length;i++){
L.data[i]=p[i]; // 复制到新的空间
}
L.MaxSize=L.MaxSize+len;
free(p); // 释放空间
}
int main(){
SeqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
// ……往顺序表中随便插入几个元素
IncreaseSize(L,5);
return 0;
}顺序表的特点
- 随机访问：即可以在O(1)时间内找到第i个元素。
- 存储密度高：每个节点只存储数据元素
- 拓展容量不方便（即采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
- 插入、删除操作不方便，需要移动大量的元素
顺序表的插入
ListInsert(&L,e)：插入操作。在表L中第i个位置上插入指定元素e。
以下代码是基于静态分配实现的顺序表，在动态分配实现上也雷同
#define MaxSize 10 // 定义最大长度
typedef struct{
int data[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义
void ListInsert(SqList &L,int i,int e){
for(int j=L.length;j>i;i--){
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;// 在位置i处放入e 注意位序、数组下标的关系，并从后面的元素依次移动
// 这里的i为数组的位序，是从1开始的
L.length++; // 长度加1
}
int main(){
SqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
ListInsert(L,2,3);
return 0;
}当调用以上的代码是，避免调用者的不规范时使用，比如：i 的范围应该在【1~length+1】，所以我们可以如下的完善相关的代码逻辑，重新编写插入函数如下：
bool ListInsert(SqList &L,int i,int e){
if(int < 1 || i > L.length + 1){
return false; // 判断i的范围是否有误
}
if(L.length >= MaxSize){
return false; // 当前的存储空间已满，不能插入
}
for(int j=L.length;j>i;j--){
L.data[j]=L.data[j-1]; // 将第i个元素及以后的元素后移
}
L.data[i-1] =e; // 将第i个元素及之后的元素后移
L.length ++; // 长度加1
return true;好的算法，应该具有“健壮性”，能够很好的处理异常情况，并给使用者反馈！
插入操作的时间复杂度：
问题规模：n = length(表长)
- 最好情况：新元素插入到表尾，不需要移动元素
i = n + 1，循环0次；最好时间复杂度 = O(1)
- 最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动
i = 1，循环n次；最坏时间复杂度 = O(n)
- 平均情况：假设新元素插入到任何一个位置的概率相同，即$ i =1,2,3...,length+1$的概率是$$p=\frac {1} {n+1}$$
i = 1，循环n次；
i = 2，循环n-次；
...
i = n+1，循环0次
平均循环次数 = $$np + (n+1)p +(n-2)p +...+1·p = \frac {n(n+1)}{2}\frac {1}{n+1}=\frac {n}{2}$$ ⇨平均时间复杂度 = O(n)
顺序表的删除
ListDelete(&L,i,&e)：删除操作。删除表L中的第i个位置的元素，并用e返回删除元素的值。
bool ListDelete(SqList &L,int i,int &e){
if(i<1||i>L.length){
return false; // 判读i的范围是否有效
}
e=L.data[i-1] // 将要被删除的元素赋值给e
for(int j=i<j<L.length;j++){
L.data[j-1]=L.data[j];
}
L.length--; // 顺序表的长度减1
return true;
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化一个顺序表
// ...此处省略一些代码，插入几个元素
int e = -1; //用变量e把删除的元素“带回来”
if(ListDelete(L,3,e)){
printf("已删除第3个元素，删除的元素值为=%d\n",e);
}else{
printf("位序i不合法，删除失败\n");
}
return 0;
}删除操作的时间复杂度
- 最好情况：删除表尾元素，不需要移动其他元素
i = n，循环0次；最好时间复杂度 = O(1)
- 最坏情况：删除时表头元素，需要将后续的n-1元素全都向前移动
i = 1，循环n-1次；最坏时间复杂度 = O(n)
- 平均情况：假设删除任何一个元素的概率相同，即 i = 1，2，3，… 的概率都是$$p = \frac {1} {n}$$
i = 1，循环n-1次；
i = 2，循环n-2次；
i = 3，循环n-3次；
……
i = n，循环0次
平均循环次数 = $$(n-1)p + (n-2)p + ... +1·p = \frac {n(n+1)}{2}\frac {1}{n} =\frac{n-1}{2}$$⇨平均时间复杂度 = O(n)
顺序表的查找
按位查找
GetElem(L,i)：按位查找操作。获取表中第i个位置的元素的值。
- 静态分配实现：
#define MaxSize 10 // 定义最大的长度
typedef struct {
ElemType data[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义（静态分配的方式）
ElemType GetElem(SqList L,int i){
return L.data[i-1]; // 因为这里传入的是查找的位序，所以是i-1
}- 动态分配实现：
#define InitSize 10 // 顺序表的初始长度
typedef struct{
ElemType *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的长度
}SeqList; // 顺序表的类型定义（动态分配方式）
ElemType GetElem(SeqList L,int i){
return L.data[i-1];
}时间复杂度：O(1)
由于顺序表的各个元素在内存中连续存放，因此可以根据起始位置和数据元素大小立即找到第i个元素 -- “随机存取”特性
按值查找
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值得元素。
#define InitSize 10 // 顺序表的初始长度
typedef struct{
ElemType *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的长度
}SeqList; // 顺序表的类型定义（动态分配方式）
// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ELemType e){
for(int i = 0; i<L.length;i++){
if(L.data[i]==e){
return i+1; // 数组下标为i的元素值等于e，返回其位序i+1
}
}
return 0; // 退出循环，说明查找失败！
}当查找的元素为`结构体类型或复杂类型不能使用==来比较！
Tips：
《数据结构》考研初试中，手写代码可以直接使用 “==”，无论ElemType是基本数据类型还是结构类型！
时间复杂度：
问题规模：n = L.length（表长）
- 最好情况：目标元素在表头
循环1次；最好时间复杂度 = O(1)
- 最坏情况：目标元素在表尾
循环n次；最坏情况复杂度 = O(n)
- 平均情况：假设目标元素出现在任何一个位置的概率相同，都是$$\frac{1}{n}$$
目标元素在第1位，循环1次
目标元素在第2位，循环2次
……
目标元素在第n位，循环n次
平均循环次数 = $$1·\frac{1}{n} + 2·\frac{1}{n} +……+n·\frac{1}{n} =\frac{n(n+1)}{2}\frac{1}{n} = \frac{n+1}{2}$$ ⇨平均时间复杂度 = O(n)
版权声明：文章转载请注明来源，如有侵权请联系删除！
