《基本数据结构及其运算3线性链表.ppt》由会员分享，可在线阅读，更多相关《基本数据结构及其运算3线性链表.ppt（97页珍藏版）》请在金锄头文库上搜索。
1、第第二二章章 基基本本数数据据公安海警学院公安海警学院2024/8/11主讲：胡云琴主讲：胡云琴结结构构及及运运算算 第第 2 章章 基本数据结构及运算基本数据结构及运算2.1 2.1 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念2.22.2线性表及其顺序存储结构线性表及其顺序存储结构线性表及其顺序存储结构线性表及其顺序存储结构2.32.3线性链表线性链表线性链表线性链表2.42.4线性表的索引存储结构线性表的索引存储结构线性表的索引存储结构线性表的索引存储结构 2.52.5 数组数组数组数组2.6 2.6 树与二叉树树与二叉树树与二叉树树与二叉树2.7 2.7 图
2、图图图复复 习习提问提问1 1：线性表顺序存储结构具有哪些：线性表顺序存储结构具有哪些优点？优点？1 1）线性表顺序存储结构具有简单、运算）线性表顺序存储结构具有简单、运算方便等优点方便等优点, ,随机存取（时间复杂度为随机存取（时间复杂度为O(1)O(1)）；）；2 2）无需为表示表中元素之间的逻辑关系）无需为表示表中元素之间的逻辑关系而增加额外的存储空间；而增加额外的存储空间；3 3）适合小规模、长度固定的线性表）适合小规模、长度固定的线性表2.线性表顺序存储结构具有哪些缺点？线性表顺序存储结构具有哪些缺点？在插入、删除时要移动大量的节点，效率低在插入、删除时要移动大量的节点，效率低表的大
3、小固定，容量难扩充，易出现上溢表的大小固定，容量难扩充，易出现上溢原因：原因：顺序存储的存储结构与逻辑结构是一致的。顺序存储的存储结构与逻辑结构是一致的。解决方法：解决方法：突破突破离散存放离散存放用指针来表示元素之间的关系。用指针来表示元素之间的关系。 引入线性链表引入线性链表链接存储的线性表链接存储的线性表用链表实现线性表（非连续存储）用链表实现线性表（非连续存储）线性表元素：线性表元素：a1、a2、a3、a4.链表链点链表链点线性关系：线性关系：a1a2a3a4指针域，指针关系指针域，指针关系链表概述：链表概述：链表是一种常见的重要的数据结构。链表是一种常见的重要的数据结构。它是动态地进
4、行存储分配的一种结构。它是动态地进行存储分配的一种结构。“头指针头指针”, ,以变量以变量headhead表示表示, ,是线性表中第一个数是线性表中第一个数据元素的存储地址；据元素的存储地址；每个结点都应包括两部分每个结点都应包括两部分: :用户需要用的实际数据和用户需要用的实际数据和下一结点的地址下一结点的地址( (指针域指针域) )；最后一个结点最后一个结点, ,该结点的指针域不再指向其他结点该结点的指针域不再指向其他结点, ,它称为它称为 表尾表尾,它的指针域放一个它的指针域放一个NULL(NULL(表示表示 空地空地址址),),链表到此结束。链表到此结束。 head 1249 1356
5、 1475 1021 1356 1475 1021 NULL1249 A B C D2.3.1 线性链表的基本概念线性链表的基本概念线性链表线性链表2.32.3.2 线性链表的基本运算线性链表的基本运算2.3.3 带链的栈与队列带链的栈与队列2.3.4 循环链表循环链表2.3.5 多项式的表示与运算多项式的表示与运算特点：特点：(1)(1)定义：采用链式存储结构的线性表称为链定义：采用链式存储结构的线性表称为链表表 ，其采用一组任意的存储单元来存，其采用一组任意的存储单元来存放线性表的数据元素（可零散的分布放线性表的数据元素（可零散的分布于内存单元的任何位置上）。于内存单元的任何位置上）。2.
6、3.1 线性链表的基本概念线性链表的基本概念结点之间可以连续，可以不连续存储结点之间可以连续，可以不连续存储结点的逻辑顺序与物理顺序可以不一致结点的逻辑顺序与物理顺序可以不一致表可扩充表可扩充(2) 结点结点(Node)组成组成 通过指针域，不论结点的物理次序通过指针域，不论结点的物理次序如何，都可将其按逻辑顺序依次链接在如何，都可将其按逻辑顺序依次链接在一起构成线性表。一起构成线性表。数据域数据域存储数据元素本身存储数据元素本身数据域数据域指针域指针域指针域指针域存储下一元素的存储位置存储下一元素的存储位置链链顺序表顺序表存储地址存储地址 存储状态存储状态 0031 赵赵 0033 钱钱 0
7、035 孙孙 0037 李李 0039 周周 0041 吴吴 0043 郑郑 0045 王王 链表链表 存储地址存储地址 存储状态存储状态 0001 李李 0007 钱钱 0013 孙孙 0019 王王 0025 吴吴 0031 赵赵 0037 郑郑 0043 周周 0043 0013 0001 NULL 0037 0007 0019 0025头指针头指针 H 数据域数据域 0031 指针域指针域 结点结点 指指针针链链表表 线性表顺序存储与链表存储比较线性表顺序存储与链表存储比较 H 赵赵钱钱孙孙李李周周吴吴郑郑王王 线线性性表表具具有有两两种种存存储储方方式式，即即顺顺序序方方式式和和链链
8、接接方方式式。现现有有一一个个具具有有五五个个元元素素的的线线性性表表L=23L=23，1717，4747，0505，3131，若若它它以以链链接接方方式式存存储储在在下下列列100100119119号号地地址址空空间间中中，每每个个结结点点由由数数据据（占占2 2个个字字节节）和和指指针（占针（占2 2个字节）组成，如下图所示。个字节）组成，如下图所示。 其其中中指指针针X X，Y Y，Z Z的的值值分分别别为为多多少少？该该线线性性表表的的首首结点起始地址为多少？末结点的起始地址为多少？结点起始地址为多少？末结点的起始地址为多少？Z Z4747Y Y3131V V2323X X1717U
9、U0505100100100100119119119119104104104104108108108108116116116116112112112112答：答：X= Y= Z= X= Y= Z= 首址首址= = 末址末址= = 。例例1：116116116116NULL(0)NULL(0)NULL(0)NULL(0)100100100100112112112112108108108108（3）链表分类）链表分类单链表：只设置一个指向后继结点地址的单链表：只设置一个指向后继结点地址的指针域。指针域。循环链表：将其首尾相接构成一个环状循环链表：将其首尾相接构成一个环状结构。结构。双向链表：有两个
10、指针域，分别指向本双向链表：有两个指针域，分别指向本结点的前驱结点和后继结点的链表。结点的前驱结点和后继结点的链表。a1(1(1）定义：）定义：所有结点的指针域中只包含一个所有结点的指针域中只包含一个指针指针( (存储直接后继结点的存储位置存储直接后继结点的存储位置) )的链表。的链表。a2an空指针空指针头指针头指针头指针头指针头结点头结点带头结点的单链表带头结点的单链表单链表常用头指针来命名，如单链表常用头指针来命名，如 La, Head.La, Head.2.3.2 线性链表线性链表(单链表单链表)的基本运算的基本运算(2(2）头结点）头结点 在单链表的第一个结点之前人为地附设的一个结点
11、。在单链表的第一个结点之前人为地附设的一个结点。 数据域数据域 L a1a2an L 头指针头指针 头结点头结点头指针头指针头指针头指针存放头结点的地址，指向链表中第一个结点存放头结点的地址，指向链表中第一个结点（或为头结点或第一个元素）的指针。（或为头结点或第一个元素）的指针。 头结点头结点 不存放任何数据不存放任何数据 存放附加信息存放附加信息( (链表的结点个数等链表的结点个数等) )指针域指针域 存放第一个结点的地址存放第一个结点的地址 （若线性表为空表，则（若线性表为空表，则“空空”，用，用 表示。）表示。） 可以看到，空表和非空表不统一可以看到，空表和非空表不统一heada1a2a
12、n非空表非空表head=NULL空表空表带头结点的非空表带头结点的非空表heada1a2an带头结点的空表带头结点的空表head设置头结点的好处：设置头结点的好处：起始结点位置存放在头结点起始结点位置存放在头结点指针域中，故在链表第一个位置上操作与表中其他指针域中，故在链表第一个位置上操作与表中其他位置上操作一致，无须特殊处理。位置上操作一致，无须特殊处理。头指针头指针HeadHead始终是指向头结点的非空指针，统一始终是指向头结点的非空指针，统一了空表与非空表的操作，简化链表操作的实现。了空表与非空表的操作，简化链表操作的实现。请写出该线性链表的逻辑顺序和链表结构图？请写出该线性链表的逻辑顺
13、序和链表结构图？存存储地址地址数据域数据域指指针域域1D437B1313C119HNULL25F3731A737G1943E25头指针头指针H31AHBC头指针头指针头指针头指针例例2 2：一个线性表的逻辑结构为：（：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,ZHAO,QIAN,SUN,LI, ZHOU,WU,ZHENG,WANGLI, ZHOU,WU,ZHENG,WANG），其存储结构用单链表表），其存储结构用单链表表示如下，请问其头指针的值是多少？示如下，请问其头指针的值是多少？存储地址存储地址数据域数据域指针域指针域1 1LILI43437 7QIANQIAN13131313
14、SUNSUN1 11919WANGWANGNULLNULL2525WUWU37373131ZHAOZHAO7 73737ZHENGZHENG19194343ZHOUZHOU25257 7ZHAOZHAOH H31头指针头指针头指针头指针H H H H的值是的值是的值是的值是31313131在在线线性性链链表表中中包包含含指指定定元元素素的的结结点点之之前前插插入入一一个个新新元素。元素。在线性链表中删除包含指定元素的结点。在线性链表中删除包含指定元素的结点。将两个线性链表按要求合并成一个线性链表。将两个线性链表按要求合并成一个线性链表。将一个线性链表按要求进行分解。将一个线性链表按要求进行分解
15、。逆转线性链表。逆转线性链表。复制线性链表。复制线性链表。线性链表的排序。线性链表的排序。线性链表的查找。线性链表的查找。2.3.2 线性链表的基本运算线性链表的基本运算 1、线性链表的插入、线性链表的插入2、线性链表的删除、线性链表的删除3、线性链表类、线性链表类2.3.2 线性链表的基本运算线性链表的基本运算 1、线性链表的插入、线性链表的插入线性链表的插入是指在链式存储结构下的线性线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。表中插入一个新元素。为了插入一个新元素，首先要给该元素分配一个为了插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值，新结点可从可新
16、结点，以便用于存储该元素的值，新结点可从可利用栈中取得，然后将存放新元素值的结点链接到利用栈中取得，然后将存放新元素值的结点链接到线性链表中指定的位置。线性链表中指定的位置。 1、线性链表的插入、线性链表的插入可利用栈与线性链表可利用栈与线性链表 1、线性链表的插入、线性链表的插入(1)(1)从可利用栈取得一个结点，设该结点号为从可利用栈取得一个结点，设该结点号为p p。 并置结点并置结点p p的数据域为插入的元素值的数据域为插入的元素值b b，即，即V(p)V(p)b b。(2)(2)在线性链表中寻找包含元素在线性链表中寻找包含元素x x的前一个结点的前一个结点q q。 1、线性链表的插入、
17、线性链表的插入(3)(3)将结点将结点p p插入到结点插入到结点q q之后：之后： 使结点使结点p p指向包含元素指向包含元素x x的结点，即的结点，即 NEXT(p)NEXT(p)NEXT(q)NEXT(q) 使结点使结点q q的指针域内容改为指向结点的指针域内容改为指向结点p p，即，即 NEXT(q)NEXT(q)p p#include stdlib.h#include stdlib.hstruct node /*struct node /*定义结点类型定义结点类型* */ / ET d ET d； struct node *nextstruct node *next； ；inslst(
18、headinslst(head，x x，b)b)ET xET x，b b；struct node *headstruct node *head； struct node *p struct node *p， * *q q； p p(struct node *)malloc(sizeof(struct node)(struct node *)malloc(sizeof(struct node)； p pddb b； /*/*置结点的数据域置结点的数据域* */ / if (*head if (*headNULL) /*NULL) /*链表为空链表为空* */ / *head *headp p；p
19、 pnextnextNULLNULL；returnreturn； if (*head if (*headd)d)x) /*x) /*在第一个结点前插入在第一个结点前插入* */ / p pnextnext* *headhead；* *headheadp p；returnreturn； q qlookst(*headlookst(*head，x)x)；/*/*寻找包含元素寻找包含元素x x的前一个结点的前一个结点q*/q*/ p pnextnextq qnextnext；q qnextnextp p；/*/*结点结点p p插到结点插到结点q q之后之后* */ / return return；
20、2、线性链表的删除、线性链表的删除在链式存储结构下的线性表中在链式存储结构下的线性表中 删除包含指定删除包含指定元素的结点。元素的结点。为了在线性链表中删除包含指定元素的结点，首为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。点放回到可利用栈。 2、线性链表的删除、线性链表的删除其删除过程如下：其删除过程如下：(1)在线性链表中寻找包含元素在线性链表中寻找包含元素x的前一个结点，设的前一个结点，设该结点序号为该结点序号为q，则包含元素，则包含元素x的结点序号的结点序号p=NEXT(q)。 2、线
21、性链表的删除、线性链表的删除其删除过程如下：其删除过程如下：(2)将结点将结点q后的结点后的结点p从线性链表中删除，即让结从线性链表中删除，即让结点点q的指针指向包含元素的指针指向包含元素x的结点的结点p的指针指向的结的指针指向的结点，即点，即NEXT(q) = NEXT(p) 。 2、线性链表的删除、线性链表的删除其删除过程如下：其删除过程如下：(3)将包含元素将包含元素x的结点的结点p送回可利用栈送回可利用栈 。#include stdlib.h#include stdlib.hstruct node /*struct node /*定义结点类型定义结点类型* */ / ET d ET d
22、； struct node *nextstruct node *next； ；delst(headdelst(head，x)x)ET xET x；struct node *headstruct node *head； struct node *p struct node *p， * *q q； if (*headif (*headNULL) /*NULL) /*链表为空链表为空* */ / printf(This is a empty list!n) printf(This is a empty list!n)；returnreturn； if (*head if (*headd)d)x) /
23、*x) /*删除第一个结点删除第一个结点* */ / p p* *headheadnextnext；free(*head) free(*head) ；* *headheadp p；returnreturn； q qlookst(*headlookst(*head，x) x) ；/*/*寻找包含元素寻找包含元素x x的前一个结点的前一个结点q*/q*/ if (q if (qnextnextNULL) /*NULL) /*链表中没有包含元素链表中没有包含元素x x的结点的结点* */ / printf(No this node in the list!n) printf(No this node
24、 in the list!n)；returnreturn； p pq qnext next ；q qnextnextp pnextnext； /*/*删除结点删除结点p*/p*/ free(p) free(p) ； /*/*释放结点释放结点p*/ returnp*/ return； 3、线性链表类、线性链表类/linked_List.h#include using namespace std;/定义结点类型定义结点类型template / T为虚拟类型为虚拟类型 struct nodeT d;node *next; 3、线性链表类、线性链表类/定义单链表类定义单链表类template /模板声
25、明，数据元素虚拟类型为模板声明，数据元素虚拟类型为Tclass linked_Listprivate: / 数据成员数据成员node *head; /链表头指针链表头指针public: /成员函数成员函数linked_List(); /构造函数，建立空链表构造函数，建立空链表 int flag_linked_List(); void prt_linked_List(); /扫描输出链表中的元素扫描输出链表中的元素void ins_linked_List(T);/在包含元素在包含元素x的结点前插入新元素的结点前插入新元素T del_linked_List(); /删除包含元素删除包含元素x的结点
26、的结点; 3、线性链表类、线性链表类/建立空链表建立空链表templatelinked_List:linked_List()head=NULL;return; /检测单链表检测单链表templateint linked_List:flag_linked_List()if(head=NULL) return(0);return(1); 3、线性链表类、线性链表类/从头指针开始扫描输出链表中的元素从头指针开始扫描输出链表中的元素templatevoid linked_List:prt_linked_List() node *p; p=head; if(p=NULL) cout空链表空链表!endl
27、; return; do coutdnext; while(p!=NULL);return; 3、线性链表类、线性链表类/在包含元素在包含元素x的结点前插入新元素的结点前插入新元素btemplate void linked_List:ins_linked_List(T x , T b) node *p,*q; p=new node; / 申请一个新结点申请一个新结点 p-d=b; /置新结点的数据域置新结点的数据域 if (head=NULL) head=p; p-next=NULL;return; q=head; while (q-next!=NULL)&(q-next)-d!=x) q=q
28、-next; /寻找包含元素寻找包含元素x的前一个结点的前一个结点q p-next =q-next; q=q-next=p; return; 3、线性链表类、线性链表类/删除链表头元素删除链表头元素templateT linked_List:del_linked_List() T y; node *p,*q; if(head=NULL) cout“空链表空链表!”d)=x) /删除第一个结点删除第一个结点p=head-next; delete head;head=p; return(-1);q=head; 3、线性链表类、线性链表类while (q-next!=NULL)&(q-next)-d
29、)!=x) q=q-next; /寻找包含元素寻找包含元素x的前一个结的前一个结点点If(q-next=NULL) return(0); /链表中无删除链表中无删除的元素的元素p=q-next; q-next=p-next;delete p;return (1);例例2.10 建立一个空线性链表，依次做如下操作：建立一个空线性链表，依次做如下操作：（1）第一次扫描输出链表）第一次扫描输出链表s中的元素；中的元素；（2）依次做如下插入操作：）依次做如下插入操作：在包含元素在包含元素10的结点前插入新元素的结点前插入新元素10；在包含元素在包含元素10的结点前插入新元素的结点前插入新元素20；在包
30、含元素在包含元素10的结点前插入新元素的结点前插入新元素30； 在包含元素在包含元素,40的结点前插入新元素的结点前插入新元素40；（3）第）第2次扫描输出链表次扫描输出链表s中的元素；中的元素；（4）在线性链表中依次删除元素）在线性链表中依次删除元素30与与50；（5）第）第3次扫描输出链表次扫描输出链表s中的元素。中的元素。主函数如下：主函数如下：/ch2_15.cpp#include “linked_List.h”int main() linked_List s;cout“第一次从头指针开始扫描输出单链表第一次从头指针开始扫描输出单链表s中的元素中的元素:”endl;s.prt_link
31、ed_List();s.ins_linked_List(10，10); /在包含元素在包含元素10的结点前插入新元素的结点前插入新元素10s.ins_linked_List(10，20);s.ins_linked_List,10，30);s.ins_linked_List(40，40);主函数如下：主函数如下：cout第第2次扫描输出链表次扫描输出链表s中的元素中的元素:endl;s.prt_linked_List();if(s.flag_linked_List()cout删除元素删除元素:s.del_linked_List()endl;if(s.flag_linked_List()cout删
32、除链表头元素删除链表头元素:s.del_linked_List()endl;cout第第3次从头指针开始扫描输出单链表次从头指针开始扫描输出单链表s中的元素中的元素:endl;s.prt_linked_List();return 0;程序运行结果：程序运行结果：第一次从头指针开始扫描输出单链表第一次从头指针开始扫描输出单链表s中的元素中的元素:空链表空链表!第二次从头指针开始扫描输出单链表第二次从头指针开始扫描输出单链表s中的元素中的元素:20301040删除元素删除元素:30链表中无元素链表中无元素:50第三次从头指针开始扫描输出单链表第三次从头指针开始扫描输出单链表s中的元素中的元素:20
33、10402.3.3 带链的栈与队列带链的栈与队列 1、带链的栈、带链的栈 2、带链的队列、带链的队列 1、带链的栈、带链的栈带链的栈可用来收集计算机存储空间中所有空闲的带链的栈可用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。存储结点，这种带链的栈称为可利用栈。带链的栈基本操作有：带链的栈基本操作有：（1）栈的初始化：建立一个空栈的存储空间。）栈的初始化：建立一个空栈的存储空间。（2）入栈：在栈顶位置插入一个新元素。）入栈：在栈顶位置插入一个新元素。（3）退栈：取出栈顶元素并赋给一个指定的变量。）退栈：取出栈顶元素并赋给一个指定的变量。（4）读栈顶元素：将栈顶元素赋给一个
34、指定的变量）读栈顶元素：将栈顶元素赋给一个指定的变量带链栈类带链栈类/linked_Stack.h#include using namespace std;template /T为虚拟类型为虚拟类型struct nodeT d;node *next;/定义带链的栈类定义带链的栈类templateclass linked_Stack private: node *top; public: linked_Stack(); void prt_linked_Stack(); int flag_linked_Stack(); void ins_linked_Stack(T); T del_linked_
35、Stack(); T read_linked_Stack();/带链栈初始化带链栈初始化templatelinked_Stack:linked_Stack()top=NULL;return;/顺序输出栈中元素顺序输出栈中元素templatevoid linked_Stack:prt_linked_Stack() node*p; p=top; if(p=NULL)cout空栈空栈!endl; return; do coutdnext; while (p!=NULL); return;/检测带链栈的状态检测带链栈的状态templateint linked_Stack:flag_linked_Sta
36、ck()if(top=0) return(0);return(1);/入栈入栈templatevoid linked_Stack:ins_linked_Stack(T x)node *p;p=new node;p-d=x;p-next=top;top=p;return;/退栈退栈templateT linked_Stack:del_linked_Stack() T y;node *q;if(top=NULL)cout空栈空栈!d;top=q-next;delete q;return(y);/读栈顶元素读栈顶元素templateT linked_Stack:read_linked_Stack()
37、if (top=NULL)cout空栈空栈!d); 例例2.11 首先建立一个空的带链栈，然后依次首先建立一个空的带链栈，然后依次将元素将元素50,60,70,80,90,100入栈，输出栈中入栈，输出栈中的元素，最后读栈顶元素，并连续的元素，最后读栈顶元素，并连续3次做退次做退栈运算，再输出栈中的元素。栈运算，再输出栈中的元素。主函数如下：主函数如下：/ch2_11.cpp#include linked_Stack.hint main()linked_Stack s;s.ins_linked_Stack(50);s.ins_linked_Stack(60);s.ins_linked_Stac
38、k(70);s.ins_linked_Stack(80);s.ins_linked_Stack(90);s.ins_linked_Stack(100); cout“输出栈中元素输出栈中元素:endl;s.prt_linked_Stack();if(s.flag_linked_Stack()cout栈顶元素栈顶元素:s.read_linked_Stack()endl;if(s.flag_linked_Stack()cout退栈元素退栈元素:s.del_linked_Stack()endl;if(s.flag_linked_Stack()cout退栈元素退栈元素:s.del_linked_Stac
39、k()endl;if(s.flag_linked_Stack()cout退栈元素退栈元素:s.del_linked_Stack()endl;cout再次输出栈中元素再次输出栈中元素:endl;s.prt_linked_Stack();return 0; 运行结果如下：运行结果如下：输出栈中元素输出栈中元素:1009080706050栈顶元素栈顶元素:100退栈元素退栈元素:100退栈元素退栈元素:90退栈元素退栈元素:80再次输出栈中元素再次输出栈中元素:706050 2、带链的队列、带链的队列带链的队列基本操作有：带链的队列基本操作有：（1）队列的初始化：建立一个空队列的存储空间。）队列的初
40、始化：建立一个空队列的存储空间。（2）入队：在队尾插入一个新元素。）入队：在队尾插入一个新元素。（3）退栈：在队列排头位置退出一个元素并赋给指）退栈：在队列排头位置退出一个元素并赋给指定的变量。定的变量。带链队列类带链队列类/文件名文件名linked_Queue.h#includeusing namespace std;template /T为虚拟类型为虚拟类型struct node T d; node *next;/定义带链队列的类定义带链队列的类template /模板声明，数据元素虚拟类型为模板声明，数据元素虚拟类型为Tclass linked_Queue private: /数据成员数
41、据成员 node *front; /带链队列的排头指针带链队列的排头指针 node *rear; /带链队列的队尾指针带链队列的队尾指针 public: /成员函数成员函数 linked_Queue(); /构造函数，建立空队列，即队列初始化构造函数，建立空队列，即队列初始化 void prt_linked_Queue(); /顺序输出带链队列中的元素顺序输出带链队列中的元素 int flag_linked_Queue(); /检测带链队列中的元素检测带链队列中的元素 void ins_linked_Queue(T); /入队入队 T del_linked_Queue(); /退队退队;/带链
42、队列初始化带链队列初始化templatelinked_Queue:linked_Queue() front=NULL; /排头指针为空排头指针为空 rear=NULL; /队尾指针为空队尾指针为空 return;/顺序输出队列中的元素顺序输出队列中的元素templatevoid linked_Queue:prt_linked_Queue() node *p; p=front; if(p=NULL) cout空队列空队列!endl; return; do coutdnext; while(p!=NULL); return; /检测带链队列的状态检测带链队列的状态templateint linke
43、d_Queue:flag_linked_Queue() if(front=NULL) return(0); return(1);/入队入队templatevoid linked_Queue:ins_linked_Queue(T x) node*p;p=new node; /申请一个新结点申请一个新结点p-d=x; /置新结点数据域值置新结点数据域值p-next=NULL; /置新结点指针域值为空置新结点指针域值为空if(rear=NULL) /原队列为空原队列为空front=p;elserear-next=p; /原队尾结点的指针指向新结点原队尾结点的指针指向新结点 rear=p; /队尾指针
44、指向新结点队尾指针指向新结点 return;/退队退队templateT linked_Queue:del_linked_Queue() T y;node *q;if(front=NULL) cout空队空队!d; /排头元素赋给变量排头元素赋给变量q=front; front=q-next; /排头指针指向下一个结点排头指针指向下一个结点delete q; /释放结点空间释放结点空间if(front=NULL) rear=NULL; /队列已空队列已空return(y); /返回退队的元素返回退队的元素例例2.12 首先建立一个空的带链队列，然后依首先建立一个空的带链队列，然后依次将元素次将
45、元素50,60,70,80,90,100入队，输出队入队，输出队中的元素，最后连续中的元素，最后连续3次做退队运算，再输次做退队运算，再输出队中的元素。出队中的元素。主函数如下：主函数如下：/ch2_12.cpp#includelinked_Queue.hint main() int a; linked_Queueq; cout第第1次输出带链队列中的元素次输出带链队列中的元素:endl; q.prt_linked_Queue(); char OperCode; int biaozhi=1; printf(Insert-In); printf(Delete-Dn); printf(Over-O
46、n); printf(Please input your intruction:); OperCode=getchar(); printf(n);while(OperCode!=O) switch(OperCode) caseI: printf(输入插入带链队列中的元素是输入插入带链队列中的元素是:); scanf(%d,&a); q.ins_linked_Queue(a); cout再次输出带链队列中的元素再次输出带链队列中的元素:endl; q.prt_linked_Queue(); break; caseD: if(q.flag_linked_Queue() cout输出退队元素输出退队
47、元素:q.del_linked_Queue()endl; cout再次输出带链队列中的元素再次输出带链队列中的元素:endl; q.prt_linked_Queue(); break; default:break;printf(Please input your intruction:);OperCode=getchar();printf(n); return 0;运行结果如下：运行结果如下：1)1)定义：是一种头尾相接的链表（即表中最后一个定义：是一种头尾相接的链表（即表中最后一个 结点的指针域指向头结点，整个链表形成一个环）。结点的指针域指向头结点，整个链表形成一个环）。2.3.4 循环链
48、表循环链表2)2)特点：特点：2.3.4 循环链表循环链表(1)(1)在循环链表中增加了一个表头结点，其数据域在循环链表中增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表第一为任意或根据需要来设置，指针域指向线性表第一个元素的结点。循环链表的头指针指向表头结点。个元素的结点。循环链表的头指针指向表头结点。(2)(2)循环链表中最后一个结点的指针域不空，而是循环链表中最后一个结点的指针域不空，而是指向表头结点。即在循环链表中，所有结点的指针指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。构成了一个环状链。3)3)优点：优点：2.3.4 循环链表循环链表(1)(1
49、)在在循循环环链链表表中中，只只要要指指出出表表中中任任何何一一个个结结点点的的位位置，就可以从它出发访问到表中其他所有的结点。置，就可以从它出发访问到表中其他所有的结点。(2)(2)由由于于在在循循环环链链表表中中设设置置了了一一个个表表头头结结点点，因因此此在在任任何何情情况况下下，循循环环链链表表中中至至少少有有一一个个结结点点存存在在，从从而使空表与非空表的运算统一。而使空表与非空表的运算统一。循环链表类循环链表类/linked_Clist.h#include using namespace std;/定义结点类型定义结点类型template /数据元素虚拟类型为数据元素虚拟类型为Ts
50、truct node T d;node *next;/定义循环链表类定义循环链表类template /模板声明模板声明,数据元素虚拟类型为数据元素虚拟类型为Tclass linked_CList private:/数据成员数据成员node *head;/循环链表头指针循环链表头指针public:/成员函数成员函数linked_CList();/构造函数构造函数,建立空的循环链表建立空的循环链表void prt_linked_CList();/扫描输出循环链表中的元素扫描输出循环链表中的元素void ins_linked_CList(T, T);/在包含元素在包含元素x的结点前的结点前插入新元素
51、插入新元素bint del_linked_CList(T);/删除包含元素删除包含元素x的结点的结点;/建立空的循环链表建立空的循环链表template linked_CList linked_CList() node *p;p=new node;/申请一个表头结点申请一个表头结点p-d=0; p-next=p; head=p; return; /扫描输出循环链表中的元素扫描输出循环链表中的元素template void linked_CList prt_linked_CList() node *p;p=head-next;if (p=head) cout 空的循环链表！空的循环链表！ end
52、l; return; do cout d next; while (p!=head);return;/在包含元素在包含元素x的结点前插入新元素的结点前插入新元素btemplate void linked_CList ins_linked_CList(T x, T b) node *p, *q;p=new node;/申请一个新结点申请一个新结点p-d=b;/置新结点的数据域置新结点的数据域q=head;while (q-next!=head)&(q-next)-d)!=x)q=q-next;/寻找包含元素寻找包含元素x的前一个结点的前一个结点qp-next=q-next;q-next=p;/新
53、结点新结点p插入到结点插入到结点q之后之后return;/删除包含元素删除包含元素x的结点元素的结点元素template int linked_CList del_linked_CList(T x) node *p, *q;q=head;while (q-next!=head)&(q-next)-d)!=x)q=q-next;/寻找包含元素寻找包含元素x的前一个结点的前一个结点qif (q-next=head) return(0); /循环链表中无删除的循环链表中无删除的元素元素p=q-next; q-next=p-next;/删除删除q的下一个结点的下一个结点pdelete p;/释放结点释
54、放结点p的存储空间的存储空间return(1); 例例2.13 建立一个空循环链表，依次做如下操作：建立一个空循环链表，依次做如下操作：（1）第一次扫描输出循环链表）第一次扫描输出循环链表s中的元素；中的元素；（2）依次做如下插入操作：）依次做如下插入操作：在包含元素在包含元素10的结点前插入新元素的结点前插入新元素10；在包含元素在包含元素10的结点前插入新元素的结点前插入新元素20；在包含元素在包含元素10的结点前插入新元素的结点前插入新元素30； 在包含元素在包含元素,40的结点前插入新元素的结点前插入新元素40；（3）第）第2次扫描输出循环链表次扫描输出循环链表s中的元素；中的元素；（
55、4）在线性链表中依次删除元素）在线性链表中依次删除元素30与与50；（5）第）第3次扫描输出循环链表次扫描输出循环链表s中的元素。中的元素。主函数如下：主函数如下：/ch2_13.cpp#include linked_Clist.hint main() linked_CLists;cout 第第1次扫描输出循环链表次扫描输出循环链表s中的元素中的元素: endl;s.prt_linked_CList(); s.ins_linked_CList(10,10); /在包含元素在包含元素10的结点前插入新元素的结点前插入新元素10s.ins_linked_CList(10,20); /在包含元素在包
56、含元素10的结点前插入新元素的结点前插入新元素20s.ins_linked_CList(10,30); /在包含元素在包含元素10的结点前插入新元素的结点前插入新元素30s.ins_linked_CList(40,40); /在包含元素在包含元素40的结点前插入新元素的结点前插入新元素40cout 第第2次扫描输出循环链表次扫描输出循环链表s中的元素中的元素: endl;s.prt_linked_CList();if (s.del_linked_CList(30) cout 删除元素删除元素:30 endl;elsecout 循环链表中无元素循环链表中无元素:30 endl;if (s.del
57、_linked_CList(50)cout 删除元素删除元素:50 endl;elsecout 循环链表中无元素循环链表中无元素:50 endl;cout 第第3次扫描输出循环链表次扫描输出循环链表s中的元素中的元素: endl;s.prt_linked_CList();return （0）; 运行结果如下：运行结果如下：第第1次扫描输出循环链表次扫描输出循环链表s中的元素中的元素:空链表空链表!第第2次扫描输出循环链表次扫描输出循环链表s中的元素中的元素:20301040删除元素删除元素: 30循环链表中无元素循环链表中无元素: 50第第3次扫描输出循环链表次扫描输出循环链表s中的元素中的元
58、素:201040 n nn 阶多项式阶多项式 Pn(x) 有有 n+1 项项。u 系数系数 c0, c1, c2, , cnu 指数指数 0, 1, 2, , n。按升幂排列。按升幂排列2.3.5 多项式的表示与运算多项式的表示与运算n n在多项式的链表表示中每个结点三个数据在多项式的链表表示中每个结点三个数据成员：成员：n n优点是：优点是：uu 多项式的项数可以动态地增长，不存多项式的项数可以动态地增长，不存在存储溢出问题。在存储溢出问题。uu 插入、删除方便，不移动元素。插入、删除方便，不移动元素。多项式的链表表示多项式的链表表示coef exp link Data Term多项式多项式
59、(polynomial)类的链表定义类的链表定义struct Term /多项式结点定义多项式结点定义 float coef; /系数系数 int exp; /指数指数 Term ( float c, int e ) coef = c; exp = e; ; class Polynomial /多项式类的定义多项式类的定义 List poly; /构造函数构造函数 friend Polynomial operator + ( Polynomial &, Polynomial &); /加法加法;多项式链表的相加多项式链表的相加AH = 1 - 3x6 + 7x12BH = - x4 + 3x6
60、 - 9x10 + 8x14AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 14两个多项式的相加算法两个多项式的相加算法n n扫描两个多项式，若都未检测完：扫描两个多项式，若都未检测完：uu 若当前被检测项若当前被检测项指数相等指数相等，系数相加。，系数相加。若未变成若未变成 0，则将结果加到结果多项，则将结果加到结果多项式。式。uu 若当前被检测项若当前被检测项指数不等指数不等，将指数小，将指数小者加到结果多项式。者加到结果多项式。n n若一个多项式已检测完，将另一个多项若一个多项式已检测完，将另一
61、个多项式剩余部分复制到结果多项式。式剩余部分复制到结果多项式。AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14pappc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14papbpc-9 10AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14papbpc-9 10AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 1
62、27 128 148 14pappc-9 10pb0AH.first CH.first 1 01 0-1 4-1 40 6-9 107 127 128 148 14pappc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14papc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14papc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14pa = pc-9 10pb AH.first C
63、H.first 1 01 0-1 4-1 4-9 107 127 128 148 14pa = pc-9 10pb Polynomial operator + ( Polynomial& ah, Polynomial& bh ) /两个带头结点的按升幂排列的多项式相加，两个带头结点的按升幂排列的多项式相加，/返回结果多项式链表的表头指针，结果不返回结果多项式链表的表头指针，结果不/另外占用存储另外占用存储, 覆盖覆盖ah和和bh链表链表 ListNode *pa, *pb, *pc, *p; Term a, b; pc = ah.poly.Firster ( ); /结果存放指针结果存放指针
64、p = bh.poly.Firster ( ); pa = ah.poly.First( ); /多项式检测指针多项式检测指针 pb = bh.poly.First( ); /多项式检测指针多项式检测指针 delete p; /删去删去bh的表头结点的表头结点 while ( pa != NULL & pb != NULL ) a = pa-data; b = pb-data; switch ( compare ( a.exp, b.exp ) ) case = :/pa-exp = pb-exp a.coef = a.coef + b.coef;/系数相加系数相加 p = pb; pb =
65、pb-link; delete p;/删去原删去原pb所指结点所指结点 if ( abs(a.coef ) -link; delete p; /相加为零相加为零, 该项不要该项不要 else /相加不为零相加不为零, 加入加入ch链链 pa-data = a; pc-link = pa; pc = pa; pa = pa-link; break; case : /pa-exp pb-exp pc-link = pb; pc = pb; pb = pb-link; break; case -exp -exp pc-link = pa; pc = pa; pa = pa-link; if ( pa != NULL ) pc-link = pa; else pc-link = pb; /剩余部分链入ch链 return ah;
