第3章 线性表

1、数据结构与算法数据结构与算法电子工业出版社电子工业出版社数据结构与算法数据结构与算法 作作 者：胡明者：胡明 王红梅王红梅 出版社：电子工业出版社出版社：电子工业出版社 邮邮 箱：箱：数据结构与算法数据结构与算法电子工业出版社电子工业出版社第第 3 章章 线性表线性表 线性表的逻辑结构线性表的逻辑结构 线性表的存储结构及实现线性表的存储结构及实现 应用实例应用实例 本章的基本内容是：本章的基本内容是：数据结构与算法数据结构与算法电子工业出版社电子工业出版社3.1 引言引言数据元素之间的关系是什么？数据元素之间的关系是什么？数据结构与算法数据结构与算法电子工业出版社电子工业出版社3.1 引言引言

2、数据元素之间的关系是什么？数据元素之间的关系是什么？现实生活中，许多问题抽象出的数据模型是线性表，如何存储现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？这种线性结构并实现插入、删除、查找等基本操作呢？ 数据结构与算法数据结构与算法电子工业出版社电子工业出版社3.1 引言引言 约瑟夫环问题约瑟夫环问题设设n(n0)个人围成一个环，个人围成一个环，n个人的编号分别为个人的编号分别为1，2，n，从第从第1个人开始报数，报到个人开始报数，报到m时停止报数，报时停止报数，报m的人出环，再的人出环，再从他的下一个人起重新报数，报到从他的下一个人起重新

3、报数，报到m时停止报数，报时停止报数，报m的出的出环，环，如此下去，直到所有人全部出环为止。当任意给，如此下去，直到所有人全部出环为止。当任意给定定n和和m后，求后，求n个人出环的次序。个人出环的次序。n = 5, m = 3时的出圈次序：时的出圈次序：约瑟夫环问题的数据模型是一种典型的环状线性结构。如何存约瑟夫环问题的数据模型是一种典型的环状线性结构。如何存储这种环形结构并求解约瑟夫环的出环次序呢？储这种环形结构并求解约瑟夫环的出环次序呢？ 数据结构与算法数据结构与算法电子工业出版社电子工业出版社p 线性表：线性表：简称表，是简称表，是n（n0）个具有）个具有相同类型相同类型的的数据元素的数

4、据元素的有限序有限序列列。p 线性表的长度：线性表的长度：线性表中数据元素的个数。线性表中数据元素的个数。p 空表：空表：长度等于零的线性表，长度等于零的线性表，记为：记为：L=( )。p 非空表非空表记为：记为：L（a1, a2 , , ai-1, ai , , an)3.2 线性表的逻辑结构线性表的逻辑结构线性表的定义线性表的定义其中，其中，ai（1in）称为数据元素；）称为数据元素；下角标下角标 i 表示该元素在线性表中的位置或序号表示该元素在线性表中的位置或序号 。数据结构与算法数据结构与算法电子工业出版社电子工业出版社a1a3a4ana23.2 线性表的逻辑结构线性表的逻辑结构线性表

5、的特性线性表的特性1. 有限性有限性：线性表中数据元素的个数是有穷的。：线性表中数据元素的个数是有穷的。2. 相同性相同性：线性表中数据元素的类型是同一的。：线性表中数据元素的类型是同一的。3. 顺序性顺序性：线性表中相邻的数据元素：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1, ai)，即，即ai-1是是ai的前驱，的前驱， ai是是ai-1的后继；的后继；a1无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。 数据结构与算法数据结构与算法电子工业出版社电子工业出版社线性表的抽象数据类型定义

6、线性表的抽象数据类型定义ADT ListData 线性表中的数据元素具有相同类型，线性表中的数据元素具有相同类型， 相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系OperationInitList 前置条件前置条件：表不存在：表不存在 输入输入：无：无 功能功能：表的初始化：表的初始化 输出输出： 无无 后置条件后置条件：建一个空表：建一个空表3.2 线性表的逻辑结构线性表的逻辑结构数据结构与算法数据结构与算法电子工业出版社电子工业出版社DestroyList 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：销毁表：销毁表 输出输出：无：无 后置条件后置条件：释放表所占

