文档介绍：第2章线性表
线性表的定义和基本操作
线性表的顺序存储结构
线性表的链式存储结构
线性表的应用举例
本章主要内容
线性表的定义和基本操作
线性表的定义
线性表是由n(n≥0)个类型相同的数据元素组成的有限序列。
L=( a1, a2,...,ai-1,ai,ai+1,...,an);其中:L为表名****惯用大写书写;ai为该线性表的数据元素****惯用小写书写;
线性表中数据元素的个数被称为线性表的长度,当n=0时,称为空线性表。
线性表特点
特点
除第一个和最后一个元素外,其他元素都存在唯一的前驱、后继关系
举例
La=(34,89,765,12,90,-34,22) 数据元素类型为int。
Ls=(Hello,World, China, e) 数据元素类型为string。
举例
Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结构类型:
struct bookinfo{
int No; //图书编号
char *name; //图书名称
char *auther; //作者名称
...;
}
在现实中,这种类型的数据结构很多很多,如学生档案学籍系统、图书管理系统、仓库管理系统、设备管理系统等
线性表的基本操作
1. 初始化线性表L InitList(L)
2. 销毁线性表L DestoryList(L)
3. 清空线性表L ClearList(L)
4. 求线性表L的长度 ListLength(L)
5. 判断线性表L是否为空 IsEmpty(L)
6. 获取线性表L中的某个数据元素
内容GetElem(L,i,e)
7. 检索值为e的数据元素 LocateELem(L,e)
了解,算法有待学****br/>8. 返回线性表L中e的直接前驱元素
PriorElem(L,e)
9. 返回线性表L中e的直接后继
元素NextElem(L,e)
元素ListInsert(L,i,e)
11. 删除线性表L中第i个数据
元素ListDelete(L,i,e)
注意:这些操作都是定义在逻辑层面上
理解,算法有待学****br/>返回
线性表的基本操作
线性表的顺序存储结构
顺序存储结构
指用一组连续的存储单元依次存储线性表中的每个数据元素。如右图所示:
说明:L为每个数据元素所占据的存储单元数目。
顺序表元素在内存的存储地址
相邻两个数据元素的存储位置计算公式
LOC(ai+1)=LOC(ai)+L
线性表中任意一个数据元素的存储位置的计算
公式为:LOC(ai+1)=LOC(a1)+(i-1)*L
顺序存储结构的特点
逻辑与物理一致:
逻辑上相邻,物理上也相邻——利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系
随机存取:
可以利用上述给出的数学公式,快速地计算出任何一个数据元素的存储地址