线性表逻辑结构、顺序表示与链式表示

1、线性表逻辑结构、顺序表示与链式表示数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构近近3周周上课内容上课内容第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串串线性结构线性结构在数据元素的非空有限集中，有且仅有一个开始在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。个直接前趋和一个直接后继。可表示为可表示为：（a1 , a2 , , an） 线性结构的特点：线性结构的特点：

2、（逻辑、存储（逻辑、存储和运算）和运算）线性结构包括线性表、堆栈、队列、字符串、线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是数组等等，其中，最简单、最常用的是-线性表线性表见第见第2章章简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一一对一对一 的。的。第第2 2章章 线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例 （a1, a2, ai-1，ai, ai+1 ，,

3、an）2.12.1 线性表的逻辑结构线性表的逻辑结构 1. 线性表的定义：线性表的定义：是是n个数据元素的有限序列个数据元素的有限序列n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，是元素的序下标，是元素的序号，表示元素在表号，表示元素在表中的位置中的位置n为元素总个数，为元素总个数，即表长即表长空表空表线性终点线性终点例例1 分析分析 26 个英文字母组成的英文表个英文字母组成的英文表( A, B, C, D, , Z )学号学号姓名姓名性别性别年龄年龄班级班级20010118102052001011810205于春梅于春梅女女 18

4、1820062006级电信级电信016016班班20010118102602001011810260何仕鹏何仕鹏男男 18 1820062006级电信级电信017017班班20010118102842001011810284王王 爽爽女女 18 1820062006级通信级通信011011班班20010118103602001011810360王亚武王亚武男男 18 1820062006级通信级通信012012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是

5、线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性线性表的抽象数据类型的定义：线性表的抽象数据类型的定义： ADT List 数据对象：数据对象：D=ai | aiElemset, i=1, 2, n, n0 数据关系：数据关系：R1= | ai-1, aiD, i=2, , n 基本操作：基本操作： InitList(&L) 操作结果：构造一个空的线性表操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：销毁线性表操作结果：销毁线性表L ClearList(&L)初始条件：线性表

6、已存在初始条件：线性表已存在操作结果：置线性表操作结果：置线性表L为空表为空表IsListEmpty(L)初始条件：线性表已存在初始条件：线性表已存在操作结果：若线性表操作结果：若线性表L为空表，则返回为空表，则返回TRUE，否则返回，否则返回FALSEListLength(L)初始条件：线性表已存在初始条件：线性表已存在操作结果：返回线性表操作结果：返回线性表L数据元素个数数据元素个数GetElem(L, i, &e)初始条件：线性表已存在（初始条件：线性表已存在（1 i ListLenght(L)）操作结果：用操作结果：用e返回线性表返回线性表L中第中第i个数据元素的值个数据元素的

