《第2章 线性表 A.pptx》由会员分享，可在线阅读，更多相关《第2章 线性表 A.pptx（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线
4、性终点6 （A,B,C,D,A,B,C,D,Z ,Z）学号学号学号学号姓名姓名姓名姓名性别性别性别性别年龄年龄年龄年龄班级班级班级班级012003010622012003010622陈建武陈建武陈建武陈建武男男男男 19 1920032003级电信级电信级电信级电信03010301班班班班012003010704012003010704赵玉凤赵玉凤赵玉凤赵玉凤女女女女 18 1820032003级电信级电信级电信级电信03020302班班班班012003010813012003010813王王王王 泽泽泽泽男男男男 19 1920032003级电信级电信级电信级电信03030303班班班班01
5、2003010906012003010906薛薛薛薛 荃荃荃荃男男男男 19 1920032003级电信级电信级电信级电信03040304班班班班012003011018012003011018王王 春春男男 19 19 19 1920032003级电信级电信级电信级电信03050305班班班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。注意：同一线性表中的
6、元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。7“同同同同一一一一数数数数据据据据逻逻逻逻辑辑辑辑结结结结构构构构中中中中的的的的所所所所有有有有数数数数据据据据元元元元素素素素都都都都具具具具有有有有相相相相同同同同的的的的特特特特性性性性”是指数据元素所包含的是指数据元素所包含的是指数据元素所包含的是指数据元素所包含的数据项的个数数据项的个数数据项的个数数据项的个数都相等。都相等。都相等。都相等。是指各元素具有
7、相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：试判断下列叙述的正误：82.2 线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析92.2.1 2.2.1 顺序表的表示顺序表的表示用用用用一一一一组组组组地地地地址址址址连连连连续续续续的的的的存存存存储储储储单单单单元元元元依依依依次次次次存储线性表的元素。存储线性表的元素。存储线性表的元素。存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储
8、单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即：VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-1101.1.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻
9、的数据元素，其物理上也相邻；2.2.若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出素存放位置亦可求出素存放位置亦可求出（利用数组利用数组利用数组利用数组VnVnVnVn的的的的下标下标下标下标）。）。）。）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：
10、为：LOC(ai+1)=LOC(ai)+LLOC(LOC(a aii)=LOC()=LOC(a a11)+L*)+L*（i-1i-1）对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点：线性表顺序存储特点：11a a a a1 1 1 1a a a a2 2 2 2a a a ai i i ia a a ai+1i+1i+1i+1a a a an n n 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
11、-1)L LLOC(aLOC(aii)=LOC(a)=LOC(a11)+L*)+L*（i-1i-1）线性表的顺序存储结构示意图线性表的顺序存储结构示意图12设有一维数组设有一维数组设有一维数组设有一维数组，下标的范围是，下标的范围是，下标的范围是，下标的范围是到到到到，每个数，每个数，每个数，每个数组元素用相邻的组元素用相邻的组元素用相邻的组元素用相邻的个字节个字节个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存储数组元素设存储数组元素设存储数组元素 的第一个字节的地址是的第一个字节的地址是的第一个字节的地址是的第一
12、个字节的地址是，则则则则 的第一个字节的地址是多少？的第一个字节的地址是多少？的第一个字节的地址是多少？的第一个字节的地址是多少？113但此题要注意下标起点略有不同：但此题要注意下标起点略有不同：LOC(M3)=98+5(4-1)=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例例113charV30;voidbuild()/*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;核心语句：核心语句：法法法法1Vi=Vi-1+1;1Vi=Vi-1+1;法法法法2
13、Vi=a+i;2Vi=a+i;法法法法3Vi=97+i;3Vi=97+i;例例2用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C语言语言程序。程序。14voidmain(void)/*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/n=26;/*n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build();display();voiddisplay()/*字母线性表的显示，即字母线性表的显示，即读表操作读表
14、操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1 核核心心语语句：句：2)2)插入插入17在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：121213132121242428283030424277771212131321212424252528283030424277771 12 23 34 45 56 67 78 81 12 23 34 45 56 67 78 89 9插入插入2525252518实现步骤：实现步骤：实现步骤：实现步骤：将第
15、将第将第将第i+1 i+1 至第至第至第至第n n 位的元素向前移动一个位置；位的元素向前移动一个位置；位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减表长减表长减1 1。注意：事先需要判断，注意：事先需要判断，注意：事先需要判断，注意：事先需要判断，删除位置删除位置删除位置删除位置i i 是否合法是否合法是否合法是否合法?应当有应当有应当有应当有1in 1in 或或或或 i=1,ni=1,n删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for(j=i+1;j=n;j+)aj-1=aj;n-;/元素前移一个位置元素前移一个位置/表长减表长减1 1 核心语句：核心
16、语句：3)3)删除删除191 12 23 34 45 56 67 78 89 91212131321212424252528283030424277771 12 23 34 45 56 67 78 812121313212124242828303042427777删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：202.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析 算法时间主要耗费在算法时间主要耗费在算法时间主要耗费在算法时间主要耗费在移动元素移动元素移动元素移动元素的操作上，因此的操作上，因此的操作上，因此的操作上，因此计算时间复杂度的基本操作（
17、最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）T(n)=OT(n)=O (移动移动移动移动元素次数元素次数元素次数元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应
18、当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。讨论讨论1：若在长度为若在长度为n的线性表的第的线性表的第i位前位前插入插入一个元素，则一个元素，则向后移动元素的次数向后移动元素的次数f(n)为为:f(n)=ni+1时间效率分析时间效率分析:21推推导导：假假定定在在每每个个元元素素位位置置上上插插入入x x的的可可能能性性都都一一样样（即即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相
19、加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1n-1;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计所有可能的元素移动次数合计：0+1+0+1+n=n(n+1)/2+n=n(n+1)/2故插入时的平均移动次数为：故插入时的平均移动次数为：n(
20、n+1)/2n(n+1)/2（n+1n+1）n/2n/2O(n)O(n)O(n)O(n)共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种!22同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为:T T（n)=(n-1)/2 n)=(n-1)/2 O(n)O(n)O(n)O(n)想一想：想一想：想一想：想一想：顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入插入效率：效率：删除删除效率：效率：教材教材P25P25算法算法2.52.5也是对执行效率的推导：也是对执行效率的推导：因为没有因为没有占用辅助占
21、用辅助空间！空间！含义：对于顺序表，含义：对于顺序表，插入、删除操作平均需要插入、删除操作平均需要移动一半元素移动一半元素(n/2)O(1)O(1)即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为O(n)23链式存储结构链式存储结构本节小结本节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元素：逻辑关系上相邻的两个元素在物理存储位置上也相邻；在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题
22、的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：24线性表的定义（见教材见教材P19P19）ADTList数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：数据关系：R1=|ai1,aiD,i=2,n基本操作：基本操作：初始化、撤销、清空、判空；初始化、撤销、清空、判空；初始化、撤销、清空、判空；初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；读元
23、素、查找（含定位）、遍历；插入、删除插入、删除插入、删除插入、删除ADTList25线性表的基本操作如何表示？线性表的基本操作如何表示？（见教材（见教材P19P19）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);/求
24、当前元素求当前元素e的后继的后继ListInsertBefore(&L,i,e);/把把e插入到第插入到第i个元素之前个元素之前ListDelete(&L,i,&e);/删除第删除第i个元素并个元素并“看看”此元素此元素ListTraverse(L,Visit();/“看看”表中全部元素（遍历）表中全部元素（遍历）l初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；l插入、删除26顺序表的存储结构是一维数组，如果插入顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？的元素个数超过数组定义的长度怎么办？采用采用动态分配动态分配的一维
25、数组的一维数组27动态数组如何实现（见教材见教材P22P22和和P24P24）#define#define List_Init_SizeList_Init_Size 100 /100 /初始空间初始空间#define#define List_IncrementList_Increment 10 /10 /分配增量分配增量 L.listsizeL.listsize=List_Init_Size;=List_Init_Size;If(L.length=If(L.length=L.listsizeL.listsize)L.listsizeL.listsize=List_IncrementList_Increment;