数据结构 1绪论new

数据结构 1绪论new

数据结构1 绪论

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

主要内容 什么是数据结构– 定义、内容

基本术语– 数据：数据对象、数据元素、数据项 – 数据结构：逻辑结构、物理结构

抽象数据类型– 定义、表示

算法和算法分析– 算法的概念、算法复杂度1 绪论 http://www.77cn.com.cn/ds 2

数据结构 1绪论new

什么是数据结构 程序 = 数据结构 + 算法– Pascal之父，Niklaus Wirth – 数据结构：问题的数学模型 —— 数据表示 – 算法：处理问题的策略 —— 数据处理 – 程序：一组指令 —— 数据结构和算法的实现

计算机解决问题的步骤：– (抽象出)数学模型 – (设计)求解算法 – (编制)程序1 绪论 http://www.77cn.com.cn/ds 3

数据结构 1绪论new

什么是数据结构 例：学生名单学号 98131 98164 98165 98182 98224 姓名 张三 李斯 王武 赵柳 ... 性别 男 女 男 女 籍贯 北京 上海 广州 香港 年龄 20 21 19 22

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

什么是数据结构 例：四皇后问题

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

什么是数据结构 例：城市交通咨询图查 询 两 地 的 最 短 路 径1 绪论 http://www.77cn.com.cn/ds 6

数据结构 1绪论new

基本术语数据对象 数据 数据元素 数据项 结构 逻辑结构

物理结构

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

基本术语：数据 数据– 所有需输入计算机并被程序所处理的对 象的总称

例如：图书借阅管理系统– 图书信息：登录号 001 书名 理论力学 借阅者编号 9002

002...

高等数学...

9001...绪论 1http://www.77cn.com.cn/ds 8

数据结构 1绪论new

基本术语：数据元素 数据元素– 数据的基本单位，在程序中常作为一个 整体考虑和处理登录号 001 002 书名 理论力学 高等数学 借阅者编号 9002 9001

一个数据元素 (一条记录)

...

...

...

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

基本术语：数据项 数据项– 数据的不可分割的最小单位 – 一个数据元素可由一或多个数据项构成3个数据项 登录号 001 002 ... 书名 理论力学 高等数学 ... 借阅者编号 9002 9001 ...1 绪论 http://www.77cn.com.cn/ds 10

数据结构 1绪论new

基本术语：数据项 数据对象– 性质相同的数据元素的集合 – 是数据(全集)的子集登录号教科书

书名 理论力学 高等数学

借阅者编号 9002 9001

001 002

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

基本术语：逻辑结构 逻辑结构– 数据元素间的逻辑关系 – 即在现实世界中的关系

分类– 集合：同在一个集合中 比如同班同学之间

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

基本术语：逻辑结构– 线性结构：一个接一个 比如学生花名册中的记录之间

– 树形结构：一对多 比如家谱

– 图形结构：多对多 比如地图

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

基本术语：物理结构 物理结构– 即存储结构 – 数据元素在计算机中存储时的关系

顺序映象(顺序存储结构)– 以存储地址上的联系来体现数据元素间的逻辑 关系

非顺序映象(链式存储结构)– 通过指针的指向来体现数据元素间的逻辑关系

1 绪论

http://www.77cn.com.cn/ds

数据结构 1绪论new

基本术语：物理结构 例：学生花名册学号 98131 98164 98165 98182 98224 姓名 张三 李斯 王武 赵柳 ... 性别 男 女 男 女 籍贯 北京 上海 广州 香港 年龄 20 21 19 22

– 数据元素之间的逻辑关系：线性关系1 绪论 http://www.77cn.com.cn/ds 15

数据结构 1绪论new

基本术语：物理结构– 顺序存储：各个数据元素在计算机中的 存储地址也是线性关系，即连续存放98131 张三 男 98164 李斯 女 ......

一个数据元素

struct student{ string _id,_name; bool boy; }; student students[60];1 绪论 http://www.77cn.com.cn/ds 16