文档介绍：计算机软件技术基础
教师：曾晓东
电话：**********
E_mail: ******@
第三章线性结构
线性表
一、线性表概念与运算
二、线性表的顺序存储结构
三、线性表的链式存储结构
四、循环链表与双向链表
栈和队列
数组
——线性表
线性表
一、线性表的概念与运算
1、线性表概念
定义： n(n≥0)个同类元素构成的有限线性序列，表示为L=（a1,a2,…,an）。
n为线性表L的表长
线性表的结构特性
除第一个元素外，线性表中所有元素有唯一直接前驱
除最后一个元素外，线性表中所有元素有唯一直接后继
ai的直接前驱是ai-1，直接后继是ai+1
——线性表
一、线性表的概念与运算
2、线性表运算
1)初始化 initiate ( L) 建立一个空线性表
2)求表长 length (L) 求表的数据元素个数
3)取结点 get(L, i) 给定元素序号 i,取元素内容(或结点地址指针）
4)定位 locate(L, x) 给定元素内容x，取元素序号 i(或结点地址指针)
5)插入 insert(L , i, x) 给定结点序号i，在其前(或其后)插入结点
6)删除 delete(L, i) 给定结点序号，删除该结点(或其后结点)
7)遍历 getlist(L) 以某种顺序读取线性表L的所有元素一次
8)查找 search(L,x)查找数据元素x在线性表L中的序号或结点地址
9)排序 sort(L) 按关键字递增或递减的顺序对L的元素重新排列
——线性表
一、线性表的概念与运算
3、线性表的分类
按存储方式分类
顺序表
链表
按可进行的操作的不同分类
栈
队列
串
数组
——线性表
线性表
二、线性表的顺序存储结构
1、顺序表
用一组地址连续的存储单元存放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构。
该结构用高级语言中的一维数组类型表示。数组中的分量下标即为元素在线性表中的序号。例如：可用一维数组A[n]来存储线性表：（a1, a2 ,...，an）。
这里需要声明：C语言中，数组下标从0开始。
——线性表
二、线性表的顺序存储结构
地址计算：设每个元素占L个单元，线性表在内存中的首地址为：Loc(a1)=b，则线性表中第i个元素的存储地址为：
Loc(ai)=Loc(ai-1)+L=Loc(a1)+(i-1)*L=b+(i-1)*L
特点：这种存储结构只要知道元素的序号，就很容易找到第i个数据元素，且无论序号i为何值，找到第i个元素所需时间相同。所以，这种存储结构亦称为随机存储结构。
——线性表
顺序表的类型定义
const int MAXSIZE 100;
struct sequenlist {
elemtype data[MAXSIZE];
int length;
}
顺序表类型的变量定义
sequenlist list,*L;
二、线性表的顺序存储结构
——线性表
二、线性表的顺序存储结构
2、顺序表有关操作
1) 顺序表初始化
⑴操作: 建立一个长度为零的空表
⑵接口：入口和出口参数均为表头指针 L
⑶算法描述：令表长度字段
⑷函数实现：
void setNull(sequenlist &L ) {
L. length = 0;
}
void setNull(sequenlist &L ) {
= 0;
}
——线性表
二、线性表的顺序存储结构
2) 顺序表的插入
⑴ 操作:
从末尾至第i个结点将内容依次后挪
将新结点放入第i个结点位置
表长度加一
⑵ 接口：
入口参数: 表头指针 L，位置 i，新结点x
出口参数: 表头指针 L
函数值：成功则返回1(用true表示),
失败则返回0(用false表示)
——线性表