程序设计综合实践（第二版）（上篇共上中下3篇）

第1章线性结构程序设计课程实践课前视频学习任务1.1线性表概念（时长：13分30秒）1.2算法和算法分析（时长：8分50秒）1.3线性表的顺序存储（时长：10分10秒）1.4.1线性表的链式存储-单链表的概念（时长：8分15秒）1.4.2线性表的链式存储-单链表基本操作的实现（时长：9分30秒）1.4.3线性表的链式存储-单链表应用举例（时长：4分15秒）课堂测试（5分钟）课堂提问（10分钟）课堂提问问题1：什么是数据、什么是数据元素和数据对象、什么是数据的逻辑结构和存储结构？主要有哪些类型存储结构？参考：计算机需要处理数值、文字、图形、图像、声音等各种形式的信息，这些计算机程序处理的信息是对客观事物的符号化编码表示，也称为数据（data）。构成数据的、具有相同性质的基本单元称为数据元素（dataelement）。性质相同的数据元素集合组成数据对象（dataobject）。数据结构(datastructure)是相互之间存在一种或多种特定关系的数据元素的集合，包含数据对象和关系两个组成部分，可以用二元组（D，S）来表示，是数据的逻辑结构，数据结构在计算机物理存储器里的实际存储方案称为数据的存储结构。通常采用两种存储结构：顺序存储结构和链式存储结构。课堂提问问题2：什么是抽象数据类型？抽象数据类型ADTList有哪些基本操作？如何遍历ADTList?参考：抽象数据类型（abstractdatatype,ADT）是与具体计算机内部表示、实现方式无关的数据类型，由一个逻辑上的数学模型和定义在该模型上的一组操作构成。抽象数据类型ADTList的基本操作包括：创建空表Create、清空Clear(L)、销毁线性表Destroy(L)、拷贝线性表Copy(L)、判空IsEmpty(L)、求长度Length(L)、获取起始位置BeginPosition(L)、获取结束位置EndPosition(L)、迭代下一位置NextPosition(L,pos)、获取元素位置LocatePosition(L,i)、定位元素位置LocateElem(L,e)、获取元素GetElem(L,pos)、设置元素SetElem(L,pos,e)、插入元素InsertBefore(L,pos,e)、删除元素Delete(L,pos)组成。可通过BeginPosition获取起始位置，然后用while循环控制迭代访问位置所在元素、更新位置，直到结束位置。课堂提问问题3：什么是算法？算法如何描述？算法如何评价？为什么时间复杂度是衡量算法性能的一个非常重要指标？参考：算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。算法可以采用多种表述方式：用人类的自然语言描述，用程序流程图来描述，参照某种程序设计语言的伪代码描述。对算法的评价，除了正确性、健壮性、可读性外，还有时间复杂度和空间复杂度。时间复杂度反映了随着问题规模的增长，实现算法的程序运行所需要花费时间增长的函数，很大程度上反映了算法的效率，因此，时间复杂度是衡量算法性能的一个非常重要指标。课堂提问问题4：线性表使用完成后为什么还需要销毁？参考：线性表在创建完成后，经常需要增加元素、删除元素等，为了保存这些元素和它们之间的关系，经常需要动态分配内存资源，线性表使用完成后，需要通过销毁操作释放这些资源，供程序的其它模块或其它程序使用，否则，会造成内存泄漏，这是C/C++程序员需要解决的关键问题之一。课堂提问问题5：单链表头结点起什么作用？为什么插入到单链表中结点一般需要动态分配？参考：在单链表中插入、删除元素时，需要修改插入、删除位置前一个结点的指针域，单链表中增加头结点，可保证插入、删除位置前始终存在这样的结点，简化单链表插入、删除操作算法。在单链表的生命周期中，它需要跨越多个函数，结点所在内存空间需要跨越函数存在，因此，不可以存放在局部变量中，而且，单链表中结点数在不停变化中，也不可以存放在全局变量中，因此，需要动态分配空间，不需要时动态释放。样例代码回顾（10分钟）样例程序回顾Ex1.1-抽象数据类型线性表的顺序实现参考代码：SeqLish.h、SeqList.c、main.c/p/hrHFQKghQH//p/zj2twDsJcq//p/HBbSRpW6MY/样例程序回顾Ex1.2-抽象数据类型线性表的链表实现参考代码：list.h、list.c、main.c/p/FnW2JsxkDY//p/d6tvjVvQtK//p/RkmFNxGJrq/样例程序回顾Ex1.3-单链表应用参考代码：/p/6DHM8qMn8K/作业解题思路15分钟习题1：编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将负整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。解题思路：要求体现模块化程序设计，采用样例中方法实现有序单链表的插入函数、显示函数和销毁函数，然后在主程序中调用相应函数，实现指定功能。习题2：编写程序，在第1题基础上合并2个单链表，合并前后单链表保持递增或相等次序，显示合并前后单链表。注意不可存在内存泄漏。解题思路：要求体现模块化程序设计，在第一题基础上，实现单链表合并函数。合并函数可采用两个指针分别指向两个单链表头结点后结点，结点中元素较小者添加在结果线性表尾部，指针向前移动一个结点，循环进行，直到一个单链表尾部，再把另一个单链表剩余结点代表的元素添加在新线性表尾部；（待续）（续）合并算法的时间复杂度应该可以达到O（m+n），其中m、n分别是两个线性表的长度。可以有两种方案：一是采用破环原两个合并前单链表，用原两个单链表中结点存储新线性表中元素，释放剩余的一个头结点；二是不破环原两个单链表，申请新结点存储新线性表中元素。在主程序中先调用相应函数，建立两个单链表，显示两个单链表，再调用合并函数合并两个单链表，显示合并后单链表，最后，销毁有关单链表。习题3：在第1题建立2个单链表基础上，设计和实现就地逆置单链表函数，即利用原单链表结点建立元素次序相反的单链表。编写程序，建立2个单链表，就地逆置这2个单链表，显示逆置前后的各单链表。注意不可存在内存泄漏。解题思路：要求体现模块化程序设计，第1题基础上，实现就地逆置单链表的函数，方法是先将原头结点后单链表截断，原头结点用于表示新单链表，再循环将截断后单链表中结点一个个插入在新单链表头部，算法时间复杂度可以达到O（n）。最后，在主程序中调用相应函数，实现指定功能。习题4：

