第二章-线性表课件.ppt

1、2022-12-28北京联合大学信息学院第二章线性表2022-12-28北京联合大学信息学院 本章导读本章导读 本章要点：线性表的基本概念、线性表的顺序存储、链本章要点：线性表的基本概念、线性表的顺序存储、链式存储、线性表的两种不同存储比较，线性表的应用。式存储、线性表的两种不同存储比较，线性表的应用。通过本章的学习，掌握线性表的基本概念、顺序表和通过本章的学习，掌握线性表的基本概念、顺序表和单链表上的基本运算。掌握循环链表、双向链表和静态单链表上的基本运算。掌握循环链表、双向链表和静态链表的概念。能够利用线性表解决实际问题。链表的概念。能够利用线性表解决实际问题。2022-12-28北京联合

2、大学信息学院2.1线性表的基本概念线性表（Linear list）是最简单且最常用的一种数据结构。是最简单且最常用的一种数据结构。线性表是具有相同类型的线性表是具有相同类型的n（n 0）个数据元素个数据元素（结点）（结点）a1,a2,an组成的有限序列。组成的有限序列。其中数据元素的个数其中数据元素的个数n定义为定义为表的长度表的长度。当。当n=0时称为时称为空表空表，常常将，常常将非空的线性表（非空的线性表（n0）记作：（）记作：（a1,a2,an)这里的数据这里的数据元素元素a ai i(1(1 i n)i n)只是一个抽象符号，具体含义视情况而不同。只是一个抽象符号，具体含义视情况而不同

3、。这种结构具有下列特点：存在一个唯一的没有前驱的这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元（头）数据元素素；存在一个唯一的没有后继的；存在一个唯一的没有后继的（尾）数据元素（尾）数据元素；此外，每一个数；此外，每一个数据元素均有一个据元素均有一个直接前驱直接前驱和一个和一个直接后继直接后继数据元素。数据元素。2022-12-28北京联合大学信息学院2.1 线性表的逻辑结构线性表的逻辑结构v例如：英文字母表（例如：英文字母表（A，B，C，Z）是一个长度为）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；的线性表，其中的每一个字母就是一个数据元素；v某公司某公司2003

4、年每月产值表（年每月产值表（400，420，500，600，650）(单位：万元单位：万元)是一个长度为是一个长度为12的线性表，其的线性表，其中的每一个数值就是一个数据元素。中的每一个数值就是一个数据元素。v上述两例中的每一个数据元素都是不可分割的，在一些复上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个杂的线性表中，每一个数据元素又可以由若干个数据项数据项组组成，在这种情况下，通常将数据元素称为成，在这种情况下，通常将数据元素称为记录记录(record)含用大量记录的线性表又称为含用大量记录的线性表又称为文件文件v例如，图例如，图2.1学生成绩表

5、就是一个线性表，表中每一个学学生成绩表就是一个线性表，表中每一个学生的成绩就是一个记录，每个记录包含六个数据项：学号、生的成绩就是一个记录，每个记录包含六个数据项：学号、姓名、高等代数姓名、高等代数。2022-12-28北京联合大学信息学院2.1 线性表的逻辑结构线性表的逻辑结构图2.1学生成绩表2022-12-28北京联合大学信息学院2.1 线性表的逻辑结构线性表的逻辑结构v矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元