7、值locateElem(L, e, compare()初始条件：线性表已存在初始条件：线性表已存在, compare()是数据元素判定函数是数据元素判定函数操作结果：返回线性表操作结果：返回线性表L中第中第1个与个与e满足关系满足关系comare()的数据元素的的数据元素的位序位序PriorElem(L, cur_e, &pre_e)初始条件：线性表已存在初始条件：线性表已存在操作结果：若操作结果：若cur_e是线性表是线性表L的数据元素，且不是第一个，则用的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义无定义NextEl

8、em(L, cur_e, &next_e)初始条件：线性表已存在初始条件：线性表已存在操作结果：若操作结果：若cur_e是线性表是线性表L的数据元素，且不是第最后一个，则用的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_e无定义无定义ListTraverse(L, visit()初始条件：线性表已存在初始条件：线性表已存在操作结果：遍历线性表。依次对线性表操作结果：遍历线性表。依次对线性表L的每个数据元素调用的每个数据元素调用visit()函数，一旦函数，一旦visit()失败，则操作失败失败，则操作失败ListInser

9、t(&L, i, e)初始条件：线性表已存在（初始条件：线性表已存在（1 i ListLenght(L)+1）操作结果：在线性表操作结果：在线性表L中第中第i个数据元素之前插入新元素个数据元素之前插入新元素e， L长度加长度加1ListDelete(&L, i, &e)初始条件：线性表已存在（初始条件：线性表已存在（1 i ListLenght(L)）操作结果：删除线性表操作结果：删除线性表L中第中第i个数据元素，用个数据元素，用e返回其值，返回其值，L长长度减度减1ADT List上述是线性表抽象数据类型的定义，其中只是一些基上述是线性表抽象数据类型的定义，其中只是一

10、些基本操作，另外可以更复杂。如将两个线性表合并等。本操作，另外可以更复杂。如将两个线性表合并等。复杂的操作可用基本操作实现。复杂的操作可用基本操作实现。例例3：将两个非递减的表合成为一个非递减的表：将两个非递减的表合成为一个非递减的表void MergeList(List la, List lb, list &lc)InitList(lc); i=j=1;k=0;la_len=ListLength(la); lb_len=ListLength(lb);while(i=la_len & j=lb_len)GetElem(la, i, ai);GetElem(lb, j, bj);

11、if(ai=bj) ListInsert (lc, +k, ai); i+; else ListInsert (lc, +k, bj); j+; while(i=la_len) GetElem(la, i+, ai); ListInsert(lc, +k, ai);while(j=lb_len) GetElem(lb, j+, bj); ListInsert(lc, +k, bj);2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 顺序表的表示顺序表的表示2.2.2 顺序表的实现顺序表的实现2.2.3 顺序表的运算效率分析顺序表的运算效率分析本节小结本节小结2.2.1 顺序表的表

12、示顺序表的表示用一组地址连续的存储单元依次存用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。储线性表的元素，可通过数组来实现。 把逻辑上相邻的数据元素存储在物理上把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻线性表顺序存储特点：线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻

13、；2. 若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图参见存储结构示意图）：）：设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为首地址），称为首地址），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则则表中任一数据元素的存放地址为：表中任一数据元素的存放地址为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai) + L 线性表的顺序存储结构示意

14、图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L例例4：一个一维数组，下标的范围是到一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素存储器按字节编址，设存储数组元素的第一个字节的地址是的第一个字节的地址是98，则，则的第一的

15、第一个字节的地址是个字节的地址是113因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：地址计算通式为：解：地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）线性表的顺序存储结构定义（静态）#define MAXSIZE 100typedef struct ElemType elemMAXSIZE; int length;SqList; .elemlengthSqList L; /声明声明L顺序表顺序表 L:int a; a:2.2.2 顺序表的实现（或操作）顺序表的实现（或操作）回忆：数据结构基本运算操作有：回忆：数据结构基本运算操作有：插入、删

16、除、查找、排序、修改插入、删除、查找、排序、修改1)1)插入插入: :在线性表的第在线性表的第i i个位置前个位置前插入插入一个元素一个元素, ,使长度为使长度为n的线性表变为长度为的线性表变为长度为n+1的线性表。的线性表。实现步骤：实现步骤： 将第将第n至第至第i 位的元素向后移动一个位置；位的元素向后移动一个位置； 将要插入的元素写到第将要插入的元素写到第i个位置；个位置； 表长加表长加1。注意：事先应判断注意：事先应判断: 插入位置插入位置i 是否合法是否合法?表是否已满表是否已满? ( a1, a2 , , ai-1, ai, , an )( a1, a2, , ai-1, x, a

17、i, , an )程序实现：程序实现：Status ListInsert_Sq(SqList &L, int i, ElemType x) /在线性表在线性表L的第的第i个元素前插入元素个元素前插入元素xif (iL.length)return(ERROR);if(L.length=MAXSIZE)return(OVERFLOW);for(j=L.length;j=i;j-)L.elemj=L.elemj-1;L.elemj=x;L.length+;return(OK);顺序表插入的演示顺序表插入的演示实现步骤：实现步骤： 将第将第i +1至第至第n 位的元素向前移动一个位置；位的元素

18、向前移动一个位置； 表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?2)删除：删除： 删除删除线性表的第线性表的第i个位置上的元素，个位置上的元素，使长度为使长度为n的线性表变为长度为的线性表变为长度为n-1的线性表。的线性表。 （a1, a2, ,ai-1, ai, ai+1, , an）（a1, a2, ,ai-1, ai+1, ,an）程序实现：程序实现：Status ListDelete_Sq(Sqlist &L, int i, ElemType &e) /删除第删除第i个元素个元素if(iL.length) return