编写程序，在前面建立1个带头结点单链表的基础上，设计一个实现单链表分离算法的Split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求Split算法时间复杂性达到O（n）,程序不可存在内存泄漏。解题思路：要求体现模块化程序设计，第1题基础上，实现单链表分离算法的Split函数，方法是先建立表示空线性表的单链表，指定从原单链表头结点开始，判断指定结点的后继结点中元素是否为偶数，如果为偶数，将指定结点的后继结点从原链表删除，添加在新链表尾部；如果不是偶数，则指定结点改为原结点的后继结点，循环进行，直到指定结点是原链表中最后一个结点为止，算法时间复杂度可以达到O（n）。最后，在主程序中调用相应函数，实现指定功能。习题5：约瑟夫环是个经典的问题。有M个人围坐成一圈，编号依次从1开始递增，现从编号为1的人开始报数，报到N的人出列，然后再从下一人开始重新报数，报到N的人出列；重复这一过程，直至所有人出列。求出列次序。本题要求用循环单链表实现。提示：开始时将循环单链表的指针变量设为空，设计实现尾部添加一人函数Append，添加第1人时，将结点的指针域指向自己，后面新添加人员时，在循环单链表指针变量所指尾部后添加新结点，并始终将循环单链表指针变量指向新添加结点，对应M个人的循环单链表中有M个结点；报数时，报到指定数后输出对应结点里的人员编号，并将该结点从链表中删除。题目输入包括M、N两个正整数，题目要求按出队列顺序输出他们的编号。如样例输入103；程序应该输出：36927185104课堂实践答疑解惑谢谢观看第1章线性结构程序设计课程实践课前视频学习任务1.4.4线性表的链式存储-双向链表应用举例（时长：10分26秒）1.5栈和队列（时长：7分50秒）课前视频学习任务课前视频学习任务样例代码回顾（10分钟）样例程序回顾Ex1.4-双链表表示无符号大数的加法实现参考代码：UBigNumber.h、UBigNumber.c、test.c/p/2V4ZHDmK96//p/V9b9Sp7SRS//p/fvbKwjbwx6/课堂提问（10分钟）课堂提问问题1：无符号大数为什么需要使用双链表存储结构而不是单链表存储结构？单链表适合从链首结点往链尾结点方向的单向处理;遇到同时需要反方向处理应用时，可以采用双向链表存储结构。无符号大数从高位到低位的各位数字组成了线性表，用线性表知识可解决无符号大数的表示和操作。无符号大数位数不确定，可以采用链表表示。无符号大数显示时需要从高位到低位次序进行，运算时又需要从低位到高位运算，因此，无符号大数可以采用双向链表存储结构。课堂提问问题2：无符号大数样例Ex1.4中如何避免内存泄漏？参考：样例中采取了函数内建立链表-无符号大数，将链表返回函数调用者，由函数调用者来通过销毁链表操作释放链表资源的策略，避免内存泄漏。课堂提问问题3：样例Ex1.4中为何需要无符号大数规范化表示的_Normalize函数？参考：无符号大数采用规范化表示，利用_Normalize函数去除高位多余0，同时保证至少含一位数，这样，任何无符号大数只有一种唯一表示方式，有利于无符号大数的比较、显示等处理，符合程序设计中模块化处理原则，也有利于在无符号大数基础上进一步拓展有符号大数、超高精度实数等应用。课堂提问问题4：用链表实现栈时，应该使用单链表还是双链表？链首结点表示栈顶还是栈底元素？这个链表是否需要头结点？36课堂提问因为栈的基本操作涉及的都是单方向处理链表，因此，为了节省存储空间、简化处理，应该使用单链表而不是双链表实现栈；链首结点表示栈顶元素，这样，入栈、出栈运算时间复杂度均为O（1）；入栈、出栈操作都发生在栈顶，因此，在栈中单链表无需头结点。课堂提问问题5：队列采用顺序存储结构时如何保证入队列、出队列运算时间复杂度均为O（1）？如果队列顺序存储时只设置队首、队尾位置下标，如何区分队满、队空？课堂提问40图1.11循环队列示意图课堂提问队列采用顺序存储结构时，为避免大量元素移动，保证入队列、出队列运算时间复杂度均为O（1），将数组视为首、尾相接，循环使用，因此，也称为循环队列。循环队列中，为区分队列空和队列满两种状态，可以将只有一个空余单元时状态视为队满状态，因此，队首、队尾位置相同时视为队空；队尾的后一个位置为队首时视为队满。C++标准模板库（STL）提供了类和队列的类模板。循环队列的入队列操作算法描述如下：//将元素x入pQueue所指队列，成功返回1，失败返回0boolEnQueue(structSeqQueue*pQueue,DataElemx){if((pQueue->iRear+1)%MaxSIZE==pQueue->iFront)return0;//下一位置已是队首位置，队满pQueue->iDatasA[pQueue->iRear]=x;//保存元素pQueue->iRear=(pQueue->iRear+1)%MaxSIZE;//调整队尾位置return1;}42课堂提问问题6：思考什么场景会使用栈，什么场景会使用队列？参考：递归——栈，多线程处理——队列课堂测试（5分钟）作业解题思路15分钟习题6：又见约瑟夫环：有M个人围坐成一圈，编号依次从1开始递增直到M，现从编号为1的人开始报数，报到N的人出列，然后再从下一人开始重新报数，报到N的人出列；重复这一过程，直至所有人出列。所有出列的人再次按出列顺序围坐成一圈，并从第1人开始报数，这次为报到K的人出队列，然后再从下一人开始重新报数，报到K的人出列；重复这一过程，直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数；N、K可能为1。题目要求按最后出队列顺序输出他们的编号，每个测试用例结果占一行，每个编号占4位。如样例输入1035；程序应该输出：74161053289。解题思路：体现模块化程序设计，用循环单链表代表人员组成的圈，也就是圆形队列，指针指向循环单链表尾部结点，设计实现Append函数，实现在循环单链表尾部添加代表指定元素的一个结点，返回新循环单链表的尾结点指针。在主程序中先建立两个空循环单链表，先循环M次调用AppendTail建立初始圆形队列，在第5题基础上，再通过调用AppendTail函数将游戏过程中出圆形队列的人加入新圆形队列尾部，循环进行，直到原圆形队列为空；然后，对新圆形队列进行同样的操作，出圆形队列的人组建起新圆形队列；最后，调用显示函数，显示结果圆形队列中所有人员，销毁单链表即可实现。习题7：好玩的约瑟夫环：有M个人，编号分别为1到M，玩约瑟夫环游戏，最初时按编号顺序排成队列；每遍游戏开始时，有一个正整数报数密码N，队列中人依次围坐成一圈，从队首的人开始报数，报到N的人出列，然后再从出列的下一人开始重新报数，报到N的人出列；重复这一过程，直至所有人出列，完成一遍游戏，所有出列的人形成新队列；游戏可能玩很多遍，每遍有新报数密码。求若干遍游戏完成后队列次序。题目输入包括若干个正整数（至少1个）,第一个正整数为玩游戏人数M，后续每个正整数为每遍游戏报数密码，报数密码可能为1，题目要求按出队列顺序输出他们的编号。样例输入：10352；样例输出：46529137810。解题思路：在第6题基础上，用循环单链表代表人员组成的圈，也就是圆形队列，指针指向循环单链表尾部结点，先建立一个非空的循环队列，每轮游戏时，从非空循环队列出队列的人员在出队列后组成一个新循环队列；循环进行，最后留下的非空循环队列就是结果队列；最后，调用显示函数，显示结果圆形队列中所有人员，销毁循环单链表即可实现。习题8：无符号大数加、减运算。程序设计中经常遇到无符号大数加、减运算问题，请在样例程序Ex1.4基础上实现无符号大数减运算。题目要求输入两个无符号大数，保证一个大数不小于第二个大数，输出它们的和、差。样例输入1234567890987654321333888999666147655765659657669789687967867样例输出13822236566473119911235769675331086912125327996651544201031799。解题思路：在无符号大数相加样例基础上，实现两个无符号大数相减运算函数，类似两个无符号大数相加算法，设一个借位变量iCarry，初值为0，从两个双向链表尾部结点开始，两相应位、借位相减形成结果中新的高位，不够减时再向高位借位；从低位到高位，循环进行，直到减数处理完毕；如果被减数还有未处理位，同样需要考虑借位因素后，将结果位保留在结果数高位，最后，进行规整化处理形成最终结果双链表。在主函数里，通过调用相应函数实现功能即可。习题9：

