数据结构C描述介绍讲述

数据结构C语言描述特色解析清华大学计算机系殷人昆教材介绍1讲座内容²教材编写背景²教材编写的考虑²学习的纲领²各章知识点、特色与疑难问题2新书数据结构C语言描述分析3教材编写背景n目前市场上用C描述的数据结构教材太多了，为什么华章约我写这样一本书？我想，主要是看重我教学经验。n到底我在数据结构方面有什么经验？我自己也有些困惑，不过，在清华BBS网站“水木清华”上学生对我的评价相当正面。n回顾以往，我第一次学习数据结构，是1978年，起步与赫赫有名的大师严蔚敏、许卓群、杨冬青等应是同一年代，何况严蔚敏的第一本教材还借走了我的笔记呢。4n不过，有一段时间我参与了VLSICAD数据库的研发，1985年去了日本，做了两年客座研究员，方向是“软件质量管理”，转向了软件工程方向，回国后成了郑人杰老师本科生“软件工程”课程的B角。1990年郑人杰老师调动工作到了清华同方，我就成了该课程的A角，直到2006年把课程交给留美归国的白晓颖老师。n在1985年前，曾确定我担任严蔚敏老师“数据结构”的B角，为此我还做了些准备。出国后换了人，前系主任唐泽圣、周立柱都曾担任过B角，但因为某些原因，先后离开了。5n1991年重新让我担任该课程的B角，为争取学校的一类课建立梯队。此前我已经担负3年全校非计算机专业二学位数据结构教学，与严蔚敏老师的配合比较顺利，大课一年一轮换，今年上大课来年上小班辅导课。直到1998年严老师退休，我开始担任A角。n此外，应北大老师相邀，从1996年起在京海研修学院为高教自考学生上“数据结构”课程，为保证通过率，安排了80个学时讲课，教材先后用过3本，感觉把数据结构的边边角角都讲到了，通过率每年都在65%以上，年年受奖。6高教自考指定教材北大许卓群杨冬青等编中科大黄刘生编北大张乃校编7n通过研究高教自考的考试试题，总结了不少在各个知识点学生容易忽视的细节，这对我的教学积累帮助不小，后来虽然不去了，但我与北大孙家潚老师、丁文魁老师、张乃孝老师建立了友谊。n1996年，美籍华人学者冀中田再次来华讲学，系主任周立柱问及在美国现在以什么语言上数据结构课，冀中田推荐了C+。因此，周立柱老师决策上C+的数据结构，并启动教材编写，由于我有积极性，决定让我来写。n当时，我和郑人杰正在与美国GrandValleyStateUniversity终身教授陶永雷合作编写实用软件工8程（第二版），顺理成章开始数据结构用面向对象方法和C+描述的合作。n我们优选的原版英文教材是E.HorowitzS.Sahni&D.Mehta在1995年出版的FundamentalsofdatastructureinC+，它的特点是章节编排顺序与严蔚敏的教材一致，便于中国老师接受，作者都是名家，内容比较权威，面向对象算法容易阅读。n编写工作十分吃力，还用了3位SRT的学生使用当时流行的BorlandC+调试算法。遗憾的是，许多调试通过的算法后来用VisualC+编译不过去（系统兼容问题），给学生造成学习困难。9n经过56年的教学实践，我们开始改版。这次是清华信息学院出面，在全院范围组织了课程教学组，参加者包括计算机、电子、自动化、微纳电子等系数据结构教师，以计算机系为主，编写数据结构用面向对象方法和C+描述（第二版）教材。n由于有了教学经验和教训，这次编写比较顺利，在讲解上更加清晰，在技术细节上避开了许多语言或编译上的陷阱，选用了一些新出现的算法。n由于多人合作，还会有些夹缠不清的或出现矛盾的情节，多谢许多热心读者帮助我们解决问题。10n直到第4次印刷后才算松了一口气，绝大多数问题都解决了。n由于以上经历，完成好华章交给的任务有把握的也是对我教学经验的一个总结。n。11教材编写的考虑n数据结构到底有什么用？r它是敲门砖ü你要进电脑公司吗？业务考试必考数据结构。ü你要深造吗？计算机专业考研、考博必考数据结构。ü你要出国吗？进外国大学计算机专业必考数据结构。ü你要获得上级的青睐吗？听话，出活是必须的，要出活如何少得了数据结构。12r它是解决问题必不可少的ü世界上很多问题的解决都可以归结到离散问题。ü解决问题的手段是建模（数学模型抽象思维维），模型求解的根本是算法（计算思维），算法设计的基础是数据结构，算法实现的基础是程序设计。ü沃斯说：算法+数据结构=程序。进一步说：高效的算法+适当的数据结构+程序语言的熟练运用=卓越的程序系统。ü系统开发能力就是如此。13n学好数据结构要靠什么？r责任感ü学习不能无目标，让你学什么就学什么。学习涉及的是一种人生观或价值观，涉及你将来在社会上扮演什么角色。ü战斗精神ü学习像打仗，没有免费的午餐。不靠拼命如何攻克堡垒，不能三天打渔两天晒网。ü实践精神ü学习不能光靠读书，要多做题。能力是知识在应用中运用的体现。14r创新精神ü问题的求解需要运用已学到的知识，问题的解决可以举一反三。特别是算法。ü严谨精神ü知识有系统性。学习就是一个系统工程，每一步学习，都在为后续的学习铺垫；每一个知识点都在后续的知识点或其他课程中用到。ü团队和奉献精神ü一个合唱队，若一个声音高亢得超出所有声音，此合唱必定不和谐。要互相帮助。15n这本数据结构教材是写给谁的？r数据结构的知识体系难吗？不难。每一个知识点看起来如此简单，像一个个音符一样；然而汇集起来，以最佳方案解决问题就不那么简单了。想把这些知识点用好，就像把音符恰到好处地安排到适当的位置，奏出最悦耳的音乐，这就是我们的目的。r这本教材想把最基本的知识体系介绍给读者且让读者能够切实理解它，掌握它。r据3年来批阅计算机考研联考试卷的体会，不少考试基本功训练不足，亟待有人引路。16r本教材完全遵照全国硕士研究生入学统一考试计算机科学与技术学科联考考试大纲安排，并参照教育部计算机科学与技术教学指导委员会高等学校计算机专业人才专业能力构成与培养的要求，以专业基础能力培养为目标，承续程序设计基础课程，培养基本计算思维能力，提高算法设计和程序实现能力，并为提高系统开发能力打下良好的基础。基本出发点：Ø采用“工科”思维，启发学生掌握“化复杂为简单”的方式，从问题入手，通过“问题子问题”分解，寻找解决方案；17Ø对基本知识点讲深讲透，通过多种应用举例，让学生了解不同问题需要采取什么方法来应对；Ø通过大量习题，从不同视点不同层面训练学生，见多才能识广，才能培养出联想能力，提高分析问题、解决问题的能力；Ø配合辅助教材数据结构习题精析与考研辅导，提供了多达600多题的参考答案和解析，并就关键点进行点拨；另外，提供了多套模拟题。18n本教材采用C语言作为数据结构及算法的描述工具，适当采用C+的少量语句以简化程序。算法描述力求结构化，注重编程风格，每个算法基本保持在100行之内，可读性强。n本教材是从作者多年在清华大学计算机系讲授的“数据结构”课程的教材和课件中取材，并经过一定改编而成，因此在叙述上适合学生的特点，在内容上浅显易懂，在选材上舍弃了很多超出规范和大纲的内容，增加了许多在老教材中忽略了的内容，应该不会辜负读者的期望。n由于2012年考研大纲增加了“外排序”的内容，相应补充内容可从华章网站下载。19参考教材（国外）20参考教材（国内）21学习的纲领n数据结构课程是计算机专业的专业基础课程，为业界做系统开发提供了不可或缺的技术和知识，是计算机专业考研的重头科目。n数据结构课程学习有几点重要的经验提供给大家参考。r注重概念r抓住特点r学会算法r拓展应用22n注重概念从考研情况分析，试题涉及的内容都很基本，没有很深很难的内容，所以要重视概念的学习：n牢记定义。结构定义有规范写出的，有言外隐藏的和引伸的概念。n注意传承。某些结构与其他结构间有传承关系，有变种关系。n区分层次。分清逻辑的和物理的结构，以及它们之间的关系。n挖掘细节。细节可提供更多解题的知识。23n抓住特点每种结构有它的特点和用途，这对于在解题中应使用哪种结构(who)，在何时(when)，何种场合(where)使用，以及如何(how)使用有重要作用。n理解结构的行为特征。明确每种结构的行为特征，例如栈是先进后出，队列是先进先出的，可帮助在解题时作出选择。n理解结构的应用背景。知道每种结构常在什么场合做什么用，可适时作出适当选择。n理解结构的声明方式。在适当时机合理地定义它们，可减少算法逻辑的混乱。24n学会算法包括结构的必要操作（初始化、建立、销毁、遍历、插入、删除）的实现和常用算法（查找、排序）、算法设计（迭代、递归、分治、回溯）的设计与分析。n基本数据结构的实现方式。主要是数据结构的存储方式定义和相应操作的程序实现。n常用算法的设计。包括设计的三阶段（基本思想、算法框架、程序实现）。n算法的简单分析。掌握时间复杂性的分析技能和附加存储空间的计算。25n拓展应用每种结构都有许多应用场合，有不同应用目的和应用方式。每种算法也可变通以适用于不同的问题求解。n明确问题求解的步骤。掌握问题求解的三阶段：分析(弄懂题意)、设计(考虑解决方案)、实现(算法设计与分析)。n坚持算法设计与分析的步骤。算法设计三阶段（基本思想、算法框架、程序实现）。n结构和算法的不同应用。这是最繁杂、范围最广的部分。通过多练习达到熟练应用。26n为在有限的时间内学习好这门课程，应当注意以下几点:n注意学习用CC+Java语言编写小程序时的语法规则和方法，为算法分析和算法设计题的求解打下基础。n函数定义和参数使用。算法一般以函数形式给出，函数编写需要注意的问题包括函数类型，函数参数传递，函数返回值类型等，以及传值参数和引用参数在使用上的区别。n函数中局部变量的作用域。特别注意在函数中对局部变量的任何改变，在函数外不能使用。27r算法设计所用数据结构的自定义。算法设计时不能忽视所用数据结构的声明。rCC+中的动态存储分配和回收方式。涉及链表结构的地方都可能有动态存储分配和回收操作。要掌握正确使用相关语句的方法。r在CC+中输入输出文件的定义和使用。特别注意正确使用文件的打开、关闭、读入、写出操作的使用。r在学习数据结构时，要注意知识体系。数据结构课程中的知识本身具有良好的结构性，有些结构面向应用，有些结构面向实现。学习时28要注意这两个层次以及它们之间的联系。r注意循序渐进Ø在学习数据结构时，首先需要学习数据结构的定义和特点，数据结构的使用范围，再学习各种操作的实现。Ø在阅读算法之前，要先弄清其基本设计思想、基本步骤，并通过事例学习了解每个算法的处理流程以加深理解，最后再阅读程序代码。r注意比较在复习中应当注意从“横向”和“纵向”进行对比以加深理解。29Ø纵向对比将一种结构与它的各种不同的实现加以比较，理解不同实现方式的优点和问题。如二叉树的顺序和链表实现。Ø横向对比是ü对属于同一类逻辑结构的不同数据结构（如线性表、栈、队列）加以比较，ü对具有相同功能的不同算法进行比较等，了解数据结构与算法实现间的关系。r注意练习Ø只看书不做题，不能真正学会有关知识，不能达到技能培养的目的。Ø做题是自我检查的重要手段。30Ø在做算法设计类型的习题时，应考虑数据结构的定义。n提高算法设计的能力。r编写算法的题可能是学生比较棘手的问题，特别是在考试这样一个氛围，时间又短促，想编出一个好算法不太容易。r一个建议是Ø首先仔细阅读试题题目，了解它到底要你干什么。Ø然后用一个简单的例子走一下，总结每一步向下走可用什么语句实现。31Ø再做归纳，整理出处理流程。Ø按照结构化程序设计的方法，搭建框架，再根据例子填入细节。r在设计一个算法时，要考虑问题解决方案的多样性、算法的适用性、问题对算法选择的限制。选择合适的数据结构，设计有效的算法。n下面我们将与严蔚敏老师的教材做一对比，说明我们的教材在何处补充了严蔚敏老师的教材。顺带给出一些问题的点拨。32各章知识点、特色与疑难问题第一章数据结构概论第二章线性表第三章栈、队列与数组第四章树与二叉树第五章图第六章查找第七章排序33n本章“绪论”的知识点有4个：©数据结构的概念©使用CC+语言描述数据结构和算法的方法©算法的