数据结构第二章线性表1

1、第第 二二 章章 线性表线性表 线性结构的基本特征为线性结构的基本特征为: : 1集合中必存在唯一的一个集合中必存在唯一的一个“首元素首元素”； 2集合中必存在唯一的一个集合中必存在唯一的一个 “尾元素尾元素” ； 3首元素无直接前驱首元素无直接前驱 ； 4 4尾元素无直接后继尾元素无直接后继 ； 线性结构线性结构 是一个数据元素的是一个数据元素的 有序（次序）集合有序（次序）集合 5集合中其它每个数据元素均有唯一的集合中其它每个数据元素均有唯一的 直接前驱和唯一的直接后继。直接前驱和唯一的直接后继。 2.1 线性表的概念及抽象数据线性表的概念及抽象数据 类型定义类型定义 2.3 线性表的链式

2、存储线性表的链式存储 2.4 一元多项式的表示及相加一元多项式的表示及相加 2.2 线性表的顺序存储线性表的顺序存储 2.1 线性表的概念及抽象数据类型定义线性表的概念及抽象数据类型定义 2.1.1 线性表的逻辑结构线性表的逻辑结构 2.1.2 线性表的抽象数据类型定义线性表的抽象数据类型定义 线性表定义线性表定义：线性表线性表(Linear List)是由是由n (n0)个类个类 型相同的数据元素型相同的数据元素a1, a2,an 组成的有限序列，记做组成的有限序列，记做 (a1,ai-1,ai,ai+1,an) 例例 英文字母表（英文字母表（A,B,C,.Z)是一个线性表是一个线性表 例例

3、 学学 籍籍 表表 2.1.1 2.1.1 线性表的逻辑结构线性表的逻辑结构 数据元素之间是一对一的关系，即每个数据元素之间是一对一的关系，即每个 数据元素最多有一个直接前驱和一个直数据元素最多有一个直接前驱和一个直 接后继。接后继。 线性表的逻辑结构图为：线性表的逻辑结构图为： 首元素首元素尾元素尾元素 数据元素数据元素(data elements) ：可由若干数据：可由若干数据 项组成项组成 ； 数据元素常被称为一个记录数据元素常被称为一个记录(record)，含有，含有 大量类型相同记录的线性表称为文件大量类型相同记录的线性表称为文件(file) （或者数据对象（或者数据对象（data

4、object）。）。 线性表的特点线性表的特点 l同一性：线性表由同类型数据元素组成，每一个同一性：线性表由同类型数据元素组成，每一个ai 必须属于同一数据对象。必须属于同一数据对象。 l有穷性：线性表由有限个数据元素组成，表长度就有穷性：线性表由有限个数据元素组成，表长度就 是表中数据元素的个数。是表中数据元素的个数。 l有序性：线性表中相邻数据元素之间存在着序偶关有序性：线性表中相邻数据元素之间存在着序偶关 系系。 线性表是一种最常见的数据结构线性表是一种最常见的数据结构:矩阵、数组、字符矩阵、数组、字符 串、串、 堆栈、队列堆栈、队列 2.1.2 线性表的线性表的抽象数据类型定义抽象数据

5、类型定义 ADT List 数据数据元素元素 D ai | ai ElemSet, i=1,2,.,n, n0 称称 n 为线性表的表长为线性表的表长; 称称 n=0 时的线性表为空表。时的线性表为空表。 结构关系：结构关系： R1 |ai ,ai+1D, i=2,.,n-1 设线性表为设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称称 i 为为 ai 在线性表中的位序。在线性表中的位序。 基本操作：基本操作： 初始化操作初始化操作 结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List InitList( L ) 操作前提：操作前提：

6、L为未初始化线性表。为未初始化线性表。 操作结果：将操作结果：将L初始化为空表。初始化为空表。 初始化操作初始化操作 结构销毁操作结构销毁操作 DestroyList(L ) 操作前提：线性表操作前提：线性表L已存在。已存在。 操作结果：将操作结果：将L销毁。销毁。 引用型操作引用型操作: : EmptyList（L） 操作前提：线性表操作前提：线性表L已存在。已存在。 操作结果：如果操作结果：如果L为空表则返回真，否则返回假。为空表则返回真，否则返回假。 ListLength（L） 操作前提：线性表操作前提：线性表L已存在。已存在。 操作结果：如果操作结果：如果L为空表则返回为空表则返回0，

7、 否则返回表中的元素个数。否则返回表中的元素个数。 Locate(L,e) 操作前提：操作前提： 表表L已存在，已存在，e为合法元素值。为合法元素值。 操作结果：操作结果： 如果如果L中存在元素中存在元素e，则将，则将“当前指针当前指针” 指向元素指向元素e所在位置并返回真，否则返回假。所在位置并返回真，否则返回假。 GetData(L,i) 操作前提：表操作前提：表L存在，且存在，且i值合法，值合法， 即（即（1iListLength（L） 操作结果：返回线性表操作结果：返回线性表L中第中第i个元素的值。个元素的值。 PriorElem( L, e) （求数据元素的前驱）（求数据元素的前驱）