有符号大数加、减运算。请在样例程序Ex1.4基础上实现无符号大数比较运算（小于、小于等于、等于、大于、大于等于），并进一步实现有符号大数的加、减运算。题目要求输入两个有符号大数，输出它们的和、差。样例输入-1234567890987654321333888999666147655765659657669789687967867样例输出-1086912125327996651544201031799-1382223656647311991123576967533解题思路：在样题和第8题基础上，继续实现无符号大数比较函数，再建立新结构体BigNumber，用来表示有符号大数，包含两个采用：用于表示绝对值的UBigNumber类型value成员和用于表示符号位的整型sign成员；然后，分别设计算法实现两个有符号大数相加、相减。两个有符号大数相加时，如果符号位相同，结果有符号大数符号也一样，绝对值部分为两个绝对值相加；两个有符号大数符号位不同时，比较两个数的绝对值，结果数的绝对值为原先两数中大绝对值减小绝对值，符号位与原先大的有符号数相同；两个有符号大数相减，相当于加上改变符号后的减数，就可以实现。在主函数里，通过分析输入字符串，得到有符号大数的符号位和绝对值，建立有符号大数，调用相应加、减函数实现运算，再调用显示函数显示有符号大数，最后，注意销毁有关有符号大数，释放链表。习题10：编写程序分别采用顺序存储结构和链式存储结构实现抽象数据类型栈和队列，再利用栈和队列，输入若干个整数，将输入后的正整数和负整数分别保存起来，输入完成后，首先将以输入相反的次序输出所有保存的正整数，再以输入相同次序输出所有保存的负整数，正整数和负整数输出各占一行。解题思路：分别设计栈和队列结构，如何用函数实现抽象数据类型栈和队列的各项基本操作，再在main函数里使用这些基本操作函数，完成应用所需处理。课堂实践答疑解惑谢谢观看第2章递归程序设计程序设计课程实践课前视频学习任务2.1栈与递归（时长：9分40秒）2.2分治法（时长：10分22秒）课前样例学习任务Ex2.1汉诺塔Ex2.2无符号大数Karatsuba乘法课堂测试（5分钟）课堂提问（10分钟）课堂提问问题1：全局变量、静态变量、局部变量和动态分配空间的生存期是什么？存放在什么样的存储空间内？（全局空间、栈空间、堆空间）参考：全局变量、静态变量在程序开始运行时建立，存放在程序专设全局空间内，直到程序运行结束才撤销；函数内局部变量在程序执行到局部变量所在函数时在栈中建立，在程序执行完局部变量所在函数代码，离开时撤销，也称栈变量；动态分配空间在堆中，在动态分配成功时在堆中建立，直到释放时才撤销，可跨函数使用，C/C++程序不释放动态分配内存，会造成内存泄漏。课堂提问问题2：递归函数执行过程中，递归函数的每个参数只有一份存储空间还是可以有多份存储空间？在程序调试时，是否可以看到函数调用关系和参数值？参考：程序执行时，每次遇到函数调用，不论是普通函数调用，还是递归函数调用，系统都会在运行栈上为本次函数调用分配空间来保存：本次函数调用执行完毕后返回地址、形参变量和函数返回值变量、函数体内局部对象，因此，递归函数的每个参数在程序运行过程中，在栈中可能有多份存储空间，当时有效值只有一个，函数退出时，参数在栈顶的存储空间撤销，参数值恢复为栈中保存的前一份存储空间中的数值，在程序调试时，各开发工具都支持查看函数调用关系和参数值，有利于程序调试。课堂提问问题3：使用分治法求解问题时，一般将问题分解为差不多规模的两个子问题好还是分解为规模相差较大的两个子问题合适？请举例说明？参考：使用分治法求解问题时，一般将问题分解为差不多规模的两个子问题比较好，这样，可以快速减小问题规模。如二分查找、第三章中的快速排序，都体现出这一点。有序表查找如果分解为查找规模为1、n-1的两个待查找子集，就会退化为顺序查找效率，时间复杂度不再是O（logn），而是O（n);快速排序如果划分后的待排序子集中有一个规模很小，算法时间复杂度不再是O（nlogn），而是O（n*n)。样例代码回顾（15分钟）样例程序回顾Ex2.1汉诺塔参考代码：/p/vf27KRWNp3/样例程序回顾Ex2.2无符号大数Karatsuba乘法参考代码：UBigNumber.h、UBigNumber.c、UBigNumber2.c、test.c/p/ZXvFcZntVx//p/kVgK5MqJNY//p/qbwm3mb6v6//p/qQbtwcsXhW/作业解题思路15分钟习题1：给定一个含n个整数顺序存储的线性表，按分治法思路，采用二分策略，设计一个求出其最大值和最小值算法，编写相应测试程序。要求分别设计出其中求最大值、最小值组合的递归算法和非递归算法。解题思路：单个元素时，最大值、最小值就是本身；超过1一个元素时可将线性表二分，分别求取前、后两个部分的最大值、最小值，再通过比较得到整个线性表的最大值、最小值，线性表范围可用数组名、起始下标、结束下标表示。递归算法比较简单，非递归算法可参照Hanoi塔非递归思路实现。习题2：编写程序，读入矩阵行数、列数及所有矩阵元素，矩阵中所有元素均为正整数，计算并打印出矩阵中的最大连通块数。注：如果两个元素值相同，并且上、下、左、右四个方向之一相邻，则称两个元素是连通的;连通关系是可传递的，一个元素的连通元素，也是与它连通元素的连通元素。最大连通块定义为所有连通元素组成的最大集，单个元素也可成为最大连通块。要求分别设计出求连通块数的递归、非递归算法。样例输入：76444444413214412214411114412234433334444444样例输出：6解题思路：可遍历矩阵所有元素，如果该元素未标识过（所有元素初始状态均未标识过），则将该元素所在连通块所有元素标识出来，并增加连通块统计数。标识一个连通块时，可采用递归方法，先标识该元素，再递归从上、下、左、右四个方向未标识的连通元素出发进行标识；采用非递归方法标识连通块时，可通过栈进行，先将待标识元素（包括它的位置）入栈，然后循环进行下列处理：从栈中取出元素，若该元素已标识（注意，同一个元素可能多次入栈），则进行下轮循环；若该元素未标识，则标识该元素，再将该元素上、下、左、右四个方向未标识的连通元素（包括它的位置）入栈，进行下轮循环。这里采用的是深度优先策略，也可采用广度优先策略（借助于队列），或通过集合合并算法实现。习题7：*在有些应用中，需要解决有符号大数的运算和比较问题，请在样例Ex2.2基础上，实现有符号大数的加、减、乘运算和比较，输入两个有符号大数，输出它们的和、差、积。解题思路：参照第1章第9题，建立结构体BigNumber，用来表示有符号大数，包含两个成员：用于表示绝对值的UBigNumber类型value成员和用于表示符号位的整型sign成员；然后，分别设计算法实现两个有符号大数相加、相减、相乘。补充习题：

