首页 数据结构与算法]

数据结构与算法]

举报
开通vip

数据结构与算法] 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® i 《数据结构与算法》常见问题解答 URL: http://db.pku.edu.cn/mzhang/ds/resource/FAQ.pdf 张 铭 修订于 2006 年 12 月 4 日 ©作者保留一切权力。 未经授权,不得转载、翻印。® 违者必究! ...

数据结构与算法]
《数据结构与算法》常见问 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® i 《数据结构与算法》常见问题解答 URL: http://db.pku.edu.cn/mzhang/ds/resource/FAQ.pdf 张 铭 修订于 2006 年 12 月 4 日 ©作者保留一切权力。 未经授权,不得转载、翻印。® 违者必究! 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® ii 目 录 一、教材信息...................................................................................................................................1 1. 教材出版信息...........................................................................................................1 2. 每位作者负责的章节...............................................................................................1 3. 课程网站(课程讲义、算法源代码等) ...............................................................1 4. 关于教材内容问题(包括错误和疑问)等数据结构技术性问题 .......................1 二、 数据结构的一般问题.............................................................................................................2 1. 伪代码到底是什么?...............................................................................................2 2. 什么是“程序的鲁棒性”? ...................................................................................2 3. 教材中多处提到 log n 是以 10 为底的对数吗? ...................................................2 4. 请问效率分析是只要记住结果还是要会自己推导? ...........................................2 5. 关于算法...................................................................................................................3 6. 怎样写抽象数据类型 ADT?..................................................................................3 7. 关于编程经验问题...................................................................................................3 8. 不同小组的作业难度不同,怎么算成绩? ...........................................................3 三、线性表和串疑难解答...............................................................................................................4 9. 教材第 1 版第 1 次印刷 p19 倒数 L1,P21,P62 等处的 “算子”一词,本身 是纯数学概念,C++中似乎不应如此解释。................................................................4 10. p24 算法 2.1,插入之前 curr 的值不确定?.....................................................4 11. assert 断言的使用问题。.....................................................................................4 12. 教材第 26 页链表部分 first 指针的含义?.........................................................4 13. 什么叫循环队列?如何区分空满循环队列? ...................................................5 14. 关于递归转化.......................................................................................................5 15. 关于双端队列和双栈的区别 ...............................................................................6 16. 关于 String 类 .......................................................................................................6 17. 教材为什么要自己定义一个 String 类? ...........................................................7 18. 局部对象在语句块结束执行后将被释放。算法 3.9 能 return temp 吗?........7 19. 第 3.3 和 3.4 节的代码可以简洁明一些 .............................................................7 20. KMP 算法疑问 .....................................................................................................8 21. 关于线性表和串的作业题意 ...............................................................................8 三、二叉树和树问题.......................................................................................................................9 22. 关于满二叉树的定义...........................................................................................9 23. 关于教材第 96 页的二叉树非递归后序周游的算法 .........................................9 24. 教材第 115 页倒数第 9 行 GetParent()是私有的,不能这么调用吧?.........10 25. 教材第 116 页中部的两段代码边界条件的讨论 .............................................10 26. 关于最大值堆和最小值堆的问题 .....................................................................11 27. 二叉树和树的计数问题.....................................................................................11 28. 教材第 139 页树的链式存储:指针、索引和下标。 .....................................11 29. 学习指导上 p96 习题 5.4...................................................................................12 四、图的问题.................................................................................................................................12 30. 关于教材中第 146 页算法 5.7 的 PrevSibling 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 中 while (pointer)循环 ....12 31. 教材第 181 页中的 DFS 中写了 PreVisit 和 PostVisit .....................................13 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® iii 32. Dijkstra 算法怎么保证从第二组所有的顶点中选取到源点距离最小? .......13 33. 第 190 页倒数第八行应该是多余的 .................................................................13 34. 图的题意.............................................................................................................14 五、排序和检索问题.....................................................................................................................14 35. 关于教材第 218 页的算法 7.11 Shell 排序的增量 ...........................................14 36. 快速排序的分区结果唯一吗? .........................................................................15 37. 系统函数 qsort 调用的比较函数问题 ...............................................................15 38. 教材第 231 页优化的两路归并排序 .................................................................16 39. 感觉书上的桶式排序 p234 的基数取法有点问题 ...........................................17 40. P243 的静态链表的基数排序第一趟分配不一致............................................17 41. 外排序多路归并时,如果某个顺串处理完了怎么办? .................................18 42. 折叠法散列函数的理解.....................................................................................18 43. ELFhash 是什么意思,我看不懂。 .................................................................18 44. 如果中英文混编,那么读入时该如何区分呢? .............................................18 45. 关于 P320-P323 散列表的一系列操作 .............................................................18 46. 对中文词建立散列函数,要转化为数字么? .................................................19 47. 排序和检索题意.................................................................................................19 六、索引和高级树结构问题.........................................................................................................21 48. 一级索引指向的是一个记录还是一个扇区? .................................................21 49. B 树/ B+树为什么那样定义? ...........................................................................21 50. 教材 p347 B 树关键码个数问题 .......................................................................22 51. 关于极限情况下 B+树的删除 ...........................................................................22 52. B 树和 B+树的读写次数?效率怎么计算? ....................................................23 53. 教材上关于叶结点的表述 .................................................................................23 54. 教材上关于 B/ B+树层数的表述 .......................................................................23 55. 关于 347 页图 10.9 的疑问 ................................................................................23 56. 关于习题集 292 页习题 10.12 的疑问 ..............................................................24 57. 第 463 页半伸展树的疑问 .................................................................................24 七、 C++常见问题 .................................................................................................................24 58. using namespace std 是什么意思? ...................................................................24 59. 关于 C++的头文件.............................................................................................24 60. 如何通过 C/C++命令运行一个文件? .............................................................25 61. 怎样使用 STL 中的队列啊?............................................................................26 62. 关于 STL 中的 top..............................................................................................26 63. 请问如何获得某段代码执行耗时? .................................................................26 64. 文件流操作.........................................................................................................27 65. 关于文本文件处理的问题 .................................................................................29 66. 关于网络爬虫中的文件路径处理 .....................................................................31 八、考研问题.................................................................................................................................31 67. 关于考研技巧问题,请到 BBS 考研版 ...........................................................31 68. 北大计算机系招生名额.....................................................................................31 69. 北大数据库方向招生名额 .................................................................................32 70. 操作系统、离散数学、高数的复习大纲?命题老师的个人主页? .............32 71. 所有报考计算机软件基础的试卷题目(代号 896)是不是一样的啊?............33 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® iv 72. 北大对跨专业报考有什么限制吗?复试会不会加试呢? .............................33 73. 您喜欢带什么样的学生? .................................................................................33 九、鸣谢.........................................................................................................................................33 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 1 一、教材信息 1. 教材出版信息 (1) 主教材: 许卓群、杨冬青、唐世渭、张铭,《数据结构与算法》,高等教育出版 社,2004 年 7 月。主教材勘误表。 (网上购书:http://www.landraco.com.cn/book/bookdetail.asp?plucode=14616-00) (2) 辅助教材:张铭、赵海燕、王腾蛟,《数据结构与算法——学习指导与习题解析》, 高等教育出版社, 2005 年 10 月。ISBN 7-04-017829-X。辅助教材勘误表。 (网上购书:http://www.landraco.com.cn/book/bookdetail.asp?plucode=17829-00) (3) 主教材和辅助教材都在北大教材科、王府井图书大厦、西单图书大厦有售。某些新 华书店也可能有售。 高教社购书热线:010-58581118,58581117,58581116。 高教社网上订购 URL:http://www.landraco.com.cn 2. 每位作者负责的章节 主教材第 1、2、3 章(第 1-84 页)由许卓群主笔,第 4、5、6 章(第 85-202 页)由杨 冬青主笔,第 8、10 章(第 254-293 页,第 333-358 页)由唐世渭主笔,第 7、9、11、12 章(第 203-253 页,第 294-332 页,第 359-468 页)由张铭主笔。 辅助教材第 7、9、10、12、13、14 章(第 162-215、244-279、280-303、324-503 页) 由张铭教授主笔,第 1、2、3、11 章(第 1-47、304-323 页)由赵海燕副教授主笔,第 4、 5、6、8 章(第 48-161、226-243 页)由王腾蛟副教授主笔。 3. 课程网站(课程讲义、算法源代码等) http://www.db.pku.edu.cn/mzhang/DS/ 4. 关于教材内容问题(包括错误和疑问)等数据结构技术性 问题 请到 http://db.pku.edu.cn/mzhang/DS/bbs/index.asp 论坛注册账号,参与讨论。 请不要给作者发 email 询问教材问题,作者非常忙,很可能没有时间直接回答您的问题。 我们 BBS 上面有助教负责整理错误和问题,并且尽量解答,而且及时更新到本勘误表中。 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 2 二、 数据结构的一般问题 1. 伪代码到底是什么? 答:http://algorithm.myrice.com/algorithm/pseudocode.htm 给出伪代码定义:伪 代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以 容易地以任何一种编程语言(Pascal, C/C++, Java, etc)实现。因此,伪代码必须结构清晰, 代码简单,可读性好,并且类似自然语言。 我们教材所用到伪代码,就是半描述半代码性质的,可以说是 C++伪代码。某些代 码细节可以忽略,甚至有些实现细节可以屏蔽掉。 当然在作业里,关键性算法的代码还是要有的。实在写不出 C++伪代码,可以写出 像教材第 38 页中缀转后缀算法(注意第一次印刷版该算法有错,勘误表已经纠正)那 样的类自然语言代码。 2. 什么是“程序的鲁棒性”? 答:鲁棒性,是英文“Robust”的音译,指程序的健壮性。就是程序对异常情况的处理能力, 例如不合理的输入、下标越界等。鲁棒性差的程序在遇到异常情况时会造出内存泄漏或 是死循环等情况,而鲁棒性强的程序就能很好的处理这些异常。 3. 教材中多处提到 log n 是以 10 为底的对数吗? 答:数据结构和算法类的教材中,大多数是 log n 是以 2 为底的对数。其实以 2 为底和以 10 为底的对数从算法复杂性来看是等价的。 loga n = logb n / logb a ,对于变量 n 和任意两个整数变量 a 和 b,loga n 与 logb n 只相 差常数因子 logb a,而与 n 的值无关。教材中的大多数代价分析都忽略常数因子,因此 有关对数的复杂性分析与对数的底数无关。 4. 请问效率分析是只要记住结果还是要会自己推导? 答: 两个层面:记住最基本的算法的时间/空间代价和会推导一些不算太复杂的算法效率。 各种算法大体的的时间代价需要记住,算法的最好最差时间/空间效率一般应该会分 析。那些特别复杂的时间代价推导,例如用到快速排序的递归推导是不会要求的。 一些不算太复杂的算法效率分析,肯定需要理解和自己会推导。比如给你一个不太难的 算法,请你估计复杂度(即时间代价);或者对你自己写的算法,分析其时间代价。 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 3 5. 关于算法 算法语言无所谓,只要能看懂。考试用 C++出题,但答题随意(可以用 C/C++、Java、 Pascal、自然语言等等,看得懂就可以)。 如果要求自己独立地写算法(而不是填空),请注意写算法思想,并加上足够的注 释。 在平时作业中,对于算法中直接使用的类和函数(例如栈、队列的函数),最好先 写 ADT,并 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 函数功能、入口参数、出口参数。尤其是同学们自己定义的类和函数。 6. 怎样写抽象数据类型 ADT? 抽象数据类型是定义了一组运算的数学模型。它与物理存储结构无关,使软件系统 建立在数据之上。从这个意义上来说,当我们定义一个抽象数据类型时,必须说清楚两 点:其一,它的逻辑结构;其二,定义在这个逻辑结构之上的抽象函数。 从抽象数据结构的观点来看,对数据结构的一切访问都是通过函数来进行的。不主 张把属性直接 public,让外界直接访问。 请同学们不要拘泥于抽象数据类型的具体形式,它只是描述数据结构的一种理论工 具。不一定要用 Interface 或者抽象类来表示。 我们提倡以下的定义方法:借用 C++语言的类定义形式,在定义抽象数据类型时, 先用注释的形式说明其逻辑定义,然后定义其主要的运算函数(够用就行了,并非越多 越好),并以注释的形式对函数功能加以说明。 7. 关于编程经验问题 答:编程上要靠自己平时多练习了,每次把自己的作业和推荐作业比较一下,看看差在什么 地方。思路同学们都差不多,差在经验上。包括教材上的例题也可以在 VC 上自己实现 看看,这些都是非常经典的算法,从算法的思想到代码结构都是值得借鉴的。 8. 不同小组的作业难度不同,怎么算成绩? 问:如果仅仅是简单相加的话,我觉得这样有失公平。每个组的题目不一样,难度也不一样。 相对来讲,做难题的那一组同学肯定吃亏。还望助教老师想出一个平衡的方法,并在网 上公布,以解除大家的疑惑。 答:助教在给分的时候会考虑题目的难易程度,况且平时作业的评分都比较高,只要你按时 交了作业并且态度端正,就可以得到相对满意的成绩。请大家不要担心。 数据结构与算法课程比较重视平时的作业和上机练习。大多数情况下,我们按照“平 时(书面作业)20%+上机(+报告)15%+期中 20%+期末 40%+考勤和态度 5%”给出成绩。 不过,如果期中、期末两次考试都没有上 50 的学生,期末绝对不能及格。考试还是一 个很过硬的指标。 例如,学生两次考试都得 70 分,每次作业得 8.5,假设态度分也是 5×0.85,那么 期评成绩就是 76。总分可以提高一大截。 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 4 三、线性表和串疑难解答 9. 教材第 1 版第 1 次印刷 p19 倒数 L1,P21,P62 等处的 “算子”一词,本身是纯数学概念,C++中似乎不应如此 解释。 答:同意。其实,“算子”在英语中对应的是“function”,在中文的不同环境中应该翻译为 “函数”或者“运算符”。 例如,P21 的 list ADT 代码,“算子”应该修改为“函数”。其他地方的“算子”, (1) 如果是英文命名的,则称“函数”; (2) 如果是“+”、“=”、“>”、“<”、“>>”、“<<”等,应该称“运算符”。 第 4 次印刷版即将改正。 10. p24 算法 2.1,插入之前 curr 的值不确定? 答:限于篇幅,没有给出某些成员函数的具体实现。list 构造函数的初始化应该为: template list::list(const int size) // 构造函数,初始化 { msize = size; curr_len= curr = 0; nodelist = new ELEM[size]; } 11. assert 断言的使用问题。 答:断言 assert 能帮助在程序中发现逻辑错误,它仅在 Debug 版本起作用,用于检查“不应 该”发生的情况。 边界判断是算法的重要组成部分。本教材中使用的 assert,并没有损坏算法的完整 和正确性。 在实际系统中,读者可以根据需要处理某些异常。例如,把 P24 算法 2.1 和 2.2 中 的 assert 置换成相应的异常处理代码,或者在调用算法 2.1 的 insert 或 2.2 的 remove 函 数前进行异常判断并作出相应处理。” 12. 教材第 26 页链表部分 first 指针的含义? 问:教材上 first->link 才指向第一个结点。first 指向的首结点不算是数据元素,那这个首结 点有什么意义?这与我们通常的编程习惯不同。请问考试时是否默认采用教材中的规 定? 答:教材上采用的是带头结点(header node,也称“头结点”,即链表首部的虚结点)的链 表,头结点的 data 域用来存储整个链表的简单信息。因此寻找第 i 个结点的算法 2.3 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 5 FindIndex(i) 中,变量 first 的指向的是一个特殊的首结点。first->link 才是。 算法 2.3 假定在进入算法前查找链表中第 i 个结点时, i 按照 C/C++数组下标编号 的规则,是从 0 到 n-1。链表的第 0 个结点应该是 first->link,即链表真正的第一个有效 结点。加入头结点后,可以使得很多操作的边界处理变得比较简单。例如,在空链表中 插入元素,在链表首部插入元素,删除后链表成为空表,等等。 13. 什么叫循环队列?如何区分空满循环队列? 答:所谓循环队列是不是就是教材中第 52 页的顺序队列。一般 front 指向队首第一个元素, rear 指向下一个该插入信息的位置。有些教材用 rear 指向循环队列最后一个元素,而且 链式队列的 rear 往往指向队列的最后一个有效元素(例如教材第 53 页算法)。 如果循环队列带上了当前的长度信息,那么可以利用所有的结点空间,如教材 51 页算法所示。 如果没有带长度信息,如果不加 int curr_len 记录队列长,那么需要利用 rear 和 front 的关系来判断,需要牺牲一个结点的空间。整个队列还有一个空位置“(rear+1) % maxsize == front”时,就要报告“队列满”。rear=front 表示为空。 14. 关于递归转化 问:Hanoi 塔问题,也可以用迭代来解决的,我看过迭代的解法,甚至在我的一本参考书上, 就写着:……any recursive problem can also be resolved iteratally。而在您翻译的《数据结 构与算法分析——C++版》上,关于 Hanoi 塔的问题,写的是:并不是所有的递归问题 都可以用迭代来解决……Hanoi 塔问题就不能用迭代来解决。我感兴趣的是,Hanoi 塔 问题的确是可以用迭代解决的,但是是否所有的递归问题都可以用迭代解决,好像需要 证明。我只是直觉上感觉可以从递归问题的出口反过来推导解决递归问题,不知道有没 有进一步的证明,您能不能给一点指导? 答:张铭翻译的《数据结构与算法分析——C++版》(电子社 2002 年版)第 81 页,"并不是 所有的递归问题都可以用迭代来解决",这里的 iteration 是指例 4.2 那种简单循环递推。 在计算机术语中,我们所指“迭代”、“递推”都是类似含义,你的参考书比较特别。 递归问题都可以用栈来化解为非递归的形式。如果是类似于二叉树访问地对问题空 间进行搜索,则可以采用教材第 94-97 页,算法 4.4-4.6 的那三个非递归深度优先周游框 架。例如,Hanoi 塔问题可以采用中序非递归深度优先周游框架来消除递归(注意修改 进出栈参数,修改算法中的 Visit 语句)。 对于图 2.15 的栈图示。建议: (1) 应该增加一个返回地址位,表示是从第一个递归语句深入还是从第二个递归语 句深入。就像二叉树后序周游那样。 (2) 类似于二叉树中序周游,简化 Hanoi 进栈的内容。从第一个递归语句返回进入 第二个递归语句时,本层内容不需要压栈。 推荐参考讲义:张铭2002年网站http://www.db.pku.edu.cn/mzhang/site/03_recrule.pdf。 推荐参考书:严蔚敏等《数据结构》 或者许卓群等《数据结构》1985 年版。 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 6 15. 关于双端队列和双栈的区别 答:双栈是一种加限制的双端队列,它规定从 end1 插入的元素只能从 end1 端删除,而从 end2 插入的元素只能从 end2 端删除。 另外,栈和队列都是特殊的双端队列,对存取加了限制。在大部分的插入和删除运 算发生在队列的一端时,可以用双端队列提高效率,这时它的时间复杂度为常量级。 16. 关于 String 类 (1) 是干什么的? 答:类似,是 C 语言的一个 library,包含一些常量的声明和常用的函数, 比如 rand()函数(产生随机数)等。 (2) #include 后,声明字符串变量 “string s1”会报错 undeclared identifier?但 是其中的一些函数如 strlen 却可以使用?难道要自己编写 string 类? 答:(a) 如果没有编写自己的 string 类,#include 之后,不能直接声明 string s1。因 为是系统的 library,里面并没有定义 string 类,只是定义了一些 char*字符串的 常用函数(其中也包括 strlen()),书上有自定义的 string 类,可以敲出来,并#include "string.h"(注意,是“”而不是<>)。 (b)事实上,可以直接引用 STL 中定义的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 string 类。首先要“#include ”,注 意,没有“.h”。然后,需要 using namespace std; 或者声明 using std::string; 这样,定义 string s1 就不会出错了。不过请注意,教材第 62 页自己定义的 Sting 类 与 STL 的 string 类略有差别。 (c) 另外,教材上定义的 strlen()是 String 类的 Public 函数,必须针对一个 String 对象引 用,单独引用 strlen()则是调用标准 C 的函数。 String P; int len len = strlen(P); 或者 len = P.strlen(); (3) strlen()和 length() 问:我看了您的勘误,感觉有个小问题:就是 String 类型的变量本身提供了 length()的 member function,而勘误上面似乎写的还是 strlen(),我编写程序和学习 C++时用到的、看到的 都是用 length(),所以我觉得应该用 length()更为恰当一些。 答:标准 C++类(STL)确实定义了一个 length()。不过,教材第 62-63 页自己定义了一个 String 类。函数名称只是代表,叫什么都无所谓。教材第 63 页第 5 行定义了 strlen(),因此我 们沿用 strlen()。 (4) string&中“&”是什么意思啊? 答:string&的&表示引用,返回的是一个引用值,所谓引用指的是对一个对象的引用。如果 一个函数返回的是一个引用类型,那么该函数可以被当作左值使用。如果一个对象或表 达式可以放在赋值号的左边,那么这个对象和表达式就叫左值。 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 7 17. 教材为什么要自己定义一个 String 类? 答: 教材定义 String 类是为了详细解释串的实现细节、运算符重载等。我们在讲解新的数 据结构时,需要了解那些标准数据结构及其函数底层的实现原理。 我们提倡采用 string.h 中的标准函数 C++的函数库、STL 的类、 VC 的 String 类。 类似地,教材定义了栈、队列等基础数据结构 任何时候,我们都提倡使用 STL,除非有特殊训练需要学生自己设计。 18. 局部对象在语句块结束执行后将被释放。算法 3.9 能 return temp 吗? 答:语句显然不符合逻辑。temp 是语句块内的局部对象,语句块结束执行后将被释放,返 回其结果(return 语句并不能返回对象的值,它只能返回一个标准表达式的值)将导致 系统错误(在 C++中实际测一下即可,我已经实际测试过了)。此算法需要在退出前重 新分配 str 空间,然后将 temp.str 复制回 str; 函数体执行完后,会是释放局部变量,但是不会释放由这些局部变量申请出来的动 态空间。return 语句完全可以返回对象,包括(临时变量)对象的内存空间和值。 问题出在析构函数~String( )在销毁对象时释放了空间。因此退出函数体时,temp 申 请的空间被释放了。 解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 只需要把析构函数~String( )的“delete [] str;”语句删除掉就可以了。本教 材在第 4 次印刷时修改了 P74 算法 3.8。 【算法 3.8】 // 析构函数 destructor String::~String(void) { // delete [] str; } 【算法 3.8 结束】 析构函数~String( )什么也不做。String 类的字符空间应该由程序员主动 delete 释放。 因为拼接运算符要求返回 String 型的值,相关函数中的临时变量申请的空间必须返回。 例如 算法 3.9 中临时变量 temp 的对象空间必须返回到上一级。如果在析构函数中销毁 了 temp 的 str 空间,则调用算法 3.9 时将出现错误。 19. 第 3.3 和 3.4 节的代码可以简洁明一些 算法 3.2 int strcmp(char *d, char *s) { int i; for (i=0;d[i]==s[i];++i ) { 《数据结构与算法》常见问题解答 张铭整理 ©张铭保留一切权力。未经授权,不得转载、翻印。违者必究!® 8 if (d[i]=='\0' ) // 此时 s[i]==d[i] return 0; // 两个字符串相等 } return (d[i]-s[i])/abs(d[i]-s[i]); //不等,比较第一个不同的字符 } 算法 3.14 int FindPat(String S, String P, int startindex) { //g 为 S 的游标,用模板 P 和 S 第 g 位置子串比较, //若失败则继续循环 for (int g= startindex; g <= S.strlen() - P.strlen(); g++) { for (int j=0; ((j
本文档为【数据结构与算法]】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_438091
暂无简介~
格式:pdf
大小:363KB
软件:PDF阅读器
页数:37
分类:工学
上传时间:2011-12-16
浏览量:933