资源描述：
《(数据结构)三讲 线性表的定义及顺序表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三讲线性表及顺序存储结构本讲主要内容：一、线性表的定义及逻辑结构二、线性表的顺序存储结构三、顺序表的实现一、线性表的定义及逻辑结构学生成绩登记表姓名英语数据结构高数学号丁一9678870101李二8790780102张三6786860103孙红6981960104王冬8774660105职工工资登记表姓名岗位津贴基本工资奖金职工号丁一6002782000101李二3001901000102张三3001861000103孙红5002182000104王冬3001901000105数据元素之间的关系是什么？线性表：简称表，是n（n≥0）个具有相同类型的数据元素的
2、有限序列。线性表的长度：线性表中数据元素的个数,一般用n表示,n≥0。空表：长度等于零的线性表，即n=0,记为：L=()。线性表的定义非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)ai（1≤i≤n）称为数据元素；下角标i表示该元素在线性表中的位置或序号(逻辑序号)。a1是表中第一个元素,称为表头元素;a2是表中第二个元素;……an是最后一个元素,称为表尾元素;线性表中各元素在位置上是有序的,这种有序就称为线性关系.线性表的定义例如：L1=()：L1是一个空的线性表；L2=(a,b,c,d,e)：L2线性表中有5个元素，其长度为5。a是表头元素、e
3、是表尾元素。c的直接前驱元素是b，c的直接后继元素是d。a元素的序号是1，c元素的序号是3。线性表的定义a1a3a4ana2线性表（a1,a2,…,ai-1,ai,…,an)的图形表示如下：线性表的图形表示元素ai和ai+1之间的先后关系用表示.线性表（a1,a2,…,ai-1,ai,…,an)的二元组表示如下：线性表的二元组表示线性表L=(D,R),其中D={ai
4、1≤i≤n,n≥0,ai属于ElemType类型}R={r}R={
5、1≤i≤n-1}注意:ElemType类型是C++的类型标识符,代表某种类型.a1a3a4a
6、na21.有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。线性表的特性线性表的抽象数据类型定义ADTList{数据对象:D={ai
7、1≤i≤n,n≥0,ai属于ElemType类型}//ElemType是C++的类型标识符数据关系:R={
8、ai,ai+1∈D,i=1,n-1}线性表的抽象数据类型定义基本运算:Init
9、List(&L)初始化线性表：构造一个空的线性表L。前置条件：表不存在输入：无功能：表的初始化输出：无后置条件：建一个空表线性表的抽象数据类型定义DestroyList(&L)销毁线性表:释放线性表L占用的内存空间。前置条件：表已存在输入：无功能：销毁表输出：无后置条件：释放表所占用的存储空间线性表的抽象数据类型定义ListEmpty(L)判断线性表是否为空：若L为空表，则返回真，否则返回假。前置条件：表已存在输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0后置条件：表不变线性表的抽象数据类型定义ListLength(L)求线性表的长度：返回L中
10、元素的个数。前置条件：表已存在输入：无功能：求表的长度输出：表中数据元素的个数后置条件：表不变线性表的抽象数据类型定义DispList(L)输出线性表：当线性表L不为空时，顺序显示L中各结点的值域。前置条件：表已存在输入：无功能：顺序显示L中各结点的值域输出：若是空表，直接返回；否则顺序显示表中各结点的值域后置条件：表不变线性表的抽象数据类型定义GetElem(L,I,&e)求线性表中某个数据元素值：用e返回L中第i(1≤i≤ListLength(L))个元素的值。前置条件：表已存在输入：元素的逻辑序号i功能：在表中取逻辑序号为i的数据元素输出：若i合法，返回
11、逻辑序号为i的元素值，否则抛出异常后置条件：表不变线性表的抽象数据类型定义LocateElem(L,e)按元素值查找:返回L中第1个值域与e相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。前置条件：表已存在输入：数据元素e功能：在线性表中查找值等于e的元素输出：若查找成功，返回e在表中的序号，否则返回0后置条件：表不变线性表的抽象数据类型定义ListInsert(&L,i,e)插入数据元素：在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e，L的长度增1。前置条件：表已存在输入：插入i；待插入的元素e功能：在表的第i个位置处插
12、入一个新元素e输出：若插入不成功，抛出