19、ERROR;else e = L.elemi; for(j=i; j = L.length-1; j+) L.elemj = L.elemj+1; L.length-;顺序表删除的演示顺序表删除的演示2.2.3 顺序表的运算效率分析顺序表的运算效率分析时间效率分析时间效率分析:插入算法花费的时间，主要在于循环中元素的后移插入算法花费的时间，主要在于循环中元素的后移当插入位置为当插入位置为1时，需时，需n次移动次移动;当当插入位置为插入位置为n时，不需移动元素时，不需移动元素;当插入位置为当插入位置为i时，时，移动次数为移动次数为n-i+1。2) 1(11) 1(1111ninninpEnini

20、iis假定在表中任意位置插入元素都是等概率的，在第假定在表中任意位置插入元素都是等概率的，在第i个位置上插入个位置上插入元素的概率元素的概率p(i)=1/(n+1)插入操作时间效率（平均移动次数）插入操作时间效率（平均移动次数） 删除操作时间效率（平均移动次数）删除操作时间效率（平均移动次数） 21)(1)(11ninninqEniniidl删除算法花费的时间，主要在于循环中元素的前移删除算法花费的时间，主要在于循环中元素的前移当删除位置为当删除位置为1时，需时，需n-1次移动次移动;当插入位置为当插入位置为n时，不需移动元素时，不需移动元素;当插入位置为当插入位置为i时，移动次数为时，移动次

21、数为n-i。假定在表中任意位置删除元素都是等概率的，则删除假定在表中任意位置删除元素都是等概率的，则删除第第i个位置上元素的概率个位置上元素的概率q(i)=1/n本节小结本节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；素在物理存储位置上也相邻；优点：可以随机存取表中任一元素优点：可以随机存取表中任一元素O(1)；存储空；存储空间使用紧凑间使用紧凑缺点：在插入，删除某一元素时，需要移动大量元素缺点：在插入，删除某一元素时，需要移动大量元素O(n); ;预先分配空间需按最大空间分配，预先分配空间需按最大空间分配，利用不充

22、分利用不充分; ;表容量难以扩充表容量难以扩充为克服这一缺点，我们引入另一种存储形式：为克服这一缺点，我们引入另一种存储形式：链式存储结构链式存储结构见见2.3节节2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 链表的表示链表的表示2.3.2 链表的实现链表的实现2.3.3 链表的运算效率分析链表的运算效率分析本节小结本节小结2.3.1 链表的表示链表的表示n用一组任意的存储单元存储线性表的数据元素用一组任意的存储单元存储线性表的数据元素n利用指针实现了用不相邻的存储单元存放逻辑上利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素相邻的元素n每个数据元素每个数据元素a

23、i，除存储本身信息外，还需存除存储本身信息外，还需存储其直接后继的信息储其直接后继的信息n结点结点 数据域：元素本身信息数据域：元素本身信息 指针域：指示直接后继的存储位置指针域：指示直接后继的存储位置数据域 指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANGH例例 线性表线性表 (ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)43131NULL3771925数据域数据域指针域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址存储地址1713192531374331H头指针头指针与链式存储有关的术语：与链式存储有关的术

24、语：1、结点：数据元素的存储映像。由数据域和指针域两部分组成；、结点：数据元素的存储映像。由数据域和指针域两部分组成；2、链表：、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储个结点由指针链组成一个链表。它是线性表的链式存储映像映像，称为线性表的链式存储结构称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表、单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表；结点只有一个指针域的链表，称为单链表或线性链表； 有两个指针域的链表，称为双链表；有两个指针域的链表，称为双链表； 有多个指针域的链表，称为多链表；有多个指针域的链表，称为多链表；

25、 首尾相接的链表称为循环链表。首尾相接的链表称为循环链表。a1headheada2anheadhead循环链表示意图：循环链表示意图：何谓头指针、头结点和首元结点头指针、头结点和首元结点？头指针头指针是指向链表中第一个结点（或为头结点或为首元结点）是指向链表中第一个结点（或为头结点或为首元结点）的指针。的指针。 单链表可由一个头指针唯一确定。单链表可由一个头指针唯一确定。头结点头结点是在链表的首元结点之前附设的一个结点；数是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息据域内只放空表标志和表长等信息; ;首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性

26、表第一个数据元素a a1 1的结的结点。点。 头指针头指针头结点头结点 首元结点首元结点a1一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储），其存储结构用单链表表示如下，请问其头指针的值是多少？结构用单链表表示如下，请问其头指针的值是多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例：答：头指针是指向链表答：头指针是指向链表中第一个结点的指针，中第一个结点的指针，因此关键是要寻找第一因此关键是要寻

27、找第一个结点的地址。个结点的地址。7ZHAOH31头指针的值是头指针的值是31上例链表的逻辑结构示意图有以下两种形式：上例链表的逻辑结构示意图有以下两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENGWANGH区别：区别： 无头结点无头结点 有头结点有头结点答：答：讨论1. 在链表中设置头结点有什么好处？讨论2. 如何表示空表空表？头结点头结点即在链表的首元结点之前附设的一个结点，该结点的即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作数据域中不存储线性表的数据元素，其作用

28、是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。程更方便。答：答：无头结点时，当头指针的值为空时表示空表；无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。有头结点时，当头结点的指针域为空时表示空表。 头指针头指针 头指针头指针头结点头结点无头结点无头结点有头结点有头结点typedef struct node ElemType data; /数据域 struct Lnode *next; /指针域LinkNode, *LinkList; / *LinkList为L

29、node类型的指针对于单链表的抽象描述:LinkNode s1; /定义改结构体类型的变量定义改结构体类型的变量S1,等价于等价于: struct node s1; LinkList p1; 定义该类型的指针变量定义该类型的指针变量,等价于等价于: LinkNode *p1;等价于等价于: struct node *p1; 补充：结构类型的补充：结构类型的C语言表示法语言表示法介绍三个有用的库函数介绍三个有用的库函数(都在都在中中)：sizeof(x)计算变量计算变量x的长度；的长度；malloc(m) 开辟开辟m字节长度的地址空间，并返字节长度的地址空间，并返回这段空间的首地址；回这段空间的

30、首地址；free(p) 释放指针释放指针p所指变量的存储空间，即所指变量的存储空间，即彻底删除一个变量。彻底删除一个变量。2.3.2 链表的实现1. 1. 单链表的建立和输出单链表的建立和输出2. 2. 单链表的修改单链表的修改3. 3. 单链表的插入单链表的插入4. 4. 单链表的删除单链表的删除5. 5. 应用举例应用举例6. 6. 其它链表形式其它链表形式1. 单链表的建立和输出头插法建单链表的演示头插法建单链表的演示尾插法建单链表的演示尾插法建单链表的演示1. 1. 单链表的建立和输出单链表的建立和输出实例：用单链表结构来存放实例：用单链表结构来存放26个英文字母组成的线性表个英文字母

31、组成的线性表 ( A，B，C，Z ), 请写出请写出C语言程序。语言程序。难点分析：每个数据元素在内存中是难点分析：每个数据元素在内存中是“零散零散”存放的，存放的，其首地址怎么找？又怎么一一链接？其首地址怎么找？又怎么一一链接？实现思路：先开辟头指针，然后陆续为每个数据元素实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。开辟存储空间并赋值，并及时将地址送给前面的指针。将全局变量及函数提前说明：将全局变量及函数提前说明：#include#includetypedef struct node char data; struct node *next;

32、 Lnode, *LinkList; Lnode *p, *q, *head; int n ; int m=sizeof(Lnode); /*结构类型定义好之后，每个变量的长度就结构类型定义好之后，每个变量的长度就固定了，固定了，m求一次即可求一次即可*/ /等价于：等价于：LinkList p, q, head;LinkList s;head=(LinkList)malloc(m);p=head;s=(LinkList)malloc(m);s-data=a+i-1;p-next=s;p=s;p-next=NULL;return head; /head是全局变量，此语句可省是全局变量，此语句可

33、省LinkList build()Step1:先建立一个头结点，并记为当前结点先建立一个头结点，并记为当前结点Step2: for(i=1; idata=a+i-1;p-next=s;p=s;p-next=NULL;return head; /head是全局变量，此语句可省是全局变量，此语句可省LinkList build() /字母链表的生成。要一个一个链入字母链表的生成。要一个一个链入int i; LinkList s;head=(LinkList)malloc(m); /m=sizeof(test) 前面已求出前面已求出p=head;for(i=1;idata=i+a-1; / 为第为第

34、i个结点值域赋值个结点值域赋值p-next=s； / 让指针变量让指针变量p改为指向新结点改为指向新结点sp-next=NULL; / 最后一个结点的最后一个结点的next为空为空return head;新手特别容易忘记！新手特别容易忘记！void display(head) /*字母链表的输出字母链表的输出*/ p=head-next; /只要没到最后一个元素，就不停地只要没到最后一个元素，就不停地“顺藤摸瓜顺藤摸瓜”输出输出 while (p!=NULL) printf(%c, p-data); p=p-next; 讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的

35、个数，该如何改写？ sum +;int sum=0;课堂练习课堂练习有线性表有线性表, ,有有n n个整数组成，个整数组成，n n和和n n个整数均有用个整数均有用户输入，请建立单链表户输入，请建立单链表提示：提示：Step1: 定义结构体定义结构体Step2: 定义功能函数定义功能函数LinkList build() Step3: 在主函数中调用在主函数中调用int main() 2. 单链表的修改单链表的修改(或读取）或读取）思路：要修改第思路：要修改第i i个数据元素，关键是要先找到该结个数据元素，关键是要先找到该结点的指针点的指针p p，然后给，然后给p-datap-data赋值赋值

36、即可。即可。难点：单链表中想取得第难点：单链表中想取得第i个元素，必须从头指针出发个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取寻找（顺藤摸瓜），不能随机存取 。Status GetElem_L(LinkList L, int i, ElemType &e)p=L-next; j=1;while(p&jnext; +j;if(!p | ji) return ERROR;e=p-data;return OK;3. 单链表的插入单链表的插入在链表中插入一个元素的示意图如下：在链表中插入一个元素的示意图如下：xsbapabpp-nexts-next(1)元素x结点应预先生成：

37、(2)结点b做x的后继(即把结点b的地址存入s的next域)(3)结点x作为a的后继（即把结点x的地址s存入P的next域）s=(LinkList)malloc(m);s-data=x;s-next=p-next (p-next的值即b的地址）p-next=s ；xsbapabp如果把以上两个语句颠倒顺序如果把以上两个语句颠倒顺序, ,可以吗？可以吗？(3)结点x作为a的后继: s-next=p-next;(2)结点b做x的后继: p-next=s ；p-next找不到了!.Status ListInsert(LinkList &L, int i, ElemType e)(1)让p指向

38、首元结点;j=1;(2)当(p非空且p不是第i个结点) p指向下一结点，j+;(3)如果(p为空或inext; j=1;while(p & jnext; j+; if( p=NULL | idata=x;s-next = p-next;p-next = s;Status ListInsert(LinkList &L, int i, ElemType e)p=L-next; j=1;while(p&jnext;+ j;if(!p | ji-1)return ERROR;S=(LinkList)malloc(sizeof(Lnode);S-data=x;S-next=p-n

39、ext;P-next=s;return OK;单链表结点插入的演示单链表结点插入的演示4. 单链表的删除单链表的删除在链表中删除某元素的示意图如下：在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：删除步骤（即核心语句）：q = p-next; /保存b的指针，靠它才能指向cp-next=q-next; /a、c两结点相连两结点相连free(q) ； /删除删除b结点，彻底释放结点，彻底释放p-next(p-next) - next删除b: 让p的next域存c的地址Status ListDelete(LinkList &L, int i, ElemType &e

40、)p=L-next; j=1;while(p&jnext; +j;if(!p|ji-1) return ERROR;q=p-next; /q指向要被删除的结点指向要被删除的结点p-next=q-next; /q结点被删除结点被删除e=q-data; /把把q的数据域存入的数据域存入efree(q);return OK;单链表结点的删除演示单链表结点的删除演示5. 应用举例：两个链表的归并应用举例：两个链表的归并(教材教材P31)算法要求：算法要求：已知：线性表已知：线性表 A、B，分别由单链表，分别由单链表 LA , LB 存储，其中存储，其中数据元素按值非递减有序排列，数据元素按值非

41、递减有序排列，要求：将要求：将 A ，B 归并为一个新的线性表归并为一个新的线性表C , C 的数据元素的数据元素仍按值非递减排列仍按值非递减排列 。设线性表。设线性表 C 由单链表由单链表 LC 存储。存储。假设：假设：A=( 3, 5, 8, 11 )，B=(2, 6, 8, 9, 11)预测：合并后预测：合并后 C =（ 2, 3, 5, 6, 8, 8, 9, 11，11 ）用链表可表示为：用链表可表示为： 3 3 5 511 11 / 8 8 LaLa 2 2 6 611 11 / 8 8 LbLb 9 9 2 2 3 3 6 6 5 5 LcLc 8 8头结点头结点算法分析：算法分

42、析：算法主要包括：搜索、比较、插入三个操作：算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。插入：将两个结点中数据小的结点插入新链表。La3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb， Pc指向新链表当前结点指向新链表当前结点Lc Pa3 PcPa5 Pc11Pc2 PbPcPa链表Pc的结点都是重新生成，空间效率低La3 5 8 11 Lb2 6 8 119 PaPbLcPc提

43、高空间效率算法实现：算法实现：void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /按值排序的单链表La,Lb，归并为Lc后也按值排序 (4) free(Lb); /释放Lb的头结点 /MergeList_L(3) 如果La没有结束，将La的剩余部分链入Lc 否则，将Lb的剩余部分链入Lc (2) 当（pa,pb都非表尾）/将pa 、pb结点按大小依次插入C中 如果 (pa所指结点小于pb) 将pa作为pc的后继，pa成为Lc最新结点 否则 将pb作为pc的后继，pb成为Lc最新结点 (1) pa、pb指向L

44、a、Lb的首元结点，用La的头结点做Lc的头结点(3) if(pa) pc-next=pa; else pc-next=pb;(2) while(pa&pb) /将pa 、pb结点按大小依次插入Lc中 if(pa-data data) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next (3) pc-next = pa?pa:pb;(1) pa=La-next; pb=Lb-next; pc=La;void MergeList_L(LinkList &La,LinkList &Lb,Link

45、List &Lc) /按值排序的单链表LA,LB，归并为LC后也按值排序pa=La-next; pb=Lb-next; Lc=pc=La； /初始化while(pa&pb) /将pa 、pb结点按大小依次插入C中 if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pc-next = pa?pa:pb ; /插入剩余段free(Lb); /释放Lb的头结点 /MergeList_L算法实现：算法实现：讨论讨论1 1：链表能不能首尾相连？怎样实现？：链表能不能首尾相连？

46、怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可答：能。只要将表中最后一个结点的指针域指向头结点即可 (P-next=head;) (P-next=head;) 。这种形成环路的链表称为循环链表。这种形成环路的链表称为循环链表。特别：带头结点的特别：带头结点的空循环链表样式空循环链表样式H参见教材参见教材P35P35 特点：特点： 1、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。 2、操作仅有、操作仅有 一一 点与单链表不同：循环条件点与单链表不同：循环条件 单链表单链表 - p = NULL 或或 p -next =NULL 循环链表循环链表- p

47、= head 或或 p-next = head6. 其它链表形式讨论讨论2：单链表只能查找结点的直接后继，能：单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？不能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可答：能。只要把单链表再多开一个指针域即可(例如用例如用*next和和*prior;) 。双向链表在非线性结构（如树结构）中将大量使用。双向链表在非线性结构（如树结构）中将大量使用。priordatanext这种有两个指针的链表称为双向链表。其特点是可这种有两个指针的链表称为双向链表。其特点是可以双向查找表中结点。参见教材以双向查找表中结点。参见教材P3539。

48、特别：带头结点的空双向链表样式：特别：带头结点的空双向链表样式： Head猴子选猴王猴子选猴王n有有 n 个猴子，编号从个猴子，编号从1到到n,站成一圈从编号站成一圈从编号为为1的猴子开始从的猴子开始从1到到3报数，凡报数为报数，凡报数为3的猴的猴子退出圈子，圈中最后剩下的一个猴子就是子退出圈子，圈中最后剩下的一个猴子就是猴王。猴王。n从键盘读入猴子个数从键盘读入猴子个数n, 输出猴王的编号。可输出猴王的编号。可以用循环队列来模拟此过程，请编程实现。以用循环队列来模拟此过程，请编程实现。解题思路解题思路n(1)先建立循环队列先建立循环队列1, 2, , nn(2)模拟报数过程，删除报数为模拟报

49、数过程，删除报数为3的结点，的结点，当链表中只剩一个结点时，报数过程结束当链表中只剩一个结点时，报数过程结束n只有一个结点的循环链表有何特征？只有一个结点的循环链表有何特征？pp-next=p;程序实现程序实现（1 1）建立循环链表）建立循环链表1, 2, nLinkList build (int n) int i;LinkList head, p,s;p=head=(LinkList)malloc(sizeof(Lnode);p-data=1;for(i=2; idata=i; p-next=s; p=s;p-next=head; / /建立循环建立循环return head;int cou

50、nt(LinkList head) int i=1;LinkList q, p=head;while(p-next!=p) /当圈中猴子多于当圈中猴子多于1个个if(i=2) /跳过下一个跳过下一个,重新报数重新报数 q=p-next; p-next=q-next; free(q); p=p-next; i=1;else /正常报数正常报数 p=p-next; i+; return p-data;程序实现程序实现（2）报数过程模拟）报数过程模拟2.3.3 链表的运算效率分析链表的运算效率分析1. 查找查找 因线性链表只能顺序存取，即在查找时要从因线性链表只能顺序存取，即在查找时要从头指针找起，

51、查找的时间复杂度为头指针找起，查找的时间复杂度为 O(n)。时间效率分析时间效率分析2. 插入和删除插入和删除 因线性链表不需要移动元素，只要修改指因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为针，一般情况下时间复杂度为 O(1)。 空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增链表中每个结点都要增加一个指针空间，相当于总共增加了加了n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)。多项式的线性表表示多项式的线性表表示An(x)=anxn+an-1xn-1+.+a1x+a0 用线性表表示为：用线性表表示为： A=(an, an-1,., a1, a0

52、)若多项式的阶次很高，而系数若多项式的阶次很高，而系数ai不为零的很少，则这不为零的很少，则这种表示浪费空间。种表示浪费空间。可写为：可写为：A(x)=amxem+am-1xem-1+.+a1xe1+a0 xe0,用线性表表示为用线性表表示为:A=(am,em), (am-1,em-1), ., (a1,e1), (a0,e0)比如：比如：A(x)=2x32+3x2表示为线性表：表示为线性表：A=(2, 32), (3, 2) )2.4 应用举例应用举例: 一元多项式的计算一元多项式的计算多项式相加的方法多项式相加的方法A + B = C1.线性表线性表C置空置空2.各取线性表各取线性表A和和

53、B的第一个元素作为当前处理的元素的第一个元素作为当前处理的元素3.比较当前处理的元素的指数值，相等，系数相加若不为零追加比较当前处理的元素的指数值，相等，系数相加若不为零追加到线性表到线性表C，各取线性表，各取线性表A和和B的下一个元素作为当前处理的元的下一个元素作为当前处理的元素；若指数不相等，则把大的元素追加到线性表素；若指数不相等，则把大的元素追加到线性表C，取该元，取该元素所在线性表的下一个元素作为当前处理的元素。素所在线性表的下一个元素作为当前处理的元素。4.重复步骤重复步骤3直到其中一个线性表处理完毕，再把另一个线性表的直到其中一个线性表处理完毕，再把另一个线性表的剩余元素追加到线

54、性表剩余元素追加到线性表C。一、多项式的数组存放一、多项式的数组存放#define MAXN 100typedef struct term float coef; /系数系数coefficient int exp; /指数指数exponentTERM;TERM polyMAXN;2.4.2 顺序结构的加法实现顺序结构的加法实现二、程序实现二、程序实现int ah, at, bh, bt, ch, ct, free;int append(float c, int e)if(free=MAXN) return(1);polyfree.ceof=c;polyfree.exp=e;free+;return(0);int poly_add(int ah, int at, int bh, int bt, int *ch_p, int *ct_p)int a_p,b_p, a_exp, b_exp;float c_coef;a_p=ah;b_p=bh;*ch_p=free;while(a_p=at & b_pb_exp) if(append(polya_p.coef,a_exp) return(1); a