汉诺塔非递归算法的程序实现解题思路：在第一章实现抽象数据类型ADTStack基础上，设计一个汉诺塔子问题结构体，在栈中保存待求解汉诺塔子问题结构体，按照教材上汉诺塔非递归算法，编写程序。课堂实践答疑解惑谢谢观看第2章递归程序设计程序设计课程实践课前视频学习任务2.3.1回溯法-八皇后问题（时长：12分22秒）2.3.2回溯法-01背包问题（时长：6分31秒）课前样例学习任务Ex2.3八皇后问题Ex2.40-1背包问题课堂测试（5分钟）课堂讨论课堂讨论讨论1：八皇后问题主要解题过程问题引入八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。基本思路回溯法基本思路：2.第二行再放一个且不能与第一个皇后相互攻击3.第三行再放一个

。。。。。n.第n行放一个，当第n行放不下的时候，取消n-1行的皇后，在原第n-1皇后的下一个位置重新放一个皇后，直到放到最n-1行的最后一个位置，当还不行的时候，就取消第n-2行，……当n-2行的皇后在n-2行的最后一个位置的时候，就取消n-3(n-2在最后一个位置，那么n-3行的一定不在最后一个位置)。再重新寻找n-2行的皇后的位置。

。。。。。

。。。。。直到找到最后一个皇后。1.第一行先放一个皇后课堂讨论回溯法基本思路：找完第一种解法，重新开始寻找第二种解法，直接第一个皇后放在第一行的第2个位置，寻找第三种解法时首先在第一行的第3个位置放第一个皇后。。。。直到寻找第n个解法。课堂讨论详细步骤：1.判断新的皇后是否与已经存在的皇后互相攻击，加入是第一个则不用判断直接加入。第1个皇后课堂讨论详细步骤：2.第二行新生成的皇后，然后与第一行判断是否攻击，是的话，向右移动一个格子，否则添加上去。第2个皇后课堂讨论详细步骤：3.第三行从左至右从第一个格子开始，判断是否与上面所有的皇后相互攻击，是的话，向右移动一个格子，否则添加上去。第3个皇后课堂讨论详细步骤：3.第三行从左至右从第一个格子开始，判断是否与上面所有的皇后相互攻击，是的话，向右移动一个格子，否则添加上去。第3个皇后。。。

