1、1数据结构数据结构(上上)2第第1章章 绪论绪论第第2章章 线性表线性表第第3章栈和队列章栈和队列第第4章章 串串第第5章数组与广义表章数组与广义表3第一章第一章 绪论绪论4学习重点：数据结构的基本概念；数据的逻辑结构、存储结构以及两者之 间的关系；算法及特性；大O记号的表示。51.1 数据结构的概念数据结构的概念 1.2 抽象数据类型（抽象数据类型（ADT）1.3 算法描述与分析算法描述与分析 6程序设计的实质即为计算机处理问题编制一组“指令”，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略；数据结构即为问题的数学模型。7数值计算问题的数学模型通常可用一组线性或非线性的代数方程
2、组或微分方程组来描述.非数值计算问题的数学模型正是本门课程要讨论的数据结构。8例如：例如：迷宫、棋盘在计算机内部的表示 交叉路口的红绿灯管理 七桥问题 9概括地说，概括地说，数据结构是一门讨论数据结构是一门讨论“描述现描述现实世界实体的数学模型实世界实体的数学模型(非数值计非数值计算算)及其上的操作在计算机中如何及其上的操作在计算机中如何表示和实现表示和实现”的学科。的学科。10一、基本概念和术语一、基本概念和术语二、数据结构二、数据结构三、数据类型和抽象数据类型三、数据类型和抽象数据类型11 所有能被输入被输入到计算机中，且能被计算机处理的符号处理的符号(数字、字符等数字、字符等)的集合。数
3、据数据是计算机操作的对象计算机操作的对象的总称。是计算机处理的信息的信息的某种特定的符号表示形式表示形式。12 是数据（集合）中的一个“个体个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本基本单位单位。数据元素数据元素例如，学生信息系统中学生信息表中的一个记录13它是数据结构中讨论的最小最小单位。又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项数据项”。称之为组合项称之为组合项年 月 日姓 名学 号班 号性别出生日期入学成绩原子项原子项14数据对象数据对象 具有相同特性的数据元素的集合。如:整数、实数等。15数据结构数据结构1.指互相之间存在着一
4、种或多种关系的数据元素的集合。2.在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。16如，在 2 行 3 列的二维数组中六个元素 a1,a2,a3,a4,a5,a6之间存在着两个关系:“行行”的次序关系的次序关系:row=,col=,“列列”的次序关系的次序关系:a1a2 a3a4a5 a617 在含 6 个数据元素a1,a2,a3,a4,a5,a6 的集合上存在如下的次序关系次序关系:|i=1,2,3,4,5可见，不同的“关系关系”构成不同的“结构结构”则构成“一维数组一维数组”。18数据结构的形式定义描述数据结构的形式定义描述为
5、:数据结构数据结构是一个二元组 Data_Structures=(D,R)其中:D 是数据元素的有限集数据元素的有限集，R 是 D上关系的有限集关系的有限集。19从关系关系或结构结构分，数据结构数据结构可归结为以下四类四类:线性线性结构树形树形结构图状图状结构集合集合结构20数据结构包括“逻辑结构逻辑结构”和“物理结物理结构构”两个方面(层次):逻辑结构逻辑结构 是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构存储结构”。21数据的存储结构关系有两种表示方法：数据的存储结构关系有两
6、种表示方法：顺序存储顺序存储以以 B 相对于相对于 A 的存储位置的存储位置 表示表示 B是是A的后继的后继 例如例如:令 B 的存储位置和 A 的存储位置之间相差一个预设常量 C，而 C 是一个隐含值，A B22链式存储链式存储以附加信息以附加信息(指针指针)表示后继关系表示后继关系以和A绑定在一起的附加信息(指针)表示后继关系，这个指针即为 B的存储地址，由此得到的数据存储结构为链式存储结构。B A以“由数据元素 A 的存储映象和附加的指针合成的结点结点”表示数据元素。23存储结构的描述方法随编程环境的不同而不同，对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同
7、，即使逻辑结构相同，数据结构能起的作用也不同。24数据类型数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型抽象数据类型（Abstract Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作 25抽象数据类型形式定义为：抽象数据类型形式定义为：ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 26一、什么是算法一、什么是算法二、算法技术分析初步二、算法技术分析初步三、算法效率的衡量方法和准则三、算法效率的衡量方法和准则四、算法的存储空间需求四、算法的存储空间需求27 是一个有
8、穷的规则集合，这是一个有穷的规则集合，这些规则为解决某一特定任务规定了些规则为解决某一特定任务规定了一个一个运算序列运算序列。算法算法描述算法的方法有：描述算法的方法有：自然语言自然语言程序设计语言（或类程序设计语言）程序设计语言（或类程序设计语言）流程图（包括传统流程图和流程图（包括传统流程图和N-S结构图）结构图）伪语言伪语言PAD图图28一个算法必须满足以下五五个重要特性特性：3可行性可行性1有穷性有穷性2确定性确定性5有输出有输出4有输入有输入29有穷性有穷性一个算法必须在有穷步之后正常结束，即必须在有限时间内完成而不能形成无穷循环。确定性确定性算法的每一步必须有确切的定义，无二义性。
9、算法的执行对应着的相同的输入仅有唯一的一条路经。30可行性可行性 算法中的每一条指令必须是切实可行的，即原则上可以通过已经实现的基本运算执行有限次来实现。有输入有输入 一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。31有输出有输出 一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。32健壮性健壮性 当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出处理出错的方法错的方法不应是中断程序的执行，而应是返回返回一个表示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。33和算法执行
10、时间时间相关的因素因素：1问题的规模问题的规模2 2书写程序的语言书写程序的语言 3 3编译程序所生成目标代码的质量编译程序所生成目标代码的质量 4 4硬件的速度硬件的速度 34 一个特定算法的算法的 “运行工作量运行工作量”的大小，只依赖于问题的规模（通常用整数量 n 表示），或者说，它是问题规模的函数是问题规模的函数。假如，随着问题规模 n 的增长，算法执行时算法执行时间的增长率和间的增长率和 f(n)的增长率相同的增长率相同，则可记作：T(n)=O(f(n)称称 T(n)为算法的为算法的(渐近)时间复杂度时间复杂度35如何估算如何估算 算法的时间复杂度？算法的时间复杂度？361.空间复杂
11、度空间复杂度空间复杂度（Space complexity）是指程序运行从开始到结束所需的存储量。它指的是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现所占用的空间也以某种单位由1增至f(n)。则称该算法的空间代价是f(n)。372.时间复杂度时间复杂度 时间复杂度时间复杂度（Time complexity）是指程序运行从开始到结束所需要的时间。定义为（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，有：f(n)cg(n)则有：f(n)(g(n)称为算法的渐进时间复杂度渐进时间复杂度（Asymptotic Complexity）。38例如：算法语句 对应的语句频度 fo
12、r（i=0；i n;i+）n for（j=0；jn;j+）n2 cij=0;n2 for(k=0;k n;k+)n3 cij=cij+aik*bkj;n3 39算法的时间复杂度，即是算法的时间量度,记做：T(n)=O(f(n)例如给出X=X+1 x=x+1；时间复杂度为O(1)，称为常量阶；for(i=1;i=n;i+)x=x+1;时间复杂度为O(n)，称为线性阶；for(i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;时间复杂度为O(n2),称为平方阶。for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ai.data last);/*线性表的数据个数*/f
13、or(i=1;ilast;i+)printf(n data=);scanf(%d,&(L-datai-1);/*输入数据*/*Creat_Seqlist end */60 在顺序表指定位置插入元素的过程。在顺序表指定位置插入元素的过程。2往顺序表中插入一个新数据元素往顺序表中插入一个新数据元素61图图2-4 2-4 顺序表插入前、后的状态示意顺序表插入前、后的状态示意 62 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表:(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n+1的表:(a1，a2，.，ai-1，x，ai，ai+1，.，an
14、)。i 的取值范围为1=ilast=MAXSIZE)printf(n Error?n);return(-1);/*表空间已满，不能插入!*/if(i L-last)printf(n Error?);return(-1);/*检查插入位置的正确性*/64 else/*向后移动数据数据*/for(j=L-last-1;j=i;j-)L-dataj+1=L-dataj;L-datai=x;/*插入数据*/L-last+;/*线性表长度加1 */return(1);/*插入成功，返回*/65插入算法的时间性能分析插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插
15、入 x，从 ai 到 an 都要向下(右)移动一个位置，共需要移动 n-i+1个元素，而 i 的取值范围为：1=i=n+1，即有 n+1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：66假设在线性表的任何位置插入元素的概率pi相等（暂不考虑概率不相等情况），则 11)1(Eniiininp11npi67 元素插入位置的可能值：i=1,2,n,n+1 相应向后移动元素次数：n-i+1=n,n-1,1,0 对n,n-1,1,0求总和，显然为n(n+1)/2。所以，插入时数据元素平均移动次数为：68这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为
16、(n)。11112)1(11)1(Eniniiinninninp69线性表的删除运算是指将表中第线性表的删除运算是指将表中第 i i 个个元素从线性表中去掉，删除后使原表长为元素从线性表中去掉，删除后使原表长为 n n的线性表：的线性表：(a(a1 1，a a2 2，a ai-1i-1，a ai i，a ai+1i+1，a an n)成成为表长为为表长为 n-1 n-1 的线性表：的线性表：(a(a1 1，a a2 2，a ai-1i-1，a ai+1i+1，a an n)。i i 的取值范围为：的取值范围为：1=i=n 1=i=n，如图如图2-52-5所示。所示。3删除顺序表中的一个数据元素
17、删除顺序表中的一个数据元素70图图2-5 2-5 顺序表里删除元素示意顺序表里删除元素示意 71 void Delete_Seqlist(Seqlist*L,int i)int j;i-;if(i L-last-1)printf(n Not exist！);else for(j=i+1;jlast-1;j+)L-dataj-1=L-dataj;/*向前移动数据数据*/L-last-;/*线性表长度减1 */72本算法注意以下问题：本算法注意以下问题：（1）删除第i个元素，i的取值为 1=ilast的值为0，条件（iL-last-1）也包括了对表空的检查。（3）删除 ai 之后，该数据已不存在，
18、如果需要，先取出 ai，再做删除。73删除算法的时间性能分析：删除算法的时间性能分析：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数：niideinp1)(E74假设在线性表的任何位置删除元素的概率qi相等（暂不考虑概率不相等情况）：元素删除位置的可能值：i=1,2,n相应向前移动元素次数：n-i=n-1,n-2,0 nqi175对n-1,1,0求总和，显然为n(n-1)/2。则删除时数据元素平均移动次数为：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法
19、的时间复杂度为(n)。11121)(1)(Eniniideninninp76 查找顺序表中第一个与给定数据相等的查找顺序表中第一个与给定数据相等的元素的算法。元素的算法。给定数据给定数据x x，在顺序表，在顺序表L L中查找第一个与中查找第一个与它相等的数据元素。如果查找成功，则返回它相等的数据元素。如果查找成功，则返回该元素在表中的位置；如果查找失败，则返该元素在表中的位置；如果查找失败，则返回回-1-1。算法如下。算法如下:4在顺序表中查找一个数据元素在顺序表中查找一个数据元素 77int Location_SeqList(SeqList*L,DataType x)int i=0;whil
20、e(idatai!=x)i+;if(iL-last-1)return-1;else return i;/*返回的是存储位置返回的是存储位置*/该算法的主要运算是比较。显然比较的次数与该算法的主要运算是比较。显然比较的次数与x x在表中的位置有关，也与表长有关。当在表中的位置有关，也与表长有关。当 a a1 1=x=x 时，比时，比较一次成功。当较一次成功。当 a an n=x=x 时比较时比较 n n 次成功。平均比较次次成功。平均比较次数为（数为（n+1n+1）/2/2，时间性能为，时间性能为O(nO(n)。78 打印顺序表中各结点值的算法。打印顺序表中各结点值的算法。算法描述：算法描述：当
21、顺序表当顺序表L L不空时，将各个结点的值打不空时，将各个结点的值打印输出。算法如下印输出。算法如下:5打印顺序表的各结点值打印顺序表的各结点值79Print_SeqList(SeqList*L)if(L-last=0)printf(The sequential list is empty!);else for(i=1;ilast;i+)printf(%d,L-datai-1);80 获取顺序表现有元素个数的算法。获取顺序表现有元素个数的算法。算法描述：由于顺序表当前的元素个数，算法描述：由于顺序表当前的元素个数，在其管理信息单元在其管理信息单元L-lastL-last里记录，因此只里记录，因
22、此只需将顺序表需将顺序表L L的的L-lastL-last当前值读出即可。算当前值读出即可。算法如下法如下:6求顺序表的长度求顺序表的长度81Length_ SeqList(SeqList*L)printf(The Length of sequential list is=%d,L-last);82 往顺序表末尾添加新元素的算法。往顺序表末尾添加新元素的算法。往顺序表往顺序表L L的末尾添加一个新的数据元的末尾添加一个新的数据元素素x x。算法如下。算法如下:7往顺序表末尾添加一个新的数据元素往顺序表末尾添加一个新的数据元素83Append_ SeqList(SeqList*L,datatyp
23、e x)if(L-last=MAXSIZE)printf(The sequential list is full!);/*顺序表已满，不能再插入顺序表已满，不能再插入*/else L-dataL-last=x;/*能够插入能够插入*/L-last+;84 例例2-4 2-4 设计一个算法，将顺序表：设计一个算法，将顺序表：L=(a1,a2,.,ai,ai+1,an1,an)中的元素进行逆置，即把顺序表中的元素进行逆置，即把顺序表SqSq中的中的元素排列顺序改换成：元素排列顺序改换成：L=(an,an1,ai+1,ai,a2,a1)应用应用:85 解：为算法取名Invert_SeqList()I
24、nvert_ SeqList(SeqList*L)if(L-last last-1;86 for(i=0;idatai;/*把第i个元素暂存于temp*/L-datai=L-dataj;/*把第j个元素存入表的第i个元素*/87 L-dataj=temp;/*把temp里内容存入表的第j个元素*/88 采用链式存储结构存放数据时，数据采用链式存储结构存放数据时，数据元素间的邻接关系不是直接通过存储结点元素间的邻接关系不是直接通过存储结点间的位置关系反映出来，而是由每个存储间的位置关系反映出来，而是由每个存储结点里的指针来指明。因此，链式存储结结点里的指针来指明。因此，链式存储结构不要求邻接的数
25、据元素在物理位置上也构不要求邻接的数据元素在物理位置上也是邻接的。是邻接的。2.3.1 2.3.1 单链表单链表89 链表是由一个个结点构成的，结点定义如下：typedef struct node DataType data;/*数据域*/struct node*next;/*指针域*/LNode，*LinkList；90图图2-7 2-7 单链表中存储结点的示意单链表中存储结点的示意 91 单链表采用的链式存储结构，优点是不单链表采用的链式存储结构，优点是不以表的总存储需求进行存储分配，而是以单以表的总存储需求进行存储分配，而是以单个数据存储结点的大小（个数据存储结点的大小（sizesize
26、）来进行动态）来进行动态存储分配，即当有新的数据元素希望进入链存储分配，即当有新的数据元素希望进入链表时，就按照存储结点的大小向系统提出存表时，就按照存储结点的大小向系统提出存储请求。储请求。92图图2-8 2-8 单链表示意单链表示意 93图图2-8 2-8 带头结点的单链表示意带头结点的单链表示意 94 单链表表头指针的作用是十分重要的，单链表表头指针的作用是十分重要的，因为从它可以找到表的第因为从它可以找到表的第1 1个存储结点，然个存储结点，然后才能够沿着各结点的指针域找到表中的其后才能够沿着各结点的指针域找到表中的其他所有结点。他所有结点。当单链表为空（即长度为当单链表为空（即长度为
27、0 0）时，其表）时，其表头指针头指针Head=NULLHead=NULL。95 我们假定，如果指针我们假定，如果指针p p指向一个单链表指向一个单链表的存储结点，那么的存储结点，那么“p-Data”p-Data”表示所指结表示所指结点的数据域，点的数据域，“p-Next”p-Next”表示所指结点的表示所指结点的指针域。指针域。2.3.2 2.3.2 单链表的基本算法描述单链表的基本算法描述96插入运算插入运算 Insert_LinkList(L,i,xInsert_LinkList(L,i,x)，在链，在链表表L L的第的第i i个元素结点处插入值为个元素结点处插入值为x x的元素。的元素
28、。算法思路：算法思路：.找到第找到第i-1i-1个结点；若存在继续个结点；若存在继续2 2，否则结束否则结束.申请、填装新结点；申请、填装新结点；.将新结点插入。结束。将新结点插入。结束。算法如下：算法如下：1往单链表中插入一个新结点往单链表中插入一个新结点97 int Insert_LinkList(LinkList L,int i,TataType x)/*在含头结点的单链表L的第i个位置上插入值为x的元素*/LNode *p,*q;p=L;int k=0;while(p!=NULL)&(knext;k+;/*查找第i-1个结点*/if(p=NULL|ki-1)printf(参数i错);r
29、eturn 0;/*第i-1个不存在不能插入*/98 else q=(LNode*)malloc(sizeof(LNode);q-data=x;/*申请、填装结点*/q-next=p-next;/*新结点插入在第i-1个结点的后面*/p-next=q;return 1;99图图2-11 单链表上插入值为单链表上插入值为x的结点的结点100 删除单链表删除单链表L L上的第上的第i i个数据结点：个数据结点：Del_LinkList(L,iDel_LinkList(L,i)算法思路：算法思路：.找到第找到第i-1i-1个结点；若存在继续个结点；若存在继续2 2，否则结束；否则结束；.若存在第若存
30、在第i i个结点则继续个结点则继续3 3，否则结，否则结束；束；.删除第删除第i i个结点，结束。个结点，结束。算法如下：算法如下：2从单链表中删除指定的结点从单链表中删除指定的结点101 void Del_LinkList(LinkList L，int i)/*删除含头结点的单链表L上的第i个结点*/LNode *p,*q,*s;q=L,p=q-next;int k=1;while(p&(knext;k+;/*查找第i个结点*/102 if(k=i)q-next=p-next;free(p);printf(“删除结点成功。”);else printf(“inext;L-next=NULL;w
31、hile(p)q=p-next;p-next=L-next;L-next=p;p=q;该算法只是对链表中该算法只是对链表中顺序扫描一边即完成顺序扫描一边即完成了倒置，所以时间性了倒置，所以时间性能为能为O(nO(n)。1052.4.1 双向链表双向链表1双链表的结点双链表的结点 所谓所谓“双向链表双向链表”，是在数据的存储结，是在数据的存储结点里，存放两个指针域，一个指向它的直接点里，存放两个指针域，一个指向它的直接后继，另一个指向它的直接前驱。后继，另一个指向它的直接前驱。106图图2-15 双链表结点及双链表示意双链表结点及双链表示意 107双向链表结点的定义如下：双向链表结点的定义如下：
32、typedef struct dlnode DataType data;struct dlnode*prior,*next;DLNode,*DLinkList;108 在双链表中值为在双链表中值为x x的结点后插入值为的结点后插入值为y y的的结点。结点。算法思想算法思想:先找值为先找值为x x的结点的结点ptrptr,有三种情有三种情况况:1 1 不存在不存在 2 2 最后一个结点最后一个结点 3 3 一般情况一般情况2在双链表指定位置后插入结点在双链表指定位置后插入结点109图图2-16 在双链表上的后向插入示意图在双链表上的后向插入示意图 110 删除双链表上删除双链表上datadata
33、域的值为域的值为x x的结点。的结点。算法思想算法思想:先找值为先找值为x x的结点的结点ptrptr,有四种情有四种情况况:1 1 不存在不存在 2 2 最后一个结点最后一个结点 3 3 一般情况一般情况 4 4 最后一个最后一个3将双链表上指定取值的结点删除将双链表上指定取值的结点删除 111 如果把单链表最后一个结点的如果把单链表最后一个结点的nextnext域存域存储的值由储的值由NULLNULL改为指向表的起始结点，使整改为指向表的起始结点，使整个表的结点首尾相接，形成一个环，这样的个表的结点首尾相接，形成一个环，这样的链表被称为链表被称为“循环链表循环链表”。2.4.2 循环链表循
34、环链表1循环链表的各种形式循环链表的各种形式112图图2-18 表头指针式的循环链表表头指针式的循环链表 113用表尾指针取代表头指针的循环链表的形式用表尾指针取代表头指针的循环链表的形式 图图2-19 表尾指针式的循环单链表表尾指针式的循环单链表 114 在用表尾指针代替表头指针后，要寻找在用表尾指针代替表头指针后，要寻找表的起始结点和终端结点都变得很方便了。表的起始结点和终端结点都变得很方便了。借助于双链表的概念，也可以把结点组织借助于双链表的概念，也可以把结点组织成循环双链表，如图成循环双链表，如图2-202-20所示。图所示。图2-202-20（a a）所示为一个循环双链表的示意；图所
35、示为一个循环双链表的示意；图2-202-20（b b）所示为一个带表头结点的循环双链表，所示为一个带表头结点的循环双链表，115这时是表头结点的这时是表头结点的priorprior域指向链表的域指向链表的终端结点，终端结点的终端结点，终端结点的nextnext域指向表头结点，域指向表头结点，从而构成循环；图从而构成循环；图2-202-20（c c）所示为带表头）所示为带表头结点的空循环双链表的形式，表头结点的结点的空循环双链表的形式，表头结点的priorprior和和nextnext域全都是指向它自己，也就是域全都是指向它自己，也就是在循环双链表空时，满足条件在循环双链表空时，满足条件Ck_h
36、Ck_h-prior=-prior=Ck_hCk_h-next-next。116图图2-20 表头指针式的循环双链表表头指针式的循环双链表117 例例2-8 2-8 有两个循环单链表，表头指针有两个循环单链表，表头指针分别是分别是Ck_h1Ck_h1和和Ck_h2Ck_h2。编写一个算法，将链。编写一个算法，将链表表Ck_h1Ck_h1链接到链接到Ck_h2Ck_h2之后，仍然保存循环链之后，仍然保存循环链表的形式。表的形式。118图图2-23 两个循环链表的链接两个循环链表的链接 119解：具体算法如下。解：具体算法如下。Link_Ck(LinkList Ck_h1,LinkList Ck_
37、h2)/*两个链表均非空两个链表均非空*/ptr=Ck_h1;while(ptr-Next!=Ck_h1)/*找到找到Ck_h1的表尾，的表尾，ptr指向它指向它*/qtr=Ck_h2;while(qtr-Next!=Ck_h2)/*找到找到Ck_h2的表尾，的表尾，qtr指向它指向它*/qtr-Next=Ck_h1;/*将将Ck_h2链接到链接到Ck_h1之后之后*/ptr-Next=Ck_h2-next;/*保持循环保持循环*/1202.5 单链表的应用单链表的应用符号多项式的相加操作是线性表处理的典型用例。在数学上的一个多项式:我们称为项多项式，是多项式的项（0in），其中ai为系数，为
38、变数，i为指数，一般多项式可以使用顺序表来表示其数据结构，也可以使用链表来表示。0111.axaxaxapnnnniixa121 设有两个已知多项式:将两个多项式相加得一个新的多项式C：5233814xxxA3610141038xxxxB5102311681014xxxxC122多项式相加的链表存储结构多项式相加的链表存储结构 多项式采用链表来表示。每个结点对应多项式的一个项，存储该项的系数和指数，其结点结构如下：typedef struct poly int coef;/*变量的系数*/intexp;/*变量的指数*/struct poly *next;/*指到下一结点的指针 */Lpoly
39、;123 每个多项式由多个结点组成，高指数的项（高次幂）的结点在链表头部，低指数的项（低次幂）的结点在链表的后部。A，B两个多项式的链表结构图如下：124多项式相加的算法实现多项式相加的算法实现 为了进行加法运算，设置p,q 两个指针变量分别指向pa,pb两个链表的第一个数据元素结点。然后对p,q两个结点的指数域进行比较。指数相同系数相加，连入C链表；指数不同，将指数较大的结点连入C表。125现设C链表头指针pc指向pa（这样充分利用现有结点，节省资源），设指针变量r也指向pa，当有结点连入C表时pc不动r向前移动。每处理一次，相关指针p,q,r一般需要向前移动。126127 对照后面多项式相
40、加的算法和图2.16可看出两个指数为14的项相加后，得一个系数为11新项连在pc链上。当p,q指针前向后移动之后，将p,q所指两个结点的指数相比，q结点的指数较大，于是将q结点连入pc链。这里p不移动，q,r各向前移动一步，此时链表状态如图2.17所示。128图图 2.17 第二次处理第二次处理 结合图示阅读后面的算法，读者自行分析，结合图示阅读后面的算法，读者自行分析，即可得相加后的链表。算法如下：即可得相加后的链表。算法如下：129Lpoly*add_poly(Lpoly*pa,Lpoly*pb)p=pa-next;q=pb-next;r=pa;pc=pa;while(p!=NULL)&(
41、q!=NULL)if(p-exp=q-exp)x=p-coef+q-coef;if(x!=0)p-coef=x;r=p;else r-next=p-next;p=p-next;q=q-next;130 else if(p-expq-exp)r-next=p;r=p;p p-next;else r-next=q;r=q;q=q-next;/*while end */if(p=NULL)r-next=q;else r-next=p;return(pc)/*add_poly end */131第3章 栈和队列132 栈和队列是二种特殊的线性表。是操作受限的线性表。一、栈一、栈1 1、栈的概述、栈的概
42、述 栈(Stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。133 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出栈是一种后进先出(Last In (Last In First Out)First Out)的线性表，简称为的线性表，简称为LIFOLIFO表。表。134 初始化栈：初始化栈：INISTACK(&S)INISTACK(&S)将栈S置为一个空
43、栈(不含任何元素)。进栈：进栈：PUSH(&S,X)PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。出栈：出栈：POP(&S)POP(&S)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。取栈顶元素：取栈顶元素：GETTOP(S)GETTOP(S)取栈S中栈顶元素。判栈空：判栈空：EMPTY(S)EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。2、栈的运算、栈的运算135例1：设栈的输入序列是(1,2,3,4),则 不可能是其出栈序列A.1243 B.2134 C.1432 D.4312 E.3214例2：依次读入数据元素序列(a,
44、b,c,d,e,f,g)进栈，每进一个元素，机器可要求下一个元素进栈或出栈；如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？A.decfbga B.fegdacb C.efdgbca D.cdbefag 136例3：一个输入序列abcd经过一个栈到达输出序列，并且一旦离开输入序列后就不能再返回到输入序列，则下面 为正确输出序列。A.bcad B.cbda C.dabc D.acbd E.dcba二、顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。并设指针top指向栈顶元素的当前位置。1371、顺序栈存储结构定义：、顺序栈存储结构定义：Struct seqstack el
45、emtype stackmaxsize;int top;注释：空栈时注释：空栈时top=0,进栈一个元素进栈一个元素top+1.1382、顺序栈的主要运算、顺序栈的主要运算 进栈操作进栈操作 void push(ElemType x)if(top=MAXSIZE-1)printf(“溢出溢出”);exit(1);else top+;elemtop=x;139出栈出栈ElemType pop()ElemType x;if(top!=0)x=elemtop;top-;return x;else printf(“栈为空栈为空!”);exit(1);140三、链栈三、链栈typedef struct
46、Lsnode ElemType data;struct Lsnode *next;Lsnode *top;一个链表栈由栈顶指针一个链表栈由栈顶指针top唯一确定。唯一确定。141进栈操作 void void Push(LsnodePush(Lsnode *top;top;ElemTypeElemType x)x)p=(p=(LsnodeLsnode *)malloc(sizeof(Lsnodemalloc(sizeof(Lsnode););p-data=x;p-data=x;p-next=top-next;p-next=top-next;top-next=p;top-next=p;/*Push
47、Push*/1、链栈的主要运算、链栈的主要运算142出栈操作 ElemTypeElemType Pop(LsnodePop(Lsnode *top)top)if(topif(top-next!=NULL)-next!=NULL)p=top-next;top-next=p-next;p=top-next;top-next=p-next;x=p-data;x=p-data;free(pfree(p);return x;);return x;else else printf(Stackprintf(Stack null!n);null!n);return#;return#;/*PopPop*/143
48、1 1、队列的概述、队列的概述 仅允许在一端进行插入，另一端进行删除的线性表，称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队头（front）。队列是一种队列是一种先进先出先进先出（First In First OutFirst In First Out）的特的特殊线性表，或称殊线性表，或称FIFOFIFO表。表。a1 a2 .an 入队 队头 队尾 出队 队列示意图 四、队列四、队列1442、队列的基本运算、队列的基本运算初始化队列初始化队列 INIQUEUE(&Q)INIQUEUE(&Q)将队列Q设置成一个空队列。入队列入队列 ENQUEUE(&Q,X)EN
49、QUEUE(&Q,X)将元素X插入到队尾中，也称“进队”，“插入”。出队列出队列 DLQUEUE(&Q)DLQUEUE(&Q)将队列Q的队头元素删除，也称“退队”、“删除”。取队头元素取队头元素 GETHEAD(Q)GETHEAD(Q)得到队列Q的队头元素之值。判队空判队空 EMPTY(Q)EMPTY(Q)判断队列Q是否为空，若为空返回1，否则返回0。1451.1.队列的顺序存储数据类型描述队列的顺序存储数据类型描述 struct seqqueue elemtype queuemaxsize;int front;/队头指针 int rear;/队尾指针 ;五、顺序队列五、顺序队列1462.2.
50、顺序队列顺序队列 理论上讲，若尾指针理论上讲，若尾指针rearrear指向一维数组最后指向一维数组最后,而头而头指针指向一维数组开头，称为指针指向一维数组开头，称为队满队满。但有可能出现这样情况，尾指针指向一维数组最但有可能出现这样情况，尾指针指向一维数组最后，但前面有很多元素已经出队，即空出很多位置，后，但前面有很多元素已经出队，即空出很多位置，这时要插入元素，仍然会发生溢出。我们将这种溢出这时要插入元素，仍然会发生溢出。我们将这种溢出称为称为“假溢出假溢出”。147 要克服“假溢出”，方法一：平移法。可以将整个队列中元素向前移动，直到头指针front为-1，或者每次出队时，都将队列中元素前
