数据结构C描述介绍.ppt

《数据结构 C语言描述》 特色解析 清华大学计算机系 殷人昆 讲座内容 教材编写背景 教材编写的考虑 学习的纲领 各章知识点、特色与疑难问题 新书 数据结构 C语言描述 分析 教材编写背景 目前市场上用 C 描述的《数据结构》教材太多了，为什么华章约我写这样一本书？我想，主要是看重我教学经验。 到底我在数据结构方面有什么经验？我自己也有些困惑，不过，在清华BBS网站“水木清华”上学生对我的评价相当正面。 回顾以往，我第一次学习《数据结构》，是1978年，起步与赫赫有名的大师严蔚敏、许卓群、杨冬青等应是同一年代，何况严蔚敏的第一本教材还借走了我的笔记呢。 不过，有一段时间我参与了 VLSI CAD 数据库的研发，1985年去了日本，做了两年客座研究员，方向是“软件质量管理”，转向了软件工程方向，回国后成了郑人杰老师本科生“软件工程”课程的B角。1990年郑人杰老师调动工作到了清华同方，我就成了该课程的A角，直到2006年把课程交给留美归国的白晓颖老师。 在1985年前，曾确定我担任严蔚敏老师“数据结构”的B角，为此我还做了些准备。出国后换了人，前系主任唐泽圣、周立柱都曾担任过B角，但因为某些原因，先后离开了。 1991年重新让我担任该课程的B角，为争取学校的一类课建立梯队。此前我已经担负 3 年全校非计算机专业二学位数据结构教学，与严蔚敏老师的配合比较顺利，大课一年一轮换，今年上大课来年上小班辅导课。直到1998年严老师退休，我开始担任A角。 此外，应北大老师相邀，从1996年起在京海研修学院为高教自考学生上“数据结构”课程，为保证通过率，安排了80个学时讲课，教材先后用过 3 本， 感觉把数据结构的边边角角都讲到了，通过率每年都在65%以上，年年受奖。 高教自考指定教材 通过研究高教自考的考试试题，总结了不少在各个知识点学生容易忽视的细节，这对我的教学积累帮助不小，后来虽然不去了，但我与北大孙家潚老师、丁文魁老师、张乃孝老师建立了友谊。 1996年，美籍华人学者冀中田再次来华讲学，系主任周立柱问及在美国现在以什么语言上数据结构课，冀中田推荐了C++。因此，周立柱老师决策上C++的数据结构，并启动教材编写，由于我有积极性，决定让我来写。 当时，我和郑人杰正在与美国Grand Valley State University终身教授陶永雷合作编写《实用软件工 程（第二版）》，顺理成章开始《数据结构 用面向对象方法和C++描述》的合作。 我们优选的原版英文教材是E.Horowitz, S.Sahni D.Mehta在1995年出版的Fundamentals of data structure in C++，它的特点是章节编排顺序与严蔚敏的教材一致，便于中国老师接受，作者都是名家，内容比较权威，面向对象算法容易阅读。 编写工作十分吃力，还用了 3 位SRT的学生使用当时流行的Borland C++调试算法。遗憾的是，许多调试通过的算法后来用Visual C++编译不过去（系统兼容问题），给学生造成学习困难。 经过56年的教学实践，我们开始改版。这次是清华信息学院出面，在全院范围组织了课程教学组，参加者包括计算机、电子、自动化、微纳电子等系数据结构教师，以计算机系为主，编写《数据结构 用面向对象方法和C++描述》（第二版）教材。 由于有了教学经验和教训，这次编写比较顺利，在讲解上更加清晰，在技术细节上避开了许多语言或编译上的陷阱，选用了一些新出现的算法。 由于多人合作，还会有些夹缠不清的或出现矛盾的情节，多谢许多热心读者帮助我们解决问题。 直到第 4 次印刷后才算松了一口气，绝大多数问题都解决了。 由于以上经历，完成好华章交给的任务有把握的也是对我教学经验的一个总结。 。 教材编写的考虑 数据结构到底有什么用？ 它是敲门砖 你要进电脑公司吗？业务考试必考数据结构。 你要深造吗？计算机专业考研、考博必考数据结构。 你要出国吗？进外国大学计算机专业必考数据结构。 你要获得上级的青睐吗？听话，出活是必须的，要出活如何少得了数据结构。 它是解决问题必不可少的 世界上很多问题的解决都可以归结到离散问题。 解决问题的手段是建模（数学模型―抽象思维），模型求解的根本是算法（计算思维），算法设计的基础是数据结构，算法实现的基础是程序设计。 沃斯说：算法+数据结构=程序。进一步说：高效的算法+适当的数据结构+程序语言的熟练运用=卓越的程序系统。 系统开发能力就是如此。 学好数据结构要靠什么？ 责任感 学习不能无目标，让你学什么就学什么。学习涉及的是一种人生观或价值观，涉及你将来在社会上扮演什么角色。 战斗精神 学习像打仗，没有免费的午餐。不靠拼命如何攻克堡垒，不能三天打渔两天晒网。 实践精神 学习不能光靠读书，要多做题。能力是知