线性表-顺序存储

• 一.逻辑结构
• 二.运算
• 三.不同的存储结构有不同的代码实现
• • 1.顺序存储
  • • (1)顺序表的定义
    • (2)初始化顺序表
    • (3)增：在指定位置处插入元素，返回是否插入成功（元素后移）
    • (4)删：删除指定位置的元素，返回是否删除成功（元素前移）
    • (5)查：按值查找，按位查找
    • (6)使用
  • 2.链式存储
• 四.顺序表和链表的区别
• • 1.相同点
  • 2.顺序表
  • • 优点
    • 缺点
  • 3.链表
  • • 优点
    • 缺点
  • 4.总结

a₁->a₂->a₃->a₄->a₅->a₆->a₇

（1）定义表
（2）初始化表
（3）销毁表
（4）求表长
（5）输出线性表
（6）判表是否为空
（7）增：在指定位置处插入元素，返回是否插入成功（位置=下标+1）
（8）删：删除指定位置的元素，返回删除的元素
（9）查：按值查找，按位查找

概念：数组

#define MaxSize 10//定义该线性表最多可以存的元素
typedef struct{
	int data[MaxSize];//数组存储线性表
	int length;//表长
}SqList;//顺序表

void InitList(SqList L){
	for(int i=0;i 
(3)增：在指定位置处插入元素，返回是否插入成功（元素后移） 
bool ListInsert(SqList L,int i,int e){//顺序表L,位置i，元素e
	if(i<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-1开始的元素全部后移一位
	}
	L.dada[i-1]=e;//第i个：下标i-1
	L.length++;//顺序表长度+1
	retrun true;
}
 
(4)删：删除指定位置的元素，返回是否删除成功（元素前移） 
bool ListDelete(SqList L,int i){//顺序表L,位置i
	if(i<1||i>L.length)return false;//判断i的范围是否有效
	for(int j=i;j 
(5)查：按值查找，按位查找 
按位查找值
 
int GetElem(SqList L,int i){//顺序表L,位置i
	return L.data[i-1];
}
 
按值查找位
 
int LocateElem(SqList L,int e){
	for(int i=0;i 
(6)使用 
int main{
	SqList L;//定义顺序表
	InitList(L);//初始化顺序表
	bool ifInsert=ListInset(L,3,3);//在L顺序表中的第3个位置（下标2）插入元素3
	bool ifDelete=ListDelete(L,3);
	return 0;
}
 
2.链式存储 
四.顺序表和链表的区别 
1.相同点 
(1)都是线性结构
 
2.顺序表 
优点 
(1)随机存取
 (2)存储密度高，每个节点只放数据
 
缺点 
(1)大片连续空间分配不方便，扩展容量不方便
 (2)插入删除需要大量移动元素，时间复杂度O(n)，移动代价高
 
3.链表 
优点 
(1)离散的小空间容易分配，改变容量方便
 (2)插入删除元素需要从头遍历查找，只需修改指针，时间复杂度O(n)，查找代价低
 
缺点 
(1)不可随机存取
 (2)存储密度小，每个结点不仅放数据还要放指针
 
4.总结 
顺序表：表长可预估，查询操作较多
 链表：表长不可预估，增删操作较多