数据结构课件之线性表.ppt

《数据结构课件之线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构课件西北大学计算机系本演示文稿可能包含观众讨论和即席反应。使用PowerPoint可以跟踪演示时的即席反应，在幻灯片放映中，右键单击鼠标请选择“会议记录”选择“即席反应”选项卡必要时输入即席反应单击“确定”撤消此框此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。10/8/20211第2章线性表2.1线性表的概念及运算2.2线性表的顺序存储2.3线性表的链式存储2.4一元多项式的表示及相加10/8/202122.1线性表的概念及运算2.1.1线性表的逻辑结构2.1.2线性表的抽象数据类型定义10/8/20213线性表的定义线性表(LinearList)是由n

2、(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1，…，an）。数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。线性表的逻辑结构图为：10/8/20214线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。10/8/202152.1.2线性表的抽象数据类型定义抽象数据类型定义：ADTLinearList{数据元素：D={ai

3、ai∈D0

4、,i=1,2,…，nn≥0，D0为某一数据对象}关系：Ｓ＝｛

5、ai,ai+1∈D0，i=1,2,…,n-1｝基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。………}ADTLinearList10/8/202162.2线性表的顺序存储2.2.1线性表的顺序存储结构2.2.2线性表顺序存储结构上的基本运算10/8/20217顺序存储结构的定义线性表的顺序存储是

6、指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为：loc(ai)=loc(a1)+(i-1)×k10/8/20218顺序存储结构示意图存储地址内存空间状态逻辑地址Loc(a1)a11Loc(a1)+(2-1)ka22………loc(a1)+(i-1)kaii………loc(a1)+(n-1)kann...loc(a1)+(

7、maxlen-1)k空闲10/8/20219顺序存储结构的C语言定义#definemaxsize=线性表可能达到的最大长度；typedefstruct{ElemTypeelem[maxsize]；/*线性表占用的数组空间*/intlast；/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/}SeqList；注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。10/8/2021102.2.2线性表顺序存储结构的基本运算线性表的基本运算：查找操作插入操作删除操作顺序表合并算法线性表顺序存储结构的优缺点分析10/8/202111查找

8、操作线性表的两种基本查找运算按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。线性表的查找运算算法描述为：10/8/202112线性表的查找运算intLocate(SeqListL，ElemTypee){i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while((i<=L.last)&&(L.elem[i

9、]!=e))i++;/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/if(i<=L.last)return(i);/*若找到值为e的元素，则返回其序号*/elsereturn(-1);/*若没找到，则返回空序号*/}10/8/202113插入操作线性表的插入运算是指在表的第i(1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表(e1，…，ei-1，ei，…，en)变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。线性表的插入运算算法。