。。。课堂讨论详细步骤：8.到第八行，新生成一个皇后，判断是否与上面所有的皇后相互攻击，没有则添加。有则向右移动一个格子。当移动至一个不相互攻击的格子，则一个解法已经生成。向后则寻找第二个方案，将第8行的皇后删除，新生成的皇后在刚才最后一个皇后的右边，为什么在右边呢？因为左边刚才已经判断过都失败了，所以新生成的在右边，然后在判断是否与上边的皇后相互攻击。课堂讨论详细步骤：9.当向右移动最后一个格子而且与上边的皇后相互攻击，则删除掉此皇后，然后把上一行的皇后向右移动一个格子，第8行从左向右从0开始生成一个新的皇后。然后步骤8.课堂讨论详细步骤：10.直到第一行的皇后走到第一行的最后一个，第二行也找到最后一个格子的皇后，而且失败，则是所有解法都寻找完成。课堂讨论回溯法基本思路：012300000100002000030000课堂讨论讨论2：0-1背包问题主要解题过程问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?使用典型的三种物品为例，问题描述如下：设有三个物品，其重量、价值分别如右表所示；请选择物品放入背包，使背包中物品总重量不超过30，但价值最大。重量价值物品11645物品21525物品31525课堂讨论讨论2：0-1背包问题主要解题过程每个物品都可以被选择中（1）或者不选（0），理论上如果不加任何限制的话一共有八种可能（2×2×2），但在搜索的过程中要时刻注意总重量不可超过30，在这个基础上使其总价值最大。可以从第一个物品开始，先选中它，其重量是16，小于30，没有问题，然后在选择第二个物品，其重量为15，二者总重量为31，超过30，所以不能选择第二个物品，同理第三个物品也不能选，也就是说在选中第一个物品的前提下，另外两个物品就都不能再选了，这是八种理论可能情况中的一种；以此类推，不选第一个物品，在此基础上选择第二个物品，总重量为15，没有问题，再选第三个，此时总重量为30，也没有问题；对照这两种情况，前者总价值为45，后者总价值为50课堂讨论讨论2：0-1背包问题主要解题过程对于上述的物品问题，在此二叉树结构中可以简单地理解为：从A出发，往左子树方向走说明选中了A，往右子树方向走说明没有选中A，即“左选右不选”，落实到上图中就是1代表选中0代表未选中；上述的第一种情况，即只选中第一个物品的情况对应上图的A->B->E->K；

