数据结构——基于Python语言（微课版）教学教案.docx

教案课程名称适用专业院（部）教研室授课教师数据结构智能科学与技术计算与信息科学学院计算机系副教授课程名称数据结构学分3总计：48学时讲授：48学时上机：。学时实验/训：0学时其它：。学时类别（请打J）公共课口公共选修课回专业基础课专业必修课专业方向选修课口实验实训课（仅限本科）公共课公共选修课口专业基础课口专业必修课口专业选修课口实验实训课（仅限高职）授课对象（请打J）回本科高职其他使用教材参考资料教材：马宏茹，吴璞，姚保峰.数据结构M.山东：中国矿业大学出版社,2022参考书：1 .严蔚敏.数据结构（C语言版）M.北京：清华大学出版社,20072 .马世霞.数据结构M.北京：机械工业出版社,20153,自编.数据结构实验指导书.福州：福州理工学院,20194.近期的期刊杂志、网站以及参考文献等教学方法教学手段课堂教学以网络视频观看、理论课讲授和实验操作实践的线上线下混合式进行，教师针对课程重点难点讲解数据结构的基本原理和知识，预先安排教学视频学习，然后再较系统地介绍软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍常用的多种查找和排序技术，并对进行性能分析和比较，内容非常丰富。让学生明白该门课程将为后续课程的学习以及软件设计水平的提高的重要性，说明数据结构课程是计算机专业的一门核心的关键性课程，提高学生的学习兴趣和积极性。还采用启发式、交互式和讨论式的教学方法引导学生掌握获取所学知识,通过布置相关实验报告，培养学生的自学和编程能力。考核方式考核要求：期末总成绩=笔试（闭卷60%）+平时成绩（40%）平时成绩包括（线上学习：章节任务点（30%）+章节测验&作业（20%）；线下学习：分组任务（30%）+课堂表现（20%）内容比例（建议）：线性表30%；树15%；图15%；查找20%；排序20%题型比例（建议）：选择题20%,填空题30%,简答题30%,编程题20%学生创新精神与实践能力的培养方法采用启发式、交互式和讨论式的教学方法引导学生掌握获取所学知识，通过布置相关实验报告，培养学生的自学和编程能力。数据结构课程教案授课时间第1周授课方式（请打Y）团讲授口上机口实验/训I其它（讨论交流）课时安排授课题目：TL绪论（C语言基础）教学目的与要求：C语言基础：输入与输出、结构、指针、动态存储分配教学重点与难点：重点：结构、指针难点：指针、动态存储分配教学内容备注1：C语言基础结构2：输入与输出3：指针4：结构5：动态存储分配案（末页）一.VisualC÷+6.0开发环境VisualC+6.0是微软公司推出的一个功能强大的可视化软件开发工具。VisualC+6.0不仅是一个C、C+编译器，它还有一个非常好的集成开发环境DeveloperStudio,包括编辑器编译器、调试器以及程序向导等组件，用它可以在编写C、C+程序时对程序的结构进行可视化的管理。二.C语言代码结构1.说明1）以#开始的语句是预处理命令。这些命令是在编译系统翻译代码之前需要由预处理程序处理的语句。2） /*/表示注释部分，不运行；3） main（）表示主函数，函数体由一对大括号扩起来。4）第2行Printf是C语言的标准输出函数；5）分号“;”是C语言的执行语句和说明语句的结束符。6 ）n为回车换行，引号中其它内容作为字符串原样输出。7 .格式特点1）习惯用小写字母，大小写敏感2）不使用行号，无程序行概念3）可使用空行和空格4）常用锯齿形书写格式8 .优秀程序员的素质之一：1）使用TAB缩进2） 对齐3）有足够的注释4）有合适的空行三.输入与输出1.格式输出函数1）格式：Primfr格式控制串”，输出表）2）功能：按指定格式向显示器输出数据3）返值：正常，返回输出字节数；出错，返回EOF（J）2.格式输入函数1）格式：SCanf（"格式控制串”，地址表）2）功能：按指定格式从键盘读入数据，存入地址表指定的存储单元中,并按回车键结束3）返值：正常，返回输入数据个数四.指针1 .指针与指针变量1）指针：一个变量的地址2）指针变量：专门存放变量地址的变量2 .&与*运算符1） &：取变量的地址，单目运算符，结合性:自右向左2） *：取指针所指向变量的内容，单目运算符，结合性:自右向左3）两者关系：互为逆运算五.结构1.语法：struct结构名数据成员列表；（变量名表列）；2 .指向结构的指针3 .访问结构变量的数据成员4 .用typcdef定义新数据1）将int型定义为COUNT,这二者等价，在程序中就可以用COUNT作为类型名来定义变量,如：COUNTa,b；2）因此，可用typedef来定义一个类型名来代表一个结构体类型六.函数与参数传递1 .C语言中函数定义包括4个部分：函数首部（函数名、形参列表、返回类型）和函数体2 .在C语言中调用函数时传递给形参表的实参必须与形参在类型、个数、顺序上保持一致3 .参数传递有两种方式：1）按值传递方式：把实参的值传递给函数局部工作区相应的副本中。函数使用副本执行必要的计算。因此函数实际修改的是副本的值，实参的值不变。2）按地址传递参数：传递的是实参的地址。函数通过地址存取被引用的实参。执行函数调用后，实参的值将发生改变。4 .函数结果的带出方式1）如果返回一个结果值，可以使用return返回方式带出一个函数结果值2）若函数结果需要带出多个值，该怎样实现？3）全局变量方式带出4）通过地址传递带出（数组方式、结构体方式、指针方式）两类方式之一来实现。七.动态存储分配1 .malloc（）和free（）2 .静态数组与动态数组的区别1）静态数组是在定义是就已经在栈上分配了空间大小，在运行时这个大小不能改变2）动态数组的大小是在运行是给定，即，运行时在堆上分配定的存储空间，同时运行时还可以改变其大小推荐阅读书目：（1）马世俊.数据结构.机械工业出版社，2015（2）自编.数据结构实验指导书.福州理工学院.2019（3）近期的期刊杂志、网站以及参考文献等数据结构课程教案授课时间第1周授课方式(请打Y)团讲授口上机口实验/训I口其它(讨论交流)课时安排1授课题目：T2绪论教学目的与要求：1：学习数据结构的概念2：学习算法的基本概念3：了解数据结构与算法在程序设计中的作用教学重点与难点：重点：数据结构的内容、时间复杂度难点：逻辑结构与物理结构的联系与区别、时间复杂度教学内容备注1：数据结构的基本概念：(1)：线性表(2)：栈与队列(3)：树和图2：算法：(1)：查找(2)：排序3：C语言基础：(1)：输入与输出(2)：结构(3)：指针(4)：动态存储分配案（末页）一.数据结构与算法的关系NiklausWirth（美国）：算法+数据结构=程序设计程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略（怎么解决?）数据结构：问题的数学模型（数据怎么表示？）例子：求一组（n个）整数中的最大值。算法：通过依次比较两个数的大小，找到最大值数据结构（模型）：用什么样的数据结构来表示整数？二.数据结构的基本概念1.数据数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。包含数值、字符、声音、图像等一切可以输入到计算机中的符号集合。例如对C源程序C编译程序源探序（.c）C链接方片.目标程序可执行程片（.obj）（.exe）2.数据元素数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：WfMI学号姓名性别籍贯出生年月住址IOl赵虹玲女河北1983.11北京3 .数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数集合：N=0,±1,±2,.）无限集字符集合：C='A',B','Z'有限集4 .数据结构数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。例如表结构：5 .数据类型数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型决定了两个方面的内容：取值范围一允许使用的一组运算.琏.鱼里的基击强提美娄，dw)6. 抽象数据类型(AbStraCtDataType-ADT)ADT定义了一个数据对象、数据对象中各元素间的结构关系以及组处理数据的操作。抽象数据类型与数据类型实质上是一个概念，只不过ADT更为广义，不仅限于各种不同计算机处理器中已定义并实现的数据类型，还包括用户自己定义的复杂数据类型。有两个重要特征：。数据抽象：强调程序处理的实体的本质特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。：信息隐蔽：将实体的外部特征和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。三.数据结构的内容数据结构：带结构的数据元素的集合；数据元素间的相互关系包括三个方面：数据的逻辑结构、数据的物理结构、数据的运算集合逻辑结构例如：一个含12位数的十进制数可以用3个4位的十进数表示：1234,5678,90111(1234),2(5678),3(9011)。在a1，az和a3之间存在“次序”关系：<aa2><a2,a3>*123456789011567812349011aa2a3a2na3数据结构的逻辑结构可归结为以下四类： :线性结构：LoC。树形结构：“OP :图形结构(网状结构)：.一广口 :集合结构：逻辑结构也可归结为：广线性结构一一线性表、栈、队、字符串、数组、广义表逻辑结构YI非线性结构树、图物理结构反映成分数据在计算机内的存储安排。逻辑结构在存储器中的映像。例如：用二进制位(bit)的位串表示数据元素(32i)10=(5i)=(Io100oooi)2X=(IOl)8=(001OOOOO1)2四.算法的基本概念是规则的有限集合，是为解决特定问题而规定的一系列操作。解决问题的一种方法或一个过程(策略)。特性： 有限性:有限步骤之内正常结束，不能形成无穷循环。 确定性:算法中的每一个步骤必须有确定含义，无二义性得以实现。 输入:有多个或O个输入。 输出:至少有一个或多个输出。 可行性:原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。一个好的算法般应具有几个基本特征：1 .正确性2 .可读性3 .健壮性(鲁棒性)4 .高效率与低存储量五.算法的性能评价1.耗费的时间T(n,I)算法性能C(n,I)1.占用的空间S3,D个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。语句频度:指该语句在一个算法中重复执行的次数。例如：两个矩阵相乘算法语句对应的语句频度1for(i=0;i<n;i+)n2for(j=0;j<n;j+)M3cilj=O;n：for(k=O;k<n;k+)n3Wujlivlhfwi-j，总执行次数：T,=2n3+2H2÷n时间复杂度：语句频度的数量级，算法的时间量度。T(n)=O(f(n)六.时间复杂度、语句频度练习数据结构中常用的时间复杂度频率计数有7个：O(I)常数型O(n)线性型0()平方型O(rP)立方型0(2指数型O(Iogzn)对数型O(nlog211)二维型按时间复杂度由小到大排列：O(I)常数型VO(Iog2n)对数型VO(n)线性型VO(nlog211)二维型<0(1?)平方型V0(113)立方型VOQn)指数型七.复习C语言常用知识点1 .变量2 .指针变量3 .函数与参数传递4 .函数结果的带出方式5 .结构体的定义6 .结构体指针7 .结构体成员的访问8 .关键字typedef9 .动态存储分配推荐阅读书目：(1)马世霞.数据结构.机械工业出版社，2015(2)自编.数据结构实验指导书.福州理工学院.2019(3)近期的期刊杂志、网站以及参考文献等数据结构课程教案授课时间第2周授课方式（请打Y）团讲授口上机团实验/训I其它（讨论交流）课时2安排授课题目：T3_线性表（顺序表）教学目的与要求：1：掌握线性表的基本概念及实现的方式2：掌握顺序表的实现教学重点与难点：重点：线性表的顺序存储结构难点：线性表的顺序表的运算教学内容备注1：线性表的概念及抽象数据类型2：顺序表存储结构3：顺序表基本运算教案(末页)线性结构是最简单、最常用的一种数据结构。-特点：除第一个元素无直接前驱、最后一个元素无直接后继外，集合中其它每个数据元素均有惟一的直接前驱和惟一的直接后继。一.线性表的概念及逻辑结构定义：n(nO)个类型相同的数据元素的有限序列。线性表的逻辑结构图为: n>0时，笫一个元素无直接前驱，最后一个元素无直接后继，其余的每个数据元素只有一个直接前驱和一个直接后继。 n=0时，为空表。 表长：表中元素的个数n。 表中元素类型相同。二.顺序表： 指用一组地址连续的存储单元依次存储线性表中的各个元素 数据元素：逻辑结构相邻=物理存储单元相邻 结构定义#definemaxsize100线性表可能达到的最大长度typedefstruct(ElemTypeelemmaxsize；线性表占用的数组空间intlast；记录线性表中最后一个元素在数组elem中的位置(下标值)，空表置为SeqList;一一注意区分元素的序号和数组的下标，如al的序号为1,而其对应的数组下标为0。基本运算_查找按序号查找GetData(LJ):-要求查找线性表L中第i个数据元素L.elemi-lsKL->elemi-l按内容查找LOCate(L,e):-要求查找线性表L中与给定值e相等的数据元素-若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如插入引列：已知线性表(4,9,15,28,30,30,42,51,62),需在第4个元素之前插入一个元素“21”。序号123456-8910插入元素前4915283030425162插入元素后491521283030425162需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置,序号123456-8910491528I30I30425162移动元素4915283030425162插入元素491521283030425162删除 引例：将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。序号123456-8910491521283030425162删除28后4915213030425162一一合并 引例：已知有两个顺序表LA和LB,其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC,要求LC也是非递减有序排列。la0821254962LB163754728290下标：01234Ol23451.C0816212537495462728290下标：012345678910推荐阅读书目：(1)马世霞.数据结构.机械工业出版社，2015(2)自编.数据结构实验指导书.福州理工学院.2019(3)近期的期刊杂志、网站以及参考文献等数据结构课程教案授课时间第3周授课方式（请打Y）0讲授口上机口实验/训I口其它（讨论交流）课时2安排授课题目：T4_线性表（单链表）教学目的与要求：1：掌握单链表的实现教学重点与难点：重点：线性表的非顺序存储结构难点：线性表的单链表的运算教学内容备注1：单链表基本概念2：单链表存储结构3：单链表基本运算本栏不够填写，可续页教 案（末页）采用链式存储结构的线性表称为链表。现在我们从两个角度来讨论链表：1 .从实现角度看，链表可分为动态链表和静态链表；2 .从链接方式的角度看，链表可分为单链表、循环链表和双链表。一.单链表的定义heack,an 由结点（Node）组成:datanext*-' 数据域（data）:存储结点的值 指针域（next）:直接后继的地址（或位置）链表中的每个结点只有一个指针域，我们将这种链表称为单链表。 头指针（head）：指向链表头结点的指针。 结点可以连续存储，也可以不连续存储。 结点的逻辑顺序与物理顺序可以不一致。例：以下分别为单链表CJD，JE，）的逻辑结构与物理存储结构: 逻辑结构：物理结构：存储地址，52S3555«59616264707173757678»IeI75IA611BS21E0ID70_“k-7“站点”结点W结点2。结点3结点4，头指针he<d>58*结构定义：typedefstructNode/结点类型定义/ElemType具体类型据实际设定,如int,char等ElemTypedata；structNode*next；Node,*LinkList:/LinkList为结构指针类型Node:结点LinkList:表二.单链表的基本运算：1 .初始化单链表对单链表进行所有操作之前，必须先进行初始化，即生成空表!1.-Qo)InitList(LinkList*L)*L=(LinkList)malloc(sizcof(Node);(*L)->next=NULL;2 .建立单链表初始化单链表后，可采用结点插入的方式实现单链表插入的基本步骤：1 .在单链表中找到要插入的位置；一(因为每次都是在表头插入，所以此时这个步骤可省)2 .产生新结点3 .在新结点中存储数据元素；4 .修改指针指向实现插入例：在以下这张带头结点的空表中插入第一个结点，结点中存储接收的字符-(假设接收的字符为A，)l-步骤2：产生新结点1 h¼sH-n描述的代码：s=(Node*)m疝Qe(SiZeof(Node);步骤3：在新结点中存储数据元素lH-llS-S3描述的代码：s->data=c;/c存储接收的字符：，步骤4：修改指针指向实现插入1.HJ310描述的代码：s->next=L->next;/L->next=OL->next=s;可按如上步骤，继续插入第二、第三个结点，让学生们自己试着操作。3 .单链表插入操作在带头结点的单链表L中第i个位置前插入一个数据元素插入的基本步骤：1 .在单链表中找到要插入的位置；-第M个结点，并由指针Pre指示2 .产生新结点3 .在新结点中存储数据元素；4 .修改指针指向实现插入例：在以下带头结点的单链表的第i个结点前插入新元素e,即在ail与ai之间插入新结点1.-QH,B步骤1：在单链表中找到要插入的位置l3hQBprepre=L;k=0;ZhiLe(nre!=NULL&&k<i-l)pre=pre->next;k=k+l;若当前Pre为空，表示已找完还未数到第i个，说明插入位置不合理if(!pre)Printf(“插入位置不合理！”)；returnError;)步骤2：产生新结点lH-2EBEBs=(Nocle*)malloc(sizeof(Node);步骤3：在新结点中存储数据元素s-m1.3-2123£0pres->data=e;步骤4：修改指针指向实现插入s->next=pre->next;pre->next=s;让学生们思考：步骤4中的两句代码是否可调换次序？4.单链表删除在带头结点的单链表L中删除第i个结点删除的基本步骤：1 .在单链表中找到要删结点的前一个结点;-由指针pre指不2 .将要删结点从链表中断开；3 .释放结点推荐阅读书目：（1）马世霞.数据结构.机械工业出版社，2015（2）自编.数据结构实验指导书.福州理工学院.2019（3）近期的期刊杂志、网站以及参考文献等数据结构课程教案授课时间第4周授课方式（请打Y）团讲授口上机口实验/训I其它（讨论交流）课时安排授课题目：T5_线性表（循环链表和双向链表）教学目的与要求：1：了解循环链表2：了解双向链表教学重点与难点：重点：循环单链表、循环双链表难点：关于循环单链表、循环双链表的操作实现教学内容备注1：循环链表2：双向链表教医1末尤一一改造单链表结构，从而可实现查找直接前驱等操作(1) 循环单链表将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点单循环链表的示例带表头结点的单循环链表(非空表)广-1(空表)假设链表长度为n在表头插入或删除，时间复杂性O(I)，在表尾插入或删除，时间复杂性O(n)若将循环单链表作如下修改：带尾结点的一般形式HZO*,.一1ajH-aJh.-IarJ*(rear->next)*rear°"则有： 在表头插入或删除，时间复杂性0(1) 在表尾插入或删除，时间复杂性0(1)所以，在循环单链表中附设尾指针有时比附设头指针会使操作变得更简单在单链表的基础上，引导学生们对单链表的查找、建表、插入、删除等操作进行修改，从而得到关于循环单链表的基本操作。(2) 循环双链表在单链表的每个结点里再增加一个指向其前趋的指针域prior0这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表(DoubleLinkedList)O数据结构课程教案授课时间第4周授课方式（请打Y）团讲授口上机口实验/训I口其它（讨论交流）课时安排授课题目：T6_线性表（应用与比较）教学目的与要求：1：熟悉顺序表和链表的区别2：熟悉一元多项式的存储教学重点与难点：重点：各种线性表的优缺点难点：各种线性表在不同情况下的优势及应用教学内容备注1：顺序表和链表的比较2：线性表链式存储方式的比较3：一元多项式的存储教卷1末页2-顺序表与链表的比较： 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。 动态链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会产生溢出。.一当线性表的长度变化较大，难以估计存储规模时，采用动态链表作为存储结构较好。 顺序表可以随机存取，对表中任一结点都可以在0(1)时间内直接存取；链表中的结点需从头指针起开始顺着链找才能取得。.一若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表存储结构 顺序表进行插入、删除时，平均要移动表中近一半的元素；而链表只需要修改指针。.一需要频繁进行插入、删除操作的线性表，宜采用链表存储结构。二.各种链表比较：名称链表找表头结点找表尾结点找P结点前驱结点带头结点单链表LL-TIeXtO(I)一重循环QaD股P结点的IIeXt域无法找到P结点的前躯带头结点循环单链表LLrnext0(1)一重循环Q(O)顺P结点的next域可以找到P结点的前驱：QO)带尾指针的循环单链表RR-nextO(I)RO(I)底P结点的next域可以找到P结点的前驱：Q(II)带头结点Ln>nextL-priorP-prior双向循环链表Lo(i)O(I)O(I)三.应用：一元多项式可按升累的形式写成: Pn(x)=p+p1xe1+p2xe2+.+pnxen,其中ei为第i项的指数(且lele2.en)Pi是指数ei的项的系数运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。-1* O - 11 1 -> 22 r 一_, 5 17 7O1112275L7推荐阅读书目:数据结构课程教案授课时间第5周授课方式(请打Y)团讲授口上机口实验/训I其它(讨论交流)课时安排授课题目：T7_线性表(栈)教学目的与要求：1：学握顺序栈的定义及存储结构2：掌握链式栈的定义及存储结构3：掌握递归的定义4：掌握递归的应用教学重点与难点：重点：栈的定义及存储结构和基本操作难点：递归算法教学内容备注1：栈的定义2：栈的表示和实现：(1)：顺序栈(2)：链栈3：栈的应用：(1)：递归算法(2)：递归的概念(3)：递归过程的实现(4)：递归的应用(5)：设计递归算法的注意点案(末页)一.归纳复习单链表请指下所列各图中的线性表名称：last012345Ilast-(tI-÷(t,÷-11.I"II1二.栈(1) 栈的定义 只允许在线性表的一端进行插入和删除 允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。 特点：后进先出(LIFO)练习：设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列。A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A练习：设有一空栈，现有输入序列1,2,3,4,5,经过PUSh,push,pop,push,pop,push,push后,输出序列是.（2） 顺序栈的定义 数组elem存储栈元素 e1em0为最早入栈的元素，即为数组的底部数组向下标增大方向扩展 如图：栈底elem0> defineStackSizc50;typedefstruct/elem用来存放栈中元素StackElementTypeelemStack_Size;inttop;/*栈顶位置(下标),top=-l时，表示空栈*/ SeqStack;（3） 顺序栈的基本操作初始化一个空的顺序栈voidInitStack(SeqStack*S)S->top=-1;判断栈是否空？空则返回L否则返回0intIsEmpty(SeqStackS)returnS->top=1;判断栈是否满？满则返回1,否则返回0intIsFull(SeqStackS)returnS->top=S->maxtop-l;进栈-若栈满返回0,否则新元素X进栈并返回1intPush(ScqStack*S,StackElementTypex)if(S->top=S->maxtop-1)returnFALSE;S->top+;S->elemS->top=x;/加入新元素returnTRUE;/出栈-删除栈顶元素datatopintPop(SeqStack*S,StackElementTypc*x)将栈S的栈顶元素弹出，放到X所指的存储空间中说S->top1)returnFALSE;clse*x=S->elemS->top;S->top-;returnTRUE;)读栈顶元素intGctTop(ScqStack*S,StackElemcntTypc*x)if(S>>top=-1)returnFALSE;else(*x=S->e1emS->top;returnTRUE;)三.链栈的定义：栈顶栈底tp-W<BW-AS-链式栈无栈满问题，空间可扩充.插入与删除仅在栈顶处执行.即：在链表的表头进行！.链表的表头指针就作为栈顶指针栈空操作：top->next=NULL;typcdcfstructnodeStackElemcntTypcdata;structnode*next;LinkStackNodc;typcdcfLinkStackNodc*LinkStack;四.链栈的基本操作补充-初始化一个空的链栈1.inkStackInitStack()(LinkStacktop;top=(LinkStack)malloc(sizeof(LinkStackNode);top->next=NULL;returntop;补充-判断栈是否空？空则返回1,否则返回0intIsEmpty(LinkStackS)returntop->next=0;)补充-判断栈是否满？满则返回1,否则返回0只要系统有可用空间，链栈就不会出现溢出。进栈一将数据元素X压入栈top中intPush(LinkStacktop,StackElementTypcx)LinkStackNode*temp;temp=(LinkStackNodc*)malloc(sizcof(LinkStackNodc);if(temp=NULL)申请空间失败returnFALSE;tcmp->data=x;temp->next=top->next;top->next=temp;returnTRUE;/出栈，将栈顶元素弹出，放到X所指的存储空间intPop(LinkStacktop,StackEIementType*x)1.inkStackNode*temp;temp=top->next;if(temp=NULL)栈为空returnFALSE;top->next=temp->next;*x=temp->data;free(temp);returnTRUE;-g¾r-rffii>返回栈顶元素intGetTop(LinkStacktop,StackEIementType*x)if(top->next=NULL)returnFALSE;else(*x=top->next->data;returnTRUE;)五.多栈技术若同时使用两个以上的栈，采用顺序栈处理极不方便。采用多个单链表实现多个链栈是很好的实现途径！01234E2-" E3 NULL名 BtdH-HINULLM-I怒 f* NULL5六.递归的概念在定义自身的同时又出现了对自身的引用七.递归在数学方面的应用(1)：Xn=X*X*X*.*X*X(2):S(n)=l+2+.+(n-l)+n一一要计算xn+l,或S(n+1),可利用前面计算过的结果以求得答案:xn+l=xn*xS(n+1)=S(n)+(n+l)(3):阶乘函数I1,当=0时I*1)!,当21时求解阶乘函数的递归算法longfact(intn)if(n=0)return1;elsereturnn*fact(n-l);.递归在数据结构方面的应用用指针实现的链表结构本质上是递归定义的.打印单链表：voidPrintLinkList(LinkListL)if(L->next!=NULL)print(L->ncxt->data);PrintLinkList(L->ncxt);计算链表长的函数ListLcngth(L)intcount(LinkListf)if(x=0)return0;return1+count(Qnext);九.递归过程的实现 递归函数调用时，按照“后调用先返回”的原则处理调用 递归过程必须通过栈来实现十.递归的应用 Hanoi塔问题：设a,b,c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小的叠在一起各圆盘从小到大编号为l,2,.,n如图所示：abc 目的：将塔座X上的这一叠圆盘移到塔座Z上，并仍按照同样顺序叠置. 在移动圆盘时应遵守以下移动规则： 规则：每次只能移动1个圆盘： 规则：任何时刻都不允许将较大的圆盘压在较小的圆盘之上; 规则：在满足移动规则和的前提下，可将圆盘移至x,y,z中任一塔座上。H-一,设计递归算法的注意点1 .寻找分解方法：将原问题分解为子问题2 .设计递归终止条件。十二.递归的消除递归算法把复杂的问题分解为简单问题，分而治之，因此，对求解某些复杂问题，递归算法的分析