8、 操作前提：线性表操作前提：线性表L已存在。已存在。 操作结果：若操作结果：若e是是L的元素，但不是第一个，的元素，但不是第一个， 则返回它的前驱，否则操作失败。则返回它的前驱，否则操作失败。 NextElem( L, e) （求数据元素的后继）（求数据元素的后继） 操作前提：线性表操作前提：线性表L已存在。已存在。 操作结果：若操作结果：若e是是L的元素，但不是最后一个，的元素，但不是最后一个， 则返回它的后继，否则操作失败。则返回它的后继，否则操作失败。 加工型操作加工型操作 ClearList(L) 操作前提：线性表操作前提：线性表L已存在已存在 。 操作结果：将表操作结果：将表L置为空

9、表。置为空表。 InsList(L,i,e) 操作前提：表操作前提：表L已存在，已存在，e为合法元素值为合法元素值 且且1iListLength(L)+1。 操作结果：在操作结果：在L中第中第i个位置之前插入新的个位置之前插入新的 数据元素数据元素e，L的长度加的长度加1。 DelList(L,i,e) 操作前提：表操作前提：表L已存在且非空，已存在且非空， 1iListLength(L)。 操作结果：删除操作结果：删除L的第的第i个数据元素，并用个数据元素，并用e返回其值，返回其值， L的长度减的长度减1。 PutElem( L, i, e ) （改变数据元素的值）（改变数据元素的值） 操作

10、前提：操作前提：线性表线性表L已存在，且已存在，且 1iLengthList(L) 。 操作结果：操作结果： L中第中第i个元素赋值同个元素赋值同e的值。的值。 在实际问题中对线性表的运算可能很多。例如在实际问题中对线性表的运算可能很多。例如 合并、分拆、复制、排序等。合并、分拆、复制、排序等。 线性表的存储结构：顺序存储结构和链式存储线性表的存储结构：顺序存储结构和链式存储 结构。结构。 还有一种叫做静态链表的存储结构，它是用顺还有一种叫做静态链表的存储结构，它是用顺 序存储结构的存储方式模拟实现的一种链式存序存储结构的存储方式模拟实现的一种链式存 储结构。储结构。 2.2 线性表的顺序存储

11、线性表的顺序存储 2.2.1 线性表的顺序存储结构线性表的顺序存储结构 2.2.2 线性表顺序存储结构上的运算线性表顺序存储结构上的运算 顺序存储结构的定义顺序存储结构的定义 线性表的顺序存储是指用一组地址连续的存储单元依次线性表的顺序存储是指用一组地址连续的存储单元依次 存储线性表中的各个元素，使得线性表中在逻辑结构上存储线性表中的各个元素，使得线性表中在逻辑结构上 相邻的数据元素存储在相邻的物理存储单元中，即通过相邻的数据元素存储在相邻的物理存储单元中，即通过 数据元素物理存储的相邻关系来反映数据元素之间逻辑数据元素物理存储的相邻关系来反映数据元素之间逻辑 上的相邻关系。上的相邻关系。 采

12、用顺序存储结构的线性表通常称为采用顺序存储结构的线性表通常称为顺序表顺序表。 “关系线性化，节点顺序存。关系线性化，节点顺序存。” 顺序表存储结构示意图顺序表存储结构示意图 用一组地址连续的存储单元依次存放线性表中的用一组地址连续的存储单元依次存放线性表中的 数据元素数据元素 a a1 1线性表的起始地址线性表的起始地址, ,称作线性表的基地址称作线性表的基地址 假设线性表中有假设线性表中有n个元素，每个元素占个元素，每个元素占k个单元个单元 ，第一个元素的地址为，第一个元素的地址为loc(a1)，则可以通过如，则可以通过如 下公式计算出第下公式计算出第i个元素的地址个元素的地址Loc(ai)

13、： loc(ai) =loc(a1)+(i-1)k 顺序存储结构的顺序存储结构的 C 语言描述语言描述 #definemaxsize=线性表可能达到的最大长度；线性表可能达到的最大长度； typedef struct ElemType elemmaxsize； /* 线性表占用的数组空间线性表占用的数组空间*/ int last； /*记录线性表中最后一个元素在数组记录线性表中最后一个元素在数组 elem 中的位置（下标值），空表置为中的位置（下标值），空表置为-1*/ SeqList； 注意注意:1. ElemType数据类型是自定的，既可以是原子类型，数据类型是自定的，既可以是原子类型，

14、也可以是结构类型。也可以是结构类型。 2.区分元素的序号和数组的下标，如区分元素的序号和数组的下标，如a1的序号为的序号为1，而其对应，而其对应 的数组下标为的数组下标为0。 顺序表的定义法：顺序表的定义法： 1.要将要将L定义为定义为SeqList类型的变量可用语句类型的变量可用语句 SeqList L；访用第；访用第i个元素个元素L.elemi-1；求；求 顺序表的长度顺序表的长度L.last+1 2.如将如将L定义为指向定义为指向SeqList类型的指针用语句类型的指针用语句 SeqList * L ;访用第访用第i个元素个元素L-elemi-1； 求顺序表的长度求顺序表的长度L-las

