2022/12/6 1
西北师范大学经济管理学院
----信息管理系
本演示文稿可能包含观众讨论和即
席反应。使用 PowerPoint 可以
跟踪演示时的即席反应，
• 在幻灯片放映中，右键单击鼠标
• 请选择“会议记录”
• 选择“即席反应”选项卡
• 必要时输入即席反应
• 单击“确定”撤消此框
此动作将自动在演示文稿末尾创建
一张即席反应幻灯片，包括您的
观点。
2022/12/6 2
第1章 绪 论
● 关于学习数据结构
数据结构的基本概念(定义)
数据结构的内容（研究范围）
算法设计
算法描述工具
对算法作性能评价
数据结构与C语言表示
2022/12/6 3
数据结构的基本概念（定义）
数据结构的相关名词：
数据（Data）
数据元素（Data Element）
数据对象（Data Object）
数据结构（Data Structure）
数据类型(Data Type)
数据抽象与抽象数据类型
2022/12/6 4
数据（Data）
定义：
数据是描述客观事物的数值、字符以及能输入
机器且能被处理的各种符号集合。
数据包含整型、实型、布尔型、图象、字符、声音
等一切可以输入到计算机中的符号集合。
C编译程序
源程序
（.c）
目标程序
（.obj）
可执行程序
（.exe）
C链接程序
例如对C源程序
2022/12/6 5
数据元素（Data Element）
定义：
数据元素是组成数据的基本单位 ，是数据
集合的个体，在计算机中通常作为一个整体进
行考虑和处理。例如：
... ... ... ... ... ...
北京河北女 赵虹玲101
住 址 出生年月 籍 贯性
别
姓 名 学
号 数
据
元
素
数据项
2022/12/6 6
数据对象（Data Object）
定义：
数据对象是性质相同的数据元素的集
合，是数据的一个子集。
整数集合：N={0，±1，±2，…} 无限集
字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ} 有限集
例如：
2022/12/6 7
数据结构（Data Structure）
定义：
数据结构是指相互之间存在一种或多种特
定关系的数据元素集合，是带有结构的数据元
素的集合，它指的是数据元素之间的相互关系，
即数据的组织形式。 例如表结构：
... ... ... ... ... ...
北京河北女 赵虹玲101
住 址 出生年月 籍 贯性
别
姓 名 学
号
2022/12/6 8
数据结构（Data Structure）
树型结构 图结构
1
2
5
4
3
2022/12/6 9
数据类型(Data Type)
定义：
数据类型是一组性质相同的值集合以
及定义在这个值集合上的一组操作的总称。
如在高级语言中，整型类型的取值范围为：
-32768~+32767，运算符集合为加、减、乘、除、
取模，即+、-、*、/、%。
2022/12/6 10
数据类型(Data Type)
高级语言中的数据类型分为两大类：
1.原子类型，其值不可分解。如C语言中的标准类
型（整型、实型、字符型、）。
2.结构类型，其值是由若干成分按某种结构组成的，
因此是可以分解的，并且它的成分可以是非结构的，
也可以是结构的。
指针类型属于哪种类型？
2022/12/6 11
数据抽象与抽象数据类型
数据的抽象
抽象数据类型(Abstract Data Type)
抽象数据类型实现
ADT的表示与实现
面向对象的概念
结构化的开发方法与面向对象开发方法
不同点
2022/12/6 12
数据结构的内容
逻辑结构
存储结构
运算集合
2022/12/6 13
逻辑结构
定义：
数据的逻辑结构是指数据元素之间逻辑关系描述。
形式化描述：
Data_Structure=（D,R）其中D是数据元素的
有限集，R是D上关系的有限集。
四类基本的结构
集合结构、线性结构、树型结构、图状结构。
2022/12/6 14
集合结构
定义：
结构中的数据元素之间除了同属于
一个集合的关系外，无任何其它关系。
集合
例如：
2022/12/6 15
线性结构
定义：
结构中的数据元素之间存在着一对
一的线性关系。
例如：
线性表
2022/12/6 16
树型结构
定义：
结构中的数据元素之间存在着一对
多的层次关系。
例如： 树
2022/12/6 17
图状结构或网状结构
定义：
结构中的数据元素之间存在着多对
多的任意关系。
例如： 图
2022/12/6 18
综上所述，数据的逻辑结构可概括为：
线性结构——线性表、栈、队、字符串
数组、广义表
逻辑结构
非线性结构——树、图
逻辑结构
2022/12/6 19
存储结构
定义：
存储结构（又称物理结构）是逻辑结构在计
算机中存储映象，是逻辑结构在计算机中的实
现，它包括数据元素的表示和关系的表示。
形式化描述：
D要存入机器中，建立一从D的数据元素到存储
空间M单元映象S ，D→M，即对于每一个d， d∈D,
都有唯一的z∈M使S（D）=Z, 同时这个映象必须明
显或隐含地体现关系R。
2022/12/6 20
逻辑结构与存储结构的关系为：
存储结构是逻辑关系的映象与元素本身映象，是数
据结构的实现；逻辑结构是数据结构的抽象。
数据元素之间关系在计算机中的表示方法：
顺序映象 （顺序存储结构）
非顺序映象（非顺序存储结构）
存储结构
2022/12/6 21
运算集合
例如工资表：
编 号 姓 名 性别 基本工资 工龄工资 应扣工资 实发工资
100001 张爱芬 女 345．67 145．45 30．00 451．12
100002 李 林 男 445．90 185．60 45．00 586．50
100003 刘晓峰 男 345．00 130．00 25．00 450．00
100004 赵
俊
女 560．90 225．90 65．00 721．80
100005 孙
涛
男 450．60 190．80 50．00 591．80
… … … … … … …
100121 张兴强 男 1025．98 365．53 100．00
2022/12/6 22
数据结构的内容
综上所述，数据结构的内容可归纳为三个部分，
逻辑结构、存储结构和运算集合：
按某种逻辑关系组织起来的一批数据，按一定的映
象方式把它存放在计算机存贮器中，并在这些数据
上定义了一个运算的集合，就叫做数据结构。
2022/12/6 23
算法
算法（Algorithm）定义
算法的特性
算法设计的要求
2022/12/6 24
算法（Algorithm）定义
定义：
Algorithm is a finite set of
rules which gives a sequence of
operation for solving a specific
type of problem.
算法是规则的有限集合，是为解决
特定问题而规定的一系列操作。
2022/12/6 25
算法的特性
1. 有限性：有限步骤之内正常结束，不能形成无穷循环
2. 确定性：算法中的每一个步骤必须有确定含义，无二
义性得以实现。
3. 输 入： 有多个或0个输入
4. 输 出： 至少有一个或多个输出。
5. 可行性：原则上能精确进行，操作可通过已实现基本
运算执行有限次而完成。
2022/12/6 26
算法设计的要求
算法的正确性
算法特征：
可读性
健壮性
高效率和低存储量
例如要求n个数的最大值问题
给出算法如下：
max:=0;
for（i=1 ；i<= n ;i++）
{ scanf("%f", x);
if (x>max) max=x;
}
2022/12/6 27
算法描述的工具
概述：
算法+数据结构=程序
算法、语言、程序的关系
设计实现算法过程步骤
类描述算法的语言选择
2022/12/6 28
算法、语言、程序的关系
1. 算法：描述了数据对象的元素之间的关系
（包括数据逻辑关系、存贮关系描述）。
2. 描述算法的工具：算法可用自然语言、框图或
高级程序设计语言进行描述。
3.程序是算法在计算机中的实现。
2022/12/6 29
设计实现算法过程步骤
1. 找出与求解有关的数据元素之间的关系
2. 确定在某一数据对象上所施加运算
3. 考虑数据元素的存储表示
4. 选择描述算法的语言
5.设计实现求解的算法，并用程序语言加以描述。
2022/12/6 30
类描述算法的语言选择
类语言：
类语言是接近于高级语言而又不是严格的高级语言，
具有高级语言的一般语句设施，撇掉语言中的细节，
以便把注意力主要集中在算法处理步骤本身的描述
上。
2022/12/6 31
3.赋值语句
对C语言作以下描述：
（1）简单赋值
1）〈变量名〉=〈表达式〉
2） 〈变量〉++，
3） 〈变量〉- -，
（2）串联赋值
〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式
〉
2022/12/6 32
对C语言作以下描述：
（4）条件赋值
〈变量名〉=〈条件表达式〉？〈表达式1〉:〈表达式
2〉
（3）成组赋值
(<变量>,<变量2>,<变量3>,…<变量k〉=(<表达式1>,<表达式2 >
,<表达式3>,…<表达式k>)
〈数组名1〉[下标1][下标2]=〈数组名2〉[下标1][下标2]
2022/12/6 33
4.条件选择语句
对C语言作以下描述：
if (<表达式>) 语句;
if (<表达式>) 语句1;
else 语句2;
2022/12/6 34
情况语句
switch (<表达式>）
{case 判断值1:
语句组 1；
break;
case 判断值2:
语句组 2；
break;
……
case 判断值n:
语句组n;
break;
[default:
语句组；
break;]
}
对C语言作以下描述：
2022/12/6 35
对C语言作以下描述：
5.循环语句
for 语句
for (<表达式1>；<表达式2>；<表达式3>）
{循环体语句；}
2022/12/6 36
while 语句
while (<条件表达式>）
{循环体语句；
}
对C语言作以下描述：
do –while 语句
do { 循环体语句
}while (<条件表达式
>）
2022/12/6 37
对算法作性能评价
评价算法的标准：
评价一个算法主要看这个算法所占
用机器资源的多少，而这些资源中时间
代价与空间代价是两个主要的方面，通
常是以算法执行所需的机器时间和所占
用的存储空间来判断一个算法的优劣。
性能评价
有关数量关系计算
2022/12/6 38
性能评价
定义：
对问题规模与该算法在运行时所占的空间S与
所耗费的时间T给出一个数量关系的评价。
问题规模N—对不同的问题其含义不同：
对矩阵是阶数；
对多项式运算是多项式项数；
对图是顶点个数；
对集合运算是集合中元素个数。
2022/12/6 39
有关数量关系计算
数量关系评价体现在时间——算法在机器中所耗
费时间。
数量关系评价体现在空间——算法在机器中所占
存储量。
关于算法执行时间
语句频度
算法的时间复杂度
数据结构中常用的时间复杂度频率计数
最坏时间复杂度
算法的空间复杂度
2022/12/6 40
关于算法执行时间
定义：
一个算法的执行时间大致上等于其所有语
句执行时间的总和，对于语句的执行时间是指
该条语句的执行次数和执行一次所需时间的乘
积。
分析：
不是针对实际执行时间的精确地算出算法执行
具体时间，而是针对算法中语句的执行次数做出估
计，从中得到算法执行时间的信息。
2022/12/6 41
语句频度
定义：
语句频度是指该语句在一个算法中重复执行的
次数。
例如：
两个
矩阵
相乘
算法语句 对应的语句频度
1 for（i=0；i< n;i++） n
2 for （j=0；j<n;j++） n2
3 {c[i][j]=0; n2
4 for (k=0;k< n; k++) n3
c[i][j]=c[i][j]+a[i][k]*b[k][j]; n3
}
总执行次数：Tn=2n
3+2n2 +n
2022/12/6 42
算法的时间复杂度
算法的时间复杂度，即是算法的时间量度
记做： T(n)=O(f(n))
例如给出X=X+1
（1）x=x+1 ；时间复杂度为O(1)，称为常量阶；
（2）for (i=1; i<= n; i++) x=x+1; 时间复杂度为O(n)，称为线性阶；
（3）for (i=1; i<= n; i++)
for (j=1;j<= n; j++) x=x+1; 时间复杂度为O(n2), 称为平方阶。
2022/12/6 43
常用的时间复杂度频率计数
数据结构中常用的时间复杂度频率计数有7个:
O(1) 常数型 O(n)线性型 O(n2)平方型
O(n3)立方型 O(2n)指数型 O(log2n)对数型
O(nlog2n)二维型
按时间复杂度由小到大排列的频率表：
2022/12/6 44
常用的时间复杂度频率计数
常用的时间复杂度频率表：
log
2
n n nlog
2
n n2 n3 2n 一般讲：前
3种可实现，
后3种虽理
论上是可实
现的，实际
上只有对N
限制在很小
范围才有意
义，当N较
大时，不可
能实现。
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 5096 65536
5 32 160 1024 32768 2147483648
2022/12/6 45
最坏时间复杂度
定义：
讨论算法在最坏情况下的时间复杂度，即
分析最坏情况下以估计出算法执行时间的上界。
例如冒泡排序算法
2022/12/6 46
void bubble(int a[], int length)
{将a中整数数组重新排序，达到
递增有序}
int i=0, j, temp;
int change ;
do{
change=false ;
for(j=1;j<length-i;j++)
if(
a[j]>a[j+1])
{
temp= a[j];
a[j]=a[j+1];
a[j+1]=temp;
change=true;
}
i=i+1 ;
}
while(i<length || change==true )
}
最坏时间复杂度
2022/12/6 47
算法的空间复杂度
定义：
用空间复杂度作为算法所需存储空间的量度，
记做： S(n)=O(f (n)) 。
2022/12/6 48
数据结构与C语言表示
数据结构与程序设计的关联性
问题描述：欲求1名学生10次C语言程序设计的测试成
绩总分与平均分。其中10次测验的成绩分别为：80，
85，77，56，68，83，90，92，80，98。
2022/12/6 49
程序示例1-1：
main()
{ int sum，verage； /*总分，平均分*/
int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10； /*10个变量存10次成绩*/
t1=80；t2=85；t3=77；t4=56； t5=68； /*分别赋值*/
t6=83；t7=90；t8=92；t9=80；t10=98;
sum= t1+t2+t3+t4+t5+t6+t7+t8+t9+t10; /*计算总分*/
average=sum/10; /*计算平均分*/
printf(“总分=%d\n”,sum); printf(“平均分=%d\n”, average);
}
2022/12/6 50
根据测试次数与测试成绩的关系，采用数组结构存储测验成绩，提高了程序的
适用范围。
main()
{ int sum，erage；int i;
int t[10] =80，85，77，56，68，83，90，92，80，98} /*分别赋值*/
sum=0; /*总分置初值*/
for (i=0; i<10; i++)
sum=sum+t[i];
average=sum/10; /*计算平均分*/
printf(“总分=%d\n”,sum); printf(“平均分=%d\n”, average);
}
程序示例1-2：
2022/12/6 51
结构化程序设计与函数的模块化
结构化程序设计 ：是为使程序具有合理的结构，以保证
程序正确性而规定的一套程序设计的方法 。
程序设计的实质：算法+数据结构=程序
即“程序是在数据的特定表示方式的基础上，对抽象算
法的具体描述”。
程序结构=控制结构+数据结构
2022/12/6 52
① 结构化程序设计目的
通过设计结构良好的程序，以程序的静态良好结构保证
程序动态执行的正确性，使程序易理解、易调试、易维
护，以提高软件开发的效率，减少出错率。
②结构化程序设计的构成单元
任何程序都可由顺序、选择、重复三种基本控制结构来
组成。
③结构化程序设计方法
其一：“自顶向下，逐步求精”的设计思想 ；其二：“
独立功能，一个入口，一个出口“的模块化结构； 其三：
“仅用三种基本控制结构”的设计原则
2022/12/6 53
面向对象与抽象数据类型
1.面向对象的概念：
面向对象=对象+类+继承+通信
对象：指在应用问题中出现的各种实体、事件、规格说明等
。
类：具有相同属性和服务的对象
继承：是面向对象方法的最有特色的方面。
2022/12/6 54
面向对象程序设计的特点是封装性、继承性和多态性
与数据结构密切相关的是定义在数据结构上的一组操作。
基本操作主要有：
⑴插入：在数据结构中的指定位置上增添新的数据元素 ；
⑵删除：删去数据结构中某个指定数据元素 ；
⑶更新：改变数据结构中某个元素的值，在概念上等价于删
除和插入操作的组合 ；
⑷查找：在数据结构中寻找满足某个特定要求的数据元素
（的位置和值）；
⑸排序：（在线性结构中）重新安排数据元素之间的逻辑
顺序关系，使数据元素按值由小到大或由大到小的次序排列。
2022/12/6 55
结构化与面向对象开发方法的不同点
结构化的开发方法：是面向过程的开发方法，
首先着眼于系统要实现的功能。
面向对象的开发方法：
首先着眼于应用问题所涉及的对象，包括对象、
对象属性和要求的操作，从而建立对象结构和为
解决问题需要执行的时间序列。
2022/12/6 56
数学模型 抽象数据模
型
数据结构
非形式算
法
伪语言程序 可执行程
序
用抽象数据类型的概念来指导问题的求解过程：
2．抽象数据类型与问题求解方法
定义：
抽象数据类型（简称ADT）是指基于一类逻辑
关系的数据类型以及定义在这个类型之上的一
组操作。
一个抽象数据类型确定了一个模型，但将模型的实现细节
隐藏起来；它定义了一组运算，但将运算的实现过程隐藏
起来。
2022/12/6 57
数据的抽象
汇编语言中十进制表示的数据、
等, 它们是二进制数据的抽象;
高级语言中，给出更高一级的数据抽象，如整
型、实型、字符型等，
还可以进一步定义更高级的数据抽象，如各种表、
队、栈、树、图、窗口、管理器等复杂的抽象数
据类型。
2022/12/6 58
抽象数据类型
线性表的抽象数据类型的描述：
ADT Linear_list
数据元素 所有a
i
属于同一数据对象，i=1，2，……，n n≥0
；
逻辑结构 所有数据元素a
i
（i=1，2，…，n-1）存在次序关系
<a
i
， a
i+1
>，a
i
无前趋，a
n
无后继；
操作 设L为Linear_list
Initial(L)初始化空线性表；
Length(L)求线性表的表长；
Get(L,i)取线性表的第i个元素；
Insert(L,i,b)在线性表的第i个位置插入元素b；
Delete(L,i)删除线性表的第i个元素；
2022/12/6 59
抽象数据类型实现
传统的面向过程的程序设计
实现的三种方法：
“包”、“模型”的设计方法
面向对象的程序设计（Object Oriented
Programming，简称OOP）
2022/12/6 60
ADT的表示与实现
ADT的定义：
ADT <ADT名>
{ 数据对象:<数据对象的定义>
结构关系:<结构关系的定义>
基本操作:<基本操作的定义>
}ADT <ADT名>
基本操作的定义格式为：<操作名称> (参数表)
操作前提:<操作前提描述>
操作结果:<操作结果描述>
2022/12/6 61
关于参数传递：
参数表中的参数有值参和变参两种。
用标准C语言表示和实现ADT描述时，主要有两个方面：
二、用C语言函数实现各操作。
一、通过结构体将int、float等固有类型组合到一起,构成一
个结构类型,再用typedef为该类型或该类型指针重新起一个
名字。
ADT的表示与实现
2022/12/6 62
算法描述规范与设计风格
1. 算法表示格式与函数模块化
[函数返回值类型] 函数名（[形式参数及说明]）
{ 内部数据说明；
执行语句组；
} /*函数名*/
•算法表示格式
2022/12/6 63
算法描述规范与设计风格
•函数的模块化
1. 算法表示格式与函数模块化
[包含文件语句]
[宏定义语句]
[自定义类型语句]
[所有子函数的原型说明]
[子函数1定义]
.
.
.
[子函数n定义]
[主函数定义]
2022/12/6 64
2. 算法描述要点
算法描述规范与设计风格
•加上必要的注释
注释形式可以用/*字符串*/
•避免函数返回值隐含说明
•预定义常量和类型
# define TRUE 1
# define FALSE 0
# define MAXSIZE 100
# define OK 1
# define ERROR 0
2022/12/6 65
•避免可能出现的二义性表达
•注意不同的退出语句区别
return <表达式>或return：用于函数结束。
break语句：可用在循环语句或switch语句中结束循环过程或
跳出情况语句。
continue语句：可用在循环语句中结束本次循环过程，进入
下一次循环过程。
exit语句：表示出现异常情况时，控制退出函数。
•使用有意义的函数名与变量名
2. 算法描述要点
算法描述规范与设计风格
•简化输入、输出表述
•规范多分支转向
2022/12/6 66
3. 与参数传递的相关技术
算法描述规范与设计风格
•变量的作用域
全局变量：程序中所有函数都可以访问的量
局部变量：只能在该函数中访问的量。
•参数传递方式
参数传递是函数之间进行信息通讯的重要渠道。
其参数传递的主要方式有传值和传地址两类。函数
参数表中的参数有两种：第一种参数只为操作提供
待处理数据,又称值参；第二种参数既能为操作提供
待处理数据，又能返回操作结果，也称变量参数。
2022/12/6 67
#include <>
viod swap1(int a,int b)
{ int c;
c=a; a=b; b=c;
printf(“swap1中的a= %d,b=%d”,a,b);
}
viod swap2(int *a,int *b)
{ int c;
c=*a, *a=*b, *b=c;
}
关于参数传递示例源程序：
2022/12/6 68
void main()
{ int x=100,y=800;
swap1(x,y); /*调用函数swap1()*/
printf(“\n调用swap1后x= %d,y=%d”,x,y); /*输出调用swap1后的数据*/
x=100;y=800;
swap2(&x,&y); /*调用函数swap2()*/
printf(“\n调用swap2后x=%d,y=%d”,x,y); /*输出调用swap2后的数据*/
}
关于参数传递示例源程序：
2022/12/6 69
4. 函数结果的带出方式
算法描述规范与设计风格
三种带出方式:全程量、函数返回值、传址参数
若函数结果需要带出多个值，该怎样实现?可以采用①全局
变量方式带出，②通过地址传递带出（数组方式、结构体方
式、指针方式）两类方式之一来实现。
通过参数表的参数传递是一种参数显式传递方式，而通过
全局变量是一种隐式参数传递，一个函数中对全局变量的
改变会影响其它程序的调用，使用全局变量必须注意这个
问题。
2022/12/6 70
①全局变量方式：
int MIN; /* 全局变量 */
int fun1(int a[], int n)
/*通过函数return返回最大值，通过全局变量MIN带回最小值*/
{ int i,max;
max=MIN=a[0]; //给最大值最小值赋初值
for (i=0;i<n;i++)
{
if(a[i]>max) max=a[i];
if (a[i]<MIN) MIN=a[i];
}
return(max);
}
一个全局变量方式带出的例子
2022/12/6 71
int *fun2(int a[],int n)
/*将最大、最小值放到数组b中，通过return返回*/
{ static int b[2];
b[0]=b[1]=a[0]; //给最大值最小值赋初值
int i;
for (i=1;i<n;i++)
{
if (a[i]>b[0])
b[0]=a[i];
if (a[i]<b[1])
b[1]=a[i];
}
return(b);
}
数组方式带出的例子
2022/12/6 72
Data *fun3(int a[],int n)
/*将最大、最小值放到结构体指针p中，通过return返回*/
{ Data *p;
int i;
p=(Data *)malloc(sizeof(Data *)); //指针初始化
p->max=p->min=a[0]; //给最大值最小值赋初值
for(i=1;i<n;i++)
{
if (a[i]>p->max)
p->max=a[i];
if (a[i]<p->min)
p->min=a[i];
}
return(p);
}
结构体方式带出的例子
2022/12/6 73
Data fun4(int a[],int n)
/*将最大、最小值放到结构体p中，通过结构体p带回返回值*/
{ Data p;
int i;
==a[0]; //给最大值最小值赋初值
for(i=1;i<n;i++)
{
if (a[i]>)
=a[i];
if (a[i]<)
=a[i];
}
return(p);
}
指针方式带出的例子
2022/12/6 74
关于学习数据结构
数据结构课程地位
数据结构课程学习特点
关于本书内容编写说明
2022/12/6 75
数据结构课程地位
数据结构与其它课程关系图：
数据结构
数据库
人工智能
专业基础课
操作系统
编译原理
非线性程序设计
离散数学
语言程序设计 计算机原理设计
2022/12/6 76
数据结构课程学习特点
教学目标：
学会分析数据对象的特征，掌握数据组织方法和计算
机的表示方法，以便为应用所涉及数据选择适当
的逻辑结构、存储结构及相应算法，初步掌握算
法时间空间分析的技巧，培养良好的程序设计技
能。
学习方法：
学习数据结构，必须经过大量的实践，
在实践中体会构造性思维方法，掌握数据组织与
程序设计的技术。
2022/12/6 77
关于本书内容编写说明
本书基本结构
第一部分：数据结构的基本概念（第1章）
第二部分：基本的数据结构
包括：线性结构—线性表、栈和队列、串、
数组与广义表 （第2—5章）
非线性结构—树、图（第6、7章）
第三部分：基本技术
包括：查找技术与排序技术（第8、9、10章）
2022/12/6 78
要点小结
1. 掌握数据结构的基本概念
数据的逻辑结构
数据的存储结构
定义其上的运算集合
线性结构（线性表、栈、队列、字符串、数组、广义表）
非线性结构
顺序存储
非顺序存储
数据结构包括数据的逻辑结构、存储结构和运算集
合这三个部分
2022/12/6 79
2. 注意逻辑结构与存储结构的区别
要点小结
•逻辑结构定义了数据元素之间的逻辑关系。
•存储结构是逻辑结构在计算机中实现。
• 一种逻辑结构可以采用不同存储方式存放在计算
机中，但都必须反映出要求的逻辑关系。
2022/12/6 80
要点小结
3．面向对象概念：理解什么是数据类型、抽象数据类型、
数据抽象和信息隐蔽规则。了解什么是面向对象。
• 抽象数据类型的封装性；
• Coad与Yourdon定义：面向对象=对象+类+继
承+通信；
• 面向对象方法着眼点在于应用问题所涉及的
对象。
2022/12/6 81
4．算法与算法分析：理解算法的定义、算法的特性、
算法的时间代价、算法的空间代价。
要点小结
•算法与程序的不同之处需要从算法的特性来解释；
•算法的正确性是最重要的要求，理解正确性的层次；
•算法的可读性是必须考虑的，算法描述的格式与方法；
•算法的时间代价是指算法的渐进时间复杂性度量。
