《数据结构与算法 (2).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (2).pdf（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法Data Structure And Algorithms2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表2.4 一元多项式的表示及相加第2章线性表线性结构是最常用、最简单的一种数据结构。而线线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：数据元素是有序且是有限的。在这种结构中：存在一个唯一的被称为存在一个唯一的被称为“第一个第一个”的数据元素的数据元素；
2、存在一个唯一的被称为存在一个唯一的被称为“最后一个最后一个”的数据元素的数据元素；除第一个元素外除第一个元素外，每个元素均有唯一一个直接前，每个元素均有唯一一个直接前驱；驱；除最后一个元素外除最后一个元素外，每个元素均有唯一一个直接，每个元素均有唯一一个直接后继。后继。第2章线性表2.1 线性表的逻辑结构线性表线性表(Linear List)：是由：是由n(n0)个数据元素个数据元素(结结点点)a1，a2，an组成的有限序列。该序列中的所有结组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数点具有相同的数据类型。其中数据元素的个数n称为线称为线性表的长度。性表的长度。当当
3、n=0时，称为时，称为空表空表。当当n0时，将非空的线性表记作：时，将非空的线性表记作：(a1，a2，an)2.1.1 线性表的定义线性表的定义a1称为线性表的称为线性表的第一个第一个(首首)结点结点，an称为线性表的称为线性表的最后最后一个一个(尾尾)结点结点。a1，a2，ai-1都是都是ai(2in)的的前驱前驱，其中，其中ai-1是是ai的的直直接前驱接前驱；ai+1，ai+2，an都是都是ai(1i n-1)的的后继后继，其中，其中ai+1是是ai的的直接后继直接后继。2.1.2线性表的逻辑结构线性表的逻辑结构线性表中的数据元素线性表中的数据元素ai所代表的具体含义随具体应所代表的具体
4、含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。象的表示符号。例例1：26个英文字母组成的字母表：个英文字母组成的字母表：(A，B，C、Z）线性表中的线性表中的结点结点可以是可以是单值元素单值元素（每个元素只有一（每个元素只有一个数据项）个数据项）例例2：某校从：某校从1978年到年到1983年各种型号的计算机拥有量年各种型号的计算机拥有量的变化情况：的变化情况：(6，17，28，50，92，188）线性表中的线性表中的结点结点可以是可以是记录型记录型元素，每个元素含有元素，每个元素含有多个数据项多个数据项，每个项称为结
5、点的一个域，每个项称为结点的一个域。每个元素。每个元素有一个可以唯一标识每个结点的有一个可以唯一标识每个结点的数据项组数据项组，称为，称为关关键字键字。例例4：某校：某校2001级同学的基本情况：级同学的基本情况：(2001414101，张里户张里户，男男，06/24/1983)，(2001414102，张化司张化司，男男，08/12/1984)，(2001414102，李利辣李利辣，女女，08/12/1984)例例3：一副扑克的点数一副扑克的点数(2，3，4，J，Q，K，A)若线性表中的结点是若线性表中的结点是按值按值(或按关键字值或按关键字值)由小到由小到大大(或由大到小或由大到小)排列排
6、列的，称线性表是有序的。的，称线性表是有序的。线性表是一种相当灵活的数据结构，其长度可根线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。据需要增长或缩短。对线性表的数据元素可以访问、插入和删除。对线性表的数据元素可以访问、插入和删除。2.1.3 线性表的抽象数据类型定义线性表的抽象数据类型定义ADT List数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：数据关系：R=|ai-1,aiD,i=2,3,n 基本操作：基本操作：InitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L；ListEmpty(L)初始条件：线性表初
7、始条件：线性表L已存在；已存在；操作结果：若操作结果：若L为空表，则返回为空表，则返回TRUE，否则返回，否则返回FALSE；.GetElem(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L)；操作结果：用操作结果：用e返回返回L中第中第i个数据元素的值；个数据元素的值；ListInsert(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L)；操作结果：在线性表操作结果：在线性表L中的第中的第i个位置插入元素个位置插入元素e；.ADT List顺序存储顺序存储：把线性表的结点：把线性表的结点按逻辑顺序按逻
8、辑顺序依次存放依次存放在一组地址连续的存储单元在一组地址连续的存储单元里。用这种方法存储的线性里。用这种方法存储的线性表简称顺序表。表简称顺序表。顺序存储顺序存储的线性表的的线性表的特点特点：线性表的逻辑顺序与物理顺序一致线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内“数据元素之间的关系是以元素在计算机内“物理物理位置相邻位置相邻”来体现。”来体现。设有非空的线性表：设有非空的线性表：(a1，a2，an)。顺序存储如图。顺序存储如图2-1所示。所示。2.2.1 线性表的顺序存储结构线性表的顺序存储结构2.2 线性表的顺序存储在具体的机器环境下：在具体的机器环境下：设线性表
9、的每个元素需占用设线性表的每个元素需占用l 个存储单元，以所占的第一个单元的存储地址作为数个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第据元素的存储位置。则线性表中第 i+1 个数据元素的存个数据元素的存储位置储位置 LOC(ai+1)和第和第 i 个数据元素的存储位置个数据元素的存储位置 LOC(ai)之间满足下列关系：之间满足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第线性表的第i个数据元素个数据元素ai的存储位置为：的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l a1 a2 ai an Loc(a1)Loc(ai)+(i-1)*l
10、图图2-1 线性表的顺序存储表示线性表的顺序存储表示在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status;typedef int ElemType;typedef struct sqlist ElemType Elem_arrayMAX_SIZE;intlength;SqList;2.2.2顺序表的基本操作顺序表的基本操作顺序存储结构
11、中，很容易实现线性表的一些操作：顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等初始化、赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论以下将对几种主要的操作进行讨论。Status Init_SqList(SqList*L)L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType);if(!L-elem_array)return ERROR;else L-length=0;return OK;1.顺序线性表初始化顺序线性表初始化2.顺序顺序线性表的插入线性表的插入在线性表在线性
12、表 L=(a1，a i-1，ai，ai+1，an)中中的的第第 i(1in)个位置上插入一个新结点个位置上插入一个新结点 e，使其成为线，使其成为线性表性表：L=(a1，a i-1，e，ai，ai+1，an)实现步骤实现步骤(1)(1)将线性表将线性表L中的中的第第i个至第个至第n个结点后移一个位置。个结点后移一个位置。(2)(2)将结点将结点e插入到结点插入到结点ai-1之后之后。(3)(3)线性表长度加线性表长度加1。算法描述算法描述Status Insert_SqList(Sqlist*L，int i，ElemType e)int j;if (iL-length-1)return ERR
13、OR;if (L-length=MAX_SIZE)printf(“线性表溢出线性表溢出!n”);return ERROR;for (j=L-length1;j=i-1;-j)L-Elem_arrayj+1=L-Elem_arrayj;/*i-1位置以后的所有结点后移位置以后的所有结点后移*/L-Elem_arrayi-1=e;/*在在i-1位置插入结点位置插入结点*/L-length+;return OK;时间复杂度分析时间复杂度分析在线性表在线性表L中的中的第第i个个元素之前插入新结点，其时间元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的主要耗费在表中结点的移动操
14、作上，因此，可用结点的移动来估计算法的时间复杂度。移动来估计算法的时间复杂度。设设在线性表在线性表L中的中的第第i个个元素之前插入结点的概率为元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为，而插入时移动结点的次数为n-i+1。总的平均移动次数：总的平均移动次数：Einsert=pi*(n-i+1)(1in)Einsert=n/2。即即在顺序表上做插入运算，平均要移动表上一半结在顺序表上做插入运算，平均要移动表上一半结点。当表长点。当表长n较大时，算法的效率相当低。因此算法的较大时，算法的
15、效率相当低。因此算法的平均时间复杂度为平均时间复杂度为O(n)。3 顺序线性表的删除顺序线性表的删除在线性表在线性表 L=(a1，a i-1，ai，ai+1，an)中删除中删除结点结点ai(1in)，使其成为线性表，使其成为线性表：L=(a1，ai-1，ai+1，an)实现步骤实现步骤(1)(1)将线性表将线性表L中的中的第第i+1个至第个至第n个结点依此向前移个结点依此向前移动一个位置。动一个位置。(2)(2)线性表长度减线性表长度减1。算法描述算法描述ElemType Delete_SqList(Sqlist*L，int i)int k;ElemType x;if (L-length=0)
16、printf(“线性表线性表L为空为空!n”);return ERROR;else if(iL-length)printf(“要删除的数据元素不存在要删除的数据元素不存在!n”);return ERROR;else x=L-Elem_arrayi-1;/*保存结点的值保存结点的值*/for(k=i;klength;k+)L-Elem_arrayk-1=L-Elem_arrayk;/*i位置以后的所有结点前移位置以后的所有结点前移*/L-length-;return(x);时间复杂度分析时间复杂度分析删除线性表删除线性表L中的中的第第i个个元素，其时间主要耗费在表元素，其时间主要耗费在表中结点的
17、移动操作上，因此，可用结点的移动来估计算中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。法的时间复杂度。设设在线性表在线性表L中中删除第删除第i个个元素的概率为元素的概率为Pi，不失一，不失一般性，设删除各个位置是等概率，则般性，设删除各个位置是等概率，则Pi=1/n，而删除时，而删除时移动结点的次数为移动结点的次数为n-i。则总的平均移动次数：则总的平均移动次数：Edelete=pi*(n-i)(1in)Edelete=(n-1)/2。即即在顺序表上做删除运算，平均要移动表上一半结点。在顺序表上做删除运算，平均要移动表上一半结点。当表长当表长n较大时，算法的效率相当低。因此较
18、大时，算法的效率相当低。因此算法的平均算法的平均时间复杂度为时间复杂度为 O(n)。4.顺序线性表的查找定位删除顺序线性表的查找定位删除在线性表在线性表 L=(a1，a2，an)中删除值为中删除值为x的第一的第一个结点个结点。实现步骤实现步骤(1)(1)在线性表在线性表L查找值为查找值为x的第的第一个数据元素。一个数据元素。(2)(2)将从找到的位置至最后一将从找到的位置至最后一个结点依次向前移动一个结点依次向前移动一个位置。个位置。(3)(3)线性表长度减线性表长度减1。算法描述算法描述Status Locate_Delete_SqList(Sqlist*L，ElemType x)/*删除线
19、性表L中值为x的第一个结点*/int i=0,k;while (ilength)/*查找值为查找值为x的的第第一个一个结点结点*/if (L-Elem_arrayi!=x)i+;else for(k=i+1;klength;k+)L-Elem_arrayk-1=L-Elem_arrayk;L-length-;break;if (iL-length)printf(“要删除的数据元素不存在要删除的数据元素不存在!n”);return ERROR;return OK;时间复杂度分析时间复杂度分析时间主要耗费在数据元素的比较和移动操作上。时间主要耗费在数据元素的比较和移动操作上。首先，首先，在线性表在
20、线性表L中查找值为中查找值为x的的结点是否存在结点是否存在;其次，若其次，若值为值为x的的结点存在，且在结点存在，且在线性表线性表L中的位置为中的位置为i，则在则在线性表线性表L中删除中删除第第i个个元素。元素。设设在线性表在线性表L删除删除数据元素概率为数据元素概率为Pi，不失一般性，不失一般性，设各个位置是等概率，则设各个位置是等概率，则Pi=1/n。比较的平均次数比较的平均次数：Ecompare=pi*i(1in)Ecompare=(n+1)/2。删除时平均移动次数删除时平均移动次数：Edelete=pi*(n-i)(1in)Edelete=(n-1)/2。平均时间复杂度：平均时间复杂度
21、：Ecompare+Edelete=n，即为即为O(n)。2.3.1线性表的链式存储结构线性表的链式存储结构链式存储链式存储：用用一组任意的存储单元存储一组任意的存储单元存储线性表线性表中的数据元素。用这种方法存储的线性表简称中的数据元素。用这种方法存储的线性表简称线性链线性链表表。存储链表中结点的一组任意的存储单元可以是连存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。链表中结点的逻辑顺序和物理顺序不一定相同。2.3 线性表的链式存储
22、为了正确表示结点间的逻辑关系，在存储每个结点为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址值的同时，还必须存储指示其直接后继结点的地址(或或位置位置)，称为，称为指针指针(pointer)或链或链(link)，这两部分组成了，这两部分组成了链表中的结点结构，如图链表中的结点结构，如图2-2所示。所示。链表是通过每个结点的指针域将线性表的链表是通过每个结点的指针域将线性表的n个结点个结点按其逻辑次序链接在一起的。按其逻辑次序链接在一起的。每一个结点只包含一个指针域的链表，称为每一个结点只包含一个指针域的链表，称为单链表单链表。为操作方便，总是在链表的第一
23、个结点之前附设一为操作方便，总是在链表的第一个结点之前附设一个个头结点头结点(头指针头指针)head指向第一个结点。头结点的数据指向第一个结点。头结点的数据域可以不存储任何信息域可以不存储任何信息(或链表长度等信息或链表长度等信息)。data next图图2-2 链表结点结构链表结点结构data：数据域，存放结点的值。：数据域，存放结点的值。next：指针：指针域，存放结点的直接后继的地址。域，存放结点的直接后继的地址。3695headfat1100bat1300cat1305eat3700hatNULL1100370013001305bat cat eat fat hat head图图2-3
24、带头结点的单链表的逻辑状态、物理存储方式带头结点的单链表的逻辑状态、物理存储方式单链表是由表头唯一确定，因此单单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。链表可以用头指针的名字来命名。例例1.1.线性表线性表L=(bat，cat，eat，fat，hat)其其带头结点的单带头结点的单链表的逻辑状态和物理链表的逻辑状态和物理存储方式如图存储方式如图2-3所示。所示。1 结点的描述与实现结点的描述与实现C语言中用语言中用带指针的结构体类型带指针的结构体类型来描述来描述typedef struct Lnode ElemType data;/*数据域，保存结点的值数据域，保存结点的值*/
25、struct Lnode*next;/*指针域指针域*/LNode;/*结点的类型结点的类型*/2 结点的实现结点的实现结点是通过动态分配和释放来的实现结点是通过动态分配和释放来的实现，即需要时分，即需要时分配，不需要时释放。实现时是分别使用配，不需要时释放。实现时是分别使用C语言提供的标语言提供的标准函数：准函数：malloc()，realloc()，sizeof()，free()。动态分配动态分配p=(LNode*)malloc(sizeof(LNode);函数函数malloc分配了一个类型为分配了一个类型为LNode的结点变量的空间，的结点变量的空间，并将其首地址放入指针变量并将其首地址
26、放入指针变量p中。中。动态释放动态释放free(p);系统回收由指针变量系统回收由指针变量p所指向的内存区。所指向的内存区。P必须是最近一必须是最近一次调用次调用malloc函数时的返回值。函数时的返回值。3 最常用的基本操作及其示意图最常用的基本操作及其示意图(1)结点的赋值结点的赋值LNode*p;p=(LNode*)malloc(sizeof(LNode);p-data=20;p-next=NULL;p20NULL(2)常见的指针操作常见的指针操作 q=p;pa操作前操作前paq操作后操作后 q=p-next;bpa操作前操作前操作后操作后qbpa p=p-next;bpa操作前操作前操
27、作后操作后pba操作前操作前ypxbqa操作后操作后ypxbqa(b)q-next=p;cpbqa操作前操作前操作后操作后qbacp(a)q-next=p-next;(a)xypbqa操作前操作前操作后操作后qbaxyp操作前操作前ypxbqa操作后操作后ypxbqa(b)2.3.2单线性链表的基本操作单线性链表的基本操作1 建立单链表建立单链表假设线性表中结点的数据类型是整型，以假设线性表中结点的数据类型是整型，以32767作作为结束标志。动态地建立单链表的常用方法有如下两种：为结束标志。动态地建立单链表的常用方法有如下两种：头插入法头插入法，尾插入法尾插入法。头插入法建表头插入法建表从一个
28、空表开始，重复读入数据，生成新结点，从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即入到当前链表的表头上，直到读入结束标志为止。即每每次插入的结点都作为链表的第一个结点次插入的结点都作为链表的第一个结点。算法描述算法描述LNode*create_LinkList(void)/*头插入法创建单链表头插入法创建单链表,链表的头结点链表的头结点head作为返回值作为返回值*/int data;LNode*head,*p;head=(LNode*)malloc(siz
29、eof(LNode);head-next=NULL;/*创建链表的表头结点创建链表的表头结点head */while(1)scanf(“%d”,&data);if(data=32767)break;p=(LNode*)malloc(sizeof(LNode);pdata=data;/*数据域赋值数据域赋值*/pnext=headnext;headnext=p;/*钩链钩链，新创建，新创建的结点总是作为第一个结点的结点总是作为第一个结点*/return(head);(2)尾插入法建表尾插入法建表头插入法建立链表虽然算法简单，但生成的链表头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入
30、的顺序相反。若希望二者次序一致，中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将可采用尾插法建表。该方法是将新结点插入到当前链表新结点插入到当前链表的表尾，使其成为当前链表的尾结点的表尾，使其成为当前链表的尾结点。算法描述算法描述LNode*create_LinkList(void)/*尾插入法创建单链表,链表的头结点head作为返回值*/int data;LNode*head,*p,*q;head=p=(LNode*)malloc(sizeof(LNode);p-next=NULL;/*创建单链表的表头结点head */while(1)scanf(“%d”,&d
31、ata);if(data=32767)break;q=(LNode*)malloc(sizeof(LNode);qdata=data;/*数据域赋值*/qnext=pnext;pnext=q;p=q;/*钩链钩链，新创建，新创建的结点总是作为最后一个结点的结点总是作为最后一个结点*/return(head);无论是哪种插入方法，如果要插入建立的单线性无论是哪种插入方法，如果要插入建立的单线性链表的结点是链表的结点是n个，算法的时间复杂度均为个，算法的时间复杂度均为O(n)。对于单链表，无论是哪种操作，只要涉及到钩链对于单链表，无论是哪种操作，只要涉及到钩链(或重新钩链或重新钩链)，如果，如果没
32、有明确给出直接后继没有明确给出直接后继，钩链，钩链(或或重新钩链重新钩链)的次序必须是的次序必须是“先右后左先右后左”。2 单链表的查找单链表的查找(1)按序号查找按序号查找取单链表中的第取单链表中的第i个元素个元素。对于单链表对于单链表，不能象顺序表中那样直接按序号不能象顺序表中那样直接按序号 i访问结点访问结点，而只能从链表的头结点出发而只能从链表的头结点出发，沿链域沿链域 next逐个结点往下搜索逐个结点往下搜索，直到搜索到第直到搜索到第 i 个结点为止个结点为止。因此因此，链表不是随机存取结构链表不是随机存取结构。设单链表的长度为设单链表的长度为 n，要查找表中第要查找表中第 i 个结
33、点个结点，仅当仅当 1in 时时，i 的值是合法的的值是合法的。算法描述算法描述ElemType Get_Elem(LNode*L，int i)int j;LNode*p;p=L-next;j=1;/*使使 p p 指向第一个结点指向第一个结点*/while (p!=NULL&jnext;j+;/*/*移动指针移动指针 p,jp,j 计数计数*/if (j!=i)return(-32768);else return(p-data);/*p/*p 为为 NULL NULL 表示表示 i i 太大太大;j;ji i 表示表示 i i 为为 0 */0 */移动指针移动指针p的频度：的频度：in：n
34、次。次。时间复杂度时间复杂度:O(n)。(2)按值查找按值查找按值查找是在链表中，查找是否有结点值等于给定按值查找是在链表中，查找是否有结点值等于给定值值key的结点？的结点？若有，则返回首次找到的值为若有，则返回首次找到的值为key的结的结点的存储位置；否则返回点的存储位置；否则返回NULL。查找时从开始结点出。查找时从开始结点出发，沿链表逐个将结点的值和给定值发，沿链表逐个将结点的值和给定值key作比较。作比较。算法描述算法描述LNode*Locate_Node(LNode*L，int key)/*在以在以L为头结点的单链表中查找值为为头结点的单链表中查找值为key的第一个结点的第一个结点
35、*/LNode*p=Lnext;while (p!=NULL&pdata!=key)p=pnext;if (pdata=key)return p;else printf(“所要查找的结点不存在所要查找的结点不存在!n”);retutn(NULL);算法的执行与形参算法的执行与形参key有关，有关，平均时间复杂度为平均时间复杂度为O(n)。3 单链表的插入单链表的插入插入运算是将值为插入运算是将值为e的新结点插入到表的第的新结点插入到表的第i个结点个结点的位置上，即插入到的位置上，即插入到ai-1与与ai之间。因此，必须首先找到之间。因此，必须首先找到ai-1所在所在的结点的结点p，然后生成一个
36、数据域为，然后生成一个数据域为e的新结点的新结点q，q结点作为结点作为p的直接后继结点。的直接后继结点。算法描述算法描述void Insert_LNode(LNode*L，int i，ElemType e)/*/*在以在以L L为头结点的单链表的第为头结点的单链表的第i i个位置插入值为个位置插入值为e e的结点的结点*/int j=0;LNode*p，*q;p=Lnext;while (p!=NULL&jnext;j+;if (j!=i-1)printf(“i太大或太大或i为为0!n”);else q=(LNode*)malloc(sizeof(LNode);qdata=e;qnext=pn
37、ext;pnext=q;设链表的长度为设链表的长度为n，合法的插入位置是，合法的插入位置是1in。算。算法的时间主要耗费法的时间主要耗费移动指针移动指针p上，故上，故时间复杂度亦为时间复杂度亦为O(n)。4 单链表的删除单链表的删除 按序号删除按序号删除删除单链表中的第i个结点。为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。设单链表长度为n，则删去第i个结点仅当1in时是合法的。则当i=n+1时，
38、虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是pnext!=NULL。显然此算法的时间复杂度也是O(n)。算法描述算法描述void Delete_LinkList(LNode*L，int i)/*删除以删除以L为头结点的单链表中的第为头结点的单链表中的第i i个结点个结点*/int j=1;LNode*p，*q;p=L;q=L-next;while (p-next!=NULL&jnext;j+;if (j!=i)printf(“i太大或太大或i为为0!n”);else pnext=qnext;free(q);按值删除按值删除删除单链表中值为删除单链表中值为key的第一个结
39、点。的第一个结点。与按值查找相类似，首先要查找值为与按值查找相类似，首先要查找值为keykey的结点是的结点是否存在？否存在？若存在，则删除；否则返回若存在，则删除；否则返回NULL。算法描述算法描述void Delete_LinkList(LNode*L，int key)/*删除以删除以L为头结点的单链表中值为为头结点的单链表中值为key的第一个结点的第一个结点*/LNode*p=L,*q=Lnext;while (q!=NULL&qdata!=key)p=q;q=qnext;if (qdata=key)p-next=q-next;free(q);else printf(“所要删除的结点不存
40、在所要删除的结点不存在!n”);算法的执行与形参算法的执行与形参k key有关，有关，平均时间复杂度为平均时间复杂度为O(n)。从上面的讨论可以看出，链表上实现插入和删除运从上面的讨论可以看出，链表上实现插入和删除运算，无需移动结点，仅需修改指针。解决了顺序表的插算，无需移动结点，仅需修改指针。解决了顺序表的插入或删除操作需要移动大量元素的问题。入或删除操作需要移动大量元素的问题。变形之一：变形之一：删除单链表中值为删除单链表中值为key的所有结点。的所有结点。与按值查找相类似，但比前面的算法更简单。与按值查找相类似，但比前面的算法更简单。基本思想基本思想：从单链表的第一个结点开始，对每个结点
41、从单链表的第一个结点开始，对每个结点进行检查，若结点的值为进行检查，若结点的值为keykey，则删除之，然后检查下，则删除之，然后检查下一个结点，直到所有的结点都检查。一个结点，直到所有的结点都检查。算法描述算法描述void Delete_LinkList_Node(LNode*L，int key)/*删除以删除以L为头结点的单链表中值为为头结点的单链表中值为key的第一个结点的第一个结点*/LNode*p=L,*q=Lnext;while (q!=NULL)if(qdata=key)p-next=q-next;free(q);q=p-next;else p=q;q=qnext;变形之二：变形
42、之二：删除单链表中所有值重复的结点，使得所有结点的删除单链表中所有值重复的结点，使得所有结点的值都不相同。值都不相同。与按值查找相类似，但比前面的算法更复杂。与按值查找相类似，但比前面的算法更复杂。基本思想基本思想：从单链表的第一个结点开始，对每个结点从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都被检查。直到所有的结点都被检查。算法描述算法描述void Delete_Node_value(LNo
43、de*L)/*删除以删除以L为头结点的单链表中所有值相同的结点为头结点的单链表中所有值相同的结点*/LNode*p=L-next,*q,*ptr;while (p!=NULL)/*检查链表中所有结点检查链表中所有结点*/*q=p,*ptr=pnext;/*检查结点检查结点p的所有后继结点的所有后继结点ptr*/while(ptr!=NULL)if(ptrdata=p-data)q-next=ptr-next;free(ptr);ptr=q-next;else q=ptr;ptr=ptrnext;p=p-next;5 单链表的合并单链表的合并设有两个有序的单链表，它们的头指针分别是设有两个有序的
44、单链表，它们的头指针分别是La、Lb，将它们合并为以，将它们合并为以Lc为为头指针的有序链表。合并前头指针的有序链表。合并前的示意图如图的示意图如图2-4所示。所示。15 图图2-4两个有序的单链表两个有序的单链表La，Lb的初始状态的初始状态-2 4 9 Lbpb-7 3 12 23 LaLcpapc合并了值为合并了值为-7，-2的结点后示意图如图的结点后示意图如图2-5所示。所示。图图2-5 合并了值为合并了值为-7，-2的结点后的状态的结点后的状态-2 4 9 15 LbpcpbLc-7 3 12 23 Lapa算法说明算法说明算法中算法中pa，pb分别是待考察的两个链表的当前分别是待考
45、察的两个链表的当前结点，结点，pc是合并过程中合并的链表的最后一个结点。是合并过程中合并的链表的最后一个结点。算法描述算法描述LNode*Merge_LinkList(LNode*La，LNode*Lb)/*合并以合并以La,Lb为头结点的两个有序单链表为头结点的两个有序单链表*/LNode*Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La ;pa=La-next;pb=Lb-next ;while(pa!=NULL&pb!=NULL)if (pa-datadata)pc-next=pa;pc=pa;pa=pa-next ;/*将将pa所指的结点合并，所指的结点合并，pa指向下一
46、个结点指向下一个结点*/if (pa-datapb-data)pc-next=pb;pc=pb;pb=pb-next ;/*将将pa所指的结点合并，所指的结点合并，pa指向下一个结点指向下一个结点*/if (pa-data=pb-data)pc-next=pa;pc=pa;pa=pa-next ;ptr=pb;pb=pb-next;free(ptr);/*将将pa所指的结点合并，所指的结点合并，pb所指结点删除所指结点删除*/if (pa!=NULL)pc-next=pa;else pc-next=pb;/*将剩余的结点链上将剩余的结点链上*/free(Lb);return(Lc);算法分析算
47、法分析若若La，Lb两个链表的长度分别是两个链表的长度分别是m，n，则链表合，则链表合并的时间复杂度为并的时间复杂度为O(m+n)。2.3.3 循环链表循环链表循环链表循环链表(Circular Linked List)：是一种头尾相是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个头结点，整个链表的指针域链接成一个环链表的指针域链接成一个环。从循环链表的任意一个结点出发都可以找到链表中从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。的其它结点，使得表处理更加方便灵活。图图2-6是带头结点的单
48、循环链表的示意图。是带头结点的单循环链表的示意图。空表空表图图2-6 单循环链表示意图单循环链表示意图非空表非空表a1a2anheadhead循环链表的操作循环链表的操作对于单循环链表，除链表的合并外，其它的操作和对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：法基础上作以下简单修改：判断是否是空链表：判断是否是空链表：head-next=head;判断是否是表尾结点：判断是否是表尾结点：p-next=head;双向链表双向链表(Double Linked List):指的是构成
49、链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的的每个结点中设立两个指针域：一个指向其直接前趋的指针域指针域prior，一个指向其直接后继的指针域，一个指向其直接后继的指针域next。这样。这样形成的链表中有两个方向不同的链，故称为形成的链表中有两个方向不同的链，故称为双向链表双向链表。和单链表类似，双向链表一般增加头指针也能使双和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。链表上的某些运算变得方便。将头结点和尾结点链接起来也能构成循环链表，并将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。称之为双向循环链表。双向链表是为了克服单链表的
50、单向性的缺陷而引入双向链表是为了克服单链表的单向性的缺陷而引入的。的。2.4 双向链表typedef struct DulnodeElemType data;struct Dulnode*prior,*next;DulNode;data nextprior图图2-7 双向链表结点形式双向链表结点形式非空双向链表非空双向链表heada2a1an空双向链表空双向链表head图图2-8 带头结点的双向链表形式带头结点的双向链表形式1 双向链表的结点及其类型定义双向链表的结点及其类型定义双向链表的结点的类型定义如下。其结点形式如图双向链表的结点的类型定义如下。其结点形式如图2-7所示所示，带头结点的双