数据结构 信息工程学完 软件与信息系统教研室 主讲教师：王玫
信息工程学院 软件与信息系统教研室 主讲教师：王玫
高级语言的发展 1初期的程序设计（五十年代） 高运行效率、少占用内存为目标 2.结构化程序设计（七十年代） 程序的可读性、可维护性为目标 程序：算法，数据结构，编程语言，1 面向过程的程序设计方法 程序的结构规定为顺序、选择和循环三种基本结构，采取 自顶向下、逐步求精的分析和设计方法，即功能分析方法。 3.面向对象的程序设计（八十年代开始） 降低程序的复杂性、提高软件的开法效率和改善工作界 面为目标 程序=对象十消息+面向对象的程序设计
高级语言的发展 1.初期的程序设计（五十年代） 高运行效率、少占用内存为目标 2.结构化程序设计（七十年代） 程序的可读性、可维护性为目标 程序: 算法，数据结构，编程语言，面向过程的程序设计方法 程序的结构规定为顺序、选择和循环三种基本结构，采取 自顶向下、逐步求精的分析和设计方法，即功能分析方法。 3.面向对象的程序设计（八十年代开始） 降低程序的复杂性、提高软件的开法效率和改善工作界 面为目标 程序=对象+消息+面向对象的程序设计
第一章绪言 §1.1什么是数据结构 程序=数据结构+算法 ★例1书目自动检索系统 线性表 书目文件 001 高等卡英映川 S01 002 登彭力学 罗远祥 L01 003 高等数学 华罗庚 S01 索引表 004 书戟性代数 栾汝书 S02 作者名： …… 按书名 分类号： 按作者名 按分类号 高等数学 001, 003.出版单位：樊映川 001,. 002, 理论力学 002 出版时间 华罗庚 002, S 001,003, 线性代数 004, 价格 栾汝书 004,… 。▣
第一章 绪言 §1.1 什么是数据结构 程序=数据结构+算法 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 001 高等数学 书目卡片 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线性代数 栾汝书 S02 …… …… …… …… 书目文件 按书名 按作者名 按分类号 高等数学 001，003…… 理论力学 002，…….. 线性代数 004，…… …… …….. 樊映川 001,… 华罗庚 002,…. 栾汝书 004,…. ……. ……. L 002,… S 001,003, …… …… 索引表 线性表
入VL ★例2人机对奕问题
例2 人机对奕问题 树 …….. …….. …... …... …... …
★多叉路口交通灯管理问题 AB AD B BA BC D DB A 助
多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 图
★数据结构定义：是一门研究非数值计算的程序设 计问题中计算机的操作对象以及它们之间的关系 和操作等等的学科
数据结构定义: 是一门研究非数值计算的程序设 计问题中计算机的操作对象以及它们之间的关系 和操作等等的学科
§1.2基本概念和术语 ★数据(data)一所有能输入到计算机中去的描述 客观事物的符号 ★数据元素(data element)一数据的基本单位， 也称节点(node)或记录(record) ★数据项(data item)一有独立含义的数据最小单 位，也称域(field) ★数据结构（data structure)一数据元素和数据元 素关系的集合 根据数据元素间关系的基本特性，有四种基本数据结构 (集合) 一数据元素间除“同属于一个集合”外，天其它关系 】 线性结构 一个对一个，如线性表、栈一队列 树形结构 一个对多个，如树 图状结构 多个对多个，如图
§1.2 基本概念和术语 数据（data)—所有能输入到计算机中去的描述 客观事物的符号 数据元素（data element）—数据的基本单位， 也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单 位，也称域(field) 数据结构（data structure)—数据元素和数据元 素关系的集合 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图
★数据的逻辑结构一只抽象反映数据元素的逻辑关系 ★数据的存储（物理）结构一数据的逻辑结构在计算 机存储器中的实现 存储结构分为： 顺序存储结构 借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 CTek Here 链式存储结构 借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 算法设计◆逻辑结构 算法实现→存储结构 →
数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算 机存储器中的实现 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系
存储地址 存储内容 元素1 Lo+m 元素2 顺序存储 自上sB雪首指s Lo+(i-1)*m 元素i ME E MM E I E 元素n Lo+(n-1)*m L0c(元素i)=L0+(i-1)*m Back
元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储
h 1345 链式存储 元素1 1400 元素2 1536 元素3 1346 元素4 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 Λ 1400 元素2 1536 0■■00■o ■■■ag■●● ■■■■■■g 1536 元素3 1346 Back
元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h