清华大学殷仁昆教授《数据结构》(C++语言描述)课件_00.ppt

《清华大学殷仁昆教授《数据结构》(C++语言描述)课件_00.ppt》由会员分享，可在线阅读，更多相关《清华大学殷仁昆教授《数据结构》(C++语言描述)课件_00.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构清华大学计算机系清华大学计算机系殷人昆殷人昆 王王 宏宏学习数据结构的背景学习数据结构的背景n计算机是一门研究用计算机进行信息表示计算机是一门研究用计算机进行信息表示和处理的科学。和处理的科学。n信息的表示和组织直接关系到信息处理程信息的表示和组织直接关系到信息处理程序的效率。随着计算机的普及，信息范围序的效率。随着计算机的普及，信息范围的拓宽，信息量的增加，使许多系统程序的拓宽，信息量的增加，使许多系统程序和应用程序的规模和复杂性增加。和应用程序的规模和复杂性增加。n为了编写出一个为了编写出一个“好好”的程序，必须分析的程序，必须分析待处理对象的特征及各对象间存在的关系，待处理对象的

2、特征及各对象间存在的关系，这就是数据结构这门课所要研究的问题。这就是数据结构这门课所要研究的问题。数据结构课程的形成和发展数据结构课程的形成和发展 n形成阶段形成阶段：60年代初期，年代初期，“数据结构数据结构”有关的内容散见有关的内容散见于操作系统、编译原理和表处理语言等课程。于操作系统、编译原理和表处理语言等课程。1968年，年，“数据结构数据结构”被列入美国一些大学被列入美国一些大学计算机科学系的教学计划。计算机科学系的教学计划。n发展阶段发展阶段：数据结构的概念不断扩充，包括了网络、集数据结构的概念不断扩充，包括了网络、集合代数论、关系等合代数论、关系等“离散数学结构离散数学结构”的内

3、容。的内容。70年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设该课程。数据结构课程的地位数据结构课程的地位 n n是介于数学、计算机硬件和计算机软件三者是介于数学、计算机硬件和计算机软件三者之间的一门核心课程之间的一门核心课程数据结构课程的地位。数据结构课程的地位。关系关系对象对象关系关系操作操作软件软件 硬件硬件对象对象关系关系操作操作数学数学n数据结构是一门研究非数值计算的程序设计数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操问题中计算机的操作对象及其之间关系与操作的学科。是介于数学、计算机硬件和计算作的学科。是介于数学、计算机硬件和计算机软件三

4、者之间的一门核心课程，属于计算机软件三者之间的一门核心课程，属于计算机学科中的一门综合性专业基础课程。机学科中的一门综合性专业基础课程。n它不仅是一般程序设计的基础，也是设计和它不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。他系统程序和大型应用程序的重要基础。n该课程于该课程于1968年开始在国外作为一门独立课年开始在国外作为一门独立课程设立，由美国唐程设立，由美国唐欧欧克努特教授开创其克努特教授开创其最初体系。最初体系。程序设计与程序设计与问题解决问题解决数据结构基础数据结构基础数学数学1数

5、学数学2计算机科学基础计算机科学基础计算机系统计算机系统原理与汇编原理与汇编算法与数算法与数据结构据结构程序设计语言基础程序设计语言基础操作系统操作系统有穷自动机有穷自动机计算机组计算机组织与结构织与结构必修课课程设置与数据结构的关系必修课课程设置与数据结构的关系 选修课课程设置与数据结构的关系选修课课程设置与数据结构的关系 数据结构基础数据结构基础计算机科学基础计算机科学基础算法与数算法与数据结构据结构文件处理文件处理(数据库数据库)算法设计与分析算法设计与分析软件工程软件工程图形学图形学系统模拟系统模拟数值计算解决问题的一般步骤数值计算解决问题的一般步骤：n数学模型数学模型选择计算机语言选

6、择计算机语言编出程序编出程序测试测试最终解答。最终解答。n数值计算的关键是：如何得出数学模型数值计算的关键是：如何得出数学模型（方程）？（方程）？n程序设计人员比较关注程序设计的技巧。程序设计人员比较关注程序设计的技巧。n典型问题典型问题：l电路分析与模拟电路分析与模拟l大坝（应力与应变）结构分析大坝（应力与应变）结构分析l弹道仿真程序弹道仿真程序等等非数值计算问题非数值计算问题n数据元素之间的相互关系一般无法用数学数据元素之间的相互关系一般无法用数学方程加以描述。方程加以描述。n例如，例如，电话号码查询问题电话号码查询问题按顺序存储方式：遍历表按顺序存储方式：遍历表按姓氏索引方式：索引表按姓

