绪论 知识结构:
知识结构 一、什么是数据结构 例1:电话号码薄的查询问题。
:表示姓名, :表示电话号码, 。
思考:
解决方案 例2:学生自然情况查询问题。
思考:
解决方案 数据结构的定义(Data Structure)
语言描述:数据结构是研究数据的逻辑结构,存储结构(物理结构)以及它们之间的关系,并对这种结构定义相适应的运算,设计出相应的算法。
形式化描述:数据结构是一个二元组
其中, :是数据元素的有限集合, :是 上关系的有限集合。
例3:集合结构。
其中,, (元素之间没有关系)。
比如:
例4:线性结构。
其中, (除了首尾结点,其余结点只有一个直接前驱,一个直接后继)。
比如:
二、基本概念与术语 1、数据(Data)
指所有能输入计算机中并被计算机程序处理的符号集合。
可以是数值数据,如整数、实数;也可以是非数值数据,如字符、文字、图形、声音等。
2、数据元素(Data Element)
数据的基本单位,也称为结点,顶点,记录。
在计算机程序中,通常被作为一个整体进行考虑和处理。
3、数据项(Data Item)
具有独立含义的最小标识单位,也称为字段(Field)。
例如:在数据库信息处理系统中,数据表中的一条记录就是一个数据元素。这条记录中的学生学号、姓名、性别、籍贯、出生年月、成绩等字段就是数据项。
可见:数据由数据元素组成,数据元素由数据项组成。
4、逻辑结构(Logic Structure)
对数据之间逻辑关系的描述。(独立于计算机)
逻辑结构 5、存储结构(Storage Structure)
逻辑结构在计算机存储器中的实现,即数据在计算机中的存放方式。
散列:利用散列函数,根据数据元素关键字来定位数据的存储。 6、数据类型(Data Type)
数据类型是数据的取值范围和对数据进行操作的总和。
如:int、long、float、double、bool、char等
7、抽象数据类型(Abstract Data Type)
抽象数据类型由一组数据以及在该组数据上的一组操作组成。
抽象数据类型的格式定义如下:
ADT Name is Data 构成该抽象数据类型所必须的基本数据项 Operations Constructor Initial Values:赋给基本数据项的值 Press:初始化对象 Operation1 Input:操作1 要求用户输入的值 PreCondition:系统执行操作1 前的数据状态 Press:操作1 的解释说明 Output:操作1 结束后返回的数据 PostCondition:系统执行操作1 后的数据状态 Operation2 … … OperationN … … End ADT Name
例5:矩形结构的ADT描述。
ADT Rectangle is Data float Length float Width Operations Constructor Initial Values:构造矩形时,赋长和宽的值。 Press:初始化对象,给矩形的长和宽赋值。 SetLength Input:赋给变量Length的新值 PreCondition:无 Press:将矩形的长度值修改为新值 Output:无 PostCondition:矩形的长度值被修改 SetWidth Input:赋给变量Width的新值 PreCondition:无 Press:将矩形宽度值修改为新值 Output:无 PostCondition:矩形的宽度值被修改 GetArea Input:无 PreCondition:矩形的长度和宽度都大于零 Press:得到矩形的面积 Output:返回矩形面积的值 PostCondition:无 GetPerimeter Input:无 PreCondition:矩形的长度和宽度都大于零 Press:得到矩形的周长 Output:返回矩形的周长 PostCondition:无 End ADT Rectangle
一旦定义了矩形结构的ADT描述,就可以用代码进行实现了。
public class Rectangle { public float Length; public float Width; public Rectangle (float length, float width) { Length = length > 0 ? length : 0f ; Width = width > 0 ? width : 0f ; } public void SetLength (float length) { Length = length > 0 ? length : 0f ; } public void SetWidth (float width) { Width = width > 0 ? width : 0f ; } public float GetArea () { if (Length * Width == 0 ) throw new ArgumentOutOfRangeException("长度或宽度为零。" ); return Length * Width; } public float GetPerimeter () { if (Length * Width == 0 ) throw new ArgumentOutOfRangeException("长度或宽度为零。" ); return (Length + Width) * 2 ; } }
三、算法与算法分析 1、算法的基本概念
1.1 算法的定义
为了解决某类特定问题而提出的一组有穷规则,即以某些值或值的集合为输入并产生某些值或值的集合为输出的一系列运算步骤。
1.2 算法的五个重要特性
确定性或无二义性(Unambiguousness):给相同的输入,即得到相同的输出。 1.3 算法设计的五点要求
健壮性(Robustness):具有很强的容错能力,对边界情况和异常情况做出处理。 占用空间(Storage Space):完成功能的前提下,时间越少,空间越小,越好。 1.4 算法与程序的区别
2、算法分析
2.1 时间复杂度(Time Complexity)
1)算法耗费的时间
一个算法耗费的时间 = 算法中每条语句的执行时间之和
每条语句的执行时间 = 语句的执行次数 语句执行一次所需的时间
一般认为每条语句执行一次所需的时间是单位时间,即:一个算法耗费的时间 = 所有语句的执行频数之和
例6:计算方阵 算法耗费的时间。
static double [,] MatrixMultiply(double [,] A, double [,] B, uint n) { double [,] C = new double [n, n]; // 1 for (int i = 0 ; i < n; i++) // n+1 { for (int j = 0 ; j < n; j++) // n*(n+1) { C[i, j] = 0 ; // n*n for (int k = 0 ; k < n; k++) // n*n*(n+1) { C[i, j] += A[i, k] * B[k, j]; // n*n*n } } } return C; // 1 }
2)问题的规模
算法求解问题的输入量,一般用一个整数表示。
3)算法的时间复杂度
就是该算法的时间耗费,是关于问题规模 的函数。
当 时,与 的同阶的简单函数称为算法的渐进时间复杂度。
例7:
所以
例8:针对一个问题,设计算法 , 其耗费时间 , ,当 时, , ,即算法 所耗费的时间远小于算法 ,在宏观上可通过渐进时间复杂度表示算法的优劣。
一般,我们把渐进时间复杂度 简称为时间复杂度。 表示算法中频数最大语句的频数。
例9:
int x = 0 ;int y = 0 ;for (int i = 0 ; i < n; i++) x++;for (int j = 0 ; j < n; j++) for (int k = 0 ; k < n; k++) y++;
例10:
int i = 50 ;int j = 60 ;int temp = i; i = j; j = temp;
4)常见的时间复杂度
5)最坏时间复杂度
例11:在数组A[n]
中查找给定值k
。
static int Find (int [] A, int k) { int i; for (i = 0 ; i < A.Length; i++) //(#) if (A[i] == k) break ; return i == A.Length ? -1 : i; }
最坏时间复杂度:最坏情况下的时间复杂度。
一般不特别说明,所讨论的时间复杂度,都指最坏时间复杂度。
2.2 空间复杂度(Space Complexity)
指该算法所耗费的存储空间,也是问题规模 的函数,渐进空间复杂度也常常称为空间复杂度。