数据结构教学大纲.doc

教学大纲一、指导思想 数据结构是计算机学科最重要的一门专业基础课，许多计算机学科的重点课程，例如操作系统、编译原理以及数据库系统原理设计都涉及到本课程所介绍的基本数据结构。数据结构课程的教学应贯彻下列指导思想。 1、基础性： 由于构成计算机科学的核心是数据结构、算法和程序设计，因此必须以本课程作为计算 机专业核心课程，为学生的专业学习打下扎实深厚的基础。 2、系统性： 本课程以系统的观点研究数据组织和操作算法，必须在抽象思维、算法设计等方面加强 学生的能力培养。 3、先进性： 本课程内容是在计算机应用于数值的和非数值的领域中形成和发展的，其新思想和新方 法不断产生，必须不断更新教学内容以拓宽学生的知识面，适应计算机应用和发展的需要。 4、实践性： 本课程是一门实践性很强的课程，在数据结构的课程实验中不仅要训练计算机实验 技能和操作能力，更应包括设计算法的创造性实验能力。 二、教学目标 通过本课程学习，要求学生掌握数据结构和算法的基本概念和技术，从而能够对于给顶问题选择合适的 数据结构，并设计相应的操作算法。掌握数组、线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及内排序、查找等重要技术。三、教学内容第一章:绪论第六章:树1.1数据结构课程研究的内容6.1 树的概念1.2数据结构课程的发展历史及课程学习的目的6.2 二叉树1.3 基本概念和术语6.3 二叉树的运算1.4 抽象数据类型的表示与实现6.4 线索二叉树1.5 算法及算法实现6.5 树和森林第二章：线性表6.6 哈夫曼树及其应用2.1 线性表的定义第七章:图2.2 基于抽象数据类型线性表的操作7.1 图的概念2.3 线性表的存储结构7.2 图的存储结构2.4 基于顺序存储结构的线性表操作算法7.3 图的遍历2.5 基于链式存储结构的线性表操作算法7.4 图的生成树和最小生成树2.6 循环链表的操作算法7.5 拓扑排序2.7 双向链表的操作算法7.6 关键路径2.8 顺序存储线性表与链式存储线性表的比较7.7 最短路径2.9 一元多项式的表示及相加第八章:查找第三章:栈和队列8.1 基本概念3.1 栈的概念8.2 顺序查找3.2 栈的存储结构8.3 二分查找3.3 顺序栈的操作算法8.4 分块查找3.4 链栈的操作算法8.5 二叉排序树的查找3.5 栈的应用举例:表达式求值8.6 Hash查找3.6 队列的概念8.7 B树和B+树3.7 队列的存储结构第九章:排序3.8 循环队列的操作算法9.1 基本概念3.9 队列的操作算法9.2 冒泡排序第四章:串9.3 选择排序4.1 串的概念9.4 插入排序4.2 串的存储结构9.5 希尔排序4.3 串的操作算法9.6 快速排序4.4 模式匹配算法的改进:KMP算法9.7 堆排序第五章:数组和广义表9.8 归并排序5.1 数组的概念9.9 基数排序5.2 数组的存储结构5.3 对称矩阵的压缩存储5.4 稀疏矩阵的压缩存储5.5 广义表的定义5.6 广义表的存储结构5.7 广义表的操作算法第一章：绪论1.1数据结构课程研究的内容数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科。它主要研究： 数据的逻辑结构-数据关系之间的逻辑关系数据的存储结构-数据的逻辑结构在计算机中的表示 操作算法-插入、删除、修改、查询、排序等 其中，数据的逻辑结构： 集合线性结构 -表、栈、队列非线性结构 -树、图 数据的存储结构： 顺序存储结构 -数组链式存储结构 -指针 1.2 数据结构课程的发展历史及课程的重要性1968年在美国开设。它随着大型程序的出现而出现。我国1980s年代初开设。它是计算机专业的核心课程，考研必考。学习数据结构的目的：提高复杂程序设计的能力培养算法设计能力为后继课程（如操作系统、编译原理等）打基础。 1.3 基本概念和术语1、数据2、数据元素3、数据项4、数据对象5、数据结构6、存储结构7、数据类型数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项是数据的不可分割的最小单位。数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0,1，2，字母字符数据对象是集合C=A,B,Z。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合 结构中的数据元素之间除了同属于一个集合的关系外，别无其他关系； 线性结构 结构中的数据元素之间存在一个对一个的关系； 树形结构 结构中的数据元素之间存在一个对多个的关系； 图状结构或网状结构 结构中的数据元素之间存在多个对多个的关系；它可形式定义为：数据结构是一个二元组Data_Structure=(D,S) 其中：D是数据元素的有限集、S是D上关系的有限集。存储结构是数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。 有两种不同的存储结构： 顺序存储结构- 其特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构- 其特点是借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。数据类型是和数据结构密切相关的一个概念。它是一个值的集合和定义在这个值集上的一组操作的总称。8、抽象数据类型抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型和数据类型实质上是一个概念。例如，各个计算机都拥有的整数类型是一个抽象数据类型，尽管它们在不同处理器上实现的方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。 和数据结构的形式定义相对应，抽象数据类型可以用以下三元组表示(D,S,P) 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型的定义格式如下：ADT 抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名*例子*例子：抽象数据类型三元组的定义：ADT Triplet数据对象：D=e1,e2,e3|e1,e2,e3ElemSet(定义了关系运算的某个集合)数据关系：R1=,基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数v1，v2和v3的值。DestroyTriplet(&T)操作结果：三元组T被销毁。Get(T,i,&e)初始条件：三元组T已存在，1i3。操作结果：用e返回T的第i元的值。Put(&T,i,e)初始条件：三元组T已存在，1i3。操作结果：改变T的第i元的值为e。IsAscending(T)初始条件：三元组T已存在。操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。IsDescengding(T)初始条件：三元组T已存在。操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最小值。ADTTriplet;1.4 抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。例子如下：例子：抽象数据类型Triplet的表示和实现。/-采用动态分配的顺序存储结构-typedef ElemType *Triplet; /由InitTriplet分配三个元素存储空间/-基本操作的函数原型说明-Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3);/操作结果：构造了三元组T，元素e1，e2和e3分别被赋以参数v1，v2和v3的值。Status DestroyTriplet(Triplet &T);/操作结果：三元组T被销毁。Status Get(Triplet T,int i,ElemType &e);/初始条件：三元组T已存在，1i3。/操作结果：用e返回T的第i元的值。Status Put(Triplet &T,int i,ElemType e);/初始条件：三元组T已存在，1i3。/操作结果：改变T的第i元的值为e。Status IsAscending(Triplet T);/初始条件：三元组T已存在。/操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。Status IsDescending(Triplet T);/初始条件：三元组T已存在。/操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。Status Max(Triplet T,ElemType &e);/初始条件：三元组T已存在。/操作结果：用e返回T的三个元素中的最大值。Status Min(Triplet T,ElemType &e);/初始条件：三元组T已存在。/操作结果：用e返回T的三个元素中的最小值/-基本操作的实现-Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3)/构造三元组T，依次置T的三个元素的初值为v1，v2和v3。T=(ElemType *)malloc(3 *sizeof(ElemType); /分配3个元素的存储空间if (!T) exit(OVERFLOW); /分配存储空间失败T0=v1; T1=v2; T2=v3;return OK; / InitTriplet Status DestroyTriplet(Triplet &T)/销毁三元组T。free(T); T=NULL;return OK; / DestroyTripletStatus Get(Triplet T,int i,ElemType &e)/1i3，用e返回T的第i元的值。if (i3) return ERROR;e=Ti-1;return OK; / GetStatus Put(Triplet &T,int i,ElemType e)/1i3，置T的第i元的值为e。if (i3) return ERROR;Ti-1=e;return Ok; / PutStatus IsAscending(Triplet T)/如果T的三个元素按升序排列，则返回1，否则返回0。return (T0=T1) & (T1=T1) & (T1=T2); / IsDescendingStatus Max(Triplet T,ElemType &e)/用e返回T的三个元素中的最大值。e=(T0=T1)?(T0=T2)?T0:T2):(T1=T2)?T1:T2);return OK; / MaxStatus Min(Triplet T,ElemType &e)/用e返回T的三个元素中的最小值。e=(T0=T1)?(T0=T2)?T0:T2):(T1=T2)?T1:T2);return OK; / Min1.5 算法和算法分析1、算法的特性算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法有五个特性：有穷性- 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；确定性- 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有 唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性- 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入- 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。输出- 一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。2、评价算法好坏的标准正确性：算法应当满足具体问题的需求。可读性：可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误难以调试和修改。 健壮性：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。例如，一个求凸多边形面积的算法，是采用求各三角形面积之和的策略来解决问题的。当输入的坐标集合表示的是 一个凹多边形时，不应继续计算，而应报告输入出错。时间复杂性：效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。空间复杂性：存储量需求指算法执行过程中所需要的最大存储空间。3、算法效率的度量度量一个程序的执行时间通常有两种方法：事后统计的方法事前分析估算的方法4、时间复杂性为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。例如，在如下所示的两个NN矩阵相乘 的算法中，乘法运算是矩阵相乘问题的基本操作。整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，记作T(n)=O(n3)。for(i=1; i=n; +i)for(j=1; j=n; +j)cij=0;for(k=1; k=n; +k)cij+=aik*bkj; 一般情况下，算法中基本操作重复执行的次数是问题规模n 的某个函数f(n)，算法的时间量度记作 T(n)=O(f(n)，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。5、空间复杂性空间复杂性(Space Complexity)作为算法所需存储空间的量度，记作S(n)=O(f(n) 其中n为问题的规模（或大小）。一个程序上机执行所需空间包括：程序指令存储的空间数据存储的空间变量分配的空间 第二章：线性表2.1 线性表的定义1、名词术语线性表-n个数据元素的有限序列，记为(a1,a2,ai-1,ai,ai+1,，an)。例如：26英文字母表(A,B,C,X,Y,Z)、一个班级的学生成绩报表等表长-线性表中元素的个数直接前驱元素-线性表中ai-1领先于ai，则ai-1是ai的直接前驱元素直接后继元素-线性表中ai领先于ai+1，则ai+1是ai的直接后继元素2、线性表的抽象数据类型定义ADT List数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在,1iListLength(L)。操作结果：用e返回L中第i数据个元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在,compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,i,e)初始条件：线性表L已存在,1iListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空,1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L,visit()初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT List2.2 基于抽象数据类型线性表的操作1、建立一个空的线性表2、求线性表中元素个数3、判断线性表L是否为空4、取线性表L中第i个元素5、在线性表中插入某元素6、在线性表中删除某元素7、求线性表中某元素的前驱元素8、求线性表中某元素的后继元素9、在线性表中查找某元素10、两个线性表进行合并2.3 线性表的存储结构1、两种存储结构：顺序存储-数组链式存储-链表2、线性表的顺序存储结构示意图：存储地址内存状态数据元素在线性表中的位序b1b+l2b+(i-1)lib+(n-1)lnb+nl空闲b+(maxlen-1)l注：设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。所以，线性表的第i个数据元素ai的存储位置为loc(ai)=loc(a1)+(i-1)*l。上述图中第一个元素存储位置设为b。类型定义：/-线性表的动态分配顺序存储结构-#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList;3、线性表的链式存储结构L=(a1,a2,an)示意图：注：(a)为非空表，(b)为空表。类型定义：/-线性表的单链表存储结构-typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;2.4 基于顺序存储结构的线性表操作算法1、创建一个空的线性表Status InitList_Sq(SqList &L)/ 构造一个空的线性表L。L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType);if (!L.elem) exit(OVERFLOW); /存储分配失败L.length=0; /空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量return OK;/InitList_Sq2、插入元素算法Status ListInsert_Sq(SqList &L,int i,ElemType e)/在顺序线性表L中第i个位置之前插入新的元素e,/i的合法值为1iListlength_Sq(L)+1if(iL.length+1) return ERROR; /i的值不合法if(L.length=L.listsize) /当前存储空间已满，增加分配newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)* sizeof(ElemType);if(!newbase) exit(OVERFLOW); /存储分配失败L.elem=newbase; /新基址L.listsize+=LISTINCREMENT; /增加存储容量q=&(L.elemi-1); /q为插入位置for(p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; /插入位置及之后的元素右移*q=e; /插入e+L.length; /表长增1return OK; /ListInsert_Sq例子：动画演示3、删除元素算法Status ListDelete_Sq(SqList &L,int i,ElemType &e)/在顺序线性表L中删除第i个元素，并用e返回其值/i的合法值为1iListlength_Sq(L)if(iL.length) return ERROR; /i的值不合法p=&(L.elemi-1); /p为被删除元素的位置e=*p; /被删除元素的值赋给eq=L.elem+L.length-1; /表尾元素的位置for(+p; p=q; +p) *(p-1)=*p; /被删除元素之后的元素左移-L.length; /表长减1return OK;/ListDelete_Sq例子：动画演示4、查找元素算法int LocateElem_Sq(Sqlist L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序/若找到，则返回其在L中的位序，否则返回0。i=1; /i的初值为第1个元素的位序p=L.elem; /p的初值为第1个元素的存储位置while(i=L.length &! (*compare)(*p+,e) +i;if(i=L.length) return i;else return 0;/LocateElem_Sq 5、两表合并算法void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)/已知顺序线性表La和Lb的元素按值非递减排列/归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType *)malloc(Lc.listsize * sizeof(ElemType);if(!Lc.elem) exit(OVERFLOW); /存储分配失败pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last & pb=pb_last) /归并if(*pa=*pb) *pc+=*pa+; else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+; /插入La的剩余元素while(pbnext=NULL; /先建立一个带头结点的单链表for (i=n; i0; -i)p=(LinkList) malloc (sizeof (LNode); /生成新结点scanf(&p-data); /输入元素值p-next=L-next; L-next=p; /插入到表头/CreateList_L例子：动画演示2、链表中插入结点算法Status ListInsert_L(LinkList &L, int i, ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素ep=L; j=0;while (p & jnext; +j; /寻找第i-1个结点if (!p | ji-1) return ERROR; /i小于1或者大于表长s=(LinkList) malloc (sizeof (LNode); /生成新结点s-data=e; s-next=p-next; /插入L中p-next=s;return OK;/ListInsert_L例子：动画演示3、链表中删除结点算法Status ListDelete_L(LinkList &L, int i, ElemType &e)/在带头结点的单链线性表L中,删除第i个元素，并由e返回其值p=L; j=0;while (p-next & jnext; +j;if (!(p-next) | ji-1) return ERROR; /删除位置不合理q=p-next; p-next=q-next; /删除并释放结点e=q-data; free(q);return OK;/ListDelete_L例子：动画演示4、两个有序链表合并成一个有序链表void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)/已知单链线性表La和Lb的元素按值非递减排列/归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。pa=La-next; pb=Lb-next;Lc=pc=La; /用La的头结点作为Lc的头结点while (pa & pb)if (pa-datadata)pc-next=pa; pc=pa; pa=pa-next;else pc-next=pb; pc=pb; pb=pb-next;pc-next=pa?pa:pb; /插入剩余段free(Lb); /释放Lb的头结点/MergeList_L例子：动画演示2.6 循环链表的操作算法* 什么是循环链表？ 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，如下图所示为单链的循环链表。注：(a)为非空表，(b)为空表。* 循环链表的操作与单链表的差别：循环链表的操作与单链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。2.7 双向链表的操作算法* 什么是双向链表？为了克服单链表单向性的缺点，可利用双向链表，在它的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。在C语言中可描述如下：/-线性表的双向链表存储结构-typedef struct DuLNodeElemType data;struct DuLNode *prior;struct DuLNode *next;DuLNode, *DuLinkList;* 在双向链表中插入结点Status ListInsert_Dul(DuLinkList &L,int i,ElemType e)/在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1i表长+1。if (!(p=GetElemp_DuL(L,i) /在L中确定第i个元素的位置指针preturn ERROR; /p=NULL,即第i个元素不存在if(!(s=(DuLinkList) malloc (sizeof (DuLNode) return ERROR;s-data=e;s-prior=p-prior; p-prior-next=s;s-next=p; p-prior=s;return OK;/ListInsert_DuL例子：动画演示* 在双向链表中删除结点Status ListDelete_Dul(DuLinkList &L,int i,ElemType &e)/删除带头结点的双链循环线性表L中第i个元素，i的合法值为1i表长。if (!(p=GetElemp_DuL(L,i) /在L中确定第i个元素的位置指针preturn ERROR;e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p); return OK;/ListDelete_DuL例子：动画演示2.8 顺序存储线性表与链式存储线性表的比较*顺序表的优点：存取数据速度快占用的存储空间小*顺序表的缺点：需占用连续存储空间插入操作需移动元素*链表的优点：不需占用连续存储空间插入操作不需移动元素*链表的缺点：存储数据麻烦、速度慢占用的存储空间大2.9 一元多项式的表示及相加1、 一元多项式的表示2、两个多项式的相加操作算法*算法思想：根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到和多项式中去。在此，和多项式链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况： 1）指针qa所指结点的指数值指针qb所指结点的指数值，则应摘取指针qa所指结点插入到和多项式链表中去；2）指针qa所指结点的指数值指针qb所指结点的指数值，则应摘取指针qb所指结点插入到和多项式链表中去；3）指针qa所指结点的指数值指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。*算法描述int cmp(term a,term b);/依a的指数值)b的指数值，分别返回-1、0和+1void AddPolyn(polynomial &Pa,polynomial &Pb)/多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成和多项式。ha=GetHead(Pa); hb=GetHead(Pb); /ha和hb分别指向Pa和Pb的头结点qa=NextPos(ha); qb=NextPos(hb); /qa和qb分别指向Pa和Pb中当前结点while(!Empty(Pa)&!Empty(Pb) /Pa和Pb均非空a=GetCurElem(qa); b=GetCurElem(qb); /a和b为两表中当前比较元素switch(*cmp(a,b)case -1: /多项式PA中当前结点的指数值小ha=qa; qa=NextPos(Pa,qa); break;case 0: /两者的指数值相等sum=a.coef+b.coef;if (sum!=0.0) /修改多项式PA中当前结点的系数值SetCurElem(az,sum); ha=qa;else /删除多项式PA中当前结点DelFirst(ha,qa); FreeNode(qa);DelFirst(hb,qb); FreeNode(qb); qb=NextPos(Pb,hb);qa=NextPos(Pa,ha); break;case 1: /多项式PB中当前结点的指数值小DelFirst(hb,qb); InsFirst(ha,qb);qb=NextPos(Pb,hb); break;/switch/whileif(!Empty(Pb) Append(Pa,qa); /链表Pb中剩余结点FreeNode(hb); /释放Pb的头结点/AddPolyn 例子：动画演示第三章:栈和队列3.1栈的概念1.定义：栈(Stack) 是限定仅在表的一端进行插入或删除操作的线性表。2.栈的示意图3.栈的抽象数据类型定义3.2栈的存储结构有两种存储结构:1、顺序栈顺序栈的类型定义：顺序栈的类型定义：/- - -栈的顺序存储表示- - -#define STACK_NINT_SIZE 100;/存储空间初始分配量#define STACKINCREMENT 10; /存储空间分配增量typedef structSElemType *base; /在栈构造之前和销毁之后，bade的值为NULLSElemType