文档介绍：数据结构 Data Structures 课程简介与教学要求
清华大学计算机系
殷人昆王宏
2012年春季学期
学****数据结构的背景
系统程序与应用程序的规模和复杂性激增
数据的表示和组织直接关系到问题求解的效率。
必须分析待处理对象的特征及各对象间存在的关系。
必须深入研究数据在计算机中存储、组织、传递和转换的过程及方法。
一门重要的计算机专业(能力考查)课程
-29,OS-35,CP-41,DS-45
数据结构课程的形成和发展
形成阶段:
60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。
1968年,“数据结构”作为一门独立课程被列入美国一些大学计算机科学系的教学计划
由唐·欧·克努特(D. E. Knuth,《The Art puter Programming》的作者,图灵奖得主)开创其最初体系。
发展阶段:
数据结构的概念不断扩充,包括了集合论、代数结构、图论等“离散数学结构”的内容。
70年代后期,我国高校陆续开设该课程。
数据结构课程的地位
介于数学、计算机硬件和计算机软件三者之间的一门核心课程。
关系
机器
组织
存储
软件
硬件
对象
关系
操作
数学
数据结构是一门侧重研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科。
不仅是复杂程序设计的基础,也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。
N. Wirth早在20世纪70年代就曾形象描述
Algorithm + Data Structure = Program
程序设计与
问题求解
数据结构基础
离散数学 1
离散数学 2
计算机科学基础
计算机系统
原理与汇编
算法设计
与分析
编译原理
操作系统
软件工程
计算机组
织与结构
必修课课程设置与数据结构的关系
选修课课程设置与数据结构的关系
数据结构
计算机科学基础
算法与复杂性
数据库
(文件处理)
人工智能
计算机网络
图形学
多媒体技术
数值计算问题求解的一般步骤
建立数学模型→选择计算机语言与算法→
编写程序→测试(调试)→最终解答。
数值计算的关键是:如何归纳出数学模型(方程)?
程序设计人员关注的是模型的建立与算法的选择
典型问题:
电路分析与模拟
大坝(应力与应变)结构分析
弹道仿真程序天气预报等
非数值计算问题
数据元素之间的相互关系有时无法或很难用数学方程加以描述。
例如,电话号码查询问题
按顺序存储方式:遍历表
按姓氏索引方式:索引表
是否可以利用性能更优的查找算法,取决于这张表的组织结构及存储方式。
数据元素的结构和存储方式决定了查找与维护(算法)的效率。
2011人机大战电脑完胜