15、t+1 2.2.2 线性表顺序存储结构的基本运算线性表顺序存储结构的基本运算 2.2.查找操作查找操作 3.3.插入操作插入操作 4.4.删除操作删除操作 5.5.顺序表的合并顺序表的合并 6.线性表顺序存储结构的优缺点分析线性表顺序存储结构的优缺点分析 1.1.初始化初始化 1.1.初始化初始化 2. 查找操作查找操作 l线性表的两种基本查找运算线性表的两种基本查找运算 l按序号查找按序号查找GetData(L,i)：要求查找线性表：要求查找线性表L中第中第i 个数据元素，其结果是个数据元素，其结果是L.elemi-1或或 L-elemi-1。 l按内容查找按内容查找Locate（L,e）:

16、 要求查找线性表要求查找线性表L中中 与给定值与给定值e相等的数据元素，其结果是：若在表相等的数据元素，其结果是：若在表L 中找到与中找到与e相等的元素，则返回该元素在表中的相等的元素，则返回该元素在表中的 序号；若找不到，则返回一个序号；若找不到，则返回一个“空序号空序号”，如，如-1。 算法思想：算法思想： 查找运算可采用顺序查找法实现，即从查找运算可采用顺序查找法实现，即从 第一个元素开始，依次将表中元素与第一个元素开始，依次将表中元素与e相相 比较。比较。 若相等，则查找成功，返回该元素在若相等，则查找成功，返回该元素在 表中的序号；表中的序号； 若若e与表中的所有元素都不相等，则与表

17、中的所有元素都不相等，则 查找失败，返回查找失败，返回“-1”。 线性表的查找运算线性表的查找运算 int Locate(SeqList L，ElemType e) i=0 ; /*i为扫描计数器，初值为为扫描计数器，初值为0，即，即 从第一个元素开始比较从第一个元素开始比较*/ while (i=L.last) /*顺序扫描表，直到找到值为顺序扫描表，直到找到值为key 的元素的元素,或扫描到表尾而没找到或扫描到表尾而没找到*/ if (i=L.last) return(i+1); /*若找到值为若找到值为e的元素，则返回其序号的元素，则返回其序号*/ else return(-1); /*

18、若没找到，则返回空序号若没找到，则返回空序号*/ 算法的时间复杂度为：算法的时间复杂度为： O( n )O( n ) 3 插入操作插入操作 插入元素时，线性表的逻辑结构发插入元素时，线性表的逻辑结构发 生什么变化？生什么变化？ 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i (1in+1)个位置，个位置， 插入一个新元素插入一个新元素e，使长度为，使长度为n的线性表的线性表 (e1，ei-1，ei，en) 变成长度为变成长度为n+1的线性表的线性表 （e1，,ei-1，e，ei，en）。）。 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai

19、, , an) a1 a2 ai-1 ai an a1 a2 ai-1 ai ean , 表的长度增加1 插入算法示意图插入算法示意图 已知：线性表已知：线性表 (4,9,15,28,30,30,42,51,62)，需在，需在 第第4个元素之前插入一个元素个元素之前插入一个元素“21”。则需要。则需要 将第将第9个位置到第个位置到第4个位置的元素依次后移一个位置的元素依次后移一 个位置，然后将个位置，然后将“21”插入到第插入到第4个位置，个位置， 算法思想：算法思想： 用顺序表作为线性表的存储结构时，由于结点的用顺序表作为线性表的存储结构时，由于结点的 物理顺序必须和结点的逻辑顺序保持一致，

20、因此物理顺序必须和结点的逻辑顺序保持一致，因此 我们必须将原表中位置我们必须将原表中位置n，n-1，i上的结点，上的结点， 依次后移到位置依次后移到位置n+1，n，i+1上，空出第上，空出第i个个 位置，然后在该位置上插入新结点位置，然后在该位置上插入新结点e。当。当i=n+1时，时， 是指在线性表的末尾插入结点，所以无需移动结是指在线性表的末尾插入结点，所以无需移动结 点，直接将点，直接将e插入表的末尾即可。插入表的末尾即可。 int InsList(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) ) /*首先判断插入位置是否合法首先判

21、断插入位置是否合法*/ printf(“插入位置插入位置i值不合法值不合法”)；return(ERROR); if(L-last=maxsize-1) printf(“表已满无法插入表已满无法插入”)； return(ERROR); for(k=L-last;k=i-1;k-) /*为插入元素而移动位置为插入元素而移动位置*/ L-elemk+1=L-elemk; L-elemi-1=e; /*在在C语言中数组第语言中数组第i个元素的下标为个元素的下标为i-1*/ L-last+; return(OK); 线性表的插入运算线性表的插入运算 可以看出，当可以看出，当i= L-last+2时，语句