7、氏索引方式：索引表n要写出好的查找算法，取决于这张表的结要写出好的查找算法，取决于这张表的结构及存储方式。构及存储方式。n电话号码表的结构和存储方式决定了查找电话号码表的结构和存储方式决定了查找（算法）的效率。（算法）的效率。求解非数值计算的问题的步骤求解非数值计算的问题的步骤：n主要考虑的是设计出合适的数据结构及相应主要考虑的是设计出合适的数据结构及相应的算法。即首先要考虑的算法。即首先要考虑对相关的各种信息如对相关的各种信息如何表示何表示、组织和存储组织和存储？n可以认为：数据结构是一门研究非数值计算可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它的程序设计问题

8、中计算机的操作对象以及它们之间的关系和操作的学科。们之间的关系和操作的学科。数据结构课程的特点数据结构课程的特点n数据结构课程是计算机专业基础课，主要数据结构课程是计算机专业基础课，主要训练学生在系统开发中的数据设计、算法训练学生在系统开发中的数据设计、算法设计与分析及数据组织的能力，它设计与分析及数据组织的能力，它是后续是后续多门课程，如数据库、操作系统、编译原多门课程，如数据库、操作系统、编译原理、网络系统基础等的基础理、网络系统基础等的基础，对于从事计，对于从事计算机系统开发的人员，是必修课程之一。算机系统开发的人员，是必修课程之一。n需要有关需要有关“程序设计语言程序设计语言”和和“离

9、散数学离散数学”的知识作为课程的基础。的知识作为课程的基础。n实践性较强。实践性较强。教材和教学参考书教材和教学参考书n主教材主教材数据结构（用面向对象方法和数据结构（用面向对象方法和C+描述），描述），第二版，殷人昆，邓俊辉等，清华大学出版社第二版，殷人昆，邓俊辉等，清华大学出版社n辅助教材辅助教材J.R.Hubbard,DataStructureswithC+,机械工业出版社影印机械工业出版社影印,中译名中译名数据结构数据结构习题习题与解答与解答C+版版，￥40（七折￥（七折￥28）数据结构习题解析（用面向对象方法与数据结构习题解析（用面向对象方法与C+语语言描述），殷人昆等，清华大学出版

10、社。言描述），殷人昆等，清华大学出版社。集体购买集体购买,出版社七折出版社七折优惠优惠,各班课代表统计各班课代表统计需要数目用需要数目用Email告诉我告诉我实验上机实验上机n在微机上使用在微机上使用BorlandC+或或VisualC+都可都可以。前者的系统体积小些。但同一个源程序在以。前者的系统体积小些。但同一个源程序在这两个编译器上可能会出现不同的编译信息。这两个编译器上可能会出现不同的编译信息。n本着教学相长的精神，希望经常对教学效果作本着教学相长的精神，希望经常对教学效果作出反馈，以便及时改进教学方法。出反馈，以便及时改进教学方法。n学好一门课程，教师的引导固然十分重要，但学好一门课

11、程，教师的引导固然十分重要，但主要靠学生的自身努力。课堂教学可以起到画主要靠学生的自身努力。课堂教学可以起到画龙点睛的作用，但只有不断练习，才能巩固、龙点睛的作用，但只有不断练习，才能巩固、掌握课程的内容。因此，本课程要求同学积极掌握课程的内容。因此，本课程要求同学积极独立完成所布置的习题。独立完成所布置的习题。课程学习要求课程学习要求n自觉预习、遵守纪律、认真听课、及时复自觉预习、遵守纪律、认真听课、及时复习；习；n按时、独立、认真地完成每次作业；按时、独立、认真地完成每次作业；n完成作业方式：完成作业方式：1.第第5周、第周、第9周、第周、第13周和第周和第17周提交作周提交作业；业；2.

12、作业分两部分：作业分两部分：第第1部分是纸面作业，要求用笔写并不部分是纸面作业，要求用笔写并不得复印和打印得复印和打印课程学习要求课程学习要求第第2部分是上机作业，要求用部分是上机作业，要求用C+语言语言编程实现，并通过网络学堂提交其源编程实现，并通过网络学堂提交其源程序及可执行文件；程序及可执行文件；n成绩评定标准：成绩评定标准：1.纸面作业，占纸面作业，占10%；2.上机作业，占上机作业，占22%；3.平时平时4次随堂测验（随机进行）取次随堂测验（随机进行）取3次成次成绩好者，占绩好者，占18%；4.期末考试，占期末考试，占50%。教师信息教师信息n殷人昆，主讲教师殷人昆，主讲教师62795589,n王王宏，主讲教师宏，主讲教师62783860,n王晓东，博士助教（负责王晓东，博士助教（负责1，2，3班）班）13910558186，n李智超，博士助教（负责李智超，博士助教（负责4，5班及外系）班及外系）13811944829，Thanks for Coming!谢谢谢谢2006年年2月月20日日THU