三、顺序表操作的效率分析 时间效率分析: 算法时间主要耗在移动元素的操作上,因此计算时 间复杂度的基本操作(最深层语句频度) T(n)=0(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置 注意:若插入在尾结点之后,则根本无需移动(特别快) 若插入在首结点之前,则表中元素全部要后移(特别慢) 应当考虑在各种位置插入(共n+1种可能)的平均移动次数才
1 三、 顺序表操作的效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时 间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置. 注意：若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才 合理
推导: 假定在毎个元素位置上插入x的可能性都一样(即概 率P相同),则应当这样来计算平均执行时间: 将所有位置的执行时间相加,然后取平均。 若在首结点前插入,需要移动的元素最多,后移n次; 若在a后面插入,要后移n-1个元素,后移次数为n-1 若在an-后面插入,要后移1个元素 若在尾结点an之后插入,则后移0个元素; 所有可能的元素移动次数合计: 0+1++n=n(n+1)/2 共有多少种插入形式?连头带尾有n+1种 故插入时的平均移动次数为: n(n+1)/2÷(n+1)=n/2≈0(m)
2 推导： 假定在每个元素位置上插入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/2≈O(n)
同理可证: 顺序表删除一元素的时间效率为 T(n)=(n-12≈0(n) 即插入、删除算法的平均时间复杂度为 O(n)
3 同理可证： 顺序表删除一元素的时间效率为: T(n)=(n-1)/2 ≈O(n) 即插入、删除算法的平均时间复杂度为 O(n)
简单回顾 线性表顺序存储结构特点:逻辑关系上相邻的两个元 素在物理存储位置上也相邻; 优点可以随机存取表中任一元素,方便快捷; 缺点:在插入或删除某一元素时,需要移动大量元素; 需要预先确定数据元素的最大个数。 解决问题的思路:改用另一种线性存储方式
4 简单回顾 线性表顺序存储结构特点：逻辑关系上相邻的两个元 素在物理存储位置上也相邻； 优点:可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素; 需要预先确定数据元素的最大个数。 解决问题的思路：改用另一种线性存储方式： 链式存储结构
23线性表的链式表示和实现 单链表的存储结构 二、单链表的操作实现 链表的运算效率分析
5 2.3 线性表的链式表示和实现 一、单链表的存储结构 二、 单 链表的操作实现 三、链表的运算效率分析
单链表的存储结构 1、单链式及表示方法 (1)单链表构成链表的结点只有一个指向直接后继结点 的指针。其结构特点:逻辑上相邻的数据元素在物理上 不一定相邻。 如何实现?通过指针来实现! 让每个存储结点都包含两部分:数据域和指针域 样式:数据域指针域或 ata next 数据域:存储 指针城:存储直接后继的 元素数值数据 存储位置 设计思想:牺牲空间效率换取时间效率
6 １、单链式及表示方法 (1)单链表:构成链表的结点只有一个指向直接后继结点 的指针。其结构特点：逻辑上相邻的数据元素在物理上 不一定相邻。 如何实现？ 通过指针来实现！ 让每个存储结点都包含两部分：数据域和指针域 样式： 数据域 指针域 或 data next 数据域：存储 元素数值数据 指针域：存储直接后继的 存储位置 设计思想：牺牲空间效率换取时间效率 一、 单链表的存储结构
定义单链表结点的结构体如下: typedef struct Node Data Type data struct Node *next SLNode 其中,data域用来存放数据元素,next域用来存放指向下 个结点的指针
7 定义单链表结点的结构体如下: typedef struct Node { DataType data; struct Node *next; }SLNode; 其中,data域用来存放数据元素,next域用来存放指向下 一个结点的指针
链表存放示意图如下: head ][a仁a仁… an ∧ 例:请画出26个英文字母表的链式存储结构。 解:该字母表的逻辑结构为:(a,b,…y,z) 该字母表在内存中链式存放的样式举例如下: head Data link Data link Data link 09201BH“b108 z'NULL 讨论1:每个存储结点都包含两部分:数据域和指针域链域)。 讨论2:在单链表中,除了首元结点外,任一结点的存储位置 由_其直接前驱结点的链域的值指示
8 例：请画出26个英文字母表的链式存储结构。 该字母表在内存中链式存放的样式举例如下： 解：该字母表的逻辑结构为：（ a, b, … ,y, z） 链表存放示意图如下： head a1 a2 a /\ …… n 讨论1 ：每个存储结点都包含两部分：数据域和 。 讨论2：在单链表中，除了首元结点外，任一结点的存储位置 由 其直接前驱结点的链域的值 指示。 指针域(链域)
(2)与链式存储有关的术语: 1)结点:数据元素的存储映像。由数据蜮和指针域两部分组成 2)链表:n个结点由指针链组成一个链表。它是线性表的链式 存储映像,称为线性表的链式存储结构 3)单链表、双链表、多链表、循环链表: 结点只有一个指针城的链表,称为单链表或线性链表; 有两个指针域的链表,称为双链表(但未必是双向链表) 有多个指针城的链表,称为多链表 首尾相接的链表称为循环链表。 循环链表示意图 head a1 a2 head
9 1）结点：数据元素的存储映像。由数据域和指针域两部分组成； 2）链表： n 个结点由指针链组成一个链表。它是线性表的链式 存储映像，称为线性表的链式存储结构。 3）单链表、双链表、多链表、循环链表： • 结点只有一个指针域的链表，称为单链表或线性链表； • 有两个指针域的链表，称为双链表（但未必是双向链表）； • 有多个指针域的链表，称为多链表； • 首尾相接的链表称为循环链表。 head a1 a2 …… an 循环链表示意图： head (2) 与链式存储有关的术语：
4)头指针、头结点和首元结点的区别 示意图如下: I head nfo a1 a2 八 头指针头结点首元结点 头指钍是指向链表中第一个结点(或为头结点、或为首元 结点)的指针; 头结点是在链表的首元结点之前附设的一个结点;数据城 内只放空表标志和表长等信息,它不计入表长度 首元结点是指链表中存储线性表第一个数据元素a。的结点
10 4）头指针、头结点和首元结点的区别 头指针 头结点 首元结点 head info a1 a2 … an ^ 头指针是指向链表中第一个结点（或为头结点、或为首元 结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域 内只放空表标志和表长等信息，它不计入表长度。 首元结点是指链表中存储线性表第一个数据元素a０的结点。 示意图如下：