22、时，语句L-elemk+1=L- elemk将不会执行，因为循环的终值大于初值，此将不会执行，因为循环的终值大于初值，此 时不需要移动元素，可直接在表尾插入时不需要移动元素，可直接在表尾插入e。 当当i= 1时，语句时，语句L-elemk+1=L-elemk需执行需执行n次，即次，即 将表中已存在的将表中已存在的n个元素依次后移一个位置才能将个元素依次后移一个位置才能将e插插 入。入。 因此，语句因此，语句L-elemk+1=L-elemk的频度与插入位置的频度与插入位置i 有关。有关。 考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的概率为 Pi ， 则在长

23、度为n 的线性表中插入一个元素所需插入一个元素所需 移动元素次数的期望值移动元素次数的期望值为： i p 1 1 1 n i iis inpE)( 1 1 ) 1( 1 1 n i is in n E 2 n 若假定假定在线性表中任何一个位置上进行插入插入 的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为： 2 )1( 1 1 nn n 4 删除操作 线性表的删除运算是指将表的第线性表的删除运算是指将表的第i(1in)个元素删去，个元素删去， 使长度为使长度为n的线性表的线性表 (e1，,ei-1，ei，ei+1， en) 变成长度为变成长度为n-1的线性表的线性表 (e1，,

24、ei-1,ei+1， en) 3 删除操作删除操作 (a(a1 1, , a, , ai-1 i-1, a , ai i, a, ai+1 i+1, , a , , an n) ) 改变为改变为(a(a1 1, , a, , ai-1 i-1, a , ai+1 i+1, , a , , an n) ) a ai+1 i+1a an n a, , a 表的长度减少表的长度减少1 1 a a1 1 a a2 2 a ai-1 i-1 a ai i a ai+1 i+1 a an n a a1 1 a a2 2 a ai-1 i-1 ListDelete( int k; if(iL-last+1)

25、 if(iL-last+1) printf(“ printf(“删除位置不合法！删除位置不合法！”) )； return(ERROR)return(ERROR)； * *e= L-elemi-1; e= L-elemi-1; / /* * 将删除的元素存放到将删除的元素存放到e e所指向的变量中所指向的变量中* */ / for(k=i;ilast;k+) for(k=i;ilast;k+) L-elemk-1= L-elemk; L-elemk-1= L-elemk; / /* *将后面的元素依次前移将后面的元素依次前移* */ / L-last-; L-last-; return(OK);

26、 return(OK); 考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需 移动元素次数的期望值移动元素次数的期望值为： i q n i idl inqE 1 )( n i dl in n E 1 )( 1 2 1 n 若假定在线性表中任何一个位置上进行删除 的概率都是相等的，则移动元素的期望值移动元素的期望值为： 5 顺序表的合并顺序表的合并 已知已知 ：有两个顺序表：有两个顺序表LA和和LB，其元素均为非递减，其元素均为非递减 有序排列，编写一个算法，将它们合并成一个顺有序排列，编写一个算法，将它们合并成一个顺

27、 序表序表LC，要求，要求LC也是非递减有序排列。也是非递减有序排列。 算法思想算法思想 ：设表：设表LC是一个空表，为使是一个空表，为使LC也是非也是非 递减有序排列，可设两个指针递减有序排列，可设两个指针i、j分别指向表分别指向表 LA和和LB中的元素，若中的元素，若LA.elemiLB.elemj， 则当前先将则当前先将LB.elemj插入到表插入到表LC中；若中；若 LA.elemiLB.elemj ，当前先将，当前先将LA.elemi 插入到表插入到表LC中；如此进行下去，直到其中一中；如此进行下去，直到其中一 个表被扫描完毕，然后再将未扫描完的表中剩个表被扫描完毕，然后再将未扫描完

28、的表中剩 余的所有元素放到表余的所有元素放到表LC中。中。 void MergeList(List La, List Lb, List / 构造空的线性表构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); （1） while(ilast i+; k+; else LC-elemk=LB-elemj; j+; k+; （2）while (i = La_len) / 当当La不空时不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 L

29、a 表中剩余元素表中剩余元素 （3）while (j next=NULL; /*建立空的单链表建立空的单链表L*/ 2.建立单链表建立单链表 头插法建表头插法建表 算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数 据存放到新结点的数据域中，然后将新结点插入到当前链表的表据存放到新结点的数据域中，然后将新结点插入到当前链表的表 头结点之后，直至读入结束标志为止。头结点之后，直至读入结束标志为止。 初始化的空表初始化的空表 申请新节点并赋值申请新节点并赋值 插入第一个节点插入第一个节点 头插法建表算法头插法建表算法 Linkl

30、ist CreateFromHead(LinkList L) Node *s; int flag=1; /* 设置一个标志，初值为设置一个标志，初值为1，当，当 输入输入“$”时，时，flag为为0，建表结束，建表结束*/ while(flag) c=getchar(); if(c!=$) /*为读入的字符分配存储空间为读入的字符分配存储空间*/ s=(Node*)malloc(sizeof(Node);/*建立新节点建立新节点*/ s-data=c; s-next=L-next; /*将将s结点插入表头结点插入表头*/ L-next=s; else flag=0; 尾插法建表尾插法建表 头插

31、法建立链表虽然算法简单，但生成的链表中结点头插法建立链表虽然算法简单，但生成的链表中结点 的次序和输入的顺序相反。若希望二者次序一致，可的次序和输入的顺序相反。若希望二者次序一致，可 采用尾插法建表。该方法是将新结点插到当前链表的采用尾插法建表。该方法是将新结点插到当前链表的 表尾上。为此需增加一个尾指针表尾上。为此需增加一个尾指针r，使之始终指向当前，使之始终指向当前 链表的表尾，如图链表的表尾，如图2.10示。示。 H (a) 建空表建空表 r c1 (b) 申请新节点并赋值申请新节点并赋值 s S指向新申请的节点空间指向新申请的节点空间 S-data=c1 c1 H r s (c) 插入

32、第一个节点插入第一个节点 H c1 r s (d) 插入第二个节点插入第二个节点 c2 (2)r=s,r始终指向单链表的表尾始终指向单链表的表尾 (1) r-next=s；r=s 图图2.10 尾插法建立单链表图示尾插法建立单链表图示 尾插法建表算法尾插法建表算法 void CreateFromTail(LinkList L) Node *r, *s; int flag =1; r=L; /*r指针始终动态指向链表的当前表尾指针始终动态指向链表的当前表尾*/ while(flag)/*标志，初值为标志，初值为1。输入。输入“$”时时flag为为0，建表结束，建表结束*/ c=getchar()

33、; if(c!=$) s=(Node*)malloc(sizeof(Node); ); /*为头结点分配存储空间为头结点分配存储空间*/ s-data=c; r-next=s; r=s ；/*将新增的字符追加到链表的末尾将新增的字符追加到链表的末尾*/ else flag=0; r-next=NULL; 3.单链表查找单链表查找 按序号查找按序号查找 算法描述：设带头结点的单链表的长度算法描述：设带头结点的单链表的长度 为为n，要查找表中第，要查找表中第i个结点。则需要从个结点。则需要从 单链表的头指针单链表的头指针L出发，从出发，从头头结点（结点（L） 开始顺着链域扫描，用指针开始顺着链域扫

34、描，用指针p指向当前扫指向当前扫 描到的结点描到的结点,初值指向初值指向头头结点（结点（p=L），）， 用用j做记数器，累计当前扫描过的结点数做记数器，累计当前扫描过的结点数 （初值为（初值为0），当），当j = i 时，指针时，指针p所指的所指的 结点就是要找的第结点就是要找的第i个结点个结点 。 按序号查找算法实现按序号查找算法实现 / * 在带头结点的单链表在带头结点的单链表L中查找第中查找第i个结点，若找到个结点，若找到(1i n)，则返回该结点的存储位置，则返回该结点的存储位置; 否则返回否则返回NULL * / Node * Get(LinkList L, int i) Node

35、*p； p=L；int j=0； / * 从头结点开始扫描从头结点开始扫描 * / if(inext!=NULL) p=L-next; / * 从表中第一个结点比较从表中第一个结点比较 * / while (p!=NULL) if (p-data!=key) p=p-next; else break; / * 找到结点找到结点key，退出循环，退出循环 * / return p; 4.单链表插入操作单链表插入操作 (1) 寻找第寻找第 i-1个结点个结点 Lan a1 . .ai-1 ai pre 算法描述：算法描述： 要在带头结点的单链表要在带头结点的单链表L中第中第i个数据元素之前插入一个

36、个数据元素之前插入一个 数据元素数据元素e。(1)需要首先在单链表中找到第需要首先在单链表中找到第i-1个结点并由个结点并由 指针指针pre指示；指示；(2)然后申请一个新的结点并由指针然后申请一个新的结点并由指针s指示，指示， 其数据域的值为其数据域的值为e；(3)并修改第并修改第i-1个结点的指针使其指向个结点的指针使其指向s， 然后使然后使s结点的指针域指向第结点的指针域指向第i个结点。个结点。 pre e (2) 申请新节点申请新节点s并赋值并赋值s (3) 插入插入s结点结点 La1 . ai-1 ai an . e s (a)与与ai连接连接 s-next=pre-next (b)

37、ai-1与与ai断链，插入断链，插入 s；pre-next=s 单链表插入操作算法实现单链表插入操作算法实现 int InsList(LinkList L,int i,ElemType e) /*在带头结点的单链表在带头结点的单链表L中第中第i个结点之前插入值为个结点之前插入值为e的的 新结点。新结点。 */ Node *pre,*s; pre=L; int k=0; if(i1) return ERROR; while(pre!=NULLk=k+1; /* 寻找第寻找第 i-1 个结点个结点*/ if(!pre) printf(“插入位置不合理！插入位置不合理！”)； return ERRO

38、R; s=(Node*)malloc(sizeof(Node); /*为为e申请一个新的结点申请一个新的结点*/ s-data=e; /*将待插入结点的值将待插入结点的值e赋给赋给s的数据域的数据域*/ s-next=pre-next; pre-next=s; return OK; 5.单链表删除单链表删除 算法描述：算法描述： 欲在带头结点的单链表欲在带头结点的单链表L中删除第中删除第i个结点。（个结点。（1） 则首先要通过计数方式找到第则首先要通过计数方式找到第i-1个结点并使个结点并使p指向第指向第i-1 个结点；（个结点；（2）而后删除第）而后删除第i个结点并释放结点空间。个结点并释放

39、结点空间。 (1) 寻找第寻找第 i-1个结点个结点,并由并由pre指向它指向它 Lan a1 . .ai-1 ai pre an . 删除并释放删除并释放i结点。结点。(a)r=pre-next; (b)删除：删除：pre-next=pre-next-next; 释放：释放：free(r) La1 . ai-1 ai pre ai+1 r 图图 2.12：单链表的删除过程：单链表的删除过程 单链表删除算法实现单链表删除算法实现 int DelList(LinkList L,int i,ElemType *e) /*在带头结点的单链表在带头结点的单链表L中删除第中删除第i个元素，并保存其值到变

40、个元素，并保存其值到变 量量*e中中*/ Node *pre,*r; p=L; int k =0; while(pre-next!=NULL k=k+1; if(!(pre-next) /* 即即while循环是因为循环是因为pre-next=NULL而跳出的而跳出的*/ printf(“删除结点的位置删除结点的位置i不合理！不合理！”); return ERROR; r=p-next; p-next=p-next-next ； /*删除结点删除结点r*/ free(r); /*释放被删除的结点所占的内存空间释放被删除的结点所占的内存空间*/ return Ok; 求单链表的长度求单链表的长度

41、 算法描述：算法描述：可以采用可以采用“数数”结点的方法来求出单链结点的方法来求出单链 表的长度，用指针表的长度，用指针p依次指向各个结点依次指向各个结点,从第一个元素从第一个元素 开始开始“数数”，一直，一直“数数”到最后一个结点（到最后一个结点（p- next=NULL）。）。 int ListLength(LinkList L) /*L为带头结点的单链表为带头结点的单链表*/ Node *p; p=L-next; j=0; /*用来存放单链表的长度用来存放单链表的长度*/ while(p!=NULL) p=p-next; j +; return j; 求两个集合的差求两个集合的差 已知：

42、已知：以单链表表示集合，假设集合以单链表表示集合，假设集合A用单链表用单链表LA表表 示，集合示，集合B用单链表用单链表LB表示，设计算法求两个集合的表示，设计算法求两个集合的 差，即差，即A-B。 算法思想：算法思想：由集合运算的规则可知，集合的差由集合运算的规则可知，集合的差A-B中中 包含所有属于集合包含所有属于集合A而不属于集合而不属于集合B的元素。具体做法的元素。具体做法 是，对于集合是，对于集合A中的每个元素中的每个元素e，在集合，在集合B的链表的链表LB中进中进 行查找，若存在与行查找，若存在与e相同的元素，则从相同的元素，则从LA中将其删除。中将其删除。 求两个集合的差算法实现

43、求两个集合的差算法实现 void Difference(LinkList LA,LinkList LB) /*此算法求两个集合的差集此算法求两个集合的差集 */ Node *pre;*p, *r; pre=LA;p=LA-next; /*p指向表中的某一结点，指向表中的某一结点，pre始终指向始终指向p的前驱的前驱*/ while(p!=NULL) q=LB-next; /*扫描扫描LB中的结点，寻找与中的结点，寻找与LA中中*P结点相同的结点结点相同的结点*/ while (q!=NULL if (q!=NULL) r=p; pre-next=p-next; p=p-next; free(r

44、); else pre=p; p=p-next; 2.3.3 循环链表循环链表 循环链表循环链表(Circular Linked List) 是一个首尾是一个首尾 相接的链表。相接的链表。 特点：将单链表最后一个结点的指针域由特点：将单链表最后一个结点的指针域由NULL 改为指向头结点或线性表中的第一个结点，就得改为指向头结点或线性表中的第一个结点，就得 到了单链形式的循环链表，并称为循环单链表。到了单链形式的循环链表，并称为循环单链表。 在循环单链表中，表中所有结点被链在一个环上。在循环单链表中，表中所有结点被链在一个环上。 带头结点的循环单链表示意图带头结点的循环单链表示意图 L (a)

45、带头结点的空循环链表带头结点的空循环链表 (b) 带头结点的循环单链表的一般形式带头结点的循环单链表的一般形式 L an a1 . .ai-1 ai (c) 采用尾指针的循环单链表的一般形式采用尾指针的循环单链表的一般形式 Lan a1 . .ai-1 ai *(rear-next) rear *rear 带头结点的循环单链表的各种操作的实现算法带头结点的循环单链表的各种操作的实现算法 与带头结点的单链表的实现算法类似，差别仅与带头结点的单链表的实现算法类似，差别仅 在于算法中的循环条件（扫描到表尾）不是在于算法中的循环条件（扫描到表尾）不是 p!=NULL或或 p-next !=NULL，而

46、是，而是p!=L或或p- next!=L。 循环单链表合并为一个循环单链表循环单链表合并为一个循环单链表 已知：已知：有两个带头结点的循环单链表有两个带头结点的循环单链表LA、LB， 编写一个算法，将两个循环单链表合并为一个编写一个算法，将两个循环单链表合并为一个 循环单链表，其头指针为循环单链表，其头指针为LA。 算法思想：算法思想：先找到两个链表的尾，并分别由先找到两个链表的尾，并分别由 指针指针p、q指向它们；然后将第一个链表的尾与指向它们；然后将第一个链表的尾与 第二个表的第一个结点链接起来；并修改第二第二个表的第一个结点链接起来；并修改第二 个表的表尾个表的表尾Q，使它的链域指向第一

47、个表的头，使它的链域指向第一个表的头 结点。结点。 循环单链表合并算法实现循环单链表合并算法实现 LinkList merge_1(LinkList LA,LinkList LB) /*此算法将两个链表的首尾连接起来此算法将两个链表的首尾连接起来*/ Node *p, *q; p=LA; q=LB; while (p-next!=LA) p=p-next; /*找到表找到表LA的表尾的表尾*/ while (q-next!=LB) q=q-next; /*找到表找到表LB的表尾的表尾*/ p-next=LB-next; /*修改表修改表LA的尾指针，使之指向表的尾指针，使之指向表LB 中的第一

48、个结点中的第一个结点*/ q-next=LA; /*修改表修改表LB 的尾指针，使之指向表的尾指针，使之指向表LA 的头结点的头结点*/ free(LB); return(LA); 2.3.4 双向链表双向链表 双向链表：双向链表：在单链表的每个结点里再增加一个指向其在单链表的每个结点里再增加一个指向其 前趋的指针域前趋的指针域prior。这样形成的链表中就有两条方向不。这样形成的链表中就有两条方向不 同的链，我们称之为双同的链，我们称之为双 ( 向向) 链表链表 (Double Linked List)。 双向链表的结构定义：双向链表的结构定义： typedef struct Dnode E

49、lemType data； struct DNode *prior，*next； DNode, * DoubleList； 双链表的结构定义双链表的结构定义 双链表的特点：双链表的特点： p-prior-next=p p-next-next=p priordatanext 后继指针域后继指针域数据域数据域 前驱指针域前驱指针域 双向循环链表示意图双向循环链表示意图 (a)空的双向循环链表空的双向循环链表 L L a1a2a3 (b)非空的双向循环链表非空的双向循环链表 图图2.15 双向循环链表图示双向循环链表图示 双向链表的前插操作双向链表的前插操作 算法描述算法描述：欲在双向链表第欲在双向

50、链表第i个结点之前插入一个个结点之前插入一个 的新的结点，则指针的变化情况如图所示。的新的结点，则指针的变化情况如图所示。 图图2.16 双向链表插入操作双向链表插入操作 双向链表的前插操作算法实现双向链表的前插操作算法实现 void DlinkIns(DoubleList L,int i,ElemType e) DNode *s,*p; /*首先检查待插入的位置首先检查待插入的位置i是否合法是否合法*/ /*若位置若位置i合法，则让指针合法，则让指针p指向它指向它*/ s=(DNode*)malloc(sizeof(DNode); if (s) s-data=e; s-prior=p-pri

51、or; p-prior-next=s; s-next=p; p-prior=s; return TRUE; else return FALSE; 双向链表的删除操作双向链表的删除操作 算法描述算法描述：欲删除双向链表中的第欲删除双向链表中的第i个结点，则指个结点，则指 针的变化情况如图所示。针的变化情况如图所示。 图图 2.17 双向链表的删除操作双向链表的删除操作 双向链表的删除操作算法实现双向链表的删除操作算法实现 intDlinkDel(DoubleList L,int i,ElemType *e) DNode *p; /*首先检查待插入的位置首先检查待插入的位置i是否合法是否合法*/

52、/*若位置若位置i合法，则让指针合法，则让指针p指向它指向它*/ *e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return TRUE; 双向链表应用举例双向链表应用举例 已知：已知：设一个循环双链表设一个循环双链表L=（a,b,c,d）编写一个算法将链表转换为）编写一个算法将链表转换为L=（b,a,c,d）。）。 算法思想：算法思想：实际上是交换表中前两个元素的次序。实际上是交换表中前两个元素的次序。 算法实现：算法实现： voidswap(DLinkList L) DNode * p,*q,*h; h=L-ne

53、xt; /* h指向表中的第一个结点，即指向表中的第一个结点，即a */ p=h-next; /* p指向指向b结点结点 */ q=h-prior; /* 保存保存a 结点的前驱结点的前驱 */ h-next=p-next; p-next-prior=h;/*变换指针指向变换指针指向*/ (h-prior=p错错) p-prior=q; p-next=h; L-next=p; *2.3.5 静态链表静态链表 基本概念：基本概念： 游标实现链表的方法：定义一个较大的结构数组作为游标实现链表的方法：定义一个较大的结构数组作为 备用结点空间（即存储池）。当申请结点时，每个结备用结点空间（即存储池）。

54、当申请结点时，每个结 点应含有两个域：点应含有两个域：data域和域和next域。域。data域存放结点的域存放结点的 数据信息，数据信息，next域为游标指示器，指示后继结点在结域为游标指示器，指示后继结点在结 构数组中的相对位置（即数组下标）。数组的第构数组中的相对位置（即数组下标）。数组的第0个分个分 量可以设计成表的头结点，头结点的量可以设计成表的头结点，头结点的next域指示了表域指示了表 中第一个结点的位置，为中第一个结点的位置，为0表示静态单链表的结束。我表示静态单链表的结束。我 们把这种用游标指示器实现的单链表叫做静态单链表们把这种用游标指示器实现的单链表叫做静态单链表 (St

55、atic Linked List)。静态链表同样可以借助一维数组。静态链表同样可以借助一维数组 来描述来描述 基本操作：基本操作： 初始化、分配结点与结点回收、前插操作、初始化、分配结点与结点回收、前插操作、 删除。删除。 静态链表的结构定义静态链表的结构定义 #define Maxsize= 链表可能达到的最大长度链表可能达到的最大长度 typedef struct ElemType data; int cursor; Component, StaticListMaxsize; 静态链表初始化静态链表初始化 算法描述：算法描述：初始化操作是指将这个静态单链表初始化初始化操作是指将这个静态单链

56、表初始化 为一个备用静态单链表。设为一个备用静态单链表。设space为静态单链表的名字，为静态单链表的名字， av为备用单链表的头指针，其算法如下：为备用单链表的头指针，其算法如下： void initial(StaticList space,int *av) int k; space0-cursor=0; /*设置静态单链表的头指针指向位置设置静态单链表的头指针指向位置0*/ for(k=0;kcursor=k+1; /*连链连链*/ spaceMaxsize-1=0; /*标记链尾标记链尾*/ *av=1; /*设置备用链表头指针初值设置备用链表头指针初值*/ 静态链表分配结点与结点回收静

57、态链表分配结点与结点回收 分配结点分配结点 int getnode(int *av)/*从备用链表摘下一个结点从备用链表摘下一个结点 空间，分配给待插入静态链表中的元素空间，分配给待插入静态链表中的元素*/ int i=*av; *av=space*av.cur; return i; 结点回收结点回收 void freenode(int *av,int k) /*将下标为将下标为 k的空闲结点插入到备用链表的空闲结点插入到备用链表*/ spacek.cursor=*av; *av=k; 静态链表前插操作静态链表前插操作 算法描述算法描述：1、先从备用单链表上取一个可用的结点；、先从备用单链表上

58、取一个可用的结点；2、 将其插入到已用静态单链表第将其插入到已用静态单链表第i个元素之前。个元素之前。 void insbefore(StaticList space,int i,int *av) j=*av ; /*j为从备用表中取到的可用结点空间的下标为从备用表中取到的可用结点空间的下标*/ av=spaceav-cursor;/*修改备用表的头指针修改备用表的头指针*/ spacej-data=x; k=space0-cursor; /*k为已用静态单链表的第一个元素的下标值为已用静态单链表的第一个元素的下标值*/ for(m=1;mcursor; spacej-cursor=space

59、k-cursor; /*修改游标域修改游标域*/ spacek-cursor=j; 静态链表删除静态链表删除 算法描述：算法描述：首先寻找第首先寻找第i -1个元素的位置，之后通过修改相应的游个元素的位置，之后通过修改相应的游 标域进行删除；在将被删除的结点空间链到可用静态单链表中，标域进行删除；在将被删除的结点空间链到可用静态单链表中， 实现回收。实现回收。 void delete(StaticList space;int i;int *av ) k=space0-cursor; for(m=1,mcursor ; j=spacek-cursor ; spacek-cursor=spacej

60、-cursor; /*从删除第从删除第i个元素个元素*/ spacej-cursor=*av; /*将第将第i 个元素占据的空间回收个元素占据的空间回收*/ av=j ; /*置备用表头指针以新值置备用表头指针以新值*/ n nn xpxpxppxp.)( 2 210 在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: : P = (p0, p1, ，pn) 一元多项式一元多项式 但是对于形如但是对于形如 P(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？ 2.4 一元多项式的表示及相加一元多项式的表示及相