《数据结构第2章-1顺序表操作的效率分析.ppt》由会员分享，可在线阅读，更多相关《数据结构第2章-1顺序表操作的效率分析.ppt（22页珍藏版）》请在三一办公上搜索。
1、1,三、顺序表操作的效率分析,时间效率分析:算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.注意：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,2,推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次；若在a1后面插入，要后移n-1个元素，后移次数为n
2、-1;若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+n=n(n+1)/2 共有多少种插入形式?连头带尾有n+1种!故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n),3,同理可证：顺序表删除一元素的时间效率为:T(n)=(n-1)/2 O(n)即插入、删除算法的平均时间复杂度为 O(n),4,简单回顾,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点:可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素;需要预先确定数据元素的最大个数。解决问题的思路：改
3、用另一种线性存储方式：,链式存储结构,5,2.3 线性表的链式存储结构及其运算,一、单链表的存储结构二、单 链表的操作实现三、链表的运算效率分析,6,2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。,7,2.3.1 线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，特点：这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意
4、位置上的。链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：,8,其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。,9,、单链式及表示方法(1)单链表:构成链表的结点只有一个指向直接后继结点的指针
5、。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。,如何实现？,通过指针来实现！,让每个存储结点都包含两部分：数据域和指针域,指针域,数据域,next,data,或,样式：,数据域：存储元素数值数据,指针域：存储直接后继的存储位置,设计思想：牺牲空间效率换取时间效率,一、单链表的存储结构,10,定义单链表结点的结构体如下:typedef struct Node DataType data;struct Node*next;SLNode;其中,data域用来存放数据元素,next域用来存放指向下一个结点的指针。,11,例：请画出26个英文字母表的链式存储结构。,该字母表在内存中链式存放的样式
6、举例如下：,解：该字母表的逻辑结构为：（a,b,y,z）,链表存放示意图如下：,讨论1：每个存储结点都包含两部分：数据域和。,讨论2：在单链表中，除了首元结点外，任一结点的存储位置 由 指示。,其直接前驱结点的链域的值,指针域(链域),12,1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。,循环链
7、表示意图：,head,(2)与链式存储有关的术语：,13,4）头指针、头结点和首元结点的区别,头指针,头结点,首元结点,头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a的结点。,示意图如下：,14,答：,讨论1.在链表中设置头结点有什么好处？,讨论2.如何表示空表？,头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编
8、程更方便。,答：,无头结点时，当头指针的值为空时表示空表；,有头结点时，当头结点的指针域为空时表示空表。,头结点不计入链表长度！,15,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,称：头指针H的值是31,、带头结点单链表和不带头结点单链表的比较例：,16,上例链表的逻辑结构示意图有以下两种形式：,区别：无头结点 有头结点,头结点不计入链表长度！,17,对比带头结点的单链表的插入、删除过程和不带带头结点的单
9、链表的插入、删除过程，可以得知：若设计的单链表带头结点，则无论是在第一个数据元素结点前插入还是在其他数据元素结点前插入都不会改变头指针的数值。若设计的单链表不带头结点，则在第一个数据元素结点前插入与在其他数据元素结点前插入其算法的处理方法不同。在单链表中删除一个结点时类似。因此，单链表一般构造成带头结点的单链表。,18,讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？,因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。,答：,以26个字母的链表为例，每个结点都有两个分量：,设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next
10、表示，这两个分量如何赋值？,方式1：直接表示为 node.dataa；node.next=q方式2：p指向结点首地址，然后 p-data=a;p-next=q;方式3：p指向结点首地址，然后(*p).data=a；(*p).nextq,19,设p为指向链表的第i个元素的指针,则第i个元素的数据域写为，指针域写为。,练习：,p-data,ai的值,p-next,ai+1的地址,附1：介绍C的三个有用的库函数/算符（都在 中）：sizeof(x)计算变量x的长度（字节数）；malloc(m)开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)释放指针p所指变量的存储空间，即彻底删除一个
11、变量。,20,sizeof(x)计算x的长度malloc(m)开m字节空间free(p)删除一个变量,问1：自定义结构类型变量node的长度m是多少？,问2：结构变量node的首地址(指针p）是多少？,问3：怎样删除结构变量node？,msizeof(node)/单位是字节,p(node*)malloc(m),free(p)/只能借助node的指针删除！,P-data=a;p-next=q,21,对于指向结构类型的指针变量，可说明为：SLNode*p,*q;/或用 struct SLNode*p,*q;/注：上面已经定义了SLNode为用户自定义的Node类型。,类型定义和变量说明可以合写为：typedef struct Node/Node是自定义结构类型名称 DataType data;/定义数据域的变量名及其类型 struct Node*next;/定义指针域的变量名及其类型SLNode，*p;/SLNode是Node结构类型的类型替代,*p是指针型的Node结构类型的替代,附2：补充结构数据类型的C表示法,22,编程训练建议：简单：先建立一个整型数的单链表，然后统计单链表中数据元素为0的个数。稍难：先建立一个字母单链表并输出到屏幕上，再试着插入一个字母（例如将I插入到L之后）。,
