第二章线性表1.ppt

《第二章线性表1.ppt》由会员分享，可在线阅读，更多相关《第二章线性表1.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第1章章绪论绪论第第2章章线性表线性表第第3章章栈和队列栈和队列第第4章章串串第第5章章数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树第第7章章图图第第9章章查找查找第第10章章排序排序目目 录录数据结构课程的起点：数据结构课程的起点：什么是什么是线性结构？线性结构？3线性结构的定义：线性结构的定义：若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直直接接前前趋趋和和一一个个直直接后继。接后继。可表示为：（可表示为：（a a1 1,a,a2 2 ,a,an n）

2、简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特特点点 除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个个直接后继。直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-线性表线性表一对一一对一(1:1)4第第2章章线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和

3、实现线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例应用举例应用举例5（a1,a2,ai-1，ai,ai1，,an）2.1线性表的逻辑结构线性表的逻辑结构线性表的定义：线性表的定义：线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数

4、，即表长。长。n0n0空表空表线性终点线性终点6 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012005010122陈陈 建建男男 192007级信工级信工0701班班012005010204吴玉凤吴玉凤女女 182007级信工级信工0502班班012005010313王泽林王泽林男男 202007级信工级信工0703班班012005010406苏苏 荃荃男男 192007级信工级信工0704班班012005010118王春花女 17 172007级文信级文信0705班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据

5、元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。72.2线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析8

6、2.2.1顺序表的表示顺序表的表示用用一一组组地地址址连连续续的的存存储储单单元元依依次次存储线性表的元素。存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn 来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，

7、即：VnVn 的有效范围是从的有效范围是从 V0V0Vn-1Vn-191.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn 的的下标下标）。）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+LL

8、OC(LOC(a ai i)=LOC()=LOC(a a11)+L*)+L*（i-1i-1）对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点：线性表顺序存储特点：10a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b+L Lb+(i-1)+(i-1)L Lb+(n-1)+(n-1)L Lb+(max-1)+(max-1)L LLOC(LOC(a ai i)=LOC(a)=LOC(a11)+L*)+L*（i-1i-1）线性表的顺序存储结构示

