资源描述：
《线性表的类型定义及顺序表示和实现ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序目录1数据结构课程的起点：什么是线性结构？2线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、
2、最常用的是------线性表一对一(1:1)3第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例4（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点5（A,B,C,D,……,Z）例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关
3、系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。6“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数据类型试判断下列叙述的正误：7线性表的定义（见教材P19）ADTList{数据对象：D={ai
4、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={
5、ai–1,ai∈D,i=2,…,n}基本操作：初始化
6、、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除}ADTList8线性表的基本操作如何表示？（见教材P19）InitList(&L);//建空表，初始化DestoryList(&L);//撤销表，释放内存intLengthList(L);//求表中元素个数，即表长POSITIONLocateElem(L,ElemTypee，compare());PriorElem(L,cur_e,&pre_e);//求当前元素e的前驱NextElem(L,cur_e,&nex
7、t_e);//求当前元素e的后继ListInsertBefore(&L,i,e);//把e插入到第i个元素之前ListDelete(&L,i,&e);//删除第i个元素并“看”此元素ListTraverse(L,Visit());//“看”表中全部元素（遍历）初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除9顺序表操作的典型例子教材例2-1：求两个线性表的“并”，即：LAULB=?算法至少有两种：①LA和LB都是无序表，则从LB中取元素逐一与LA中所有元
8、素比较，相同则不插入LA；②若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。102.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析112.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：特点：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V
9、[n]的有效范围是从V[0]～V[n-1]121.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示线性表顺序存储特点：13地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b
10、+Lb+(i-1)Lb+(n-1)Lb+(max-1)LLOC(ai)=LOC(a1)+L*（i-1）线性表的顺序存储结构示意图14设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？113但此题要注意下标起点略有不同：LOC(M[3])=98+5×(4-1)=113解：已知地址计算通式为：LOC(ai)=LOC(a1)+
