大连理工大学：《数据结构》课程教学课件（PPT讲稿）第一章 绪言

数据结构

课程内容： ★计算机软件的基础知识一 数据结构 课时安排： ★数据结构 —32学时 ★上机一12学时 16,17,18周，周一晚(5：00~9：00) 必信息学院软件中心（计算机系二楼） 教材： ★数据结构基础 曹桂琴 大工 参考书： ★数据结构 严蔚敏 清华

课程内容： 计算机软件的基础知识———数据结构 课时安排： 数据结构——32学时 上机——12学时 ❖16,17,18周，周一晚（5：00~9：00） ❖信息学院软件中心（计算机系二楼） 教材： 数据结构基础 曹桂琴 大工 参考书： 数据结构 严蔚敏 清华

第一章绪言 §1.1什么是数据结构 程序=数据结构+算法 ★例1书目自动检索系统 线性表 书目文件 001 高等卡英映川 S01 002 登歃力学 罗远祥 L01 003 高等数学 华罗庚 S01 索引表 004 书戟性代数 栾汝书 S02 作者名： 。g . 按书名 分类号： 按作者名 按分类号 高等数学 001, 003.出版单位：樊映川 001, L 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人机对奕问题 O●

例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 元素21536 元素3 1346 元素4 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 A 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