考试时间：（黄双喜）11月1日(周二)9:50，六教C.数据结构的定义有限集G，以及G上元素关系的集合S，定义数据结构(D,S)。最常见的G上元素关系是有序偶：a1,a2表示两个元素一种有序关系，例如：--数组（或链表）中相邻两个元素的关系，由于有前后之分，所以是有序的；--二叉树的父子节点的关系，同样是有序的；--有向无权图中的边。当然也可能有其他的G上元素关系，例如含有指向兄弟节点的指针的树（需要定义三元组）S是这样的关系的有限集合，而不是这种关系本身。2.第k小的全排列问题：给定自然数n=1，试给出算法，求出{1,2,...,n}的第k小的全排列，k是比较小的一个数。两个全排列的大小按照字典序比较。解释：全排列个数是n!，当n稍大时就会溢出。而这种题问的是第k小的全排列，k是（相比与n!）很小的一个数（不会溢出）。思考：既然k很小，肯定是不能也不应该遍历所有的全排列的。因此，应该从最小的全排列(1,2,...,n)开始，逐个向上寻找。问题转化为：给定一个全排列，如何找到字典序比它大的全排列中的最小的那一个（即把n!个全排列递增排序，找出它右边紧邻的那一个）算法：对于这个全排列，从右向左开始寻找，每次找相邻的两个数(p,q)，直到第一次出现pq的情况。出现这种情况后，把p和q互换位置，然后把q右侧的所有数（不含q）颠倒顺序。举例：已知一个全排列(1,3,6,5,4,2)，找出字典序比它大的全排列中的最小的那一个。从右侧开始，先找(4,2)，不满足pq，再左移一点，找(5,4)，还不满足。直到找到(3,6)是满足pq的，把3和6互换，然后把之后的数(5,4,2)倒序成(2,4,5)。这样得到(1,6,3,2,4,5)就是想要的答案！同理也很容易推广到找到第k大的全排列。复杂度分析：当n较大时，由于k很小，所以“动过”的数其实只有靠右的少数几个。记“动过”的位数为r，则r!大约为k。这样给出复杂度的上界为O(rk)，根据Stirling公式，比O(k*log(k))还小。这个基本模型很强大，如果稍加约束条件，仍然能很好地工作，比如说栈混洗问题。3.栈混洗问题问题：入栈队列是(1,2,...,n)，试找到所有可能出栈队列中第k大的那一个。同样，两个序列按照字典序比较大小。（刘烨斌OnlineJudgeQ6.1）分析：我们已有找出全排列中第k大的算法了。一个出栈队列（栈混洗队列）和全排列相比，多了哪些约束条件呢？显然是：任何一个元素右侧的元素中，比它小的元素都应该是降序排列的。（“栈混洗”条件）那么同样，我们可以从最大的出栈队列(n,n-1,...,2,1)开始，去找第k大的出栈队列。仍然需要寻找字典序依次递减的全排列，只不过只有当符合“栈混洗”条件时才把计数变量加1。判定队列是否满足“栈混洗”条件需要费一些时间，如果考虑到“动过”的位数只有r，最后复杂度的上界是O((r^3)*k)，其中r!与k同阶。同样根据Stirling公式，这一上界小于O(k*log(k))。4.KMP算法记ptrT为指向T字符串的一个字符指针，ptrP为指向P字符串的一个字符指针，其中T为较长的一个字符串，P为模式串。目标是快速地在T中找到与P相同的一个字串。传统的字符串查找算法需要反复回退比较，而且每次都必须保守地回退到最安全地地方，再开始新一轮地比较。为什么要回退那么多步（ptrT回退到本轮比较地起始点的下一位，ptrP回退到字符串开头）？因为不知道该回退多少步，只能按最坏情况，选择最保守的办法。那么这个该回退的步数是否依赖于字符串T呢？如果依赖，那没办法，只能每趟遍历都算一次。如果不依赖，那就好办了，因为这个信息独立于T，可以事先算好，这样就可以不用每趟遍历都算，从而避免冗余的计算了。结论是：不依赖。直接上一个精心构造的例子：第一轮匹配：当发现D和E不匹配时，前面几位一定是匹配了的。但这时候，能否就把T的这部分"ADAD"直接抛掉，从后面的"ADAE"开始比呢？不行，因为T结尾的AD可能和P开头的AD能匹配上。第二轮匹配应该是：而不是：关键点就在于T正在匹配的部分的结尾可能和P开头的能匹配上（例如字串"AD"）。还要注意到：T正在匹配的部分的结尾，就是P失配字符前的部分！（除掉失配的那单个字符）因而这和T无关，充要条件就是：P的开头的几个字符和P失配字符前的几个字符相同（和T无关）由于P的每个字符都可能失配，因而我们把每个字符失配时，上述相同的那部分的长度可以事先记录下来，放到next[]数组里面。根据next数组，第二轮匹配可以直接从位置开始，而不需要按传统算法那样，从位置开始。推送里不方便长篇大论，但是还是推荐大家仔细阅读教材（读不懂紫皮书时，推荐读邓俊辉老师的教材：越厚的教材，读起来越容易读懂），也可以上网查找相应的资料，例如Wikipedia（见“阅读原文”）。5.补充：数组从0开始计数而是从1开始计数？紫皮书的习惯是从1开始，绿皮书（邓俊辉老师的教材）的习惯是从0开始。从1开始，与数学上的习惯一致，并且第0个元素可以存一些额外信息。（R/MATLAB等语言采用）从0开始，便于计算指针偏移量（特别是多维数组！），对于数组a[n]，一个指向a[n]位置的指针可以用来指示末尾，非常方便。（C/C++/Java/Python等采用）我建议大家认准一种习惯，保证能够适应就好了。最后祝大家考试顺利！考试时间：（黄双喜）11月1日（周二）9:50，六教C点击阅读原文，查看维基百科词条：KMP算法
据说赞赏数与期中考试成绩成正比
赞赏
人赞赏
治疗白癜风最好的医院是哪里郑州白癜风治疗中心
转载请注明：http://www.92nongye.com/tlfc/204614204.html
