数据结构第2章-1顺序表操作的效率分析.pptVIP

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