第1章数据结构的基本概念.ppt

文档介绍：计算机软件技术基础
冯花平
北京工业大学耿丹学院信息工程系
第1章数据结构基本概念
什么是数据结构
基本概念和术语
算法及其分析
3
下面文字的含义:
漆黑的头发没有麻子脚不大周正
演绎1
漆黑的头发,没有麻子,脚不大,周正。
结论:描述一个古代美人!
演绎2
漆黑的头发没有,麻子,脚不大周正。
结论:描述了一个古代丑女人,还是个瘸子。
结论
两个不同的演绎表现为不同的结果,一个是古代美人,一个确实古代丑女人,原因只是文字的不同组合造成!
也就是说:相同的文字(数据)经过不同的组合(结构)会得到不同的结果,这就是我们要介绍的数据结构:数据及其之间的关系(结构)。
什么是数据结构
计算机解决问题的步骤?
数值计算解决问题的一般步骤:
数学模型→选择计算机语言→编出程序→测试→最终解答。
数值计算的关键是:如何得出数学模型(方程)?
程序设计人员比较关注程序设计的技巧。
非数值计算问题:
数据元素之间的相互关系一般无法用数学方程加以描述
诸如表、树、图之类的数据结构
例1:问题:图书管理,完成书目的检索(线性关系)
数据:各类书籍,更确切地说是每本书的信息,即书名、作者、出版社、出版日期、书号、价格、内容提要等。
操作:书目入库、查询、借书、还书
非数值计算问题3个引例
书目自动检索系统的数学模型
书目文件
按书名
按作者名
按分类号
索引表
线性表
例2:人机对奕问题的数学模型(树结构)
树
……..
……..
…...
…...
…...
…...
问题:人机对弈,即人与计算机下棋
数据:各种棋局状态,确切地说是描述棋盘格局的信息。
操作:走棋,即选择一种策略使棋局状态发生变化(由一个格局派生出另一个格局)
C
E
D
A
B
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
图
例3:多叉路口的交通灯管理问题的数学模型
问题:多叉路口的交通灯管理,即在多叉路程口设置几种颜色的交通灯,以保证交通畅通。
数据:路口各条路的信息。
操作:设置信号灯(求出各个可同时通行的路的集合。
求解非数值计算的问题:
主要考虑的是设计出合适的数据结构及相应的算法。
即:首先要考虑对相关的各种信息如何表示、组织和存储?
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。
程序设计:为计算机处理问题编制一组指令集。
算法:处理问题的策略。
数据结构:问题的数学模型。
Niklaus Wirth
什么是数据结构
Algorithm+DataStructures=Programs《算法+数据结构=程序》
基本概念和术语

数据(data):
数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的”原料”。
分类: 数值性数据
非数值性数据