第2章线性表1

1、1上堂课要点回顾上堂课要点回顾数据结构课程数据结构课程涉及数学、计算机硬件和计涉及数学、计算机硬件和计算机软件算机软件数据结构定义数据结构定义指互相有关联的数据元素的指互相有关联的数据元素的集合，用集合，用D_S=( D, S ) 或或 S=( D, R) 表示。数据结构内容数据结构内容数据的逻辑结构、存储结构数据的逻辑结构、存储结构和运算和运算 算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率 2数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构3第第2 2章章 线性表线性表第第3 3章章 栈和

2、队列栈和队列第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表 线性结构线性结构若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a1 , a2 , , an） 线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）4线性结构的特点：线性结构的特点： 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个直接前驱

3、和一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a1 , a2 , , an） 线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是-线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的见第见第2章章5第第2章章 线性表线性表2.1 线性表的逻辑结构线性表的逻辑结构 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 应用举例应用举例 作业作业6（a1, a2, ai-

4、1，ai, ai1 ，, an）2.1 线性表的逻辑结构线性表的逻辑结构 1. 线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点7例例1 分析分析26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级2001011810205于春梅于春梅女女 18200

5、1级电信级电信016班班2001011810260何仕鹏何仕鹏男男 182001级电信级电信017班班2001011810284王王 爽爽女女 182001级通信级通信011班班2001011810360王亚武王亚武男男 182001级通信级通信012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性8练：判断下列叙述的正误：练：判断下列叙述的正误：1. 数据的逻辑结构是指数据元素之间的逻

6、辑关系，数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。是用户按使用需要建立的。2. 线性表的逻辑结构定义是唯一的，不依赖于计线性表的逻辑结构定义是唯一的，不依赖于计算机。算机。3. 数据结构是指相互之间存在一种或多种关系的数据结构是指相互之间存在一种或多种关系的数据元素的全体。数据元素的全体。4. 线性结构反映结点间的逻辑关系是一对一的。线性结构反映结点间的逻辑关系是一对一的。一维向量是线性表，但二维或一维向量是线性表，但二维或N维数组不是。维数组不是。5.“同一数据逻辑结构中的所有数据元素都具有同一数据逻辑结构中的所有数据元素都具有相同的特性相同的特性”是指数据元素所包含

7、的数据项的是指数据元素所包含的数据项的个数都相等。个数都相等。92.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 顺序表的表示顺序表的表示2.2.2 顺序表的实现顺序表的实现2.2.3 顺序表的运算效率分析顺序表的运算效率分析本节小结本节小结作作 业业102.2.1 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素，可通过存储线性表的元素，可通过数组数组VnVn来实现。来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序

8、表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻11线性表顺序存储特点：线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（素存放位置亦可求出（利用数组下标利用数组下标）。计算方法）。计算方法是（是（参见存储结构示意图参见存储结构示意图）：）：设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为

9、首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L 注意：注意：C C语言中的数组的下标从语言中的数组的下标从0 0开始，开始， 即：即：VnVn的有效范围是的有效范围是V0V0Vn-1Vn-112线性表的顺序存储结构示意图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i

10、 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 L13一个一维数组，下标的范围是一个一维数组，下标的范围是到，每个数组元素用相邻的到，每个数组元素用相邻的个字节个字节存储。存储器按字节编址，设存储数组存储。存储器按字节编址，设存储数组元素元素 的第一个字节的地址是的第一个字节的地址是，则则 的第一个字节的地址是的第一个字节的地址是 113例例1因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址计算通式为：地址计算通式为：LOC

