数 据 结 构主 讲,唐轶媛上机及批改作业,张浩启迪管理课程
22
数据结构教程 (第 2版）
李春葆 编著 清华大学出版社参考书目：
1.严蔚敏，吴伟民,数据结构（ C语言版）,清华大学出版社
2.陈元春，张亮等,实用数据结构基础,中国铁道出版社启迪管理课程
33
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
44
1.1 学习,数据结构,的意义及要求意义
1.算法和数据结构是 计算机科学 的两大支柱
2.数据结构是程序设计的基础数据结构是设计 OS,DBMS、编译等 系统程序 和各种 应用程序 的重要基础程序 =算法 +数据结构计算机科学早期定义为：研究 算法 的科学近期定义为：研究 数据 的科学。
启迪管理课程
55
1.1 学习,数据结构,的意义及要求意义
3,数据结构是计算机专业及相关专业的一门专业基础课
是一门必修的学位课程
是计算机研究生入学考试必考科目
是软件人员水平考试内容启迪管理课程
66
1.1 学习,数据结构,的意义及要求要求
掌握各类 基本数据结构类型 和相应的 存储结构
提高阅读和编写 算法 的能力
能针对给定问题,选择 相适应的数据结构，并能 设计和分析算法启迪管理课程
77
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
88
1.2,数据结构,的主要内容例 1：
61011219880331988132602661599448933537
9234099
610112198803319881 某人身份证号码
3260266 物电学院办公室电话号码
15994489335 手机号码
379234099 QQ号码结论 1：杂乱的数据不能表达和交流信息。数据都是按一定的规则和顺序进行排列的。
启迪管理课程
99
1.2,数据结构,的主要内容例 2：
学号 姓名 性别 班号
1 张斌 男 9901
8 刘丽 女 9902
34 李英 女 9901
20 陈华 男 9902
12 王奇 男 9901
26 董强 男 9902
5 王萍 女 9901
有一学生表 (数据）如下所示：要求设计一个算法，给定一个学生姓名，能查出该生的相关信息。
启迪管理课程
1010
1.2,数据结构,的主要内容
如果姓名的排列次序无规律，则只能逐个比较姓名进行查找
如果按字典顺序组织，那么查找就快捷多了结论 2：数据之间是有联系的这些联系常常影响算法的选择和算法执行的效率
,DS,就是要研究数据之间的联系例 2：
启迪管理课程
1111
1.2,数据结构,的主要内容结论 3：数据之间是有结构的例 3,大学生管理机构学校中文学院 物电学院… …
一年级 二年级 三年级 四年级电气 1班 … 电气 4班张三 李四…
,DS,就是要研究数据之间的各类结构启迪管理课程
1212
1.2,数据结构,的主要内容结论 4：在某种数据结构上可定义一组运算例 4,图书目录管理
,DS,就是要研究各类数据结构上的各种运算设每个书目含,书名，作者，登陆号，分类，出版年月对图书目录常用的操作如下：
查找：某书是否在书库中？
插入：购进新书时要进行入库；
删除：报废或丢失的书，要在目录中去掉启迪管理课程
1313
1.2,数据结构,的主要内容综上所述：,DS,主要研究内容：
数据的各种逻辑结构和物理结构，以及它们之间的相应关系并对每种结构定义相适应的各种运算设计出相应的算法分析算法的效率启迪管理课程
1414
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
1515
1.3 基本术语
数据 (Data):所有能被计算机处理的 符号 的集合。
数据元素 (Data Element):是数据这个集合中的一个个体。
设定一个数据集合为,D={d1,d2,…d n}
则 di属于 D，并称 di为数据元素。
数据项 (Data Item):数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。
启迪管理课程
1616
1.3 基本术语
数据结构 (Data Structure):是带有结构的数据元素的集合。
所谓结构就是数据元素之间的关系，即描述数据元素之间的运算及运算规则用集合的形式描述，数据结构是一个二元组：
DS＝（ D,R）
其中,D是数据元素的集合,R是 D上关系的集合数据元素和其相互关系的集合称为数据结构简言之：
启迪管理课程
1717
1.3 基本术语
逻辑结构 (Logical Structure):指数据元素之间的逻辑关系。
(1)集合元素间关系仅有,同属于一个集合,
(2)线性结构有一个开始结点和一个终端结点，其余结点有且仅有一个前驱，有且仅有一个后继。
d1 d2 d3 d4 d5 d6 d7
启迪管理课程
1818
1.3 基本术语
逻辑结构 (Logical Structure):指数据元素之间的逻辑关系。
(3)树形结构每个结点最多只有一个前驱,但可以有多个后继。
a
b c
d e f
(4)图形结构每个结点的前驱和后继可以有任意多个。
a
b c
d e f
启迪管理课程
1919
1.3 基本术语
物理结构 (Physical Structure):指数据元素及其关系在计算机存储器中存储方式，即数据结构在机内的表示。
(1)顺序存储方法
(2)链式存储方法
(3)索引存储方法
(4)散列存储方法启迪管理课程
2020
1.3 基本术语
数据类型 (Data Type):是一个值的集合和定义在此集合上的一组操作的总称。
不同类型的变量，其所能取的值的范围不同,所能进行的操作不同。
简单类型,值是不可分解的，如 C语言中的基本类型
（整型、实型、字符型等）、指针类型和空类型。
结构类型,值由若干成分按某种结构组成，并且其中的成分可以是非结构的，也可以是结构的。 如 C
语言中的数组、结构体、共用体和 用户自定义的类型。
启迪管理课程
2121
1.3 基本术语
数据类型可以被定义为是一种数据结构和对该数据结构允许进行的运算集 。 是在某种程序设计语言中已经实现了的数据结构。
数据结构是指计算机处理的数据元素的组织形式和相互关系，借助程序设计语言提供的数据类型可构造出各种新的数据结构。
数据类型 & 数据结构启迪管理课程
2222
1.3 基本术语
抽象数据类型 (Abstract Data Type,ADT):仅指用户进行软件系统设计时从问题的数学模型中抽象出来的 逻辑数据结构 和逻辑数据结构上的 运算 。
ADT 抽象数据类型名
{
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本运算,<基本运算的定义 >
}ADT抽象数据类型名启迪管理课程
2323
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
2424
1.4 算法描述和算法分析一,算法 (Algorithm)
1.算法概念：算法是一个有限的指令集，遵循指令流可以完成特定的功能。
有穷性,算法经有限步后结束；
确定性,下一步必须是明确的；
可行性,每一步是可执行的；
输入,算法加工的对象的量值；
输出,算法的功能；
2.算法基本特性：
启迪管理课程
2525
1.4 算法描述和算法分析一,算法 (Algorithm)
3.算法与程序的区别
算法 是指解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法
程序 是用某种程序设计语言对算法的具体实现。
程序可以是无穷的，例如 OS；算法是有穷的
程序可以是错误的，算法必须是正确的；
程序是用程序设计语言描述，在机器上可以执行；算法还可以用流程图、表、自然语言等方式描述。
主要区别在,有穷性、正确性和描述方法启迪管理课程
2626
1.4 算法描述和算法分析一,算法 (Algorithm)
3.算法与程序的区别怎样的程序可以称得上是算法？
看下面的一段描述
void exam1()
{
n＝ 2;
while (n%2＝＝ 0)
n＝ n+2;
printf("%d\n",n);
}
启迪管理课程
2727
1.4 算法描述和算法分析二,算法描述本书中采用 C/C++语言描述算法。
说明,C++语言中提供了一种 引用 运算符
,&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象 (目标 )的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。
注意,Turbo C不支持引用类型。
启迪管理课程
2828
例如：
int a=4; /*a为普通的整型变量 */
int &b=a; /*b是 a的引用变量 */
这里说明 b变量是变量 a的引用,b也等于 4,之后这两个变量同步改变 。 当 a改变时 b也同步改变,同样,当
b改变时 a也同步改变 。
1.4 算法描述和算法分析二,算法描述
引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参。
启迪管理课程
2929
1.4 算法描述和算法分析二,算法描述例如,有如下函数 (其中的形参均为引用型形参 )：
void swap(int &x,int &y)
/*形参前的,&”符号不是指针运算符即不表示取地址运算 */
{
int tmp=x;
x=y;y=tmp
}
当用执行语句 swap(a,b)时,a和 b的值发生了交换。
30
#include "stdafx.h"
void SwapData(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int main(int argc,char* argv[])
{
int i=2,j=5;
SwapData(i,j);
printf("\n%d,%d\n",i,j);
return 0;
}
2
i
5
ja=i b=j
2
temp
5 2
形参 a,b分别是实参 i与 j的引用，在函数 SwapData()中对引用名 a与 b的操作就是对实参 i
与 j的操作，从而实现形参向实参
“传值”的功能。
形参 a是实参 i的“小名”
形参 b是实参 j的“小名”
四,C++的引用及在函数,传值”中的应用 — 例
1
启迪管理课程
3131
1.4 算法描述和算法分析二,算法描述反之，有以下函数 swap1()，当用执行语句
swap1(a,b)时,a和 b的值不会发生交换。
void swap1(int x,int y)
{
int temp;
temp=a;a=b;b=temp;
}
32
#include "stdafx.h"
void SwapData(int a,int b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int main(int argc,char* argv[])
{
int i=2,j=5;
SwapData(i,j);
printf("\n%d,%d\n",i,j);
return 0;
}
三,C语言的函数及形参与实参
2
i
5
j
2
a
5
b
2
temp
5 2
a
× ×
C/C++只容许实参向形参传递值，但不容许形参向实参传回值。
所以函数 SwapData不能使主函数的两个变量 i与 j的值产生交换。
即 C/C++实参与形参间的数据传递是单向的“值传递” 方式如何用函数 SwapData()实参主函数两变量 i与 j的数值交换？
启迪管理课程
3333
1.4 算法描述和算法分析二,算法描述在 C语言中，由于不支持引用类型，所以采用指针的方式来回传形参的值，需将上述函数改为：
int swap2(int *x,int *y)
{
int temp;
temp=*a; /*将 a的值放在 temp中 */
*a=*b; /*将 a所指的值改为 *b*/
*b=temp； /*将 b所指的值改为 temp*/
}
上述函数的调用改为 swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。
启迪管理课程
3434
1.4 算法描述和算法分析三,算法分析如何衡量一个正确算法的优劣？
衡量的 三个尺度：
运行所花费的时间（算法的时间特性即算法效率）
所占用存储空间的大小（算法的空间特性）
其他（可读性、可使用性、健壮性等）
时间和空间的巨大改进源于更好的数据结构或算法启迪管理课程
3535
1.4 算法描述和算法分析算法效率衡量方法和准则缺点,1,必须执行程序
2,其它因素掩盖算法本质
事后统计法
事前分析估算法启迪管理课程
3636
1.4 算法描述和算法分析与算法效率相关的因素
问题的规模
编写程序的计算机语言
编译程序产生的机器语言代码的质量
计算机执行指令的速度启迪管理课程
3737
1.4 算法描述和算法分析如何估算算法时间复杂度？
算法＝控制结构 (顺序,分支和循环 )＋原操作对所研究的问题来说是基本运算的原操作。
语句频度 （ Frequency Count）
语句可能重复执行的最大次数。
时间复杂度 （ Time Complexity）
基本运算 （ Base Operation）
算法的基本运算的次数。
原操作,本来是指计算机执行的基本指令,但用高级语言时是指固有数据类型的操作 。
启迪管理课程
3838
1.4 算法描述和算法分析
问题的规模,算法求解问题的输入量 n（初始数据量）
时间复杂度,即算法所耗费的时间 T(n)，是问题规模的函数
渐近时间复杂度,当问题的规模 n趋于无穷大时，时间复杂度 T(n)的数量级（阶）
cnfnTn )(/)(lim
其中 f(n)是 最简单 的函数,c为不等于零的常数记 T(n)=O(f(n))为算法的渐近时间复杂度
2/)1232(lim/)(lim 3233 nnnnnnT nn
1)2/()1232(lim)2/()(lim 3233 nnnnnnT nn
)()( 3nOnT?
启迪管理课程
3939
1.4 算法描述和算法分析例,程序段 语句频度 时间复杂度
1,x=x+1; 1 O(1) 常数阶
2,For (i=0;i<n;i++) n+1
x=x+1; n O(n) 线性阶
3,For (i=0;i<n;i++;) n+1
For (j=0;j<n;j++;) n(n+1)
x=x+1; n2 O(n2) 平方阶对多重循环语句只需考虑最里层循环体的语句的频度，
而忽略步长增值、终值判断、控制转移等。
启迪管理课程
4040
例：求两个 n阶方阵的相加 C=A+B的算法如下,分析其时间复杂度 。
#define MAX 20 /*定义最大的方阶 */
void matrixadd(int n,int A[MAX][MAX],
int B[MAX][MAX],int C[MAX][MAX])
{ int i,j;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
C[i][j]=A[i][j]+B[i][j];
}
该算法中的基本运算是两重循环中最深层的语句
C[i][j]=A[i][j]+B[i][j],分析它的频度,即,
T(n)=
=O(n2)
1
0
2
1
0
1
0
1
0
*11
n
i
n
i
n
i
n
j
nnnnn
启迪管理课程
4141
1.4 算法描述和算法分析
常见的时间复杂度按数量级递增排列如下：
O(1)<O(logn)
<O(n)<O(nlogn)
<O(n2)<O(n3)
<O(2n)<O(n!)
<O(nn)
启迪管理课程
4242
第一章 小 结本章主要学习要点如下：
(1)数据结构的定义,数据结构包含的逻辑结构,存储结构和运算三方面的相互关系 。
(2)各种逻辑结构即线性结构,树形结构和图形结构之间的差别 。
(3)算法的定义及其特性。
(4)算法的时间复杂度分析。
本章练习：
完成 P25的习题练习题 1.3,P26的上机实验题 1.1。
22
数据结构教程 (第 2版）
李春葆 编著 清华大学出版社参考书目：
1.严蔚敏，吴伟民,数据结构（ C语言版）,清华大学出版社
2.陈元春，张亮等,实用数据结构基础,中国铁道出版社启迪管理课程
33
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
44
1.1 学习,数据结构,的意义及要求意义
1.算法和数据结构是 计算机科学 的两大支柱
2.数据结构是程序设计的基础数据结构是设计 OS,DBMS、编译等 系统程序 和各种 应用程序 的重要基础程序 =算法 +数据结构计算机科学早期定义为：研究 算法 的科学近期定义为：研究 数据 的科学。
启迪管理课程
55
1.1 学习,数据结构,的意义及要求意义
3,数据结构是计算机专业及相关专业的一门专业基础课
是一门必修的学位课程
是计算机研究生入学考试必考科目
是软件人员水平考试内容启迪管理课程
66
1.1 学习,数据结构,的意义及要求要求
掌握各类 基本数据结构类型 和相应的 存储结构
提高阅读和编写 算法 的能力
能针对给定问题,选择 相适应的数据结构，并能 设计和分析算法启迪管理课程
77
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
88
1.2,数据结构,的主要内容例 1：
61011219880331988132602661599448933537
9234099
610112198803319881 某人身份证号码
3260266 物电学院办公室电话号码
15994489335 手机号码
379234099 QQ号码结论 1：杂乱的数据不能表达和交流信息。数据都是按一定的规则和顺序进行排列的。
启迪管理课程
99
1.2,数据结构,的主要内容例 2：
学号 姓名 性别 班号
1 张斌 男 9901
8 刘丽 女 9902
34 李英 女 9901
20 陈华 男 9902
12 王奇 男 9901
26 董强 男 9902
5 王萍 女 9901
有一学生表 (数据）如下所示：要求设计一个算法，给定一个学生姓名，能查出该生的相关信息。
启迪管理课程
1010
1.2,数据结构,的主要内容
如果姓名的排列次序无规律，则只能逐个比较姓名进行查找
如果按字典顺序组织，那么查找就快捷多了结论 2：数据之间是有联系的这些联系常常影响算法的选择和算法执行的效率
,DS,就是要研究数据之间的联系例 2：
启迪管理课程
1111
1.2,数据结构,的主要内容结论 3：数据之间是有结构的例 3,大学生管理机构学校中文学院 物电学院… …
一年级 二年级 三年级 四年级电气 1班 … 电气 4班张三 李四…
,DS,就是要研究数据之间的各类结构启迪管理课程
1212
1.2,数据结构,的主要内容结论 4：在某种数据结构上可定义一组运算例 4,图书目录管理
,DS,就是要研究各类数据结构上的各种运算设每个书目含,书名，作者，登陆号，分类，出版年月对图书目录常用的操作如下：
查找：某书是否在书库中？
插入：购进新书时要进行入库；
删除：报废或丢失的书，要在目录中去掉启迪管理课程
1313
1.2,数据结构,的主要内容综上所述：,DS,主要研究内容：
数据的各种逻辑结构和物理结构，以及它们之间的相应关系并对每种结构定义相适应的各种运算设计出相应的算法分析算法的效率启迪管理课程
1414
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
1515
1.3 基本术语
数据 (Data):所有能被计算机处理的 符号 的集合。
数据元素 (Data Element):是数据这个集合中的一个个体。
设定一个数据集合为,D={d1,d2,…d n}
则 di属于 D，并称 di为数据元素。
数据项 (Data Item):数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。
启迪管理课程
1616
1.3 基本术语
数据结构 (Data Structure):是带有结构的数据元素的集合。
所谓结构就是数据元素之间的关系，即描述数据元素之间的运算及运算规则用集合的形式描述，数据结构是一个二元组：
DS＝（ D,R）
其中,D是数据元素的集合,R是 D上关系的集合数据元素和其相互关系的集合称为数据结构简言之：
启迪管理课程
1717
1.3 基本术语
逻辑结构 (Logical Structure):指数据元素之间的逻辑关系。
(1)集合元素间关系仅有,同属于一个集合,
(2)线性结构有一个开始结点和一个终端结点，其余结点有且仅有一个前驱，有且仅有一个后继。
d1 d2 d3 d4 d5 d6 d7
启迪管理课程
1818
1.3 基本术语
逻辑结构 (Logical Structure):指数据元素之间的逻辑关系。
(3)树形结构每个结点最多只有一个前驱,但可以有多个后继。
a
b c
d e f
(4)图形结构每个结点的前驱和后继可以有任意多个。
a
b c
d e f
启迪管理课程
1919
1.3 基本术语
物理结构 (Physical Structure):指数据元素及其关系在计算机存储器中存储方式，即数据结构在机内的表示。
(1)顺序存储方法
(2)链式存储方法
(3)索引存储方法
(4)散列存储方法启迪管理课程
2020
1.3 基本术语
数据类型 (Data Type):是一个值的集合和定义在此集合上的一组操作的总称。
不同类型的变量，其所能取的值的范围不同,所能进行的操作不同。
简单类型,值是不可分解的，如 C语言中的基本类型
（整型、实型、字符型等）、指针类型和空类型。
结构类型,值由若干成分按某种结构组成，并且其中的成分可以是非结构的，也可以是结构的。 如 C
语言中的数组、结构体、共用体和 用户自定义的类型。
启迪管理课程
2121
1.3 基本术语
数据类型可以被定义为是一种数据结构和对该数据结构允许进行的运算集 。 是在某种程序设计语言中已经实现了的数据结构。
数据结构是指计算机处理的数据元素的组织形式和相互关系，借助程序设计语言提供的数据类型可构造出各种新的数据结构。
数据类型 & 数据结构启迪管理课程
2222
1.3 基本术语
抽象数据类型 (Abstract Data Type,ADT):仅指用户进行软件系统设计时从问题的数学模型中抽象出来的 逻辑数据结构 和逻辑数据结构上的 运算 。
ADT 抽象数据类型名
{
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本运算,<基本运算的定义 >
}ADT抽象数据类型名启迪管理课程
2323
第一章 绪 论学习,数据结构,的意义及要求
,数据结构,的主要内容基本术语算法描述及分析启迪管理课程
2424
1.4 算法描述和算法分析一,算法 (Algorithm)
1.算法概念：算法是一个有限的指令集，遵循指令流可以完成特定的功能。
有穷性,算法经有限步后结束；
确定性,下一步必须是明确的；
可行性,每一步是可执行的；
输入,算法加工的对象的量值；
输出,算法的功能；
2.算法基本特性：
启迪管理课程
2525
1.4 算法描述和算法分析一,算法 (Algorithm)
3.算法与程序的区别
算法 是指解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法
程序 是用某种程序设计语言对算法的具体实现。
程序可以是无穷的，例如 OS；算法是有穷的
程序可以是错误的，算法必须是正确的；
程序是用程序设计语言描述，在机器上可以执行；算法还可以用流程图、表、自然语言等方式描述。
主要区别在,有穷性、正确性和描述方法启迪管理课程
2626
1.4 算法描述和算法分析一,算法 (Algorithm)
3.算法与程序的区别怎样的程序可以称得上是算法？
看下面的一段描述
void exam1()
{
n＝ 2;
while (n%2＝＝ 0)
n＝ n+2;
printf("%d\n",n);
}
启迪管理课程
2727
1.4 算法描述和算法分析二,算法描述本书中采用 C/C++语言描述算法。
说明,C++语言中提供了一种 引用 运算符
,&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象 (目标 )的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。
注意,Turbo C不支持引用类型。
启迪管理课程
2828
例如：
int a=4; /*a为普通的整型变量 */
int &b=a; /*b是 a的引用变量 */
这里说明 b变量是变量 a的引用,b也等于 4,之后这两个变量同步改变 。 当 a改变时 b也同步改变,同样,当
b改变时 a也同步改变 。
1.4 算法描述和算法分析二,算法描述
引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参。
启迪管理课程
2929
1.4 算法描述和算法分析二,算法描述例如,有如下函数 (其中的形参均为引用型形参 )：
void swap(int &x,int &y)
/*形参前的,&”符号不是指针运算符即不表示取地址运算 */
{
int tmp=x;
x=y;y=tmp
}
当用执行语句 swap(a,b)时,a和 b的值发生了交换。
30
#include "stdafx.h"
void SwapData(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int main(int argc,char* argv[])
{
int i=2,j=5;
SwapData(i,j);
printf("\n%d,%d\n",i,j);
return 0;
}
2
i
5
ja=i b=j
2
temp
5 2
形参 a,b分别是实参 i与 j的引用，在函数 SwapData()中对引用名 a与 b的操作就是对实参 i
与 j的操作，从而实现形参向实参
“传值”的功能。
形参 a是实参 i的“小名”
形参 b是实参 j的“小名”
四,C++的引用及在函数,传值”中的应用 — 例
1
启迪管理课程
3131
1.4 算法描述和算法分析二,算法描述反之，有以下函数 swap1()，当用执行语句
swap1(a,b)时,a和 b的值不会发生交换。
void swap1(int x,int y)
{
int temp;
temp=a;a=b;b=temp;
}
32
#include "stdafx.h"
void SwapData(int a,int b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int main(int argc,char* argv[])
{
int i=2,j=5;
SwapData(i,j);
printf("\n%d,%d\n",i,j);
return 0;
}
三,C语言的函数及形参与实参
2
i
5
j
2
a
5
b
2
temp
5 2
a
× ×
C/C++只容许实参向形参传递值，但不容许形参向实参传回值。
所以函数 SwapData不能使主函数的两个变量 i与 j的值产生交换。
即 C/C++实参与形参间的数据传递是单向的“值传递” 方式如何用函数 SwapData()实参主函数两变量 i与 j的数值交换？
启迪管理课程
3333
1.4 算法描述和算法分析二,算法描述在 C语言中，由于不支持引用类型，所以采用指针的方式来回传形参的值，需将上述函数改为：
int swap2(int *x,int *y)
{
int temp;
temp=*a; /*将 a的值放在 temp中 */
*a=*b; /*将 a所指的值改为 *b*/
*b=temp； /*将 b所指的值改为 temp*/
}
上述函数的调用改为 swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。
启迪管理课程
3434
1.4 算法描述和算法分析三,算法分析如何衡量一个正确算法的优劣？
衡量的 三个尺度：
运行所花费的时间（算法的时间特性即算法效率）
所占用存储空间的大小（算法的空间特性）
其他（可读性、可使用性、健壮性等）
时间和空间的巨大改进源于更好的数据结构或算法启迪管理课程
3535
1.4 算法描述和算法分析算法效率衡量方法和准则缺点,1,必须执行程序
2,其它因素掩盖算法本质
事后统计法
事前分析估算法启迪管理课程
3636
1.4 算法描述和算法分析与算法效率相关的因素
问题的规模
编写程序的计算机语言
编译程序产生的机器语言代码的质量
计算机执行指令的速度启迪管理课程
3737
1.4 算法描述和算法分析如何估算算法时间复杂度？
算法＝控制结构 (顺序,分支和循环 )＋原操作对所研究的问题来说是基本运算的原操作。
语句频度 （ Frequency Count）
语句可能重复执行的最大次数。
时间复杂度 （ Time Complexity）
基本运算 （ Base Operation）
算法的基本运算的次数。
原操作,本来是指计算机执行的基本指令,但用高级语言时是指固有数据类型的操作 。
启迪管理课程
3838
1.4 算法描述和算法分析
问题的规模,算法求解问题的输入量 n（初始数据量）
时间复杂度,即算法所耗费的时间 T(n)，是问题规模的函数
渐近时间复杂度,当问题的规模 n趋于无穷大时，时间复杂度 T(n)的数量级（阶）
cnfnTn )(/)(lim
其中 f(n)是 最简单 的函数,c为不等于零的常数记 T(n)=O(f(n))为算法的渐近时间复杂度
2/)1232(lim/)(lim 3233 nnnnnnT nn
1)2/()1232(lim)2/()(lim 3233 nnnnnnT nn
)()( 3nOnT?
启迪管理课程
3939
1.4 算法描述和算法分析例,程序段 语句频度 时间复杂度
1,x=x+1; 1 O(1) 常数阶
2,For (i=0;i<n;i++) n+1
x=x+1; n O(n) 线性阶
3,For (i=0;i<n;i++;) n+1
For (j=0;j<n;j++;) n(n+1)
x=x+1; n2 O(n2) 平方阶对多重循环语句只需考虑最里层循环体的语句的频度，
而忽略步长增值、终值判断、控制转移等。
启迪管理课程
4040
例：求两个 n阶方阵的相加 C=A+B的算法如下,分析其时间复杂度 。
#define MAX 20 /*定义最大的方阶 */
void matrixadd(int n,int A[MAX][MAX],
int B[MAX][MAX],int C[MAX][MAX])
{ int i,j;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
C[i][j]=A[i][j]+B[i][j];
}
该算法中的基本运算是两重循环中最深层的语句
C[i][j]=A[i][j]+B[i][j],分析它的频度,即,
T(n)=
=O(n2)
1
0
2
1
0
1
0
1
0
*11
n
i
n
i
n
i
n
j
nnnnn
启迪管理课程
4141
1.4 算法描述和算法分析
常见的时间复杂度按数量级递增排列如下：
O(1)<O(logn)
<O(n)<O(nlogn)
<O(n2)<O(n3)
<O(2n)<O(n!)
<O(nn)
启迪管理课程
4242
第一章 小 结本章主要学习要点如下：
(1)数据结构的定义,数据结构包含的逻辑结构,存储结构和运算三方面的相互关系 。
(2)各种逻辑结构即线性结构,树形结构和图形结构之间的差别 。
(3)算法的定义及其特性。
(4)算法的时间复杂度分析。
本章练习：
完成 P25的习题练习题 1.3,P26的上机实验题 1.1。
