第 1章 绪论
1.2 算法及其描述
1.1 什么是数据结构
1.3 算法分析本章小结
1.1.1 数据结构的定义
1.1.2 逻辑结构类型
1.1.3 存储结构类型
1.1.4 数据结构和数据类型
1.1 什么是数据结构数据,是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。
数据元素：是数据 (集合 )中的一个“个体”,
是数据的基本单位。
1.1.1 数据结构的定义例如,200402班为一个学生数据,而其中的
,张三,是一个数据元素 )。
数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。
因此,可时把数据结构看成是带结构的数据元素的集合。
数据结构包括如下几个方面：
(1)数据元素之间的逻辑关系,即数据的逻辑结构 。
(2)数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构 。
(3)施加在该数据上的操作,即数据的运算 。
例 1.1 有一个学生表如表 1.1所示 。 这个表中的数据元素是学生记录,每个数据元素由四个数据项 (即学号,姓别,性别和班号 )组成 。
学号 姓名 性别 班号
1 张斌 男 9901
8 刘丽 女 9902
34 李英 女 9901
20 陈华 男 9902
12 王奇 男 9901
26 董强 男 9902
5 王萍 女 9901
表 1.1 学生表该表中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为：
<1,8>,<8,34>,<34,20>,<20,12>,
<12,26>,<26,5>
其中尖括号,<ai,ai+1>”表示元素 ai和 ai+1之间是相邻的,即 ai在 ai+1之前,ai+1在 ai之后 。
这些数据在计算机存储器中的存储方式就是存储结构 。 通常可以采用 C/C++语言中的结构体数组和链表两种方式实现其存储结构 。
存放学生表的结构体数组 Stud定义为：
struct {
int no; /*存储学号 */
char name[8]; /*存储姓名 */
char sex[2]; /*存储性别 */
char class[4]; /*存储班号 */
} Stud[7]={{1,“张斌,,“男,,“9901”},…,
{5,"王萍 ","女 ","9901"}};
结构体数组 Stud各元素在内存中顺序存放,
即第 i(1≤i≤6) 个学生对应的元素 Stud[i]存放在第 i+1个学生对应的元素 Stud[i+1]之前,Stud[i+1]正好在 Stud[i]之后。
存放学生表的链表的结点类型 StudType定义为：
typedef struct studnode
{
int no; /*存储学号 */
char name[8]; /*存储姓名 */
char sex[2]; /*存储性别 */
char class[4]; /*存储班号 */
struct studnode *next;
/*存储指向下一个学生的指针 */
} StudType；
head 1 张斌 男 9901
8 刘丽 女 9902
34 李英 女 9901
20 陈华 男 9902
12 王奇 男 9901
26 董强 男 9902
5 王萍 女 9901 ∧
学生表构成的链表如右图所示。
其中的 head为第一个数据元素的指针。
学生表构成的链表对于,学生表,这种数据结构,可以进行一系列的运算,例如,增加一个学生记录,
删除一个学生记录,查找性别为,女,的学生记录,查找班号为,9902”的学生记录等等 。
从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的 。
例如,查找学号为 20的学生的姓名：
对于 Stud 数组,可以从 Stud[0] 开始比较,Stud[0].no不等于 20,再与 Stud[1].no比较,…,
直到 Stud[3].no等于 20,返回 Stud[3].name。
对于 head为首结点指针的链表,从 head所指结点开始比较,head->no不等于 20,从它的 next得到下一个结点的地址,再与下一个结点的 no域比较,…,直到某结点的 no域等于 20,返回其 name域 。
为了更确切地描述一种数据结构,通常采用二元组表示：
B=(K,R)
其中,B是一种数据结构,它由数据元素的集合 K和 K上二元关系的集合 R所组成。其中：
K={ki| 1≤i≤n,n≥0}
R={rj| 1≤j≤m,m≥0}
其中 ki表示集合 K中的第 i个结点或数据元素,n为 K中结点的个数,特别地,若 n=0,则 K是一个空集,因而 B也就无结构可言,有时也可以认为它具有任一结构 。
rj表示集合 R中的第 j个二元关系 (后面均简称关系 ),m为 R中关系的个数,特别地,若 m=0,
则 R是一个空集,表明集合 K中的元结点间不存在任何关系,彼此是独立的 。
K上的一个关系 r是序偶的集合,对于 r中的任一序偶 <x,y>(x,y∈ K),我们把 x叫做序偶的第一结点,把 y叫做序偶的第二结点,又称序偶的第一结点为第二结点的直接前驱 (通常简称前驱 ),称第二结点为第一结点的直接后继 (通常简称后继 )。 如在 <x,y>的序偶中,x为 y的前驱,而 y为 x的后继 。
若某个结点没有前驱,则称该结点为开始结点；若某个结点没有后继,则称该结点为终端结点 。
例如,采用二元组表示例 1.1的学生表 。
学生表中共有 7个结点,依次用 k1～ k7表示,则对应的二元组表示为 B=(K,R),其中：
K={k1,k2,k3,k4,k5,k6,k7}
R={r}
r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,
<k6,k7>}
又例如,有如下数据即一个矩阵：
119105
47128
1362
对应的二元组表示为 B=(K,R),其中：
K={2,6,3,1,8,12,7,4,5,10,9,11}
R={r1,r2} 其中,r1表示行关系,r2表示列关系
r1={<2,6.<6,3>,<3,1>,<8,12>,<12,7>,<7,4>,<5,10>,
<10,9>,<9,11>}
r2={<2,8>,<8,5>,<6,12>,<12,10>,<3,7>,<7,9>,<1,4>,
<4,11>}
一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,
两结点之间的连线对应着关系中的一个序偶。
上述,学生表,数据结构用下图的图形表示。
k1 k2 k3 k4 k5 k6 k7
学生表数据结构图示
(1)线性结构所谓线性结构,该结构中的结点之间存在一对一的关系 。 其特点是开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱,有且仅有一个后继 。
顺序表就是典型的线性结构 。
1.1.2 逻辑结构类型返回
(2)非线性结构所谓非线性结构,该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。
所谓树形结构,该结构中的结点之间存在一对多的关系 。 其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点 。 非线性结构树形结构简称为树 。
所谓图形结构,该结构中的结点之间存在多对多的关系 。 其特点是每个结点的前驱和后继的个数都可以是任意的 。 因此,可能没有开始结点和终端结点,也可能有多个开始结点,多个终端结点 。 图形结构简称为图 。
(1)顺序存储方法
(2)链式存储方法
(3)索引存储方法
(4)散列存储方法
1.1.3 存储结构类型返回
(1)数据类型在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,
其所能取的值的范围不同,所能进行的操作不同。数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1.1.4 数据结构和数据类型返回如 C/C++中的 int就是整型数据类型。它是所有整数的集合 (在 16位计算机中为－ 32768到
32767的全体整数 )和相关的整数运算 (如＋、－、
＊、／等 )。
(2)抽象数据类型抽象数据类型 (Abstract Data Type简写为
ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。
例如,抽象数据类型复数的定义：
ADT Complex
{
数据对象：
D={e1,e2|e1,e2均为实数 }
数据关系：
R1={<e1,e2>| e1是复数的实数部分,e2是复数的虚数部分 }
基本操作：
AssignComplex(&Z,v1,v2)：构造复数 Z,其实部和虚部分别赋以参数 v1和 v2的值 。
DestroyComplex(&Z):复数 Z被销毁 。
GetReal(Z,&real):用 real返回复数 Z的实部值 。
GetImag(Z,&Imag):用 Imag返回复数 Z的虚部值 。
Add(z1,z2,&sum):用 sum返回两个复数 z1,z2的和值 。
} ADT Complex
1.2 算法及其描述
1.2.1 什么是算法
1.2.2 算法描述
1.2.1 什么是算法数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。我们把具体存储结构上的操作实现步骤或过程称为算法。
返回算法的五个重要的特性
(1)有穷性,在有穷步之后结束。
(2)确定性,无二义性。
(3)可行性,可通过基本运算有限次执行来实现 。
(4)有输入
(5)有输出例 1.2 考虑下列两段描述：
(1)
void exam1()
{
n＝ 2;
while (n%2＝＝ 0)
n＝ n+2;
printf("%d\n",n);
}
(2)
void exam2()
{
y=0;
x=5/y;
printf(“%d,%d\n”,x,y);
}
这两段描述均不能满足算法的特征,试问它们违反了哪些特征？
解,(1)算法是一个死循环,违反了算法的有穷性特征 。
(2)算法包含除零错误,违反了算法的可行性特征 。
1.2.2 算法描述本书中采用 C/C++语言描述算法。
说明,C++语言中提供了一种 引用 运算符
,&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象 (目标 )的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。
返回例如：
int a=4;
int &b=a;
这里说明 b变量是变量 a的引用,b也等于 4,之后这两个变量同步改变 。
引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数 (其中的形参均为引用型形参 )：
void swap(int &x,int &y)
/*形参前的,&”符号不是指针运算符 */
{
int tmp=x;
x=y;y=tmp
}
当用执行语句 swap(a,b)时,a和 b的值发生了交换。
例 1.3 编写一个算法,读入三个整数 x,y和 z的值,要求从大到小输出这三个数 。
解：依次输入 x,y和 z这三个整数,通过比较交换后,使得 x≥y≥z,然后输出 x,y,z。
在算法中应考虑对这三个元素作尽可能少的比较和移动,如下述算法在最坏的情况下只需进行 3次比较和 7次移动 。
void Descending()
{
printf("输入 x,y,z");
scanf("%d,%d,%d",&x,&y,&z);
if (x<y) {
temp=x;x=y;y=temp； /*交换 x,y,使 x>=y*/
}
if (y<z) {
temp=z;
z=y; /*使 temp>z*/
if (x>=temp) y=temp；
else {
y=x;x=temp;
}
}
printf("%d,%d,%d\n",x,y,z);
}
1.3 算法分析
1.3.1 算法时间复杂度分析
1.3.2 算法空间复杂度分析返回一个算法是由控制结构 (顺序,分支和循环三种 )和原操作 (指固有数据类型的操作 )构成的,则算法时间取决于两者的综合效果 。
1.3.1 算法时间复杂度分析返回为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究的问题来说是基本运算的原操作 (以下将基本运算的原操作简称为基本运算 ),算法执行时间大致为基本运算所需的时间与其运算次数 (也称为频度 )的乘积 。
被视为算法基本运算的一般是最深层循环内的语句 。
在一个算法中,进行基本运算的次数越少,
其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多 。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数 。
算法中基本运算次数 T(n)是问题规模 n的某个函数 f(n),记作：
T(n)=O(f(n))
记号,O”读作,大 O”,它表示随问题规模 n
的增大算法执行时间的增长率和 f(n)的增长率相同 。,O”的形式定义为：
若 f(n)是正整数 n的一个函数,则 T(n)=O(f(n))
表示存在一个正的常数 M,使得当 n≥n0时都满足：
|T(n)|≤M|f(n)|
也就是只求出 T(n)的最高阶,忽略其低阶项和常系数,这样既可简化 T(n)的计算,又能比较客观地反映出当 n很大时,算法的时间性能 。
例如,T(n)=3n2-5n+10000=O(n2)
一个没有循环的算法的基本运算次数与问题规模 n无关,记作 O(1),也称作常数阶。
一个只有一重循环的算法的基本运算次数与问题规模 n的增长呈线性增大关系,记作 O(n),也称线性阶。
其余常用的还有平方阶 O(n2)、立方阶 O(n3)、
对数阶 O(log2n)、指数阶 O(2n)等。
各种不同数量级对应的值存在着如下关系：
O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<
O(2n)<O(n!)
例 1.4 求两个 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
例 1.5 分析以下算法的时间复杂度 。
int fun(int n)
{
int i,j,k,s;
s=0;
for (i=0;i<=n;i++)
for (j=0;j<=i;j++)
for (k=0;k<=j;k++)
s++;
return(s);
}
解,该算法的基本操作是语句 s++,其频度：
T(n)=
=O(n3)
则该算法的时间复杂度为 O(n3)。
n
i
i
j
j
k0 0 0
1
空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模 n的函数,以数量级形式给出,记作：
S(n) = O(g(n))
若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作 。 若所需存储量依赖于特定的输入,则通常按最坏情况考虑 。
1.3.2 算法空间复杂度分析返回例 1.6 分析例 1.4和例 1.5的空间复杂度。
解：由于这两个算法中临时变量的个数与问题规模 n无关,所以空间复杂度均为
O(1)。
本章小结本章介绍了数据结构的基本概念,主要学习要点如下：
(1)数据结构的定义,数据结构包含的逻辑结构,存储结构和运算三方面的相互关系 。
(2)各种逻辑结构即线性结构,树形结构和图形结构之间的差别 。
返回
(3)数据结构和数据类型的差别和联系 。
(4)算法的定义及其特性 。
(5)算法的时间复杂度和空间复杂度分析。
本章练习：
完成 P17－ 18习题 3,习题 5和习题 6。
1.2 算法及其描述
1.1 什么是数据结构
1.3 算法分析本章小结
1.1.1 数据结构的定义
1.1.2 逻辑结构类型
1.1.3 存储结构类型
1.1.4 数据结构和数据类型
1.1 什么是数据结构数据,是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。
数据元素：是数据 (集合 )中的一个“个体”,
是数据的基本单位。
1.1.1 数据结构的定义例如,200402班为一个学生数据,而其中的
,张三,是一个数据元素 )。
数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。
因此,可时把数据结构看成是带结构的数据元素的集合。
数据结构包括如下几个方面：
(1)数据元素之间的逻辑关系,即数据的逻辑结构 。
(2)数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构 。
(3)施加在该数据上的操作,即数据的运算 。
例 1.1 有一个学生表如表 1.1所示 。 这个表中的数据元素是学生记录,每个数据元素由四个数据项 (即学号,姓别,性别和班号 )组成 。
学号 姓名 性别 班号
1 张斌 男 9901
8 刘丽 女 9902
34 李英 女 9901
20 陈华 男 9902
12 王奇 男 9901
26 董强 男 9902
5 王萍 女 9901
表 1.1 学生表该表中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为：
<1,8>,<8,34>,<34,20>,<20,12>,
<12,26>,<26,5>
其中尖括号,<ai,ai+1>”表示元素 ai和 ai+1之间是相邻的,即 ai在 ai+1之前,ai+1在 ai之后 。
这些数据在计算机存储器中的存储方式就是存储结构 。 通常可以采用 C/C++语言中的结构体数组和链表两种方式实现其存储结构 。
存放学生表的结构体数组 Stud定义为：
struct {
int no; /*存储学号 */
char name[8]; /*存储姓名 */
char sex[2]; /*存储性别 */
char class[4]; /*存储班号 */
} Stud[7]={{1,“张斌,,“男,,“9901”},…,
{5,"王萍 ","女 ","9901"}};
结构体数组 Stud各元素在内存中顺序存放,
即第 i(1≤i≤6) 个学生对应的元素 Stud[i]存放在第 i+1个学生对应的元素 Stud[i+1]之前,Stud[i+1]正好在 Stud[i]之后。
存放学生表的链表的结点类型 StudType定义为：
typedef struct studnode
{
int no; /*存储学号 */
char name[8]; /*存储姓名 */
char sex[2]; /*存储性别 */
char class[4]; /*存储班号 */
struct studnode *next;
/*存储指向下一个学生的指针 */
} StudType；
head 1 张斌 男 9901
8 刘丽 女 9902
34 李英 女 9901
20 陈华 男 9902
12 王奇 男 9901
26 董强 男 9902
5 王萍 女 9901 ∧
学生表构成的链表如右图所示。
其中的 head为第一个数据元素的指针。
学生表构成的链表对于,学生表,这种数据结构,可以进行一系列的运算,例如,增加一个学生记录,
删除一个学生记录,查找性别为,女,的学生记录,查找班号为,9902”的学生记录等等 。
从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的 。
例如,查找学号为 20的学生的姓名：
对于 Stud 数组,可以从 Stud[0] 开始比较,Stud[0].no不等于 20,再与 Stud[1].no比较,…,
直到 Stud[3].no等于 20,返回 Stud[3].name。
对于 head为首结点指针的链表,从 head所指结点开始比较,head->no不等于 20,从它的 next得到下一个结点的地址,再与下一个结点的 no域比较,…,直到某结点的 no域等于 20,返回其 name域 。
为了更确切地描述一种数据结构,通常采用二元组表示：
B=(K,R)
其中,B是一种数据结构,它由数据元素的集合 K和 K上二元关系的集合 R所组成。其中：
K={ki| 1≤i≤n,n≥0}
R={rj| 1≤j≤m,m≥0}
其中 ki表示集合 K中的第 i个结点或数据元素,n为 K中结点的个数,特别地,若 n=0,则 K是一个空集,因而 B也就无结构可言,有时也可以认为它具有任一结构 。
rj表示集合 R中的第 j个二元关系 (后面均简称关系 ),m为 R中关系的个数,特别地,若 m=0,
则 R是一个空集,表明集合 K中的元结点间不存在任何关系,彼此是独立的 。
K上的一个关系 r是序偶的集合,对于 r中的任一序偶 <x,y>(x,y∈ K),我们把 x叫做序偶的第一结点,把 y叫做序偶的第二结点,又称序偶的第一结点为第二结点的直接前驱 (通常简称前驱 ),称第二结点为第一结点的直接后继 (通常简称后继 )。 如在 <x,y>的序偶中,x为 y的前驱,而 y为 x的后继 。
若某个结点没有前驱,则称该结点为开始结点；若某个结点没有后继,则称该结点为终端结点 。
例如,采用二元组表示例 1.1的学生表 。
学生表中共有 7个结点,依次用 k1～ k7表示,则对应的二元组表示为 B=(K,R),其中：
K={k1,k2,k3,k4,k5,k6,k7}
R={r}
r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,
<k6,k7>}
又例如,有如下数据即一个矩阵：
119105
47128
1362
对应的二元组表示为 B=(K,R),其中：
K={2,6,3,1,8,12,7,4,5,10,9,11}
R={r1,r2} 其中,r1表示行关系,r2表示列关系
r1={<2,6.<6,3>,<3,1>,<8,12>,<12,7>,<7,4>,<5,10>,
<10,9>,<9,11>}
r2={<2,8>,<8,5>,<6,12>,<12,10>,<3,7>,<7,9>,<1,4>,
<4,11>}
一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,
两结点之间的连线对应着关系中的一个序偶。
上述,学生表,数据结构用下图的图形表示。
k1 k2 k3 k4 k5 k6 k7
学生表数据结构图示
(1)线性结构所谓线性结构,该结构中的结点之间存在一对一的关系 。 其特点是开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱,有且仅有一个后继 。
顺序表就是典型的线性结构 。
1.1.2 逻辑结构类型返回
(2)非线性结构所谓非线性结构,该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。
所谓树形结构,该结构中的结点之间存在一对多的关系 。 其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点 。 非线性结构树形结构简称为树 。
所谓图形结构,该结构中的结点之间存在多对多的关系 。 其特点是每个结点的前驱和后继的个数都可以是任意的 。 因此,可能没有开始结点和终端结点,也可能有多个开始结点,多个终端结点 。 图形结构简称为图 。
(1)顺序存储方法
(2)链式存储方法
(3)索引存储方法
(4)散列存储方法
1.1.3 存储结构类型返回
(1)数据类型在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,
其所能取的值的范围不同,所能进行的操作不同。数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1.1.4 数据结构和数据类型返回如 C/C++中的 int就是整型数据类型。它是所有整数的集合 (在 16位计算机中为－ 32768到
32767的全体整数 )和相关的整数运算 (如＋、－、
＊、／等 )。
(2)抽象数据类型抽象数据类型 (Abstract Data Type简写为
ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。
例如,抽象数据类型复数的定义：
ADT Complex
{
数据对象：
D={e1,e2|e1,e2均为实数 }
数据关系：
R1={<e1,e2>| e1是复数的实数部分,e2是复数的虚数部分 }
基本操作：
AssignComplex(&Z,v1,v2)：构造复数 Z,其实部和虚部分别赋以参数 v1和 v2的值 。
DestroyComplex(&Z):复数 Z被销毁 。
GetReal(Z,&real):用 real返回复数 Z的实部值 。
GetImag(Z,&Imag):用 Imag返回复数 Z的虚部值 。
Add(z1,z2,&sum):用 sum返回两个复数 z1,z2的和值 。
} ADT Complex
1.2 算法及其描述
1.2.1 什么是算法
1.2.2 算法描述
1.2.1 什么是算法数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。我们把具体存储结构上的操作实现步骤或过程称为算法。
返回算法的五个重要的特性
(1)有穷性,在有穷步之后结束。
(2)确定性,无二义性。
(3)可行性,可通过基本运算有限次执行来实现 。
(4)有输入
(5)有输出例 1.2 考虑下列两段描述：
(1)
void exam1()
{
n＝ 2;
while (n%2＝＝ 0)
n＝ n+2;
printf("%d\n",n);
}
(2)
void exam2()
{
y=0;
x=5/y;
printf(“%d,%d\n”,x,y);
}
这两段描述均不能满足算法的特征,试问它们违反了哪些特征？
解,(1)算法是一个死循环,违反了算法的有穷性特征 。
(2)算法包含除零错误,违反了算法的可行性特征 。
1.2.2 算法描述本书中采用 C/C++语言描述算法。
说明,C++语言中提供了一种 引用 运算符
,&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象 (目标 )的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。
返回例如：
int a=4;
int &b=a;
这里说明 b变量是变量 a的引用,b也等于 4,之后这两个变量同步改变 。
引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数 (其中的形参均为引用型形参 )：
void swap(int &x,int &y)
/*形参前的,&”符号不是指针运算符 */
{
int tmp=x;
x=y;y=tmp
}
当用执行语句 swap(a,b)时,a和 b的值发生了交换。
例 1.3 编写一个算法,读入三个整数 x,y和 z的值,要求从大到小输出这三个数 。
解：依次输入 x,y和 z这三个整数,通过比较交换后,使得 x≥y≥z,然后输出 x,y,z。
在算法中应考虑对这三个元素作尽可能少的比较和移动,如下述算法在最坏的情况下只需进行 3次比较和 7次移动 。
void Descending()
{
printf("输入 x,y,z");
scanf("%d,%d,%d",&x,&y,&z);
if (x<y) {
temp=x;x=y;y=temp； /*交换 x,y,使 x>=y*/
}
if (y<z) {
temp=z;
z=y; /*使 temp>z*/
if (x>=temp) y=temp；
else {
y=x;x=temp;
}
}
printf("%d,%d,%d\n",x,y,z);
}
1.3 算法分析
1.3.1 算法时间复杂度分析
1.3.2 算法空间复杂度分析返回一个算法是由控制结构 (顺序,分支和循环三种 )和原操作 (指固有数据类型的操作 )构成的,则算法时间取决于两者的综合效果 。
1.3.1 算法时间复杂度分析返回为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究的问题来说是基本运算的原操作 (以下将基本运算的原操作简称为基本运算 ),算法执行时间大致为基本运算所需的时间与其运算次数 (也称为频度 )的乘积 。
被视为算法基本运算的一般是最深层循环内的语句 。
在一个算法中,进行基本运算的次数越少,
其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多 。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数 。
算法中基本运算次数 T(n)是问题规模 n的某个函数 f(n),记作：
T(n)=O(f(n))
记号,O”读作,大 O”,它表示随问题规模 n
的增大算法执行时间的增长率和 f(n)的增长率相同 。,O”的形式定义为：
若 f(n)是正整数 n的一个函数,则 T(n)=O(f(n))
表示存在一个正的常数 M,使得当 n≥n0时都满足：
|T(n)|≤M|f(n)|
也就是只求出 T(n)的最高阶,忽略其低阶项和常系数,这样既可简化 T(n)的计算,又能比较客观地反映出当 n很大时,算法的时间性能 。
例如,T(n)=3n2-5n+10000=O(n2)
一个没有循环的算法的基本运算次数与问题规模 n无关,记作 O(1),也称作常数阶。
一个只有一重循环的算法的基本运算次数与问题规模 n的增长呈线性增大关系,记作 O(n),也称线性阶。
其余常用的还有平方阶 O(n2)、立方阶 O(n3)、
对数阶 O(log2n)、指数阶 O(2n)等。
各种不同数量级对应的值存在着如下关系：
O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<
O(2n)<O(n!)
例 1.4 求两个 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
例 1.5 分析以下算法的时间复杂度 。
int fun(int n)
{
int i,j,k,s;
s=0;
for (i=0;i<=n;i++)
for (j=0;j<=i;j++)
for (k=0;k<=j;k++)
s++;
return(s);
}
解,该算法的基本操作是语句 s++,其频度：
T(n)=
=O(n3)
则该算法的时间复杂度为 O(n3)。
n
i
i
j
j
k0 0 0
1
空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模 n的函数,以数量级形式给出,记作：
S(n) = O(g(n))
若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作 。 若所需存储量依赖于特定的输入,则通常按最坏情况考虑 。
1.3.2 算法空间复杂度分析返回例 1.6 分析例 1.4和例 1.5的空间复杂度。
解：由于这两个算法中临时变量的个数与问题规模 n无关,所以空间复杂度均为
O(1)。
本章小结本章介绍了数据结构的基本概念,主要学习要点如下：
(1)数据结构的定义,数据结构包含的逻辑结构,存储结构和运算三方面的相互关系 。
(2)各种逻辑结构即线性结构,树形结构和图形结构之间的差别 。
返回
(3)数据结构和数据类型的差别和联系 。
(4)算法的定义及其特性 。
(5)算法的时间复杂度和空间复杂度分析。
本章练习：
完成 P17－ 18习题 3,习题 5和习题 6。
