数结构
课程内容 ★计算机软件的基础知识一 数据结构 课时安排: ★数据结构—32学时 ★上机—12学时 16,17,18周,周一晚(5:00~9:00) 心信息学院软件中心(计算机系二楼) 教材: ★数据结构基础曹桂琴大工 参考书: ★数据结构严蔚敏清华
课程内容： 计算机软件的基础知识———数据结构 课时安排： 数据结构——32学时 上机——12学时 ❖16,17,18周，周一晚（5：00~9：00） ❖信息学院软件中心（计算机系二楼） 教材： 数据结构基础 曹桂琴 大工 参考书： 数据结构 严蔚敏 清华
第一章绪言 §1.1什么是数据结构 程序〓数据结构十算法 ★例1书目自动检索系统 线性表 书目文件 001高等数到下英映川 S01 002a理论力学|罗远祥 LOl 003 高等数学华罗庚 S01 索引表 004平线性代数栾汝书 S02 佾者名 按书名 分类号: 按作者名 按分类号 高等数学01,003出版单:樊映川「00 002, 理论力学02,…出版时间:华罗庚00 s1001,003, 线性代数d04, 栾汝书|004
第一章 绪言 §1.1 什么是数据结构 程序=数据结构+算法 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 001 高等数学 书目卡片 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线性代数 栾汝书 S02 …… …… …… …… 书目文件 按书名 按作者名 按分类号 高等数学 001，003…… 理论力学 002，…….. 线性代数 004，…… …… …….. 樊映川 001,… 华罗庚 002,…. 栾汝书 004,…. ……. ……. L 002,… S 001,003, …… …… 索引表 线性表
★例2人机对奕问题 树 O●○ ○●● ○
例2 人机对奕问题 树 …….. …….. …... …... …... …
★多叉路口交通灯管理问题 C AB D B BA/B E A ED
多叉路口交通灯管理问题 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 ite)一有独立含义的数据最小单 位,也称域(fied) ★数据结构( data structure)一数据元素和数据元 素关系的集合 根据数据元素间关系的基本特性,有四种基本数据结构 (集合) 数据元素间除“同属于一个集合”外,天其它关系 线性结构一个对一个,如线性表、栈队列○ 树形结构 个对多个,如树 图状结构 多个对多个,如图
§1.2 基本概念和术语 数据（data)—所有能输入到计算机中去的描述 客观事物的符号 数据元素（data element）—数据的基本单位， 也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单 位，也称域(field) 数据结构（data structure)—数据元素和数据元 素关系的集合 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图
★数据的逻辑结构一只抽象反映数据元素的逻辑关系 ★数据的存储(物理)结构一数据的逻辑结构在计算 机存储器中的实现 存储结构分为: 顺序存储结构—借助元索在存储器中的相对位置来表示 数据元素间的逻辑关系《 链式存储结构—借助指示元素存储地址的指针表示数据 元素间的逻辑关系 CEsk her 数据的逻辑结构与存储结构密切相关 算法设计—逻辑结构 算法实现 存储结构
数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算 机存储器中的实现 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系
存储地址存储内容 元素1 Lotm 元素2 顺序存储 Lo+(i-1)*m 元素i L+(n1元素n 0c(元素i)=Lo+(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 链式存储 元素11400元素21536元素31346元素4∧ 存储地址存储内容指针 1345 元素1 1400 1346 元素4 ■■■■■■● ■■■● 1400 元素2 1536 O ■■。 ● 1536 元素3 1346
元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h