11、(ai) = LOC(a1) + L *（i-1）14用数组用数组V来存放来存放26个英文字母组成个英文字母组成的线性表（的线性表（a，b，c，z），写出在顺），写出在顺序结构上序结构上生成生成和和显示显示该表的该表的C语言程序。语言程序。 void build() /*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/ int i;V0=a;for(i=1;i=n-1;i+) Vi=Vi-1+1; 核心语句：核心语句：法法1 Vi= Vi-1+1;法法2 Vi=a+i;法法3 Vi=97+i;例例215void main(void) /*主函数主函数，字母线性表的生成和输出，字母线

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

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

14、位置元素前移一个位置/ / 表长减表长减1 1 核心语句：核心语句：20123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：21顺序表插入和删除的完整程序可自行用顺序表插入和删除的完整程序可自行用C C语言编制。语言编制。自行上机练习题：自行上机练习题：设有线性表设有线性表 LALA（3,5,8,113,5,8,11）和）和 LB=LB=（2,6,8,9,11,15,202,6,8,9,11,15,20）；）； 若若LALA和和LBLB分别表示两个集合分别表示两个集

15、合A A和和B B，求新集合，求新集合 A AA U BA U B（并并操作，相同元素不保留）；操作，相同元素不保留）；注：此题来源于教材的例注：此题来源于教材的例2.12.1和例和例2.22.2，见，见P20P20按规律插入按规律插入插入到尾部插入到尾部预测输出：预测输出：LA=LA=（3,5,8,11,3,5,8,11,2,6,9,15,202,6,9,15,20） 将将LALA与与LBLB表归并，要求仍有序（相同元素要保留）表归并，要求仍有序（相同元素要保留）预测输出：预测输出：LC=LC=（2,2,3,5,3,5,6,8,6,8,8,8,9,11,9,11,11,11,15,2015,

16、20）222.2.3 顺序表的运算效率分析顺序表的运算效率分析 算法时间主要耗费在移动元素的操作上，因此算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数移动元素次数) 移动元素的个数取决于插入或删除元素的位置移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若要考虑在各种位置插入（共若要考虑

17、在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数，该如何计算？移动次数，该如何计算？讨论讨论1：若在长度为若在长度为 n 的线性表的第的线性表的第 i 位前位前 插入一插入一元素，则向后移动元素的次数元素，则向后移动元素的次数f(n)为为:f(n) =n i + 1时间效率分析时间效率分析:23讨论讨论2：若在长度为若在长度为n n的线性表上删除第的线性表上删除第i i位元素，位元素，向前移动元素的次数向前移动元素的次数f(n)f(n)为：为： f(n) =f(n) =思考：思考：若删除尾结点，则根本无需移动（特别快）；若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中元

18、素全部要前移（特别慢）；若删除首结点，则表中元素全部要前移（特别慢）；若要考虑在各种位置删除（共若要考虑在各种位置删除（共n+1种可能）的种可能）的平均平均移动次数，该如何计算？移动次数，该如何计算？n i可以证明：可以证明：插入、删除操作平均需要移动一半元素插入、删除操作平均需要移动一半元素(n/ 2)插入、删除算法的平均插入、删除算法的平均时间时间复杂度为：复杂度为：O(n)显然，顺序表的显然，顺序表的空间空间复杂度复杂度S(n)=O(1)S(n)=O(1)（没有占用辅助空间）（没有占用辅助空间）24证明：证明：假定在每个元素位置上插入假定在每个元素位置上插入x x的可能性都一样（即的可能

19、性都一样（即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1;n-1;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计：所有可能的元素

20、移动次数合计： 0+1+n = n(n+1)/20+1+n = n(n+1)/2所以平均移动次数为：所以平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2O(n)O(n) 共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 O(n)O(n) 25教材教材P25算法算法2.5也是对执行效率的推导：也是对执行效率的推导：假定在表中任意位置插入、删除元素都是等概率的，假定在表中任意位置插入、删除元素都是等概率的，插入概率

21、插入概率p(i)=1/(n+1) ，删除概率，删除概率q(i)=1/n ，则：，则：插入操作时间效率插入操作时间效率（平均移动次数）（平均移动次数） 2) 1(11) 1(1111ninninpEniniiis删除操作时间效率删除操作时间效率（平均移动次数）（平均移动次数） 21)(1)(11ninninqEniniidl26本节小结本节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的：逻辑关系上相邻的两个元素在物理存储位置上也相邻；两个元素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素；可以随机存取表中任一元素；缺点：缺点：在插入，删除某一元素时，需要移动大在

22、插入，删除某一元素时，需要移动大量元素。量元素。为克服这一缺点，我们引入另一种存储形式：为克服这一缺点，我们引入另一种存储形式：链式存储结构链式存储结构见见2.3节节272.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 链表的表示链表的表示2.3.2 链表的实现链表的实现2.3.3 链表的运算效率分析链表的运算效率分析本节小结本节小结作作 业业282.3.1 链表的表示链表的表示链式存储结构特点：链式存储结构特点：其结点在存储器中的其结点在存储器中的位置是位置是随意随意的，的，即逻辑上相邻的数据元素逻辑上相邻的数据元素在物理上不一定相邻在物理上不一定相邻。如何实现？ 通过来实现注

23、意：注意：每个存储结点都包含两部分：每个存储结点都包含两部分： 数据域数据域和和指针域指针域29例例1 画出画出26 个英文字母表的链式存储结构。个英文字母表的链式存储结构。该字母表在内存的链式存放示意图如下：该字母表在内存的链式存放示意图如下： 解：该字母表的逻辑结构为：解：该字母表的逻辑结构为：（ a, b, ,y, z）aheadb/z各结点由两个域组成：各结点由两个域组成：数据域：数据域：存储元素数值数据；存储元素数值数据；指针域：指针域：存储直接后继或者直接前驱的存储位置。存储直接后继或者直接前驱的存储位置。指针数据指针数据指针或或样式：样式：30与链式存储有关的术语：与链式存储有关的术语：1、结点：、结点：数据元素的存储映像。由数据域和指针域两部分组成；数据元素的存储映像。由数据域和指针域两部分组成；2、链表：、链表： n 个结点由个结点由指针链指针链组成一个链表。它是线性表的链式组成一个链表。它是线性表的链式存储映像存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。3、单链表、