【精品数据结构】绪论.pptVIP

第1章 绪论 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次移动。 * * 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所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。 9902 男 陈华 20 9902 男 董强 26 9901 男 王奇 12 9901 女 王萍 5 9901 女 李英 34 9902 女 刘丽 8 9901 男 张斌 1 班号 性别 姓名 学号 表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];