数据结构课件第二章1

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

2、n） 简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继。特点特点 ai ai是属于某个数据对象同一类型的元素，它是属于某个数据对象同一类型的元素，它可以是一个数字、一个字母或一个记录。可以是一个数字、一个字母或一个记录。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-一对一一对一 (1:1

3、)45（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的逻辑结构线性表的逻辑结构 用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点6 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级40306114陈建武陈建武男男 192003级电信级电信0301班班40306115赵玉凤赵玉凤女女 182003级电

4、信级电信0302班班40306116王王 泽泽男男 192003级电信级电信0303班班40306117薛薛 荃荃男男 192003级电信级电信0304班班40306118王 春男 19192003级电信级电信0305班班： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么

5、结构。7“同一数据逻辑结构中的所有数据元素都具有相同的特性同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的是指数据元素所包含的数据项的个数数据项的个数都相等。都相等。试判断下列叙述的正误：试判断下列叙述的正误：82.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 顺序表的表示顺序表的表示2.2.2 顺序表的实现顺序表的实现2.2.3 顺序表的运算效率分析顺序表的运算效率分析92.2.1 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理

6、上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-1101. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位

7、置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + L 对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点：线性表顺序存储特点：11a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址

8、内容内容 元素在表中的位序元素在表中的位序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 L线性表的顺序存储结构示意图线性表的顺序存储结构示意图12设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数，每个数组元素用相邻的组元素用相邻的个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存储数组元素 的第一个字节的地址是的第一个字节的地址是，则则 的第一个字节的地址是多少？的第一个字节的地址是多少？113但此题要注

9、意下标起点略有不同：但此题要注意下标起点略有不同：LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）例例1 113 char V30;void build() /*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心语句：核心语句：例例2用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z），写出在顺序结构上），写出在顺序结构上生成生成和和显示

10、显示该表的该表的C语言语言程序。程序。14void main(void) /*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/ n=26; /* n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build( );display( );void display( ) /*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/ int i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 核核心心语语句

11、：句：2)2)插入插入17在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入18实现步骤：实现步骤：将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?应当有应当有1in 或或 i=1, n删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for ( j=i+1; j=n; j+ )aj-1=aj; n-;/

12、/ 元素前移一个位置元素前移一个位置/ / 表长减表长减1 1 核心语句：核心语句：3)3)删除删除19123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：顺序表插入和删除的完整程序请同学们自编。顺序表插入和删除的完整程序请同学们自编。202.2.3 顺序表的运算效率分析顺序表的运算效率分析算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度） T(n)=

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

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

15、后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计所有可能的元素移动次数合计： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/2故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少种插入形式共有多少种插入形式? ?连头带尾有连头带尾有n+1n+1种种! !22同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入插入效率：效率

16、：删除删除效率：效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin教材教材P25算法算法2.5也是对执行效率的推导：也是对执行效率的推导：因为没有因为没有占用辅助占用辅助空间！空间！含义：对于顺序表，含义：对于顺序表，插入、删除操作平均需要插入、删除操作平均需要移动一半元素移动一半元素( n / 2 )O(1)O(1)即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为 O(n)23链式存储结构链式存储结构本节小结本节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元素：逻辑关系上相邻的两个

17、元素在物理存储位置上也相邻；在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：24课堂讨论：课堂讨论：顺序表的顺序表的“宏观宏观”算法该如何书写？算法该如何书写？采用采用抽象数据类型抽象数据类型来表示来表示顺序表的存储结构是一维数组，如果插入顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？的元素个数超过数组定义的长度怎么办？采用采用动态分配

18、动态分配的一维数组的一维数组25线性表的定义线性表的定义（见教材见教材P19）ADT List 数据对象：数据对象：D=ai | aiElemSet, i=1,2,n,n0数据关系：数据关系：R1= | ai 1, ai D, i=2,n基本操作：基本操作：l初始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；l插入、删除插入、删除 ADT List26线性表的基本操作如何表示？线性表的基本操作如何表示？ （见教材（见教材P19）InitList( &L ); /建空

19、表，初始化建空表，初始化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的后继的后继ListInsertBefore(&L, i, e ); /把把e插入到第插入到第i个元素之前个元素之前ListDelete( &L, i,&e ); /删除第删除第i个元素并个元素并“看看”此元素此元素ListTraverse( L, Visit() ); / “看看”表中全部元素（遍历）表中全部元素（遍历）l初始化