9、意图线性表的顺序存储结构示意图11设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数，每个数组元素用相邻的组元素用相邻的个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存储数组元素 的第一个字节的地址是的第一个字节的地址是，则则 的第一个字节的地址是多少？的第一个字节的地址是多少？113但此题要注意下标起点略有不同：但此题要注意下标起点略有不同：LOC(M3)=98+5(4-1)=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例例112charV30;voidbuild()/*字母线性表的生成，即字

10、母线性表的生成，即建表操作建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;核心语句：核心语句：法法法法11ViVi=Vi-1+1;=Vi-1+1;法法法法22ViVi=a+ia+i;法法法法33ViVi=97+i;=97+i;例例2用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C语言语言程序。程序。13voidmain(void)/*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/intn=26;/*n n是表长，是数据元素

11、的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build();display();voiddisplay()/*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1 核核心心语语句：句：2)2)插入插入16在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：12132124283042771213212425252830427712345678123456789插入插入

12、2525252517实现步骤：实现步骤：将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?应当有应当有1in 或或 i=1,n删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for(j=i+1;j=L.listsizeL.listsize)L.listsizeL.listsize=List_IncrementList_Increment;P23P23的的mallocmalloc()()函数与函数与P24P24的的reallocrealloc()()函数有什么

13、函数有什么不同？不同？25动态数组简介动态数组简介先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因插入元素而插入元素而空间不足空间不足时，可为顺序表增加一个时，可为顺序表增加一个固定长固定长度的空间增量度的空间增量。#defineLIST_INIT_SIZE100/存储空间的初始分配量存储空间的初始分配量#defineLISTINCREMENT10/存储空间的分配增量存储空间的分配增量TypedefstructElemType*elem;/表表基址基址(用指针用指针*elemelem表示表示）intlength;/表表长度（长度（表中有多少个元素表中有多少个元素

14、）intlistsize;/当前当前分配的表尺寸分配的表尺寸（字节单位字节单位）SqList;注：三个分量可简写为：注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（存储结构描述如下（见教材见教材P22P22）：）：26线性表的定义线性表的定义（见教材见教材P19）ADTList数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：数据关系：R1=|ai1,aiD,i=2,n基本操作：基本操作：l初始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含

15、定位）、遍历；读元素、查找（含定位）、遍历；l插入、删除插入、删除ADTList27线性表的基本操作如何表示？线性表的基本操作如何表示？（见教材（见教材P19）InitList(&L);/建空表，初始化建空表，初始化DestoryList(&L);/撤销表，释放内存撤销表，释放内存int LengthList(L);/求表中元素个数，即表长求表中元素个数，即表长POSITION LocateElem(L,ElemType e，compare();PriorElem(L,cur_e,&pre_e);/求当前元素求当前元素e的前驱的前驱NextElem(L,cur_e,&next_e);/求当前元

16、素求当前元素e的后继的后继ListInsertBefore(&L,i,e);/把把e插入到第插入到第i个元素之前个元素之前ListDelete(&L,i,&e);/删除第删除第i个元素并个元素并“看看”此元素此元素ListTraverse(L,Visit();/“看看”表中全部元素（遍历）表中全部元素（遍历）l初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；l插入、删除28sizeof(xsizeof(x)算符的意思是：算符的意思是：计算变量计算变量x x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开函数的意思是：新开一片大小为一片

17、大小为m字节字节的连续空间，的连续空间，并把该区首址作为函数值。并把该区首址作为函数值。StatusInitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序L.length=0;/暂无元素放入，空表暂无元素放入，空表L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量ReturnOK;/InitList_SqInitList_Sq动态创建

18、一个动态创建一个动态创建一个动态创建一个空空空空顺序表的算法：顺序表的算法：顺序表的算法：顺序表的算法：29realloc(*p,newsize)函数的意思是：新开一函数的意思是：新开一片大小为片大小为newsize的连续空间，并把以的连续空间，并把以*p为为首址的原空间数据都拷贝进去。首址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee)/在顺序线性表中第在顺序线性表中第i i个位置之前插入新的元素个位置之前插入新的元素e eif(iL.length+

19、1)returnERROR;/检验检验i值的合法性值的合法性if(L.length L.listsize)/若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTLISTINCREMENTINCREMENT)*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报错分配失败则退出并报错L.elem=newbase;/重置新基址重置新基址L.listsize=L.listsize+LISTINCREMENTLISTINCREMENT

20、;/增加表尺寸增加表尺寸30q=&L.elemi-1;/q为插入位置。这是没有头结点的情况为插入位置。这是没有头结点的情况for(p=L.elemL.length-1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的元素统统后移,p为元素位置为元素位置*q=e;/插入插入e+L.length;/增加增加1个数据元素，则表长个数据元素，则表长+1returnOK;/ListInsert_Sq动态数组的核心是动态数组的核心是reallocrealloc(void(void*ptrptr,newsizenewsize)函数！函数！31动态顺序表的删除算法动态顺序表的删

21、除算法动态顺序表的删除算法动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e)/在顺序表在顺序表L中删除第中删除第i个元素，用个元素，用e返回其值返回其值if(iL.length)returnERROR;/i值不合法，返回值不合法，返回p=&L.elemi-1;/p是被删除元素的位置是被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给eq=L.elem+L.length-1;/q是表尾的位置是表尾的位置for(+p;p=q;p+)*(p-1)=*p;/待删元素后面的统统前移待删元素后面的统统前移-L.length;/表长表

22、长-1returnOK;/ListDelete_Sq32顺序表操作的典型例子顺序表操作的典型例子教材教材例例2-1：求两个线性表的：求两个线性表的“并并”，即：即：LA U LB=?算法至少有两种：算法至少有两种：LA和和LB都是都是无序表无序表，则从，则从LB中取元素逐一与中取元素逐一与LA中所有元素比较，相同则不插入中所有元素比较，相同则不插入LA；若若LA和和LB已经是已经是有序表有序表，则，则“归并归并”的时间的时间效率可以大大提高。效率可以大大提高。33链式存储结构链式存储结构2.22.2节小结节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元素：逻辑关系上相邻的两个元素在物理存储位置上也相邻；在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：