数据结构与算法实习概论内容

数据结构与算法概张路zhanglu[at]数据结构与算法概张路zhanglu[at]张教程》（国家十一五规划教材），高教社2011年1羊例人菜狼羊例人菜狼羊人空算法＋数据结＝程问题算法＋数据结＝程问题•数数据结构Structure）：•算法（algorithm）：对特定问题求解过程的程序（program）••课程目配合“数据结构与算法补充高级数据结构知提高实际动手能力课程目配合“数据结构与算法补充高级数据结构知提高实际动手能力和程序设的质数据结构的定数据的逻辑图树二叉树数据的存储数据的数据结构的定数据的逻辑图树二叉树数据的存储数据的数结图形图图形图北京大学版权所有，转载或翻印Page进度安第一周：数据结构与算法实习简第二周：大作业介绍，社交网络查询（两班合上第进度安第一周：数据结构与算法实习简第二周：大作业介绍，社交网络查询（两班合上第三周：程序设计实践与技巧（一）：编程和排第四周：国庆放第五周：高级数据结构（一）：线段树、树状数第六周：程序设计实践与技巧（二）：软件开发第七周：高级数据结构（二）：树堆、平衡二叉第八周：程序设计实践与技巧（三）：文件系第九周：高级数据结构（三）：后缀树、后缀数第十周：高级数据结构（四）：空间数据结第第九周：高级数据结构（三）：后缀树、后缀数第十周：高级数据结构（四）：空间数据结第十一周：问题建模专题讨第十二周：高级数据结构（五）：图的建第十三周：高级数据结构（六）：二部图问题求第十四周：数据结构应第十五周：期末总复习、大实习设计与项目演第十六周：大实习设计与项目演示、期末答9月22日上课安地点：一教形式：两班合9月22日上课安地点：一教形式：两班合成绩评定办平时POJ北大ACMPOJ综合上机题：期末成绩评定办平时POJ北大ACMPOJ综合上机题：期末闭卷考设计和实问题求数学建模（问题建模数据结构抽算法抽效率分编程设设计和实问题求数学建模（问题建模数据结构抽算法抽效率分编程设反复试验，推倒重来，直至算法分穷举法——万能回溯、搜索——跳过无解递归分治——自顶向下，问题化算法分穷举法——万能回溯、搜索——跳过无解递归分治——自顶向下，问题化动态规划——自底向上，利用中间结果，迅速构贪心法——动态规划的最优子结构——最优八皇后问在8×8格的国际象棋棋盘上放8个皇后，使其不能互相攻八皇后问在8×8格的国际象棋棋盘上放8个皇后，使其不能互相攻问有多少种摆法八皇后问题的一个QQQQQQQQ八皇后问题的一个QQQQQQQQ穷举法（枚举法共有44穷举法（枚举法共有44＝256种情有4!＝24种情最后输出合理的穷举法的代穷举问题域的所有解问题规模n，搜索空间ΣT=|Σ|t，O(n!)=穷举法的代穷举问题域的所有解问题规模n，搜索空间ΣT=|Σ|t，O(n!)=四皇后问题及其解空间解表示成一个4维向<x1,x2,x3,x4>（放置列号搜索空间：4叉树（排列树1243234341341241238434434423324223112112116953742324341314四皇后问题及其解空间解表示成一个4维向<x1,x2,x3,x4>（放置列号搜索空间：4叉树（排列树12432343413412412384344344233242231121121169537423243413142412132312112QQQQ搜索过程从结点1结点2足条件122x1=1,向382X41433423454637423323414411搜索过程从结点1结点2足条件122x1=1,向382X41433423454637423323414411331942Q搜索过程结点3不满1X2123823414334向4546374233234搜索过程结点3不满1X2123823414334向454637423323414411331942QXQ搜索过程结点9不1X21点23823414334446374233234搜索过程结点9不1X21点2382341433444637423323414411331942点5QQX搜索过程向下搜1X21继续向下搜索到结点14满足238234143344637423323414411搜索过程向下搜1X21继续向下搜索到结点14满足2382341433446374233234144113314942条件置第三个皇后5QQQ搜索过程12238234143344546374233234144113搜索过程1223823414334454637423323414411331942QQQX搜索过程1结点16回溯到结X212382341433445463742332341441搜索过程1结点16回溯到结X2123823414334454637423323414411331942QQX搜索过程回溯到结点1X212382341433445463742332341441搜索过程回溯到结点1X2123823414334454637423323414411331942Q搜索过程到结点1向下搜索到结点22向下搜索到结点满足条件，放置第382X41433423个皇后x=2搜索过程到结点1向下搜索到结点22向下搜索到结点满足条件，放置第382X41433423个皇后x=2454637423323414411331942QXXQ搜索过程向下搜索到结点30，满足条1皇后22382X4143342345搜索过程向下搜索到结点30，满足条1皇后22382X41433423454637423323414411331942QQQQ四皇后的解空间12243823414334546374233234四皇后的解空间1224382341433454637423323414411331942状态空●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●状态空●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●解空间根（root）问题状态states）：状态空间（statespace）：由根结点到其它解状解空间根（root）问题状态states）：状态空间（statespace）：由根结点到其它解状态（solutionstates）S：由根到S的路答案状态states）S：由根到S回溯法图“可行则进，不行则换、换不成则退简化为4皇后问题。搜索过程如下0123012●●●●01●●●●回溯法图“可行则进，不行则换、换不成则退简化为4皇后问题。搜索过程如下0123012●●●●01●●●●回溯算可行则进，不行则换不成则回溯算可行则进，不行则换不成则八皇后问题的表棋盘行列、皇后依次编上1,…，7A[0..n-1][0..n-表示n×n棋盘上的八皇后问题的表棋盘行列、皇后依次编上1,…，7A[0..n-1][0..n-表示n×n棋盘上的八后问题的全部解向量为xi表示皇后i所处的列对任何 j<8，及i≠j，有x1,…，x7)状态空间缩小为没有两个皇后在同一斜线上（斜率为重点）斜率+1，i+j={0,1,0123456701234567斜率+1，i+j={0,1,0123456701234567斜率-1，i-j={-760123456701234567斜率-1，i-j={-760123456701234567皇后的控制范皇后的控制范//前0..i-1行皇后占//斜率为+1//斜率为-1C[i-试探安排八个皇从第0行开始，逐步安排每行皇后对第i个皇后，找正确的位试探安排八个皇从第0行开始，逐步安排每行皇后对第i个皇后，找正确的位置(设为第jA[j]、B[i+j]、C[i-j+7]标记A[j]、B[i+j]、C[i-j+7]继续安排下一个皇后(第i+1个否则，如果找不到合适位置，应该退回(即“回溯”)到第i-1行的皇后，重新安回溯过如果8个皇后都排好了，则打印这种方回溯过如果8个皇后都排好了，则打印这种方抹掉前面试探留下的标记，即恢复A[j]B[i+j]、C[i-j+7]使得各行的皇后都能试探到各种可能的回溯法的框问题的解n元组(x0,x1,…，xn-1)：voidrectry(k){ 置X[k]为第一个可能回溯法的框问题的解n元组(x0,x1,…，xn-1)：voidrectry(k){ 置X[k]为第一个可能值while(X[k]可能值没有试完{设置X[k]所涉及的标记if((X[0],X[1]，…，X[n-1])是解elserectry(k+1);}}八皇后的递归算voidqueen(int{intfor(j=0;j<n;{if(place(i,j)X[i]=mark(i,j);八皇后的递归算voidqueen(int{intfor(j=0;j<n;{if(place(i,j)X[i]=mark(i,j);标记（i,j）if(i<n-queen(i+1);//接着试下一个elseprint(count);//打印一个解erase(i,j);//回溯，去掉刚才标记}}}四皇后时，函数执行失败情况下回溯过程模拟//for(j=0;试探x[1]=2,摆不了，函数试探x[1]=3,01四皇后时，函数执行失败情况下回溯过程模拟//for(j=0;试探x[1]=2,摆不了，函数试探x[1]=3,01●●●●皇后函数执行模拟(续X[1,3,0,2]……erase(3,试探下一个当然erase(2,试探其他，都失erase(1,erase(0,试探其他，都失败//x[0]=2,mark(0,2)x[1]=0,皇后函数执行模拟(续X[1,3,0,2]……erase(3,试探下一个当然erase(2,试探其他，都失erase(1,erase(0,试探其他，都失败//x[0]=2,mark(0,2)x[1]=0,mark(1,…….得到第二个解X=[2,0,3,0123八皇后算法如果只要求出一个解，这个程要作修八皇后算法如果只要求出一个解，这个程要作修多叉路口交通灯管理道路C、E把可以同时行驶而不发生碰撞的路线用一种颜用多少种颜色的交通灯，怎样分配给这些行驶不考虑过渡灯（例如黄灯DEACB多叉路口交通灯管理道路C、E把可以同时行驶而不发生碰撞的路线用一种颜用多少种颜色的交通灯，怎样分配给这些行驶不考虑过渡灯（例如黄灯DEACB13种行驶路D不能同如AB、BC；EB、可以同如AB、EACB13种行驶路D不能同如AB、BC；EB、可以同如AB、EACB不能同时走的路线(ABBC)(ABDA)(ABDE(ACDA)(ACDB)(ACEA)(ADEA)(ADEB)(AD不能同时走的路线(ABBC)(ABDA)(ABDE(ACDA)(ACDB)(ACEA)(ADEA)(ADEB)(ADA(BC(BCC(BDDA)(BDEB)(BDB(DA(DB(DA11112231312441111223131244地图着对一张地图用若干种颜色着要求相邻的区域用不同的颜地图着对一张地图用若干种颜色着要求相邻的区域用不同的颜地图着色问穷举法或回溯法来解地图着色问穷举法或回溯法来解决地图着色问题对于小型地图可以使地图着色：贪心用一种颜色给尽可能多的顶色选择某未着色的顶点并用该新地图着色：贪心用一种颜色给尽可能多的顶色选择某未着色的顶点并用该新颜色上扫描未着色的其他各顶点，考察它们2换一种颜色重复1，直到所有顶贪心法近似按1，2，3，4，5顺序着351245贪心法近似按1，2，3，4，5顺序着351245最优35121,3,4最优35121,3,4总结问题求理论、抽象和设计的三个层根据实际问题取舍数据结构和算在总结问题求理论、抽象和设计的三个层根据实际问题取舍数据结构和算在时间和空间复杂度之间进行平软件开发、工程的规范实践、自主学习、研究创新能课程资平时练习、期末机数据结构与算法国家精课程作业课程资平时练习、期末机数据结构与算法国家精课程作业和答疑，教学网的讨诚信端正学习态度、调动学习提倡讨论，但严禁抄可以讨论思但要亲自动诚信端正学习态度、调动学习提倡讨论，但严禁抄可以讨论思但要亲自动手实发现抄袭，严肃查抄袭者和被抄袭者本次作业或上机题计双-20以后的作业题会得到重点检严重的期评将给予不及格处作业要实习课1道大综合调试、要测4人一提交上机报告，“诚实代作业要实习课1道大综合调试、要测4人一提交上机报告，“诚实代码包含不同规模的测试若干道POJPOJ的账号就用自己的学上机题提交要00308096张宁1readme.txt2.诚实代码保证、源程序以及相关的项上机题提交要00308096张宁1readme.txt2.诚实代码保证、源程序以及相关的项目和例如，VC++中的.dsw,.ds文件，rc目录中的图像资源文件；Jbuilder中的.jpr或.jpx文件，特殊的Java包等等上机团队合作能专业能技术过硬,沟通能表达能力,全局不要成为团队的敬业精个人信团队合作能专业能技术过硬,沟通能表达能力,全局不要成为团队的敬业精个人信大作业编程风诚实代码保内部文档要过程代码要面向对象的代码要大作业编程风诚实代码保内部文档要过程代码要面向对象的代码要按时提交作业，严禁抄规定时间的课间交书面作或之前在课程网站提交电子计分标准10按时提交作业，严禁抄规定时间的课间交书面作或之前在课程网站提交电子计分标准10准时提交，满分可达10分（个别分延迟3天之内提交，满分可达7分；延迟7天之内提交，满分可达3分；7天之后提交或不交抄袭20分5分作业提交期限的说有利于同学及时讨论复破例申请——要在deadline提个别有困作业提交期限的说有利于同学及时讨论复破例申请——要在deadline提个别有困难的同(2)生病或事教1赵海王腾宋国杰，《数据高教教1赵海王腾宋国杰，《数据高教社2011年1月，ISBN7-04-030214-1。2.张铭、赵海燕、王腾蛟，《数据结构与－－学习指导与习题解析》，高等教育出版2005年9月。ISBN7-04-017829-X3.张铭、王腾蛟、赵海燕，《数据结构与算序设计实践》，机械工业出版社，2003年95.M.H.Alsuwaiyel,Algorithms序设计实践》，机械工业出版社，2003年95.M.H.Alsuwaiyel,AlgorithmsTechniquesandAnalysis电子工业出版社影ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms高等教育出版社影印，2002年5DonaldE.Knuth教材：张赵海王腾宋国杰，《数据结与算法实验教程》，国家十一五规划教材，教材：张赵海