文档介绍：算法和数据结构
*
算法数据和数据结构
刘宇
2001年
算法和数据结构
*
程序=算法+数据结构
软件：刻画现实世界，解决现实世界中的问题
语言：实现的工具
算法：解的描述（日常的：如魔方）
数据结构：现实世界的数据模型
程序=算法+数据结构
第一章：概论
算法和数据结构
*
几个例子（问题）
表达式解释
6+5*4=？
字符串匹配
串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位置上
排序
一个序列，如何最快地对其进行排序
压缩编码
AAAABBBCDDE?
图的最短路径
地理研究中的交通网络
第一章：概论
算法和数据结构
*
课程讲述的内容
上述问题的答案，包括
一些常用的数据结构类型以及其应用
与这些数据结构的有关算法
空间数据结构
第一章：概论
算法和数据结构
*
数据结构（一）
作为学科的数据结构
数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等等的学科。
非数值计算
操作对象（数组）
第一章：概论
算法和数据结构
*
作为研究对象的数据结构
数据（和信息的关系）
数据项目
数据对象
第一章：概论
数据结构（二）
算法和数据结构
*
数据
数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
数值性数据
非数值性数据
算法和数据结构
*
数据元素
数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。
有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。
数据元素又称为元素、结点、记录。
算法和数据结构
*
数据对象
数据的子集。具有相同性质的数据成员（数据元素）的集合。
整数数据对象
N = { 0, 1, 2, … }
学生数据对象
算法和数据结构
*
数据结构（三）
树形关系
网状关系
1
5
2
4
3
6
1
5
2
4
3
6
数据结构：存在一种或多种特定关系的数据元素的集合
集合＋关系
Data_Structure = (D,S) D:数据元素的有限集合 S:关系