Part2 顺序表

1 概念

1.1 线性表

零个或多个数据元素的有限序列。元素之间存在顺序，第一个元素无前驱，最后一个元素无后继，其他元素有且仅有一个前驱和后继。

1.2 顺序表

线性表的顺序存储结构---数组

即顺序表：用一组地址连续的存储单元依次存储线性表的数据元素。

即：逻辑上相邻的数据元素，其物理次序也是相邻的。

2 顺序表实现

2.1 数据元素属性

（1）存储空间的起始地址：数组名

（2）线性表的最大存储容量：数组长度

（3）线性表的当前长度：length

2.2 建表

数组初始化：声明一个类型和大小的数组并赋值的过程。

2.2.1 栈区：函数结束后系统自动回收

结点类型以及顺序表类型定义：

     ElemType data[MAXSIZE];//数组：预留空间
     int length;//实际元素个数

2.2.2 堆区：动态内存分配

结点类型以及顺序表类型定义：

算法描述：

 （1）为顺序表list动态分配一个预定义大小的数组空间，使elem指向这段空间的首地址
 （2）将表的当前长度设置为0

优势：更有效的利用系统资源。

方法：二级指针

 返回值是程序执行的状态，
 参数是顺序表的首地址
 （跨函数修改一级指针的值：采用二级指针）
 pl:二级指针
 *pl:一级指针

参考代码：（MAX --- 宏定义即可）

练习

定义一个线性表的顺序存储结构，完成数据初始化(直接赋值)

2.3 取值

前提：顺序表已存在

取值：根据指定的位置序号i,获取顺序表中第i个数据元素的值。

算法步骤：

 (1) 判断位置序号i的值是否合理
 1<= i <=  MAX
 若不合理:返回error(返回值是程序执行结果：status)
 (2)若合理：
     将第i个数据元素l->book_mes[i-1]的参数赋值给参数e,
     通过e返回第i个数据元素的传值。
 ​
 status get_elem(sql_list_p l,int i,elem_type *e);

示例：

算法分析：

时间复杂度：O(1)（与问题规模无关）

2.4 查找

算法步骤：

 （1）遍历顺序表，找到第一个与e相等的元素l->data[i]。
 若查找成功，则返回该元素在表中的位置序号
 若查找失败，则返回0

示例：

算法分析：O(n)

2.5 插入

算法步骤：

 (1)判断插入位置i是否合法
 1<=i <=MAX;
 若不合法：返回error
 (2)判断顺序表的存储空间是否已满，若满则返回error
 (3)将第length个至第 i 个元素依次向后移动一个位置，空出第i个位置，（i=max时无需移动）
 (4)将要插入的新元素e放入第i个位置
 (5)length+1；

示例：

算法分析

顺序表长度：n

在位置i上插入数据是等概率的

数学期望E(x) = 每次可能的结果* 每次的概率

故：其时间复杂度O(n)

2.6 删除元素

图示：

算法步骤：

 (1)判断删除位置i是否合法 1<= i <=  l->length,若不合法，返回status
 (2)判断是否为空表
 (3)将位置i的值l->data[i-1]保存给e;
 (4)将第i+1个至第n个的元素依次向前移动一个位置（i=n时无需移动）
 (5)表长-1

示例：

算法分析：

详见同插入

时间复杂度：O(n)

2.7 整表查询

算法步骤：

数据元素查询的循环执行

示例代码：

算法分析：O(n)

2.8 整表删除

3 小结

3.1 优势

存储有序，取值快速

3.2 缺点

（1）插入和删除需要移动大量数据，耗费了时间

（2）由于数组有长度相对固定的静态特性，当表中数据元素个数较多，且变化较大时，操作过程相对复杂，也会导致存储空间的浪费。

3.3 解决方案：

链表

作业

作业:写一个微信好友的顺序表/qq好友的顺序表/图书管理的顺序表

作业2：

完善剩下的代码，并且添加功能：

（1）打印整表数据

（2）去除表内重复的数据

（3）修改位置序号i处数据的值为e

（4）两个顺序表合并