7、用的存储空间：释放表所占用的存储空间Length 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：求表的长度：求表的长度 输出输出：表中数据元素的个数：表中数据元素的个数 后置条件后置条件：表不变：表不变3.2 线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构与算法数据结构与算法电子工业出版社电子工业出版社Get 前置条件前置条件：表已存在：表已存在 输入输入：元素的序号：元素的序号i 功能功能：在表中取序号为：在表中取序号为i的数据元素的数据元素 输出输出：若：若i合法，返回序号为合法，返回序号为i的元素值，否则抛出异常的元素值，否则

8、抛出异常 后置条件后置条件：表不变：表不变Locate 前置条件前置条件：表已存在：表已存在 输入输入：数据元素：数据元素x 功能功能：在线性表中查找值等于：在线性表中查找值等于x的元素的元素 输出输出：若查找成功，返回：若查找成功，返回x在表中的序号，否则返回在表中的序号，否则返回0 后置条件后置条件：表不变：表不变3.2 线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构与算法数据结构与算法电子工业出版社电子工业出版社Insert前置条件前置条件：表已存在：表已存在输入输入：插入：插入i；待插待插x功能功能：在表的第：在表的第i个位置处插入一个新元素个

9、位置处插入一个新元素x输出输出：若插入不成功，抛出异常：若插入不成功，抛出异常 后置条件后置条件：若插入成功，表中增加一个新元素：若插入成功，表中增加一个新元素Delete前置条件前置条件：表已存在：表已存在输入输入：删除位置：删除位置i功能功能：删除表中的第：删除表中的第i个元素个元素 输出输出：若删除成功，返回被删元素，否则抛出异常：若删除成功，返回被删元素，否则抛出异常 后置条件后置条件：若删除成功，表中减少一个元素：若删除成功，表中减少一个元素3.2 线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构与算法数据结构与算法电子工业出版社电子工业出版社

10、Empty 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：判断表是否为空：判断表是否为空 输出输出：若是空表，返回：若是空表，返回1，否则返回，否则返回0 后置条件后置条件：表不变：表不变ADT进一步说明进一步说明: :（1 1）线性表的基本操作根据实际应用是而定；）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。对不同的应用，操作的接口可能不同。3.2 线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构与算法数据结构与算

11、法电子工业出版社电子工业出版社3.3 线性表的存储结构及实现线性表的存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743 4存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743存储空间的起始位置存储空间的起始位置 4用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（

