数据结构与算法.ppt

文档介绍：数据结构与算法
-5

为什么需要数据结构

什么是数据结构
基本概念和术语
抽象数据类型的表示和实现
算法和算法分析
什么是数据结构
Two classics:
[1] . The Art puter Programming. Addison-Wesley, 1968.
[2] . Algorithms + Data Structures = Programs.
Prentice-Hall, 1976.
数据结构是一门研究非数值计算程序设计问题中计算机的操作对象及其之间关系和操作的学科。
程序= 数据结构+ 算法
“数据结构”的内容
线性表(Linear List)
栈(Stack)
队列(Queue)
串(String)
数组(Array)
树(Tree)
图(Graph)
对“数据结构”的操作
遍历(Traversing)
查找(Searching)
排序(Sorting)
“数据结构”应用举例
图书馆书目检索——线性表
计算机博弈——树
多叉路口交通灯管理——图
基本概念和术语
数据(Data):对客观事物的符合表示;
数据元素(Data Element):数据的基本单位,一个数据元素可由若干个数据项(Data Item)组成;
数据对象(Data Object):性质相同的数据元素的集合;
数据结构:相互间存在一种或多种特定关系的数据元素的集合。
数据的逻辑结构——数学抽象
集合
线性结构——一个对一个
树型结构——一个对多个
图状结构——多个对多个
数据结构分类
数据的物理结构——机内表示
表示单位——位、字节、字串、结点(Node)
表示方法——顺序、非顺序(链式)
F
E
D
C
A
B
6
3
5
2
1
4
B
D
A
F
E
C
6
3
5
2
1
4
B
C
A
4
6
2