当搜索路径到达K后，得到了一组值，即总重量为16，总价值为45，此时，由于已经到了树的叶子结点，因此需要回溯直到根，再继续进行后续的搜索；在后续搜索过程中，一方面要进行结点的判断，另一方面，一旦得到了一个合符要求的价值，则与前一次搜索所得到的结果进行比较，如果比前一次搜索得到的值大，则取代，反之，继续搜索直到整个树搜索结束所得到的最大值即为问题的解。例：n=3，C=20，(v1,v2,v3)=(45,25,2)，(w1,w2,w3)=(12,7,7)，求X=(x1,x2,x3)使背包价值最大？ABFGHJLKMNOx1=1x1=0x2=1x2=0x3=1x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=0当前最优价值当前背包剩余容量当前剩余价值当前背包价值045+25+2=72200027845C45272000+27<45，剪枝D4521704570A70284545+2<70，剪枝1<7，不可达I700170课堂讨论讨论2：0-1背包问题主要解题过程整体思路01背包属于找最优解问题，可用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：

基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。

在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。

为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。课堂讨论讨论2：0-1背包问题主要解题过程整体思路01背包属于找最优解问题，可用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：

基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。

课堂讨论讨论2：0-1背包问题主要解题过程整体思路

在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索；否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包；由此得到的价值是右子树中解的上界。为了便于计算上界，可先将物品依其单位重量价值从大到小排列，此后只要按顺序考察各物品即可。课堂讨论讨论2：0-1背包问题主要解题过程整体思路-0-1背包问题的解空间可用子集树表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。为了便于计算上界，可先将物品依其单位重量价值从大到小排列，此后只要按顺序考察各物品即可。应用实例—0-1背包问题解空间：子集树可行性约束函数：上界函数：template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//计算上界,剪枝依据。