12、最大长度）顺序表的当前长度顺序表的当前长度3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743 4如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度一般情况下，一般情况下，(a1，a2，, ai-1，ai ,

13、, an)的顺序存储：的顺序存储：数组的长度数组的长度Max线性表的长度线性表的长度Length数组的长度大于等于当前线性表的长度数组的长度大于等于当前线性表的长度 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序表存储结构的定义顺序表存储结构的定义3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何求得任意元素的存储地址？如何求得任意元素的存储地址？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度一般情况下，一般情况下，(a1，a

14、2，, ai-1，ai , , an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度Loc(ai)=Loc(a1) + (i - -1)c随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素一般情况下，一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法

15、数据结构与算法电子工业出版社电子工业出版社存储结构是数据及其逻辑结构在计算机中的表示；存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对查找操作的时间性存取结构是在一个数据结构上对查找操作的时间性能的一种描述。能的一种描述。存储结构和存取结构存储结构和存取结构 “顺序表是一种顺序表是一种随机存取随机存取的的存储存储结构结构”的含义为：的含义为：在顺序表这种存储结构上进行的查找操作，其时间在顺序表这种存储结构上进行的查找操作，其时间性能为性能为O(1)。3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社操作接口：操作

16、接口：void InitList(SeqList &L) 算法描述：算法描述：void SeqList(SeqList &L) L.length = 0; 顺序表的实现顺序表的实现初始化顺序表初始化顺序表 datalength03.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社操作接口：操作接口：void Creat(SeqList &L, DataType a , int n) 顺序表的实现顺序表的实现建立顺序表建立顺序表 顺序表顺序表 数组数组a3512243342535122433423.3 线性表的存储结

17、构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社void Creat(SeqList &L, DataType a , int n) if (n MaxSize) printf(参数非法参数非法); exit(-1); for (i = 0; i =MaxSize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序号）指的是元素的序号）顺序表的实现顺序表的实现插入插入 435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件3.3 线性表的存储结构及实现线性表

18、的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社1. 如果表满了，则抛出如果表满了，则抛出上溢上溢异常异常;2. 如果元素的插入位置不合理，则抛出如果元素的插入位置不合理，则抛出位置位置异常异常;3. 将最后一个元素至第将最后一个元素至第i个元素分别向后移动一个位置；个元素分别向后移动一个位置；4. 将元素将元素x填入位置填入位置i处；处；5. 表长加表长加1；算法描述算法描述伪代码伪代码顺序表的实现顺序表的实现插入插入3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社void Insert(SeqList &a

19、mp;L, int i, DataType x) if (L.length = MaxSize) printf(上溢上溢); exit(-1); if (i length + 1) printf(位置位置); exit(-1); for (j = L.length; j = i; j-) /j表示元素序号表示元素序号 L.dataj = L.dataj - 1; L.datai - 1 = x; L.length+;算法描述算法描述C描述描述顺序表的实现顺序表的实现插入插入基本语句基本语句？3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出

20、版社最好最好情况（情况（ i=n+1）：）： 基本语句执行基本语句执行0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（ i=1）：）： 基本语句执行基本语句执行n+1次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：）： 时间复杂度为时间复杂度为O(n)。时间性能分析时间性能分析顺序表的实现顺序表的实现插入插入 + +- -+ += =11)=1(niiinp + +- -+ + += =11)=1(11niinn2n=O(n)3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社操作接口：操作接口

21、： DataType Delete(int i)删除前：删除前：( (a1, , ai- -1, ,ai, ,ai+1,an) )删除后：删除后：( (a1,ai- -1, ,ai+1, ,an) ) 顺序表的实现顺序表的实现删删 除除ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社例：（例：（35, 33, 12, 24, 42），），删除删除i=2的数据元素。的

22、数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1. 分析边界条件；分析边界条件；2. 分别给出伪代码和分别给出伪代码和C描述的算法；描述的算法；3. 分析时间复杂度。分析时间复杂度。顺序表的实现顺序表的实现删删 除除 535a1a2a3a40 1 2 3 4422412334a51224423.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序表的实现顺序表的实现按位查找按位查找操作接口：操作接口： DataType Get(int i) 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲

23、n算法描述：算法描述：DataType Get(SeqList &L, int i) if (i L.length) printf(查找位置非法查找位置非法); exit(-1); else return L.datai - 1;时间复杂度时间复杂度？3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序表的实现顺序表的实现按值查找按值查找操作接口：操作接口： int Locate(DataType x ) 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35, 33, 12, 24, 42） 中查找

24、值为中查找值为12的元素，的元素，返回在表中的序号。返回在表中的序号。iii注意序号和下标之间的关系注意序号和下标之间的关系3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社int Locate(SeqList &L, DataType x) for (i = 0; i data ;*s.data ;data如何引用指针域如何引用指针域？nexts-next;s=(Node *)malloc(sizeof(Node) ;3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单

25、链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表重点在数据元素之间的逻辑关系的重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。表示，所以，将实际存储地址抽象。什么是存储结构什么是存储结构？3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表头指针：头指针：指向第一个结

26、点的地址。指向第一个结点的地址。尾标志：尾标志：终端结点的指针域为空。终端结点的指针域为空。3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表空表和非空表不统一，缺点？空表和非空表不统一，缺点？如何将空表与非空表统一如何将空表与非空表统一？3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社头结点：头结点：在在单链表的第以一个元

27、素结点之前附设一个单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。类型相同的结点，以便空表和非空表处理统一。 单链表单链表非空表非空表firsta1a2an空表空表first3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现初始化单链表初始化单链表 操作接口操作接口： Node *InitList(Node *first) Node *InitList(Node *first) first = (Node *)malloc(sizeof(Node); /生成头结点生成头结点 firs

28、t-next = NULL; /头结点的指针域置空头结点的指针域置空 return first;first3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现遍历操作遍历操作操作接口操作接口： void PrintList(Node *first) v核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点。从头结点（或开始结点）出发，通过工作指针的反复后移而将（或开始结点）出发，通过工作指针的反复后移而将整个单链表整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）（或遍历）

29、。firsta1pa2panaippp3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现遍历操作遍历操作算法描述：算法描述：void PrintList(Node *first) p = first-next; /工作指针工作指针p初始化初始化 while (p != NULL) printf(p-data); p = p-next; p+能否完成指针后移？能否完成指针后移？a1a2pp+p-next3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表

30、的实现单链表的实现按位查找按位查找操作接口：操作接口： DataType Get(int i);firsta1a2anaipp查找失败查找失败1. 工作指针工作指针p初始化初始化; 累加器累加器count初始化初始化;2. 重复执行下述操作，直到重复执行下述操作，直到p为空：为空： 2.1 工作指针工作指针p后移后移; 2.2 count+;3. 返回累加器返回累加器count的值；的值；pcount =1pcount =2p查找成功查找成功count =i3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社DataType Get(No

31、de *first, int i) p = first-next; count = 1; while (p != NULL & count next; /工作指针工作指针p后移后移 count+; if (p = NULL) printf(位置位置); exit(-1); /查找失败查找失败 else return p-data;单链表的实现单链表的实现按位查找按位查找算法描述算法描述3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社int Locate(Node *first, DataType x) p = first-ne

32、xt; count = 1; while (p != NULL) if (p-data = x) return count; /查找成功查找成功 p = p-next; count+; return 0; /退出循环表明查找失败退出循环表明查找失败单链表的实现单链表的实现按值查找按值查找算法描述算法描述3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现插入插入操作接口：操作接口： void Insert(int i, DataType x); 如何实现结点如何实现结点ai-1、x和和ai之间逻辑关系的变化？之间逻

33、辑关系的变化？pxsfirsta1ai-1anai算法描述：算法描述：s=(Node *)malloc(sizeof(Node); s-data=x;s-next=p-next; p-next=s;3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。 单链表的实现单链表的实现插入插入firsta1anaipxs算法描述：算法描述：s=(Node *)malloc(sizeof(Node); s-data=x;s-next=p-next; p-next=s;pxs由于单链表带头结点，由

34、于单链表带头结点，表头、表中、表尾三种表头、表中、表尾三种情况的操作语句一致。情况的操作语句一致。 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社算法描述算法描述伪代码伪代码 1. 工作指针工作指针p初始化；初始化； 2. 查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点； 3. 若查找不成功，则插入位置不合理，抛出插入位置异常；若查找不成功，则插入位置不合理，抛出插入位置异常； 否则，否则， 3.1 生成一个元素值为生成一个元素值为x的新结点的新结点s； 3.2 将新结点将新结点s插入到结点插入到结点

35、p之后；之后；单链表的实现单链表的实现插入插入3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社void Insert(Node *first, int i, DataType x) p = first ; count = 0; /工作指针工作指针p应指向头结点应指向头结点 while (p != NULL & count next; /工作指针工作指针p后移后移 count+; if (p = NULL) printf(位置位置); exit(-1); else s = (Node *)malloc(sizeof(Node);

36、 s-data = x; /申请一个结点申请一个结点s，其数据域为，其数据域为x s-next = p-next; p-next = s; 单链表的实现单链表的实现插入插入基本语句？时间复杂度？基本语句？时间复杂度？3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现建立单链表建立单链表 操作接口：操作接口：LinkList(DataType a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。算法描述：算法描述：first = (Node *)malloc(sizeof

37、(Node); first-next = NULL; 数组数组a3512243342初始化初始化first3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社操作接口：操作接口：LinkList(DataType a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。数组数组a3512243342算法描述：算法描述：s = (Node *)malloc(sizeof(Node);s-data = a0; s-next = first-next; first-next = s; 插入第一个元素结点插

38、入第一个元素结点first35s单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社操作接口：操作接口：LinkList(DataType a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。数组数组a3512243342依次插入每一个结点依次插入每一个结点12sfirst35算法描述：算法描述：s = (Node *)malloc(sizeof(Node);s-data = a1; s-next = first-next; first-next =

39、 s; 单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社Node *Creat(Node *first, DataType a , int n) first = (Node *)malloc(sizeof(Node); first-next = NULL; /初始化头结点初始化头结点 for (i = 0; i data = ai; /为每个数组元素建立一个结点为每个数组元素建立一个结点 s-next = first-next; first-next = s; return first;单

40、链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：first = (Node *)malloc(sizeof(Node);r = first; 数组数组a3512243342初始化初始化first r单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构

41、与算法电子工业出版社电子工业出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：s = (Node *)malloc(sizeof(Node);s-data = a0;r-next = s; r = s; 数组数组a3512243342插入第一个元素结点插入第一个元素结点first r35s r单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社尾插法：尾插法：将

42、待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 操作接口：操作接口：LinkList(DataType a , int n)数组数组a3512243342依次插入每一个结点依次插入每一个结点first35 r12s r单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：r-next=NULL;数组数组a

43、3512243342最后一个结点插入后最后一个结点插入后first3542s r单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社Node *Creat(Node *first, DataType a , int n) first = (Node *)malloc(sizeof(Node); /生成头结点生成头结点 r = first; /尾指针初始化尾指针初始化 for (i = 0; i data = ai; /为每个数组元素建立一个结点为每个数组元素建立一个结点 r-next = s;

44、 r = s; r-next = NULL; return first;算法描述：算法描述：单链表的实现单链表的实现建立单链表建立单链表 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现删除删除操作接口：操作接口： DataType Delete(int i); p如何实现结点如何实现结点ai-1和和ai之间逻辑关系的变化？之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; free(q);q3.3 线性表的存储结构及实现

45、线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社单链表的实现单链表的实现删除删除算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; free(q);注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。 pqpq表尾的特殊情况：表尾的特殊情况：虽然被删结点不存在，虽然被删结点不存在，但其前驱结点却存在。但其前驱结点却存在。 p-next=NULLfirsta1ana23.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社算法描述算法描述伪代码伪代码 1.工作指针工作指针p初

46、始化；初始化； 2. 查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点； 3. 若若p不存在或不存在或p不存在后继结点，则抛出位置异常；不存在后继结点，则抛出位置异常； 否则，否则， 3.1 暂存被删结点和被删元素值；暂存被删结点和被删元素值； 3.2 摘链，将结点摘链，将结点p的后继结点从链表上摘下；的后继结点从链表上摘下； 3.3 释放被删结点；释放被删结点； 3.4 返回被删元素值；返回被删元素值； 单链表的实现单链表的实现删除删除3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社DataType D

47、elete(Node *first, int i) p = first; count = 0; /注意工作指针注意工作指针p要指向头结点要指向头结点 while (p != NULL & count next; count+; if (p = NULL | p-next = NULL) printf(位置位置); exit(-1); else q = p-next; x = q-data; /暂存被删结点暂存被删结点 p-next = q-next; /摘链摘链 free(q); return x; 单链表的实现单链表的实现删除删除3.3 线性表的存储结构及实现线性表的存储结构及实现数

48、据结构与算法数据结构与算法电子工业出版社电子工业出版社启示：算法设计的一般过程启示：算法设计的一般过程算法设计的一般步骤：算法设计的一般步骤：第一步：确定第一步：确定入口入口（已知条件）、（已知条件）、出口出口（结果）；（结果）；第二步：根据一个小实例画出第二步：根据一个小实例画出示意图示意图；第三步：第三步： 正向思维正向思维：选定一个思考问题的起点，逐：选定一个思考问题的起点，逐步提出问题、解决问题；步提出问题、解决问题； 逆向思维逆向思维：从结论出发分：从结论出发分析为达到这个结论应该先有什么；析为达到这个结论应该先有什么； 正逆结合正逆结合；第四步：写出第四步：写出顶层顶层较抽象算法，

49、分析较抽象算法，分析边界边界情况；情况；第五步：第五步：验证验证第四步的算法；第四步的算法；第六步：写出第六步：写出具体具体算法；算法；第七步：第七步：进一步进一步验证，手工运行。验证，手工运行。数据结构与算法数据结构与算法电子工业出版社电子工业出版社双链表双链表如何求结点如何求结点p的直接前驱，时间性能？的直接前驱，时间性能？为什么可以快速求得结点为什么可以快速求得结点p的后继？的后继？如何快速求得结点如何快速求得结点p的前驱？的前驱？3.3 线性表的存储结构及实现线性表的存储结构及实现firsta1a2an数据结构与算法数据结构与算法电子工业出版社电子工业出版社双链表：双链表：在在单链表的

50、每个结点中再设置一个指向其前单链表的每个结点中再设置一个指向其前驱结点的指针域驱结点的指针域。双链表双链表结点结构：结点结构：priordatanextdata：数据域，存储数据元素；数据域，存储数据元素；prior：指针域，存储该结点的前趋结点地址；指针域，存储该结点的前趋结点地址；next：指针域，存储该结点的后继结点地址。指针域，存储该结点的后继结点地址。3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社typedef int DataType; / DataType为线性表的数据类型为线性表的数据类型typedef struct

51、 DulNode DataType data; struct DulNode *prior, *next; DulNode, *first; /first为双链表的头指针为双链表的头指针双链表双链表启示？启示？时空权衡时空权衡空间换取时间空间换取时间priordatanext定义结点结构：定义结点结构：3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社双链表的操作双链表的操作插入插入s-prior=p; s-next=p-next;p-next-prior=s;p-next=s; ai-1ai操作接口：操作接口： void Insert

52、(DulNode *p, DataType x); pxs注意指针修改的注意指针修改的相对相对顺序顺序3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社双链表的操作双链表的操作删除删除( (p-prior) )-next=p-next; ( (p-next) )-prior=p-prior; 操作接口：操作接口： DataType Delete(DulNode *p); ai-1aipai结点结点p的指针是否需要修改？的指针是否需要修改？free(p); 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电

53、子工业出版社电子工业出版社循环链表循环链表firsta1ai-1anaip从单链表中某结点从单链表中某结点p出发如何找到其前驱？出发如何找到其前驱？将单链表的首尾相接，将终端结点的指针域由空指针将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成改为指向头结点，构成单循环链表单循环链表，简称，简称循环链表循环链表。3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社循环链表循环链表空表和非空表的处理一致空表和非空表的处理一致附设头结点附设头结点first空循环链表空循环链表firsta1ai-1anai非空循环链表非空循环链

54、表3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社firsta1ai-1anai循环链表循环链表插入插入xspxspxsp算法描述：算法描述：s=(Node *)malloc(sizeof(Node); s-data=x; s-next=p-next; p-next=s;3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社 template void LinkList :Insert(int i, DataType x) p = first ; count = 0; while

55、(p != first & count next; count+; if (p = NULL) throw 位置位置; else s = (Node *)malloc(sizeof(Node); s-data = x; s-next = p-next; p-next = s; 循环链表循环链表插入插入与单链表的插入操作相比，差别是什么？与单链表的插入操作相比，差别是什么？3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社循环条件：循环条件：p != NULLp != firstp-next != NULLp-next != fi

56、rst循环链表循环链表循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何查找开始结点和终端结点？如何查找开始结点和终端结点？循环链表循环链表firsta1ai-1anai开始结点：开始结点：first-next 终端结点：将单链表扫描一遍，时间为终端结点：将单链表扫描一遍，时间为O(n)3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社reara1ai-1anai开始结点：开始结点：rear-nex

57、t-next终端结点：终端结点：rear循环链表循环链表带尾指针的循环链表带尾指针的循环链表一个存储结构设计得是否合理，取决于基于该存储一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。结构的运算是否方便，时间性能是否提高。 3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社静态链表：静态链表：用用数组来表示单链表，用数组元素的下标数组来表示单链表，用数组元素的下标来模拟单链表的指针。来模拟单链表的指针。静态链表静态链表data：存储放数据元素；：存储放数据元素；next：也称游标，存储该元素的后继在数组

58、的下标。：也称游标，存储该元素的后继在数组的下标。数组元素（结点）的构成：数组元素（结点）的构成： data next数据域数据域指针域指针域3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社例：线性表例：线性表(张，王，李，赵，吴张，王，李，赵，吴)的静态链表存储的静态链表存储张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data next静态链表静态链表firstavailfirst：静态链表头指针，为了方：静态链表头指针，为了方便插入和删除操作，通常静态链便插入和删除操作，通常静态链表带头结点；表带

59、头结点；avail：空闲链表头指针，空闲链：空闲链表头指针，空闲链表由于只在表头操作，所以不带表由于只在表头操作，所以不带头结点；头结点；3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社静态链表静态链表静态链表的存储结构定义如下：静态链表的存储结构定义如下：const int MaxSize = 10; /最多最多10个数组单元个数组单元typedef int DataType; / DataType是线性表的数据类型是线性表的数据类型typedef struct DataType data; int next; /指针域（也称游标）

60、，注意不是指针指针域（也称游标），注意不是指针 SNode, SListMaxSize;3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社在线性表在线性表(张，王，李，赵，吴张，王，李，赵，吴)中中“王王”之后插入之后插入“孙孙”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data next静态链表静态链表张张 2王王 6李李 4赵赵 5吴吴 -1012345678孙孙 3 8 -1 1data next王之后王之后插入孙插入孙3.3 线性表的存储结构及实现线性表的存储结构及实现数据结构与算法数据结构与算法电子工业出版社电子工业出版社静态链表静态链表假设结点假设结点s插在结点插在结