数据结构：第2章线性表A

1、1课堂练习：课堂练习：1. 1. 分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1; while(i=n) i=i*3; 2将下列函数，按它们在将下列函数，按它们在n时的无穷大阶数，从小到大排序。时的无穷大阶数，从小到大排序。n, n-n3+0.7n5, nlogn, 2n/2, n3, 100logn, n1/2+logn, n!答：答：100logn, n1/2+logn, n, nlogn, n3, n-n3+0.7n5, 2n/2, n!答：答：O(log3n)2 习题集习题集1.6 1.7 1.8 1.10 1.17 1.20习题集习题集 2.8 2.10 2.21 2

2、.22 2.34 2.35助教助教蔡科超蔡科超4302066563第第1章回顾章回顾数据结构课程数据结构课程 数据结构算法程序，涉及数学、数据结构算法程序，涉及数学、计算机硬件和软件。计算机硬件和软件。数据结构定义数据结构定义指互相有关联的数据元素的集合，指互相有关联的数据元素的集合，可用可用data_Structure=(D,R)data_Structure=(D,R)表示。表示。数据结构内容数据结构内容数据的逻辑结构、存储结构和基本数据的逻辑结构、存储结构和基本运算运算(计算机处理非数值对象计算机处理非数值对象) 数据结构学习工具数据结构学习工具抽象数据类型和伪码

3、抽象数据类型和伪码（类（类C）算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率 4第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序目目 录录什么是什么是线性结构？线性结构？6线性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

4、接后继。 可表示为：（可表示为：（a a1 1 , a, a2 2 , , , a, an n） 简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-一对一一对一 (1:1)78（a1, a2, ai-1，ai, ai1 ，, an）2.1 线

5、性表的逻辑结构线性表的逻辑结构 用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点9 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级U200913798章达航章达航男男19通信工程通信工程200901班班U200913818张岩张岩男男19通信工程通信工程200902班班U200913955周凯周凯男男19通信工程通信工程

6、200903班班U200913887吴益阳吴益阳男男1919通信工程通信工程200904班班： ： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。10“同一数据逻辑结构中的所有数据元素都具有相同的特性同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包

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

8、序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VVn n 的有效范围是从的有效范围是从 VV0 0 VVn-1n-1 131. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组V

9、nVn的的下标下标）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为为？ 先画图先画图线性表顺序存储特点：线性表顺序存储特点：14a 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 +(m

10、ax-1)+(max-1)L L线性表的顺序存储结构示意图线性表的顺序存储结构示意图 LOC ( a ) = LOC( a ) + L 表中任一数据表中任一数据元素的元素的存放地存放地址址为为:下标起下标起点是点是1 115设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数，每个数组元素用相邻的组元素用相邻的个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存储数组元素 的第一个字节的地址是的第一个字节的地址是9898，则，则 的第一个字节的地址是多少？的第一个字节的地址是多少？答案：答案：113但此题要注意下标起点是从但此题要注意下标起点是从0 0开始

11、：开始： LOC( M3 ) = 98 + 5 (3-0) =113或或: : LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）例例1 116 char V30;void build() /字母线性表的字母线性表的生成生成，即建表操作，即建表操作 例例2用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C语言语言程序。程序。省略了省略了includeinclude语句语

12、句 int i; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 17void main(void) /主函数，字母线性表的主函数，字母线性表的生成和输出生成和输出 n=26; / n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的实际下标的实际下标 build( ); display( );void display( ) /字母线性表的字母线性表的显示显示，即读表操作，即读表操作 执行结果：执行结果： a b c d e f g h i j k l m n o p q r s t u v w x y z int i; for( i=0

13、; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 事先应判断事先应判断: 插入位置插入位置i 是否合法是否合法? 表是否已满表是否已满? 应当符合条件：应当符合条件： 1in+1 或或 i=1, n+1 将第将第n至第至第i 位的元素向后移动一个位置；位的元素向后移动一个位置； 将要插入的元素写到第将要插入的元素写到第i个位置；个位置； 表长加表长加1。核核心心语语句句if ( iL.length+1) return ERROR2112345678912132124252830427712

14、3456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素3)3)删除删除22实现步骤：实现步骤： 将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1。for ( j=i+1; j=n; j+ )aj-1=aj; n-;/ / 元素前移一个位置元素前移一个位置/ / 表长减表长减1 1 核心语句：核心语句：顺序表插入和删除的完整程序请同学们自编，顺序表插入和删除的完整程序请同学们自编，并务必上机验证！并务必上机验证！if

15、( iL.length) return ERROR 注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?应当符合条件：应当符合条件：1in 或或 i=1, n232.2.3 顺序表的运算效率分析顺序表的运算效率分析 算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数移动元素次数)而移动元素的个数取决于插入或删除元素的位置。而移动元素的个数取决于插入或删除元素的位置。思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若

16、插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。讨论讨论1：若在长度为若在长度为 n 的线性表的第的线性表的第 i 位前位前 插入插入一个元素，一个元素，则向后移动元素的次数则向后移动元素的次数f(n)为为:f(n) = n i + 1时间效率分析时间效率分析:24推导：推导：假定在每个元素位置上插入假定在每个元素位置上插入x x的可能性都一样（即的可能性都一样（即概率概率P P

17、相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：若在首结点前插入，需要移动的元素最多，后移次数为若在首结点前插入，需要移动的元素最多，后移次数为n n；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1n-1; ;若在若在a an-1n-1后面插入，后移次数为后面插入，后移次数为1 1；若在尾结点若在尾结点a an n之后插入，则后移次数为之后插入，则后移次数为0 0；故插入时的故插入时的平均平均移动次数为：移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少种插入形式共有多少种插

18、入形式? ?连头带尾有连头带尾有n+1n+1种种! !所有所有可能的元素移动次数合计可能的元素移动次数合计： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/225同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入效率：插入效率：删除效率：删除效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin教材教材P25算法算法2.5也是对执行效率的推导：也是对执行效率的推导：因为没有占用辅助空间！因为没有占用辅助空间！含义：对于顺序表，插入、删除操含义：对于顺序表，插入、删除操作平均需要移动一半元素作平均需要移动一半元素( n / 2 )O(1)O(1)即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为 O(n)26例例1(1(华为招聘试题华为招聘试题) )：试用试用C C或类或类C C语言编写一语言编写一高效高效算法，将一顺序存储的线性表（设元素均为整型算法，将一顺序存储的线性表（设元素均为整型量）中所