Typewcleft=c-cw;//剩余容量

Typepb=cp;//以物品单位重量价值递减序装入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}装载问题的上界函数为当前载量cp+剩余集装箱重量r<=当前最优装载量bestp;对于0-1背包问题，更好的上界为：当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。样例代码回顾样例程序回顾Ex2.3八皇后问题参考代码：/p/7PfVgwz7WM/样例程序回顾Ex2.40-1背包问题参考代码：/p/GrDWVVVsW2/作业（三选一）解题思路习题1：*迷宫问题。如图所示，迷宫可以用一个矩阵表示，迷宫中有一个入口、一个出口，迷宫内有通道，也有墙，迷宫中行走时可以从当前位置的上、下、左、右四个方向的通道通过。迷宫中的通道和墙可以用矩阵中元素0和1表示，编写程序，输入迷宫矩阵和入口、出口位置，找到一条从入口到出口的路径，没有这样的路径时，提示迷宫设置有问题。解题思路：迷宫数据可存放在文件里，可采用试探回溯法（深度优先策略）找出入口到出口的一条路径（或所有路径），为避免重复经过，可设置经过标记。本题也可采用广度优先策略，分别求出经过1、2、3...n步可以到达的位置，最后可求出最短路径或判断出不存在这样的路径。附加拓展选项：用图形化方法显示迷宫和动态搜索过程，图形库可参考第8章采用MFC、QT或其他简易图形库。习题2：排列组合问题之排列部分。编写程序，输入正整数n（n<10），输出由1、2、3...n组成的所有排列，统计并输出所有排列。解题思路：采用回溯法实现。先将1、2、3...n放入一个线性表中，如果已试探取出整数个数达到要求，则输出一种排列；否则，依次循环取出线性表中剩余数中一个，再递归处理剩余数的排列问题。注意，回溯时，试探取出的数需放回线性表原先位置，恢复未取状态。习题3：

