资源描述：
《数据结构第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、目录第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序数据结构课程的起点线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是1对1的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n
2、=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0线性终点2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点（a1,a2,…ai-1，ai,ai＋1,…,an）（A,B,C,D,……,Z）学号姓名性别年龄班级012004011401朱原女19电子信息工程200401班012004011402魏喜燕女18电子信息工程200401班012004011403章巧
3、娟女19电子信息工程200401班012004011405张政男19电子信息工程200401班012004011410刘琰男19电子信息工程200401班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母）， 元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。2.1.2抽象数据类型线性表的定义ADTList{数据对象：D={ai
4、ai∈ElemSet,i=1,2,,...,n,n>=0}数据关系：R1={
5、ai-1,ai∈
6、D,i=2,...,n}基本操作：1.IiniList(&L)//构造空的线性表L2.LengthList(L)//求L的长度3.GetElem(L,i,&e)//取L中元素ai,由e返回ai4.PriorElem(L,ce,&pre_e)//求ce的前驱,由pre_e返回5.InsertElem(&L,i,e)//在元素ai之前插入新元素e6.DeleteElem(&L,i)//删除第i个数据元素7.EmptyList(L)//判断L是否为空表8.ClearList(&L)//置L为空表......}ADTList算法2.1步骤：1．从线性表LB中依次取得每个数据元素;G
7、etElem(LB,i)→e2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)算法2.2步骤：1．分别从LA和LB中取得当前元素ai和bj；2．若ai≤bj，则将ai插入到LC中，否则将bj插入到LC中。算法时间复杂度算法2.1的时间复杂度为O(ListLength(LA)×ListLength(LB))算法2.2的时间复杂度为O(ListLength(LA)+ListLength(LB))2.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运
8、算效率分析2.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像顺序存储定义：顺序存储方法：特点：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]1.逻辑上相邻的数据元素，其物理上也相邻；若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为
9、L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示线性表顺序存储特点(a1,a2,...an)顺序存储结构的一般形式序号存储状态存储地址1b2b+pib+(i-1)*pnb+(n-1)*p自由区maxlengb+(maxleng-1)*p其中:b----表的首地址/基地址/元素a1的地址。p----1个数据元素所占存储单元的数目。maxleng----最大长度,为某个常数。a1a2...ai...an//////线性表
