文档介绍：数据结构
课程内容:
计算机软件的基础知识———数据结构
课时安排:
数据结构——64学时
上机——16学时
4,5,6,7,10,11,12,13周,周一上午(10:00~12:00)
计算中心
教材:
数据结构严蔚敏清华
第一章绪言
什么是数据结构
程序=数据结构+算法
例1 书目自动检索系统
登录号:
书名:
作者名:
分类号:
出版单位:
出版时间:
价格:
书目卡片
书目文件
按书名
按作者名
按分类号
索引表
线性表
例2 人机对奕问题
树
……..
……..
…...
…...
…...
…...
多叉路口交通灯管理问题
C
E
D
A
B
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
图
数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科
基本概念和术语
数据(data)—所有能输入到计算机中去的描述客观事物的符号
数据元素(data element)—数据的基本单位,也称节点(node)或记录(record)
数据项(data item)—有独立含义的数据最小单位,也称域(field)
数据结构(data structure)—数据元素和数据元素关系的集合
根据数据元素间关系的基本特性,有四种基本数据结构
(集合)——数据元素间除“同属于一个集合”外,无其它关系
线性结构——一个对一个,如线性表、栈、队列
树形结构——一个对多个,如树
图状结构——多个对多个,如图
数据的逻辑结构—只抽象反映数据元素的逻辑关系
数据的存储(物理)结构—数据的逻辑结构在计算机存储器中的实现
数据的逻辑结构与存储结构密切相关
算法设计逻辑结构
算法实现存储结构
存储结构分为:
顺序存储结构——借助元素在存储器中的相对位置来表示
数据元素间的逻辑关系
链式存储结构——借助指示元素存储地址的指针表示数据
元素间的逻辑关系
元素n
……..
元素i
……..
元素2
元素1
Lo
Lo+m
Lo+(i-1)*m
Lo+(n-1)*m
存储地址
存储内容
Loc(元素i)=Lo+(i-1)*m
顺序存储
1536
元素2
1400
元素1
1346
元素3
∧
元素4
1345
h
存储地址
存储内容
指针
1345
元素1
1400
1346
元素4
∧
…….
……..
…….
1400
元素2
1536
…….
……..
…….
1536
元素3
1346
链式存储
h