第八章 数据结构简介
数据：
数值数据
字符数据
表格数据
声音数据
图象数据
视频数据
问题：
1、数据本身的逻辑关系
2、在计算机中如何处理
与存储
本章要讨论的问题
第一节 数据结构基本概念
一、信息、数据与信息载体
信息,用来刻划现实世界中各种事物的一些
特征及事物之间的关系。
数据,由计算机加工过的信息。
信息载体,承载信息的各种数码、符号、文字、
图像及电、磁、光、声音等。
二、数据结构的概念
编号 名称 类型 学时 学分 先行课程
1001 高等数学 必修 80 4
1002 计算机导论 必修 80 4
1003 数字逻辑电路 必修 60 3
1004 离散数学 选修 60 3 1001
1005 C语言 必修 80 4 1002
…
1103 计算机原理 必修 80 4 1002,1003
1104 算法设计 必修 60 3 1002,1005
1105 计算机网络 必修 60 3 1002,1103
数据结构,指数据以及相互之间的关系。
这种数据之间的逻辑联系，称为数据的
逻辑结构 。在用计算机表示数据时，不
仅要存储数据本身，而且要存储它们之
间的联系（逻辑结构）。一种数据结构
在计算机存储器中的存储方式称为数据
的 物理结构（存储结构） 。
第二节 串（ string）
一、串的定义
串 是由 0个或多个字符组成的有限序列。
一般记为,S = ‘a1a2…a n’ (n≥0)
串名 串值
字符 子串,串中任意个 连续字符 组成的
子序列。
A=‘How nice to see you!’
B=‘nice to see you’
C=‘o se’
二、串的基本运算
1、字符变量赋值
A=‘How nice to see you!’
B=A
2、比较两字符串是否相等
字符串相等要求 长度 及 对应位置 上的字符均
相等，特别要注意空格与大小写。
A=‘bei jing’ B=‘Bei jing’
C=‘beijing’
3、取子串
A=‘How nice to see you!’
B=substr(A,5,15)
4、字符串合并
A=‘How nice to see you!’
B=‘Hello! World!
C=A+B
三、串的存储结构
H
e
l
l
o
!
W
o
r
l
d
^
A=‘Hello! World’
H e l l
o ! W
o r l d
^
1、顺序存储
非紧缩格式
紧缩格式
2、链式存储（ 删除与插入操作 ）
W h o 2 i s 3 W a n g 4 F e n ^
2 3 4
3ohW 3si g 4naW ^neF
2 3 4
2ohW 5si g 4naW ^neF
6iL n 3giP
2 3 4
5 6
第三节 数组（ array）
英语 化学 物理
张易 70 85 90
李玉 77 76 70
杨华 88 66 78
王旭 90 89 59
A（ 1） =张易
A（ 2） =李玉
A（ 3） =杨华
A（ 4） =王旭
B（ 1） =英语
B（ 2） =化学
B（ 3） =物理
C（ 1,1） = 70 C（ 1,2） = 85 C（ 1,3） = 90
C（ 2,1） = 77 C（ 2,2） = 76 C（ 2,3） = 70
C（ 1,1） = 90 C（ 3,2） = 89 C（ 3,3） = 59
一、数组的定义
数组,一组具有相同属性的 数据元素 （即数
据元素的数据类型、长度相同）按一定方式
进行排列，使得其中的每一数据元素都能由
一个整数系列唯一确定它的位置（即该元素
在数组中的序号），这样的数据结构称为 数
组 。
C（ 1,1） = 70 C（ 1,2） = 85 C（ 1,3） = 90
C（ 2,1） = 77 C（ 2,2） = 76 C（ 2,3） = 70
C（ 1,1） = 90 C（ 3,2） = 89 C（ 3,3） = 59
一维数组
二维数组
A（ 1） =张易
A（ 2） =李玉
A（ 3） =杨华
A（ 4） =王旭
B（ 1） =英语
B（ 2） =化学
B（ 3） =物理
C（ 1,1） = 70 C（ 1,2） = 85
C（ 1,3） = 90 C（ 2,1） = 77
C（ 2,2） = 76 C（ 2,3） = 70
C（ 1,1） = 90 C（ 3,2） = 89
C（ 3,3） = 59
二、数组的逻辑结构
三维数组
A（ 1,1,1） =10
A（ 1,1,2） =12
…
A（ 3,1,1） =43
A（ 3,3,3） =90
三、数组的存储结构
A（ 9）
A（ 8）
A（ 7）
A（ 6）
A（ 5）
A（ 4）
A（ 3）
A（ 2）
A（ 1）
A（ 0）
long int A(10);
int A(10);
设 C语言中定义的 一维数组,
32位
00001111000011110000111100001111
16位
数组的地址如何计算？
若已知 address[A(0)]=100,
则 address[A(n)]=?
address[A(n)]=
address[A(0) ] ＋ 4× n
二维数组：
int A(3,3);
A（ 2,2）
A（ 2,1）
A（ 2,0）
A（ 1,2）
A（ 1,1）
A（ 1,0）
A（ 0,2）
A（ 0,1）
A（ 0,0）
行优先
A（ 2,2）
A（ 1,2）
A（ 0,2）
A（ 2,1）
A（ 1,1）
A（ 0,1）
A（ 2,0）
A（ 1,0）
A（ 0,0）
列优先
A（ 0,0） A（ 0,1） A（ 0,2）
A（ 1,0） A（ 1,1） A（ 1,2）
A（ 2,0） A（ 2,1） A（ 2,2）
数组的地址如何计算？
若已知 address[A(0,0)]=100,
则 address[A(m,n)]=?
第四节 表（ table）
编号 名称 类型 学时 学分 先行课程
1001 高等数学 必修 80 4
1002 计算机导论 必修 80 4
1003 数字逻辑电路 必修 60 3
1103 计算机原理 必修 80 4 1002,1003
1104 算法设计 必修 60 3 1002,1005
1105 计算机网络 必修 60 3 1002,1103
一、表的定义
上表有如下特征：
1、由 N个元素组成，一个元素为表的一行（在数据库中称为
一条记录）。
2、每一个数据元素又由多个数据项组成（编号、类型,… ）
，数据元素的每一数据称为一个数据项，同一列上的数据项
具有相同的数据类型。
3、整个表称为一个数据文件。
表的定义：
表 是 一组有序的数据元素 。每一数据元素可含一个或多个
数据项，而且每一数据元素可与唯一的关键字相关联，用来
从表中检索相应的数据元素。
根据表的定义，可见 数组 是一种特殊的表。
二、表的运算
1、求表中元素个数
2、对于给定的关键字，查找表中相应的数据元素
3、在表中指定位置插入一个元素
4、删除表中指定位置上的数据元素
5、按某种要求对表中数据重新排序
三、表的存储结构
表有两种存放方式,顺序存放 与 链式存放
1、顺序存放
480必修高等数学1001
480必修计算机导论1002
360必修数字逻辑电路1003
1002,1003480必修计算机原理1103
1002,1005360必修算法设计1104
1002,1103360必修计算机网络1105a
6
a5
a4
a3
a2
a1
用 M个字节存储
addr[ai]=addr[a1]＋ (i-1) × M
2、链式存放
0F00H480必修高等数学1001
0F10H480必修计算机导论1002
0FF0H360必修数字逻辑电路1003
1000H480必修计算机原理1103
1010H360必修算法设计1104
^360必修计算机网络1105
指针域
优点：
它的优点是无需将表中各元素连续、顺序地
放在一起，为插入和删除表元素操作带来了
方便，只需修改指针即可。
缺点：
（ 1）检索操作时，须从链头开始，沿链依次
查找，费时；
（ 2）增加了指针域，从而增加存储空间的开
销。
第五节 栈（ stack）与队列
（ queue）
一、栈的定义
如果对表的插入与删除操作仅限于表的末端
进行，则将这样的表称为 栈 或 堆栈 。
栈顶
栈底
IN OUT
S
数据进栈时,S=S+1
数据出栈时,S=S-1
0≤S≤Max (Max为栈容量）
S=0时，栈空
S=Max时，栈满
栈最重要的特征是,数据先进后出
（ First IN Last Out:FILO);
二、栈的存储结构
三、队列的定义
如果只允许从 表的终端 插入数据元素，从 表的
始端 删除数据元素，则称这样的表为 队列 。
First In First Out, FIFO
三、队列的存取方式
a(1)a(2)…a(i)…
尾指针 头指针
a(1)a(2)…a(i)A(i+1)…
尾指针 头指针
a(1)a(2)…a(i)A(i+1)…
尾指针 头指针
an an-1 …
队列头队列尾
Q(n) Q(n-1) … Q(2) Q(1)
队列假溢出现象：
解决办法：
an
an-1 …
队列头
队列尾
X
第六节 树（ tree）
数据结构
线性结构 非线性结构
串 数组 表 栈 队列 树 图
一、树的概念
C:\
Windows TT
system command desktop tt.exe tt.hlptt.his
WB
xcopy Deltree.exe Fdisk.exe
树 是 N（ N＞ 0）个结点的有限集。在任一棵树中：
（ 1）有且仅有一个特定的称为根的结点；
（ 2）当 N＞ 1时，其余结点可分为 M（ M＞ 0）个互
不相交的有限集 T1,T2,…, Tm，其中每一个集
合本身是一棵树，并且称为根的子树（ subtree)。
树的一枝所含结点的数目称为 度,一棵树各结点
度的最大值称为这棵树的度。
二、树的存储方式 链表方式存储树结构。
数据域 指针域
\ pt1 pt2 Pt3
system ^
Command pt9 pt10 Pt11
Desktop ^
Tt pt6 pt7 Pt8
Wb ^
tt.exe ^
tt.hlp ^
tt.his ^
Xcopy.exe ^
Deltree.exe ^
Fdisk.exe ^
Pt1
Pt2
Pt3
Pt4
Pt5
Pt6
Pt7
Pt8
Pt9
Pt10
pt11
三、基本操作
（ 1）查找
（ 2）找前驱或后继
（ 3）扩展树
（ 4）删除子树
（ 5）按某种顺序输出树中全部结点
第七节 图（ graph）
V1
V2 V3 V4
V1
V2 V3 V4
树 图
V1
V2 V3 V4
V1
V2 V3 V4
无向图 有向图
一、图的定义
设 V是数据元素的集合,V={d1,d2,…,d n},其中
每个元素在图论中称为顶点（ Vertex),如果两个数据
元素 di和 dj是相关的，则说明这两个顶点间存在一条
边（ edge），若将这样的边所组成的集合记为 E，那
么就将二元式（ V,E）称为一个图，记为：
G=（ V,E）
V = {v1,v2,v3,v4}
E = {（ v1,v2）,（ v1,v3）,
（ v1,v4）,（ v2,v3）,
（ v2,v4）,（ v3,v4） }
V1
V2 V3 V4
V1
V2 V3 V4
有向图
几个概念：
两顶点 邻接
顶点的 度
图的度
入度
出度
二、图的存储方式
V1
V2 V3 V4
V1
V2
V3
V4
V2 V3 V4 ^
V1 V3 V4 ^
V2 V1 V4 ^
V2 V3 V1 ^
数据：
数值数据
字符数据
表格数据
声音数据
图象数据
视频数据
问题：
1、数据本身的逻辑关系
2、在计算机中如何处理
与存储
本章要讨论的问题
第一节 数据结构基本概念
一、信息、数据与信息载体
信息,用来刻划现实世界中各种事物的一些
特征及事物之间的关系。
数据,由计算机加工过的信息。
信息载体,承载信息的各种数码、符号、文字、
图像及电、磁、光、声音等。
二、数据结构的概念
编号 名称 类型 学时 学分 先行课程
1001 高等数学 必修 80 4
1002 计算机导论 必修 80 4
1003 数字逻辑电路 必修 60 3
1004 离散数学 选修 60 3 1001
1005 C语言 必修 80 4 1002
…
1103 计算机原理 必修 80 4 1002,1003
1104 算法设计 必修 60 3 1002,1005
1105 计算机网络 必修 60 3 1002,1103
数据结构,指数据以及相互之间的关系。
这种数据之间的逻辑联系，称为数据的
逻辑结构 。在用计算机表示数据时，不
仅要存储数据本身，而且要存储它们之
间的联系（逻辑结构）。一种数据结构
在计算机存储器中的存储方式称为数据
的 物理结构（存储结构） 。
第二节 串（ string）
一、串的定义
串 是由 0个或多个字符组成的有限序列。
一般记为,S = ‘a1a2…a n’ (n≥0)
串名 串值
字符 子串,串中任意个 连续字符 组成的
子序列。
A=‘How nice to see you!’
B=‘nice to see you’
C=‘o se’
二、串的基本运算
1、字符变量赋值
A=‘How nice to see you!’
B=A
2、比较两字符串是否相等
字符串相等要求 长度 及 对应位置 上的字符均
相等，特别要注意空格与大小写。
A=‘bei jing’ B=‘Bei jing’
C=‘beijing’
3、取子串
A=‘How nice to see you!’
B=substr(A,5,15)
4、字符串合并
A=‘How nice to see you!’
B=‘Hello! World!
C=A+B
三、串的存储结构
H
e
l
l
o
!
W
o
r
l
d
^
A=‘Hello! World’
H e l l
o ! W
o r l d
^
1、顺序存储
非紧缩格式
紧缩格式
2、链式存储（ 删除与插入操作 ）
W h o 2 i s 3 W a n g 4 F e n ^
2 3 4
3ohW 3si g 4naW ^neF
2 3 4
2ohW 5si g 4naW ^neF
6iL n 3giP
2 3 4
5 6
第三节 数组（ array）
英语 化学 物理
张易 70 85 90
李玉 77 76 70
杨华 88 66 78
王旭 90 89 59
A（ 1） =张易
A（ 2） =李玉
A（ 3） =杨华
A（ 4） =王旭
B（ 1） =英语
B（ 2） =化学
B（ 3） =物理
C（ 1,1） = 70 C（ 1,2） = 85 C（ 1,3） = 90
C（ 2,1） = 77 C（ 2,2） = 76 C（ 2,3） = 70
C（ 1,1） = 90 C（ 3,2） = 89 C（ 3,3） = 59
一、数组的定义
数组,一组具有相同属性的 数据元素 （即数
据元素的数据类型、长度相同）按一定方式
进行排列，使得其中的每一数据元素都能由
一个整数系列唯一确定它的位置（即该元素
在数组中的序号），这样的数据结构称为 数
组 。
C（ 1,1） = 70 C（ 1,2） = 85 C（ 1,3） = 90
C（ 2,1） = 77 C（ 2,2） = 76 C（ 2,3） = 70
C（ 1,1） = 90 C（ 3,2） = 89 C（ 3,3） = 59
一维数组
二维数组
A（ 1） =张易
A（ 2） =李玉
A（ 3） =杨华
A（ 4） =王旭
B（ 1） =英语
B（ 2） =化学
B（ 3） =物理
C（ 1,1） = 70 C（ 1,2） = 85
C（ 1,3） = 90 C（ 2,1） = 77
C（ 2,2） = 76 C（ 2,3） = 70
C（ 1,1） = 90 C（ 3,2） = 89
C（ 3,3） = 59
二、数组的逻辑结构
三维数组
A（ 1,1,1） =10
A（ 1,1,2） =12
…
A（ 3,1,1） =43
A（ 3,3,3） =90
三、数组的存储结构
A（ 9）
A（ 8）
A（ 7）
A（ 6）
A（ 5）
A（ 4）
A（ 3）
A（ 2）
A（ 1）
A（ 0）
long int A(10);
int A(10);
设 C语言中定义的 一维数组,
32位
00001111000011110000111100001111
16位
数组的地址如何计算？
若已知 address[A(0)]=100,
则 address[A(n)]=?
address[A(n)]=
address[A(0) ] ＋ 4× n
二维数组：
int A(3,3);
A（ 2,2）
A（ 2,1）
A（ 2,0）
A（ 1,2）
A（ 1,1）
A（ 1,0）
A（ 0,2）
A（ 0,1）
A（ 0,0）
行优先
A（ 2,2）
A（ 1,2）
A（ 0,2）
A（ 2,1）
A（ 1,1）
A（ 0,1）
A（ 2,0）
A（ 1,0）
A（ 0,0）
列优先
A（ 0,0） A（ 0,1） A（ 0,2）
A（ 1,0） A（ 1,1） A（ 1,2）
A（ 2,0） A（ 2,1） A（ 2,2）
数组的地址如何计算？
若已知 address[A(0,0)]=100,
则 address[A(m,n)]=?
第四节 表（ table）
编号 名称 类型 学时 学分 先行课程
1001 高等数学 必修 80 4
1002 计算机导论 必修 80 4
1003 数字逻辑电路 必修 60 3
1103 计算机原理 必修 80 4 1002,1003
1104 算法设计 必修 60 3 1002,1005
1105 计算机网络 必修 60 3 1002,1103
一、表的定义
上表有如下特征：
1、由 N个元素组成，一个元素为表的一行（在数据库中称为
一条记录）。
2、每一个数据元素又由多个数据项组成（编号、类型,… ）
，数据元素的每一数据称为一个数据项，同一列上的数据项
具有相同的数据类型。
3、整个表称为一个数据文件。
表的定义：
表 是 一组有序的数据元素 。每一数据元素可含一个或多个
数据项，而且每一数据元素可与唯一的关键字相关联，用来
从表中检索相应的数据元素。
根据表的定义，可见 数组 是一种特殊的表。
二、表的运算
1、求表中元素个数
2、对于给定的关键字，查找表中相应的数据元素
3、在表中指定位置插入一个元素
4、删除表中指定位置上的数据元素
5、按某种要求对表中数据重新排序
三、表的存储结构
表有两种存放方式,顺序存放 与 链式存放
1、顺序存放
480必修高等数学1001
480必修计算机导论1002
360必修数字逻辑电路1003
1002,1003480必修计算机原理1103
1002,1005360必修算法设计1104
1002,1103360必修计算机网络1105a
6
a5
a4
a3
a2
a1
用 M个字节存储
addr[ai]=addr[a1]＋ (i-1) × M
2、链式存放
0F00H480必修高等数学1001
0F10H480必修计算机导论1002
0FF0H360必修数字逻辑电路1003
1000H480必修计算机原理1103
1010H360必修算法设计1104
^360必修计算机网络1105
指针域
优点：
它的优点是无需将表中各元素连续、顺序地
放在一起，为插入和删除表元素操作带来了
方便，只需修改指针即可。
缺点：
（ 1）检索操作时，须从链头开始，沿链依次
查找，费时；
（ 2）增加了指针域，从而增加存储空间的开
销。
第五节 栈（ stack）与队列
（ queue）
一、栈的定义
如果对表的插入与删除操作仅限于表的末端
进行，则将这样的表称为 栈 或 堆栈 。
栈顶
栈底
IN OUT
S
数据进栈时,S=S+1
数据出栈时,S=S-1
0≤S≤Max (Max为栈容量）
S=0时，栈空
S=Max时，栈满
栈最重要的特征是,数据先进后出
（ First IN Last Out:FILO);
二、栈的存储结构
三、队列的定义
如果只允许从 表的终端 插入数据元素，从 表的
始端 删除数据元素，则称这样的表为 队列 。
First In First Out, FIFO
三、队列的存取方式
a(1)a(2)…a(i)…
尾指针 头指针
a(1)a(2)…a(i)A(i+1)…
尾指针 头指针
a(1)a(2)…a(i)A(i+1)…
尾指针 头指针
an an-1 …
队列头队列尾
Q(n) Q(n-1) … Q(2) Q(1)
队列假溢出现象：
解决办法：
an
an-1 …
队列头
队列尾
X
第六节 树（ tree）
数据结构
线性结构 非线性结构
串 数组 表 栈 队列 树 图
一、树的概念
C:\
Windows TT
system command desktop tt.exe tt.hlptt.his
WB
xcopy Deltree.exe Fdisk.exe
树 是 N（ N＞ 0）个结点的有限集。在任一棵树中：
（ 1）有且仅有一个特定的称为根的结点；
（ 2）当 N＞ 1时，其余结点可分为 M（ M＞ 0）个互
不相交的有限集 T1,T2,…, Tm，其中每一个集
合本身是一棵树，并且称为根的子树（ subtree)。
树的一枝所含结点的数目称为 度,一棵树各结点
度的最大值称为这棵树的度。
二、树的存储方式 链表方式存储树结构。
数据域 指针域
\ pt1 pt2 Pt3
system ^
Command pt9 pt10 Pt11
Desktop ^
Tt pt6 pt7 Pt8
Wb ^
tt.exe ^
tt.hlp ^
tt.his ^
Xcopy.exe ^
Deltree.exe ^
Fdisk.exe ^
Pt1
Pt2
Pt3
Pt4
Pt5
Pt6
Pt7
Pt8
Pt9
Pt10
pt11
三、基本操作
（ 1）查找
（ 2）找前驱或后继
（ 3）扩展树
（ 4）删除子树
（ 5）按某种顺序输出树中全部结点
第七节 图（ graph）
V1
V2 V3 V4
V1
V2 V3 V4
树 图
V1
V2 V3 V4
V1
V2 V3 V4
无向图 有向图
一、图的定义
设 V是数据元素的集合,V={d1,d2,…,d n},其中
每个元素在图论中称为顶点（ Vertex),如果两个数据
元素 di和 dj是相关的，则说明这两个顶点间存在一条
边（ edge），若将这样的边所组成的集合记为 E，那
么就将二元式（ V,E）称为一个图，记为：
G=（ V,E）
V = {v1,v2,v3,v4}
E = {（ v1,v2）,（ v1,v3）,
（ v1,v4）,（ v2,v3）,
（ v2,v4）,（ v3,v4） }
V1
V2 V3 V4
V1
V2 V3 V4
有向图
几个概念：
两顶点 邻接
顶点的 度
图的度
入度
出度
二、图的存储方式
V1
V2 V3 V4
V1
V2
V3
V4
V2 V3 V4 ^
V1 V3 V4 ^
V2 V1 V4 ^
V2 V3 V1 ^
