数据结构课件第01章.ppt

文档介绍：数据结构(C语言版) Data Structure
主讲教师 马宁
计算机科学学院 软件工程教研室
1
学习的直接收益
编程基础
计算机专业考研课程
计算机等级考试课程
软件资格与水平考试课程
进入优秀企业的敲门砖盖茨说:学通了这本书(程序设计技巧,共三卷,其中第一卷主要为数据结构)来找我吧!
请同学们重视本课程的学习。
总学时:64 学时
讲课学时:48 学时
实验学时:16 学时
教材: 《数据结构》( C语言版)严蔚敏、吴伟民
-----清华大学出版社
课程安排
参考书目
计算机及软件技术丛书——
现代计算机常用数据结构和算法 
潘金贵编著
南京大学出版社
数据结构习题与解析(C语言篇)修订版
李春葆主编
计算机专业教学辅导丛书
清华大学出版社
《程序设计》课程与《数据结构》课程的关系
《程序设计》强调程序设计的基本概念和做法,如:
数据类型与表达式
程序流程控制
子程序
递归
数据抽象,等
《数据结构》强调程序设计思想和技术的典型应用,如:
线性表、栈、队列
检索、排序
图、树,等
两者的内容又有交叉
本课程的体系结构
第一章绪论
介绍数据、数据结构和抽象数据类型的概念。
第二章——第七章基本数据结构
从抽象数据类型的角度,
分别讨论线性表、栈和队列、
串、数组和广义表、
树、图等基本数据结构及其应用。
数据结构学科的研究对象
什么是程序、软件?
(Niklaus Wirth)教授提出:
程序=算法+数据结构
以上公式说明了如下两个问题:
(1)数据上的算法决定如何构造和组织数据
(算法→数据结构)
(2)算法的选择依赖于作为基础的数据结构
(数据结构→算法)
软件=程序+文档(软件工程的观点)
第一章绪论
2. 电子计算机的主要用途
早期:
主要用于数值计算。
后来:
应用逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)。
数据复杂→数据结构
3. 计算机解决问题的一般步骤
数学模型→算法→程序
(1)数值计算
数学模型→选择计算机语言→编出程序→测试→最终解答。
数值计算的关键是:如何得出数学模型(方程)?
程序设计人员比较关注程序设计的技巧。
(2)非数值计算问题
数据元素之间的相互关系一般无法用数学方程加以描述。
例1、电话号码查询问题
查找:给出一个姓名,如果存在,打印此人的电话号码;
如果不存在,报告没有这个人的标志。
(1)按顺序存储方式:须遍历表
(2)按姓氏索引方式:索引
要写出好的查找算法,取决于这张表的结构及存储方式。
电话号码表的结构和存储方式决定了查找(算法)的效率。
4. 非数值计算问题举例