1.2 线性表的顺序表示
大约 8 分钟
1.2 线性表的顺序表示
1.2.1 顺序表的定义
顺序表：线性表的顺序存储，它是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。
1.2.2 顺序表的特点
①随机访问：可直接通过下标访问
②存储密度高：每个节点只能存数据元素
③拓展容量不方便：即便采用动态分配方式，迁移数据时时间复杂度也比较高
④插入、删除操作不方便：需要移动大量元素
1.2.3 顺序表的实现方式
实现方式：静态分配和动态分配
1.2.4 静态分配的顺序表上的操作
静态分配的顺序表的优缺点
缺点：顺序表的表长确定后无法修改，存满了就存不了了
顺序表的类型描述
#define MaxSize 10; //定义最大长度
typedef struct{
int data[MaxSize]; //“静态”的数组存数据，存int数据
int length; //顺序表的当前长度
}SqList;
初始化
//初始化
void InitList(SqList &L){
for(int i=0; i<MaxSize; i++){
L.data=[i]=0; //将所有元素都设为默认值0
}
L.length=0; //顺序表长度初始为0
}
插入
//插入操作：在顺序表L的第i个(位序)上插入x
bool ListInsert(SqList &L, int i,int e){
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
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; //将e放到第i个位置
L.length++; //长度+1
}
插入的时间复杂度：
最好情况：插到表尾，不需移动元素，循环0次，最好时间复杂度=O(1)
最坏情况：插到表头，移动n个元素，循环n次，最坏时间复杂度=O(n)
平均情况：设插入概率为p=1/n+1，则循环np+(n-1)p+…+1p=n/2，平均时间复杂度=O(n)
删除
//删除操作：删除顺序表L中第i个元素并返回其元素值
bool ListDelete(SqList &L, int i,int &e){
if(i<1||i>L.length+1){ //判断i的范围是否有效
return false;
}else{
e = L.data[i-1]; //将被删除的元素赋值给e
for(int j=i; j<L.length; j++){
L.data[j]=L.data[j-1]; //将第i个后面的元素前移
}
L.length--; //长度-1
return ture;
}
}
删除的时间复杂度：
最好情况：删除表尾，不需移动元素，循环0次，最好时间复杂度=O(1)
最坏情况：删除表头，移动n-1个元素，循环n次，最坏时间复杂度=O(n)
平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n-1)/2，平均时间复杂度=O(n)
查找
按位查找
//按位查找：返回顺序表中第i个元素的元素值
int GetElem(Sqlist L, int i){
return L.data[i-1];
}
按位查找的时间复杂度
时间复杂度=O(1)
按值查找
//按值查找：返回顺序表L中第一个值为x的元素的位置
int LocateElem(Sqlist L, int e){
for(int i=0; i<L.length; i++){
if(L.data[i] == e)
return i+1; //返回元素位置
}
return -1; //查找失败，返回-1
}
按值查找的时间复杂度
最好情况：目标在表头，循环1次，最好时间复杂度=O(1)
最坏情况：目标在表尾，循环n次，最坏时间复杂度=O(n)
平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n+1)/2，平均时间复杂度=O(n)
无销毁
系统自动销毁
1.2.5 动态分配的顺序表上的操作
动态分配的顺序表的优缺点：
优点：可以动态增加长度
缺点：动态增加长度中的迁移工作时间开销大
顺序表的类型描述
typedef struct{
int *data; //指向“动态”分配的数组的指针
int MaxSize; //顺序表的最大长度
int length; //顺序表的当前长度
}SqList;
初始化
//初始化
void InitList(SqList &L){
//用malloc函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
L.MaxSize=InitSize;
L.length=0; //顺序表长度初始为0
}
动态增加数组长度
方法：借用一个指针指向原来顺序表，新建一个更大的顺序表，将原数据迁移过来，并更改顺序表大小，最后释放原顺序表空间
//动态分配
void IncreaseSize(SqlList &L, int len){
int *p=L.data;
L.data=(int *)malloc((L.InitSize+len)*sizeof(int));
for(int i=0; i<L.length; i++){
L.data[i]=p[i]; //将数据迁移至新区域
}
L.MaxSize=L.MaxSize+len; //顺序表最大长度+len
free(p); //释放原来的内存空间
}
插入
在静态分配的基础上，如果容量不够，则动态增加
//插入操作：在顺序表L的第i个(位序)上插入x
bool ListInsert(SqList &L, int i,int e){
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
if(L.length>=MaxSize) //当存储空间已满时，动态增加数组长度
IncreaseSize(L,10);
for(int j=L.length; j>=i; j--)
L.data[j]=L.data[j-1]; //将第i个及后面的元素后移
L.data[i-1]=e; //将e放到第i个位置
L.length++; //长度+1
}
插入的时间复杂度：
最好情况：插到表尾，不需移动元素，循环0次，最好时间复杂度=O(1)
最坏情况：插到表头，移动n个元素，循环n次，最坏时间复杂度=O(n)
平均情况：设插入概率为p=1/n+1，则循环np+(n-1)p+…+1p=n/2，平均时间复杂度=O(n)
删除(与静态一样)
//删除操作：删除顺序表L中第i个元素并返回其元素值
bool ListDelete(SqList &L, int i,int &e){
if(i<1||i>L.length+1){ //判断i的范围是否有效
return false;
}else{
e = L.data[i-1]; //将被删除的元素赋值给e
for(int j=i; j<L.length; j++){
L.data[j]=L.data[j-1]; //将第i个后面的元素前移
}
L.length--; //长度-1
return ture;
}
}
删除的时间复杂度：
最好情况：删除表尾，不需移动元素，循环0次，最好时间复杂度=O(1)
最坏情况：删除表头，移动n-1个元素，循环n次，最坏时间复杂度=O(n)
平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n-1)/2，平均时间复杂度=O(n)
查找(与静态一样)
按位查找
//按位查找：返回顺序表中第i个元素的元素值
int GetElem(Sqlist L, int i){
return L.data[i-1];
}
按位查找的时间复杂度
时间复杂度=O(1)
按值查找
//按值查找：返回顺序表L中第一个值为x的元素的位置
int LocateElem(Sqlist L, int e){
for(int i=0; i<L.length; i++){
if(L.data[i] == e)
return i+1; //返回元素位置
}
return -1; //查找失败，返回-1
}
按值查找的时间复杂度
最好情况：目标在表头，循环1次，最好时间复杂度=O(1)
最坏情况：目标在表尾，循环n次，最坏时间复杂度=O(n)
平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n+1)/2，平均时间复杂度=O(n)
销毁
//销毁操作
void DestroyList(Sqlist &L){
free(L.data);
L.length = 0;
L.MaxSize = 0;
L.data = nullptr; //令其为空指针
}
1.2.6 共同的操作
求表长
//求表长
int Length(Sqlist L){
return L.length;
}
遍历
//遍历操作
void PrintList(Sqlist L){
for(int i=0; i<L.length; i++){
cout<<L.data[i]<<" ";
}
cout<<endl;
}
判空
//判空操作
int Empty(Sqlist L){
return L.length==0? 1 : 0;
}
1.2.7 完整代码
//动态分配的顺序表的完整代码
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 100 //定义线性表的最大长度
typedef struct Sqlist{
int data[MaxSize];
int length;
}Sqlist;
//初始化
void Init(Sqlist &L){
L.length = 0;
}
//求表长
int Length(Sqlist L){
return L.length;
}
//插入操作：在表中第i个位置上插入x
void Insert(Sqlist &L, int i, int x){
if(i<1 || i>L.length+1 || L.length >= MaxSize){
cout<<x<<" Insert failed."<<endl;
return;
}
for(int j=L.length; j>=i; j--){ //第i个及以后的元素后移
L.data[j] = L.data[j-1];
}
L.data[i-1]=x;
L.length++;
}
//遍历操作
void PrintList(Sqlist L){
cout<<"L: ";
for(int i=0; i<L.length; i++){
cout<<L.data[i]<<" ";
}
cout<<endl;
}
//按值查找：返回顺序表L中第一个值为x的元素的位置
int LocateElem(Sqlist L, int x){
for(int i=0; i<L.length; i++){
if(L.data[i] == x)
return i+1; //返回元素位置
}
return -1; //查找失败，返回-1
}
//按位查找：返回顺序表中第i个元素的元素值
int GetElem(Sqlist L, int i){
return L.data[i-1];
}
//删除操作：删除顺序表L中第i个元素并返回其元素值
int Delete(Sqlist &L, int i, int &x){
if(i<1 || i>L.length){
return -1;
}else{
x = L.data[i-1];
for(int j=i; j<L.length; j++){
L.data[j-1] = L.data[j];
}
L.length--;
return x;
}
}
//判空操作
int Empty(Sqlist L){
return L.length==0? 1 : 0;
}
int main(){
Sqlist L;
Init(L);
Insert(L, 1, 50);
Insert(L, 2, 60);
Insert(L, 1, 40);
Insert(L, 1, 666);
Insert(L, 5, 70);
Insert(L, 6, 40);
Insert(L, 7, 100);
cout<<"长度："<<Length(L)<<endl;
PrintList(L);
int x;
cout<<"第三个元素是："<<GetElem(L,3)<<endl;
cout<<"40在第"<<LocateElem(L,40)<<"位"<<endl;
cout<<"删除"<<Delete(L,6,x)<<endl;
PrintList(L);
if(!Empty(L)){
cout<<"L不为空"<<endl;
}else{
cout<<"L为空"<<endl;
}
return 0;
}