数据结构第三次课-第2章线性表.ppt

《数据结构第三次课-第2章线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构第三次课-第2章线性表.ppt（34页珍藏版）》请在三一办公上搜索。

1、1,每课一贴：两个人在森林里，遇到了一只大老虎。A就赶紧从背后取下一双更轻便的运动鞋换上。B急死了，骂道：“你干嘛呢，再换鞋也跑不过老虎啊！”A说：“我只要跑得比你快就好了。”二十一世纪，没有危机感是最大的危机。即使是电信，银行，保险，甚至是公务员这些我们以为非常稳定和有保障的职业，也会面临许多的变数。更多的老虎来临时，我们有没有准备好自己的跑鞋？,2,数据结构课程的内容,3,(2，3，4，J，Q，K，A）,生活实例：,4,简言之，线性结构反映结点间的逻辑关系是 一对一(1:1)的,线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的

2、数据元素除第一个元素外，集合中的每个数据元素均只有一个前驱除最后一个元素外，集合中的每个数据元素均只有一个后继,5,（逻辑、存储和运算）,线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是-,线性表,第2章,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 应用举例,7,（a1,a2,ai-1，ai,ai1，,an）,2.1 线性表的逻辑结构,2.1.1 线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总

3、个数，即表长,空表,线性终点,8,例1 分析一副扑克的点数组成的英文表,(2，3，4，J，Q，K，A）,例2 分析学生情况登记表,数据元素都是记录;元素间关系是线性,数据元素都是牌面点数;元素间关系是线性,同一线性表中的元素必定具有相同特性,9,练：判断下列叙述的正误：,1.线性表的逻辑结构定义是唯一的，不依赖于计算机。2.线性结构反映结点间的逻辑关系是一对一的。3.一维数组是线性表，但二维或N维数组不是。4.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,10,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示2.2.2 顺序表的实现2.2

4、.3 顺序表的运算效率分析,顺序表小结,11,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素，可通过数组Vn来实现。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,简言之，逻辑上相邻，物理上也相邻,12,线性表的顺序存储结构示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b+L,b+(i-1)L,b+(n-1)L,13,线性表顺序存储特点：,1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元

5、素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai)=LOC(a1)+L*（i-1）LOC(ai+1)=LOC(ai)+L,注意：Java语言中的数组的下标从0开始，即：Vn的有效范围是V0Vn-1,14,一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的起始地址是，则的起始地址是,113,例1,因此：LOC(M3)=98+5(3-0)=113,解：地址计算通式为：,LOC(ai)=LOC

6、(a1)+L*（i-1）,15,2.2.2 顺序表的实现（或操作）,回忆：数据结构基本运算操作有：修改、插入、删除、查找、排序,1)修改 通过数组的下标便可访问某个特定元素并修改之。,核心语句:Vi=x;,显然，顺序表修改操作的时间效率是T(n)=O(1),16,2)插入 在线性表的第i个位置前插入一个元素,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,17,实现步骤：？将第n至第i 位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i 是否合法?表是否已满?应当有1in+1 或 i=1,n+1,for(j=n;j=i;j-)aj+1=a

7、j;ai=x;n+;,/元素后移一个位置,/插入x,/表长加1,核心语句：,18,3)删除 删除线性表的第i个位置上的元素,删除顺序表中某个指定的元素的示意图如下：,19,实现步骤：？将第i 至第n 位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i 是否合法?应当有1in 或 i=1,n,for(j=i+1;j=n;j+)aj-1=aj;n-;,/元素前移一个位置,/表长减1,核心语句：,20,练习题：设有线性表 LA（3,5,8,11）和 LB=（2,6,8,9,11,15,20）；若LA和LB分别表示两个集合A和B，求新集合 AA U B（并操作，相同元素不保留）；预测输

8、出：LA=（3,5,8,11,2,6,9,15,20）,按规律插入,插入到尾部,将LA与LB表归并，要求仍有序（相同元素要保留）预测输出：LC=（2,3,5,6,8,8,9,11,11,15,20）,21,2.2.3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？,讨论1：若在长度为 n 的线性表

9、的第 i 位前 插入一元素，则向后移动元素的次数f(n)为:f(n)=n i+1,时间效率分析:,22,讨论2：若在长度为n的线性表上删除第i位元素，向前移动元素的次数f(n)为：f(n)=,思考：若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中元素全部要前移（特别慢）；若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？,n i,可以证明：插入、删除操作平均需要移动一半元素(n/2)插入、删除算法的平均时间复杂度为：O(n),显然，顺序表的空间复杂度S(n)=0（没有占用辅助空间）,23,证明：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算

10、平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次；若在a1后面插入，要后移n-1个元素，后移次数为n-1;若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+n=n(n+1)/2,所以平均移动次数为：n(n+1)/2(n+1)n/2 T(n)=O(n),共有多少种插入形式?连头带尾有n+1种,同理可证：顺序表删除一元素的时间效率为:f(n)=(n-1)/2 T(n)=O(n),24,假定在表中任意位置插入、删除元素都是等概率的，插入概率p(i)=1/(n+1)，删除概率q(i)=1/

11、n，则：,插入操作时间效率（平均移动次数）,删除操作时间效率（平均移动次数）,故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,25,顺序表小结,链式存储结构,见2.3节,顺序存储结构的优缺点优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充,26,2.3 线性表的链式表示和实现,2.3.1 链表的表示2.3.2 链表的实现2.3.3 链表的运算效率分析,链表小结,27,2.3.1 链表的表示,链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数

12、据元素在物理上不一定相邻。,如何实现？,通过指针来实现,注意：每个存储结点都包含两部分：数据域和指针域,28,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,29,例1 画出26 个英文字母表的链式存储结构。,该字母表在内存的链式存放示意图如下：,解：该字母表的逻辑结构为：（a,b,y,z）,各结点由两个域组成：数据域：存储元素数值数据；指针域：存储直接后继或者直接前驱的存储位置。,样式：,30,与链式存储有关的术语：,1、结点：数据元素的存储映像。由数据域和指针域两部分组成；2、链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性

13、表的链式存储结构3、单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。,循环链表示意图：,31,4、头指针、头结点和首元结点,示意图如下：,头指针,头结点,首元结点,头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。,32,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,例：,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,头指针的值是31,33,上例链表的逻辑结构示意图有以下两种形式：,区别：无头结点 有头结点,34,答：,讨论1.在链表中设置头结点有什么好处？,讨论2.如何表示空表？,头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。,答：,无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。,