6、素，而其中的每一个数据元素又是每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。一个线性表。v因此，线性表或者是一个空表（因此，线性表或者是一个空表（n=0），或者可以写成：），或者可以写成：（a1，a2，a3，ai-1，ai，ai+1，an）。）。2022-12-28北京联合大学信息学院2.1 线性表的基本操作线性表的基本操作n数据的运算(线性表的基本操作）是定义在逻辑结构上的，而运算的具体实现则是在存储结构上。n线性表的基本运算：（1）置空表 InitList(L):将线性表L置成空表 （2）求长度 ListLength(L):求线性表L中结点个数 （3）取结点GetNode(

7、L,i):取出线性表L中第i个结点 （4）定位 Locate(L,x):在线性表L中查找x的位置 （5）插入Insert(L,x,i):在线性表L的第i个位置插入一 值为x的新结点 （6）删除Delete(L,i):删除线性表L的第i个结点2022-12-28北京联合大学信息学院2.2 线性表的顺序存储结构和实现线性表的顺序存储结构和实现n在计算机中用一组地址连续的存储单元依次存储线性表的各个在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构，线性表称为数据元素，称作线性表的顺序存储结构，线性表称为顺序表顺序表。2.2.1 线性表的顺序存储结构线性表的顺序

8、存储结构 在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。很方便的。假设线性表中的第一个数据元素的存储地址为假设线性表中的第一个数据元素的存储地址为Loc(a1)，每一个，每一个数据元素占数据元素占d字

9、节，则线性表中第字节，则线性表中第i个元素个元素ai在计算机存储空间中在计算机存储空间中的存储地址为：的存储地址为：Loc(ai)=Loc(a1)+(i-1)*d2022-12-28北京联合大学信息学院只要确定了存储线性表的起始位置，线性表中任一元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。在程序设计语言中，通常利用数组来表示线性在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特表的顺序存储结构。这是因为数组具有如下特点点:(1)数据中的元素间的地址是连续的；数据中的元素间的地址是连续的；(2)数组中所有元素的数据类型相同。数组中所有元素的数

10、据类型相同。这两特点与线性表的顺序存储结构类似。这两特点与线性表的顺序存储结构类似。2022-12-28北京联合大学信息学院2.2 线性表的顺序存储结构线性表的顺序存储结构v顺序表数据类型描述 typedef int datatype#define maxsize 1024 typedef struct datatype datamaxsize;int length;sequenlist;2022-12-28北京联合大学信息学院2.2 线性表的顺序存储结构线性表的顺序存储结构n顺序表是用向量实现的线性表，向量的下标可以看成是结点的相对地址。它的特点是逻辑上相邻的结点其物理上亦相邻。2.2.2顺

11、序表上的基本运算 1.顺序表的插入操作 线性表的插入运算是指在表的第i（1 i n)个位置上，插入新结点x,使长度为n的线性表：（a1，ai-1，ai，an）变成长度为n+1的线性表：（a1，ai-1，x，ai，an）2022-12-28北京联合大学信息学院2.2.2顺序表上的基本运算2.2顺序表中插入结点的过程a1a2ai-1aiai+1ana1a2ai-1xaiai+1an插入前插入后一般情况下，在第i（1 i n)个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。2022-12-28北京联合大学信息学院2.2.2顺序表上的基本运算i插入算法n int Ins

12、ert_Item(SeqList*L,DataType x,int i)nn int j;n if(iL-length+1)n return 0;n for(j=L-length;j=i-1;j-)n L-dataj+1=L-dataj;n L-datai-1=x;n L-Length+;n return 1;n2022-12-28北京联合大学信息学院2.2.2顺序表上的基本运算 2.顺序表的删除操作 线性表的删除运算是指将表的第i个结点删去，使长度为n的线性表 （a1，ai-1，ai，an）变为长度为n-1的线性表 （a1，ai-1，ai1，an）其删除过程如图2.3所示：2022-12-2

