《程序设计综合实践》-第1章 线性结构-第2次课

课前视频学习任务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：用链表实现栈时，应该使用单链表还是双链表？链首结点表示栈顶还是栈底元素？这个链表是否需要头结点？11课堂提问因为栈的基本操作涉及的都是单方向处理链表，因此，为了节省存储空间、简化处理，应该使用单链表而不是双链表实现栈；链首结点表示栈顶元素，这样，入栈、出栈运算时间复杂度均为O（1）；入栈、出栈操作都发生在栈顶，因此，在栈中单链表无需头结点。课堂提问问题5：队列采用顺序存储结构时如何保证入队列、出队列运算时间复杂度均为O（1）？如果队列顺序存储时只设置队首、队尾位置下标，如何区分队满、队空？课堂提问15图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;}17课堂提问问题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：编写程序分别采用顺序存储结构和