网络异常，图片无法展示
|
顺序表
用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现
计算一个数据元素的大小： C语言中提供的一个函数sizeof(Elem Type) eg:
sizeof(int) = 4B
当然一个结构体的数据元素也可以算出来
typedef struct { int num; int people; } Customer sizeof(Customer) = 8B
顺序表的静态分配
define定义中的MaxSize决定了最大数组的长度，
#define MaxSize 10 //定义最大长度 typedef struct{ ElemType data[MaxSize]; //用静态的“数组”存放数据元素 int length //顺序表当前长度 }SqList; //顺序表的类型定义（静态分配方式）
初始化一个顺序表
void InitList(SqList $L){ L.length=0; //顺序表初始长度为0 }
静态的顺序表当被声明后就不容易被修改
顺序表的动态分配
#define MaxSize 10 //定义最大长度 typedef struct{ ElemType *data; //指针动态分配数组的指针 int MaxSize; //顺序表最大容量 int length //顺序表当前长度 }SqList; //顺序表的类型定义（动态分配方式）
c语言中的malloc、free函数分别可以动态的申请和释放内存空间，malloc函数返回一个指针，需要强制转性为你定义的数据元素类型指针；在c++中可以用new、delete这两个关键字来实现
L.data=(ElemType *) malloc(sizeof(ElemType *InitSize))
顺序表的插入
ListInsert($L,i,e):插入操作，在表L中的第i个位置上插入指定元素e
实现的基本思路就是把原L中第i个元素及之后的元素后移
void ListInsert(SqList $L,int i,int e){ for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; }
在实现的过程中需要判断i是否是合法的，同时要考虑顺序表的长度。改进后的代码：
void 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]; L.data[i-1]=e; L.length++; return true; }
时间复杂度：
- 最好情况：新元素插入到表尾，不用移动元素，T（n）= O（1）
- 最坏情况：新元素插入到表头，T（n）= O（n）
- 平均情况：T（n）= O（n）
顺序表的删除
bool ListDelete(SqList $L, int i.int &e){ if(i<1 || i>L.length) //判断i是否合法 return false; e=L.data[i-1]; //删除的元素赋给e for(int j=i;j<L.length;j++) //将第i个位置后的元素前移 L.data[j-1]=L.data[j]; L.length--; //线性表的长度减1 retrun true; }
时间复杂度：
- 最好情况：删除表尾元素，不用移动元素，T（n）= O（1）
- 最坏情况：删除表头元素，将n+1个元素全部向前移动，T（n）= O（n）
- 平均情况：T（n）= O（n）
顺序表的查找
按位查找
GetElem(L,i)：按位查找操作，获取表L中的第i个位置的元素的值
ElemType GetElem(SeqList L, int i){ return L.data[i-1]; }
时间复杂度：T(n)=O(n)
按值查找
LocateElem(L,e)：按值查找操作，在表L中查找具有给定关键字值的元素
int LocateElem(SeqList L, ElemType e){ for(int i=0; i<L.length; i++) if(L.data[i]==e) return i+1; return 0; }
在顺序表L中查找第一个元素值等于e的元素，并返回其位序，当数组中的下标为i的元素的值等于e的时候，返回位序i+1
时间复杂度：T(n)=O(n)