13、8北京联合大学信息学院2.2.2顺序表上的基本运算2.3顺序表中删除结点的过程a1a2ai-1aiai+1ana1a2ai-1ai+1an删除前删除后般情况下，删除第i（1 i n)个元素时需将从i+1至第n（共n-i）个元素向前移动一个位置。2022-12-28北京联合大学信息学院2.2.2顺序表上的基本运算v删除算法 int Delete(sequenlist*L,int i)int j;if(iL-length)return FALSE;for(j=i;jdataj=L-dataj+1;L-length=L-length-1;return TRUE;2022-12-28北京联合大学信息学

14、院算法分析(以下须xiugai)从上述两个算法来看，很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。而移动元素的次数取决于插入或删除元素的位置。假设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的平均次数为2)(110ninnEniins()0()nis niiEpni2022-12-28北京联合大学信息学院算法分析如果在线性表的任何位置插入或删除元素的概率相等，即 则 可见，在顺序存储结构的线性表中插入或删除

15、一个元素时，平均要移动表中大约一半的数据元素。若表长为n，则插入和删除算法的时间复杂度都为O(n)。在顺序存储结构的线性表中其他的操作也可直接实现，在此不再讲述)1(10inqEniidel11npinqi121)1(110ninnEnidel2022-12-28北京联合大学信息学院2.3 线性表的链式存储结构和实现线性表的链式存储结构和实现v从线性表的顺序存储结构的讨论中可知，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而应采用本节要介绍的链式存储结构。v线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需

16、用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，把这种存储单元称为结点。2022-12-28北京联合大学信息学院2.3 线性表的链式存储结构线性表的链式存储结构v 在链式存储结构方式下，存储数据元素的结点空间可以在链式存储结构方式下，存储数据元素的结点空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系由指针域关系可以不一致，而数据元素之间的逻辑关系由指针域来确定。来确定。v 链式存储方式可用于表示线性结构，也可用于表示非线链式存储

17、方式可用于表示线性结构，也可用于表示非线性结构。性结构。数据域指针域2022-12-28北京联合大学信息学院n例线性表 (zhao,qian,sun,li,zhou,wu,zheng,wang)的链表存储结构.存储地址 数据域 指针域 1 li 43 7 qian 13 头指针head 13 sun 1 19 wang NULL 25 wu 37 31 zhao 7 37 zheng 19 43 zhou 25 整个链表的存取必须从头指针(链表中第一个结点的存储位置)开始进行,最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针域为“空”(NULL)。312022-12-28北京联合大

18、学信息学院qianzhaowangsunlizhouwuzhenghead2022-12-28北京联合大学信息学院2.3.1 单链表1单链表单链表 线性链表中数据元素的逻辑顺序是通过链表中的指针链接次线性链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。因此，在存储线性表中的数据元素时，一方面要存储序实现的。因此，在存储线性表中的数据元素时，一方面要存储数据元素的值，另一方面要存储各数据元素之间的逻辑顺序。数据元素的值，另一方面要存储各数据元素之间的逻辑顺序。此种形式的链表因只含有一个指针域，又称为单向链表，简此种形式的链表因只含有一个指针域，又称为单向链表，简称单链表。称单链表。图图

19、2.5(a)所示为一个空线性链表。图所示为一个空线性链表。图2.5(b)所示为一个非空线性链所示为一个非空线性链表（表（a0，a1，a2，an-1）。）。a1a2an head head (a)(b)图2.5 线性链表的存储结构2022-12-28北京联合大学信息学院2.3.1 单链表v 通常在线性链表的第一结点之前附设一个称为头结点的结通常在线性链表的第一结点之前附设一个称为头结点的结点。头结点的数据域可以不存放任何数据，也可以存放链点。头结点的数据域可以不存放任何数据，也可以存放链表的结点个数的信息。表的结点个数的信息。v 对空线性表，附加头结点的指针域为空（对空线性表，附加头结点的指针域

20、为空（NULL或或0表示），表示），用用 表示。头指针表示。头指针head指向链表附加头结点的存储位置。指向链表附加头结点的存储位置。对于链表的各种操作必须从头指针开始。单链表由头指针对于链表的各种操作必须从头指针开始。单链表由头指针唯一确定。唯一确定。2022-12-28北京联合大学信息学院2.3.1 单链表用C语言描述单链表如下：typedef int datatype typedef struct Lnode datatype data;struct Lnode*next;LinkList;LinkList*head,*L;2022-12-28北京联合大学信息学院2.3.1 单链表 在在

21、C语言中，用户可以利用语言中，用户可以利用malloc函数向系统申请分配链表结点的存储函数向系统申请分配链表结点的存储空间，该函数返回存储区的首地址，如：空间，该函数返回存储区的首地址，如：p=(LinkList*)malloc(sizeof(LinkList);指针指针p指向一个新分配的结点。指向一个新分配的结点。如果要把此结点归还给系统，则用函数如果要把此结点归还给系统，则用函数free(p)来实现。来实现。我们无法通过预先定义的标识符去访问这种动态的结点变量，而只能通我们无法通过预先定义的标识符去访问这种动态的结点变量，而只能通过指针过指针p来访问它，即用来访问它，即用*p作为该结点变量

22、的名字来访问。作为该结点变量的名字来访问。(*p).data和和(*p).next或或 p-data和和p-next。2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作1.建立单链表建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入字符型结点，并以假设线性表中结点的数据类型是字符，我们逐个输入字符型结点，并以“#”作为作为输入结束标志符。输入结束标志符。（1）头插法建表）头插法建表 LinkList*CreateListF()char ch;LinkList*head,*s;head=Null;ch=getchar();while(ch!=#)s=(LinkL

23、ist*)malloc(sizeof(LinkList);s-data=ch;s-next=head;head=s;ch=getchar();return head;2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作(2)尾插法建表 LinkList*CreateListR()char ch;LinkList*head,*s,*r;head=null;r=null;ch=getchar();while(ch!=#)s=(LinkList*)malloc(sizeof(linklist);s-data=ch;if(head=null)head=s;else r-next

24、=s;r=s;ch=getchar();if(r!=null)r-next=null;return head;2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作2.单链表的插入操作单链表的插入操作 1）已知线性链表已知线性链表headhead，在，在p p指针所指向的结点后插入一个元素指针所指向的结点后插入一个元素x x。在一个结点后插入数据元素时，操作较为简单，不用查找便可直接插入。在一个结点后插入数据元素时，操作较为简单，不用查找便可直接插入。操作过程如图操作过程如图2.72.7所示。所示。p(a)插入前图2.7 单链表的后插入sa1a2 headai+1an x

25、(b)插入后sa1a2 headaian xai+1paip2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作 s=(LinkList*)malloc(sizeof(linklist);s-data=x;s-next=p-next;p-next=s;2）已知线性链表已知线性链表headhead，在，在p p指针所指向的结点前插入一个元指针所指向的结点前插入一个元素素x x。前插时，必须从链表的头结点开始，找到。前插时，必须从链表的头结点开始，找到P P指针所指针所指向的结点的前驱。设一指针指向的结点的前驱。设一指针q q从附加头结点开始向后移从附加头结点开始向后移动进

26、行查找，直到动进行查找，直到p p的前趋结点为止。然后在的前趋结点为止。然后在q q指针所指指针所指的结点和的结点和p p指针所指的结点之间插入结点指针所指的结点之间插入结点s s。2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作(a)插入前图2.8 单链表的前插入qpsa1a2 headaian xai-1pq(a)插入后ppsa1a2 headaian xai-1p2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作 q=head;while(q-next!=p)q=q-next;s=(LinkList*)malloc(sizeof(li

27、nklist);s-data=x;s-next=p;q-next=s;2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作单链表的前插入算法 int insert(LinkList*h,int i,datatype x)/*在链表h中，在第i个数据元素插入一个数据元素x*/LinkList*p,*q,*s;int j=0;p=h;while(p!=NULL&jnext;j+;/*寻找第i-1个结点*/if(j!=i-1)printf(“Error!”);return FALSE;/*插入位置错误*/if(s=(LinkList*)malloc(sizeof(LinkLi

28、st)=NULL)return FALSE;s-data=x;s-next=p-next;q-next=s;return TRUE;2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作例：下面下面C程序中的功能是，首先建立一个线性链表程序中的功能是，首先建立一个线性链表head=3，5，7，9，其元素，其元素值依次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为值依次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为x的元素前插入一个值为的元素前插入一个值为y的数据元素。若值为的数据元素。若值为x的结点不存在，则将的结点不存在，则将y插在表尾插

29、在表尾。#include“stdlib.h”#include“stdio.h”struct LinkList datatype data;struct LinkList*next;/*定义结点类型*/main()int x,y,d;struct linklist*head,*p,*q,*s;head=NULL;/*置链表空*/q=NULL;scanf(“%d”,&d);/*输入链表数据元素*/while(d0)2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作p=malloc(sizeof(struct linklist);/*申请一个新结点*/p-data=d;p-

30、next=NULL;if(head=NULL)head=p;/*若链表为空，则将头指针指向当前结点p*/else q-next=p;/*链表不为空时，则将新结点链接在最后*/q=p;/*将指针q指向链表的最后一个结点*/scanf(“%d”,&d);scanf(“%d,%d”,&x,&y);s=malloc(sizeof(struct linklist);s-data=y;q=head;p=q-next;while(p!=NULL)&(p-data!=x)q=p;p=p-next;/*查找元素为x的指针*/s-next=p;q-next=s;/*插入元素y*/2022-12-28北京联合大学信

31、息学院单链表上的基本操作单链表上的基本操作3.单链表的删除操作若要删除线性链表h中的第i个结点，首先要找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。操作过程如图2.9所示。aiai-1ai+1an(a)寻找第i个结点指向其前驱ppsanai+1aiai-1(b)删除并释放第i个结点图2.9 在线性链表中删除一个结点的过程2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作int Delete(linklist*h,int i)/*在链表h中删除第i个结点*/linklist*p,*s;int j;p=h;j=0;while(p

32、-next!=NULL&jnext;j=j+1;/*寻找第i-1个结点,p指向其前驱*/if(j!=i-1)printf(“Error!”);/*删除位置错误!*/return FALSE;s=p-next;p-next=p-next-next;/*删除第i个结点*/free(s);/*释放被删除结点空间*/return TRUE;2022-12-28北京联合大学信息学院单链表上的基本操作单链表上的基本操作 请读者比较插入算法与删除算法中所用的条件 (p!=NULL&jnext!=NULL&jnext!=nullp-next!=null；而在循环链表中应改为；而在循环链表中应改为p!=head

33、p!=head或或p-p-next!=headnext!=head。v 在循环链表中，除了头指针在循环链表中，除了头指针headhead外，有时还加了一个尾指针外，有时还加了一个尾指针rearrear，尾指针，尾指针rearrear指向最后一结点，从最后一个结点的指针又可立即指向最后一结点，从最后一个结点的指针又可立即找到链表的第一个结点。如图找到链表的第一个结点。如图2.112.11所示在实际应用中，使用尾指所示在实际应用中，使用尾指针代替头指针来进行某些操作，往往更简单。针代替头指针来进行某些操作，往往更简单。a0a1an-1ai图2.11 带尾指针单循环链表表示示意图*rearrear*

34、(rear-next)head2022-12-28北京联合大学信息学院2.3.2 循环链表循环链表例：在链表上实现将两个线性表(a1,a2,an)和(b1,b2,bn)链结成一个线性表（a1,a2,an,b1,b2,bn）2022-12-28北京联合大学信息学院2.3.2 循环链表循环链表linklist*connect(linklist*ra,linklist*rb)linklist*p;p=ra-next;ra-next=rb-next-next;free(rb-next);rb-next=p;return rb;2022-12-28北京联合大学信息学院1双向链表双向链表 在单链表的每个结

35、点中只有一个指示后继的指针域，因此从任何一个结点都能通过指针域找到它的后继结点；若需找出该结点的前驱结点，则此时需从表头出发重新查找。换句话说，在单链表中，查找某结点的后继结点的执行时间为O(1)，而查找其前驱结点的执 行时间为O(n)。我们可用双向链表来克服单链表的这种缺点，在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。2.3.3 双向链表双向链表2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表双向链表的结构可定义如下：typedef struct Dnode datatype

36、data;struct Dnode*prior,*next;DLinkList;DLinkList *head;2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表a0a1 an-1 head(c)非空的双循环链表图2.12 双链表示意图双链表一般由头指针唯一确定，增加头结点也能使双链表上的某些运算变的方便，将头结点和尾结点链接起来也能构成循环链表，称之为双（向）循环链表。如图2.12所示：2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表 若p为指向双向链表中的某一个结点ai的指针，则双链表结构的对称性可用下式刻化：p-prior-next p=p-next

37、-prior 在双向链表中，有些操作如：求长度、取元素、定位等，因仅需涉及一个方向的指针，故它们的算法与线性链表的操作相同；但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为O(n)。2双向链表的插入和删除操作双向链表的插入和删除操作（1）在双向链表中插入一个结点 在双向链表的第i个元素前插入一个结点时，可用指针p指该结点（称p结点），先将新结点的prior指向p结点的前一个结点，其次将p结点的前一个结点的next指向新结点，然后将新结点的next指向p结点，最后将p结点的prior指向新结点。操作过程如图2.13所示。2022-12-28北京联合大学信息学院2.3.3

38、 双向链表双向链表双向链表的插入：int DuInsertBefore(dlinklist*head,int i,datatype x)/*在带头结点的双向链表中第i个位置之前插入元素x*/dlinklist*p,*s;int j;p=head;(a)插入前 （b）插入后 图2.13 在双向链表中插入结点ai-1ai s x p ai-1 aip s x 2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表 j=0;while(p!=NULL&jnext;j+;if(j!=i|idata=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-p

39、rior=s;return TRUE;2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表讨论：在双向链表中进行插入操作时，需注意下面两种情况：1）当在链表中的第一个结点前插入新结点时，新结点的prior应为空，原链表第一个结点的prior应指向新结点，新结点的next应指向原链表的第一个结点。2）当在链表的最后一个结点后插入新结点时，新结点的next应为空，原链表的最后一个结点的next应指向新结点，新结点的prior应指向原链表的最后一个结点。（2）在双向链表中删除一个结点 在双向链表中删除一个结点时，可用指针p指向该结点(称p结点)，然后将p结点的前一个结点的next指向

40、p结点的下一个结点，再将p的下一个结点的prior指向p的上一个结点。如图2.14所示，2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表双向链表的删除:int Dlinklist_Delete(dlinklist*head,int i)dlinklist*p,*s;int j;p=head;j=0;while(p!=NULL&jnext;j+;图2.14 在双向链表中删除一个结点ai-1aiai+1p2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表 if(j!=i|iprior-next=p-next;/*图中步骤*/p-next-prior=p-pri

41、or;/*图中步骤*/free(s);return TRUE;讨论：在双向链表中进行删除操作时，需注意下面两种情况：1）当删除链表的第一个结点时，应将链表开始结点的指针指向链表的第二个结点，同时将链表的第二个结点的prior置为NULL。2022-12-28北京联合大学信息学院2.3.3 双向链表双向链表2）当删除链表的最后一个结点时，只需将链表的最后一个结点的上一个结点的next置为NULL即可。上面我们详细讲解了链式存储结构，链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：（1

42、）每个结点中的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重就显得很大。（2）链式存储结构是一种非随机存储结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。2022-12-28北京联合大学信息学院2.5线性表的应用2.5.1 一元多项式的表示及相加一元多项式的表示及相加符号多项式的表示及其操作是线性表处理的典型用例，在数学上，一个一元多项式Pn(x)可以表示为：Pn(x)=a0+a1x+a2x2+anxn (最多有n+1项)aixi是多项式的第i项（0in），其中ai为系数，x为变量，i为指数。它有n+1个系数，因此，在计算机里

43、，它可用一个线性表P来表示：P=（a0,a1,a2,，an）假设Qn(x)是一元m次多项式，同样可用线性表Q来示：Q=（b0,b1,b2,，bm）若mnext;qb=Bh-next;/*qa和qb分别指向两个链表的第一结点*/r=qa;Ch=Ah;/*将链表Ah作为相加后的和链表*/while(qa!=NULL&qb!=NULL)/*两链表均非空*/if(qa-exp=qb-exp)/*两者指数值相等*/x=qa-coef+qb-coef;if(x!=0)qa-coef=x;r-next=qa;r=qa;s=qb+;free(s);qa+;/*相加后系数不为零时*/else s=qa+;fre

44、e(s);s=qb+;free(s);/*相加后系数为零时*/2022-12-28北京联合大学信息学院2.5线性表的应用 else if(qa-expexp)r-next=qa;r=qa;qa+;/*多项式Ah的指数值小*/else r-next=qb;r=qb;qb+;/*多项式Bh的指数值小*/if(qa=NULL)r-next=qb;else r-next=qa;/*链接多项式Ah或Bh中的剩余结点*/return(Ch);2022-12-28北京联合大学信息学院2.5线性表的应用2.5.2 约瑟夫环问题2.5.3 电文加密2022-12-28北京联合大学信息学院 上机实验题上机实验题n利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。n巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。