排列组合问题之组合部分。某单位有若干人员，现执行某任务需要一定人数人员。编写程序，输入单位总人数和每位员工名字，再输入执行任务所需人数，输出所有可能派出人员方案，统计并输出方案数。派出人员方案中，先输入人员排在前面，后输入人员排在后面。解题思路：假设单位总人数为n，需要派出人员数为m，可将单位人员依次编号为1、2、3...n，这实际是组合问题，同样可以采用回溯法实现。先将1、2、3...n放入一个线性表中，如果已试探取出整数个数达到要求m，则输出一种组合；否则，依次循环取出线性表中剩余数中一个，这里取出的数必须大于方案中前面已取出数，再递归处理剩余数的组合问题。注意，回溯时，试探取出的数需放回线性表原先位置，恢复未取状态。习题4：马踏棋盘问题。假定棋盘大小为8乘8，先将”马”放在任意指定的方格中，按照”马”走棋的规则将”马”进行移动。要求每个方格只能进入一次，最终使得”马”走遍棋盘的64个方格。qi'p任意一个位置，“马”最多有8个方向可以跳动，所以每次都要依据这最多8个方向进行选择。解题思路：马踏棋盘问题可以采用试探-回溯法解决。对于快速寻解，每个点用固定的优先顺序进行搜索下一步方向对运算时间的影响很大，可以考虑采用随机化的策略；也可以考虑采用先搜索下一步的可行方案数少的方向。课堂实践答疑解惑谢谢观看第3章查找和排序程序设计课程实践课前视频学习任务3.1查找和简单排序（时长：10分36秒）3.2归并排序和快速排序（时长：16分55秒）3.3其它特殊排序方法（时长：11分50秒）课前实践任务预先实现各排序算法，准备课堂讨论和实现评测。课堂测试（5分钟）课堂提问（30分钟）课堂提问问题1：顺序查找和二分查找的区别。//算法3.1在n个元素的数组A中顺序查找是否存在元素关键字为key，存在返回下标；不存在返回-1intSequentialSearch(ElemTypeA[],intn,KeyTypekey){for(i=0;i<n;++i)if(A[i].key==key)returni;return-1;}课堂提问//算法3.2在n个元素的递增排序数组A中进行二分查找，存在时，返回下标；不存在时返回-1intBinarySearch(ElemTypeA[],intn,KeyTypekey){low=0;high=n-1;while(low<=high){middle=(low+high)/2;//获取中间位置下标if(A[middle].key==key)returnmiddle;//查找到if(A[middle].key>key){high=middle-1;//继续在前半段查找}elselow=middle+1;//继续在后半段查找}return-1;//确定没有}课堂提问问题2：冒泡排序方法思路//算法3.3冒泡排序。对存放n个元素的数组按关键字递增排序voidBubbleSort(ElemTypeA[],intn){for(i=0;i<n-1;++i)//冒泡遍数控制for(j=0;j<n-i-1;++i)//子序列范围{if(A[j].key>A[j+1].key)//元素次序不符swap(A[j],A[j+1])//交换元素}}/zcl_love_wx/article/details/83576962课堂提问问题3：选择排序方法思路//算法3.4简单选择排序。对存放n个元素的数组按关键字递增排序voidSelectSort(ElemTypeA[],intn){for(i=0;i<n-1;++i)//选择遍数控制{minI=i;//初始最小元素位置for(j=i+1;j<n;++i)//选择比较范围{if(A[minI].key>A[j].key)minI=j;//迭代最小元素所在位置}swap(A[i],A[minI]);//交换两个元素}}//算法3.4直接插入排序。对存放n个元素的数组按关键字递增排序voidInsertionSort(ElemTypeA[],intn){for(i=1;i<n;++i)//插入遍数控制{x=A[i];//取出待插入元素，便于前面元素后移j=i-1;//从子序列最后一个元素位置开始while(j>=0&&x.key<A[j].key)//需要后移元素{A[j+1]=A[j];//后移一个位置--j;//从后往前查找插入位置}A[j+1]=x;//完成插入}}123课堂提问问题5：归并排序算法思路//算法3.5归并排序。对存放n个元素的数组按关键字递增排序voidMergeSort(ElemTypeA[],intlow,inthigh,ElemTypeAux[]){if(low>=high)return;//规模不超过1，无需排序m=(low+high)div2;//二分法划分MergeSort(A,low,m，Aux);//前一半子序列排序MergeSort(A,m+1,high，Aux);//后一半子序列排序Merge(A,low,m,high,Aux);//归并两段有序子序列for(i=low;i<=high;++i)A[i]=Aux[i];//移动回原数组}125

//归并排序中有序段合并子算法voidMerge(ElemTypeA[],intlow,intm,inthigh,ElemTypeAux[]){i=low;//前段有序子序列起点j=m+1;//后段有序子序列起点k=i;//归并结果起始下标while(i<=m&&j<=high){//较小元素先转移至结果缓冲区i