数据结构第2章线性表.ppt

《数据结构第2章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、栈、队列、字符串、数组等，其中最典型、最常用的是------线性表见第2章一对一(1:1)1（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构1.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，

2、表示元素在表中的位置n为元素总个数，即表长空表线性终点2例1分析26个英文字母组成的英文表是什么结构。（A,B,C,D,……,Z）学号姓名性别年龄班级012002009524刘禹圻男182002级计科0201班012002009613武锐男182002级计科0202班012002009710彭隽男172002级计科0203班012002009801郭芳女182002级计科0204班012002009904张珍珍女182002级计科0205班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意

3、：同一线性表中的元素必定具有相同特性！32.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现。注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]4线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a1的存放地址为LOC(a1)（称为首地

4、址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示：5线性表的顺序存储结构示意图a1a2……aiai+1……an地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L6设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是113例1因此：LOC(M[3])=98+5×(3-0)=

5、113解：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）72.2.2顺序表的实现（或操作）回忆：数据结构基本运算操作有：修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改之。核心语句:V[i]=x;显然，顺序表修改操作的时间效率是T(n)=O(1)82)插入在线性表的第i个位置前插入一个元素实现步骤：将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?应当有1≤i≤n+1或i=[1,n+1]for(j=n;j>=i;j--)a[j+1]=a[j];a[i]=x;n++;//

6、元素后移一个位置//插入x//表长加1核心语句：9在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入2510实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?应当有1≤i≤n或i=[1,n]3)删除删除线性表的第i个位置上的元素for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一个位置//表长减1核心语句：111234567891213212425283042771234567812132124283042

7、77删除顺序表中某个指定的元素的示意图如下：122.2.3顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算