第2章 线性表A.ppt

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

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

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

3、示和实现2.4 应用举例应用举例4（a1,a2,ai-1，ai,ai1，,an）2.1线性表的逻辑结构线性表的逻辑结构线性表的定义：线性表的定义：线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线性终点5 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男 192003级

4、电信级电信0301班班012003010704赵玉凤赵玉凤女女 182003级电信级电信0302班班012003010813王王 泽泽男男 192003级电信级电信0303班班012003010906薛薛 荃荃男男 192003级电信级电信0304班班012003011018王 春男 19192003级电信级电信0305班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系

5、是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。6“同同一一数数据据逻逻辑辑结结构构中中的的所所有有数数据据元元素素都都具具有有相相同同的的特特性性”是指数据元素所包含的是指数据元素所包含的数据项的个数数据项的个数都相等。都相等。是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：试判断下列叙述的正误：7

6、2.2线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析82.2.1顺序表的表示顺序表的表示用用一一组组地地址址连连续续的的存存储储单单元元依依次次存储线性表的元素存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：可以利用可以利用数组数组VnVn来

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

8、的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+LLOC(LOC(a ai i )=LOC()=LOC(a a1 1)+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

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

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

11、母线性表的，字母线性表的生成和输出生成和输出*/n=26;/*n n是是表表长长，是是数数据据元元素素的的个个数数，而而不不是是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个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277

12、1213212425252830427712345678123456789插入插入2525252517实现步骤：实现步骤：将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?应当有应当有1in 或或 i=1,n删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素for(j=i+1;j=n;j+)aj-1=aj;n-;/元素前移一个位置元素前移一个位置/表长减表长减1 1 核心语句：核心语句：3)3)删除删除18123456789121321242528304277

13、123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：顺序表插入和删除的完整程序请同学们自编。顺序表插入和删除的完整程序请同学们自编。19线性表的抽象数据类型定义线性表的抽象数据类型定义（见教材见教材P19）ADTList数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：数据关系：R1=|ai1,aiD,i=2,n基本操作：基本操作：l初始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；读元素、

14、查找（含定位）、遍历；l插入、删除插入、删除ADTList20线性表的基本操作如何表示？线性表的基本操作如何表示？（见教材（见教材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);/求当前元素求当前元素e的的后继

15、后继ListInsertBefore(&L,i,e);/把把e插入到第插入到第i个元素之前个元素之前ListDelete(&L,i,&e);/删除第删除第i个元素并个元素并“看看”此元素此元素ListTraverse(L,Visit();/“看看”表中全部元素（遍历）表中全部元素（遍历）l初始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；l插入、删除插入、删除21顺序表操作的典型例子顺序表操作的典型例子教材教材例例2-1：求两个线性表的：求两个线性表的“并并”，即：

16、即：LA U LB=?算法至少有两种：算法至少有两种：LA和和LB都是都是无序表无序表，则从，则从LB中取元素逐一与中取元素逐一与LA中所有元素比较，相同则不插入中所有元素比较，相同则不插入LA；若若LA和和LB已经是已经是有序表有序表，则，则“归并归并”的时间的时间效率可以大大提高。效率可以大大提高。以上以静态的顺序表来存储数据元素，存在利弊。以上以静态的顺序表来存储数据元素，存在利弊。22动态数组如何实现动态数组如何实现（见教材见教材P22和和P24）#define#define List_Init_SizeList_Init_Size 100 /100 /初始空间初始空间#define#

17、define List_Increment 10 /List_Increment 10 /分配增量分配增量typedef struct ElemType*elem;/存储空间基址存储空间基址 int length;/当前长度当前长度 int listsize;/当前分配的存储容量（以当前分配的存储容量（以sizeof(ElemType)/为单位）为单位）Sqlist;23动态数组简介动态数组简介先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因插入元素而插入元素而空间不足空间不足时，可为顺序表增加一个时，可为顺序表增加一个固定长固定长度的空间增量度的空间增量。#d

18、efineLIST_INIT_SIZE100/存储空间的初始分配量存储空间的初始分配量#defineLISTINCREMENT10/存储空间的分配增量存储空间的分配增量typedefstructElemType*elem;/表基址表基址(用指针用指针*elemelem表示表示）intlength;/表长度（表长度（表中有多少个元素表中有多少个元素）intlistsize;/当前分配的表尺寸当前分配的表尺寸（字节单位字节单位）SqList;注：三个分量可简写为：注：三个分量可简写为：(L.elemL.lengthL.listsize)(L-elemL-lengthL-listsize)存储结构描

19、述如下存储结构描述如下：24sizeof(xsizeof(x)算符的意思是：算符的意思是：计算变量计算变量x x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开函数的意思是：新开一片大小为一片大小为m字节字节的连续空间，的连续空间，并把该区首址作为函数值。并把该区首址作为函数值。StatusInitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序L.leng

20、th=0;/暂无元素放入，空表暂无元素放入，空表L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量returnOK;/InitList_SqInitList_Sq动态创建一个动态创建一个动态创建一个动态创建一个空空空空顺序表的算法：顺序表的算法：顺序表的算法：顺序表的算法：P23P23的的mallocmalloc()()函数与函数与P24P24的的reallocrealloc()()函数有什么函数有什么不同？不同？25realloc(*p,newsize)函数的意思是：新开一函数的意思是：新开一片大小为片大小为newsize的的连续空间，并把以连续空间，并

21、把以*p为为首址的原空间数据都拷贝进去。首址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee)/在顺序线性表中第在顺序线性表中第i i个位置之前插入新的元素个位置之前插入新的元素e eif(iL.length+1)returnERROR;/检验检验i值的合法性值的合法性if(L.length L.listsize)/若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase=(ElemType*)realloc(L.elem,(L.list

22、size+LISTLISTINCREMENTINCREMENT)*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报分配失败则退出并报错错L.elem=newbase;/重置新基址重置新基址L.listsize=L.listsize+LISTINCREMENTLISTINCREMENT;/增加表尺寸增加表尺寸26q=&L.elemi-1;/q为插入位置。这是没有头结点的情为插入位置。这是没有头结点的情况况for(p=L.elemL.length-1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的

23、元素统统后移,p为元素位为元素位置置*q=e;/插入插入e+L.length;/增加增加1个数据元素，则表长个数据元素，则表长+1returnOK;/ListInsert_Sq动态数组的核心是动态数组的核心是reallocrealloc(void(void*ptrptr,newsizenewsize)函数！函数！27动态顺序表的删除算法动态顺序表的删除算法动态顺序表的删除算法动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e)/在顺序表在顺序表L中删除第中删除第i个元素，用个元素，用e返回其值返回其值if(iL.length)retur

24、nERROR;/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;/表长表长-1returnOK;/ListDelete_Sq282.2.3顺序表的运算效率分析顺序表的运算效率分析算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本

25、操作（最深层语句频度）T(n)=O(移动移动元素次数元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才移动次数才合理。合理。讨论讨论1：若在长度为若在长度为n的线性表的第的线性表的第i位前位前插入插入一个元素，则一个元素，则向后移动元素的次数向后移动

26、元素的次数f(n)为为:f(n)=ni+1时间效率时间效率分析分析:29推推导导：假假定定在在每每个个元元素素位位置置上上插插入入x x的的可可能能性性都都一一样样（即即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，

27、后移次数为n-1n-1;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计所有可能的元素移动次数合计：0+1+n0+1+n=n(n+1)/2=n(n+1)/2故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2O(n)O(n)O(n)O(n)共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种!30同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为

28、:T T（n)=(n-1)/2 n)=(n-1)/2 O(n)O(n)O(n)O(n)想一想：想一想：想一想：想一想：顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入插入效率：效率：删除删除效率：效率：教材教材P25算法算法2.5也是对执行效率的推导：也是对执行效率的推导：因为没有因为没有占用辅助占用辅助空间！空间！含义：对于顺序表，含义：对于顺序表，插入、删除操作平均需要插入、删除操作平均需要移动一半元素移动一半元素(n/2)O(1)O(1)即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为O(n)31讨论：讨论：顺序表的顺序表的

29、“宏观宏观”算法该如何书写？算法该如何书写？采用采用抽象数据类型抽象数据类型来表示来表示顺序表的存储结构是一维数组，如果插入顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？的元素个数超过数组定义的长度怎么办？采用采用动态分配动态分配的一维数组的一维数组32链式存储结构链式存储结构本节小结本节小结线性表线性表顺序存储结构特点：顺序存储结构特点：逻辑关系上相邻的两个元素在物逻辑关系上相邻的两个元素在物理存储位置上也相邻；理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷，可以随机存取表中任一元素，方便快捷，存储空间使用紧凑；缺点：缺点：1.1.在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。2.2.预先分配空间需按最大空间分配，利用不充分预先分配空间需按最大空间分配，利用不充分 3.3.表容量难以扩充表容量难以扩充解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：33