知识结构：
知识结构一、什么是数据结构例1：电话号码薄的查询问题。
：表示姓名，
：表示电话号码，
。
思考：
怎样组织数据？怎样存储数据？怎样操作数据？添加操作删除操作修改操作查询操作排序操作怎样代码实现？解决方案例2：学生自然情况查询问题。
思考：
怎样组织数据？怎样存储数据？怎样操作数据？添加操作删除操作修改操作查询操作排序操作怎样代码实现？解决方案数据结构的定义（DataStructure）
语言描述：数据结构是研究数据的逻辑结构，存储结构（物理结构）以及它们之间的关系，并对这种结构定义相适应的运算，设计出相应的算法。
形式化描述：数据结构是一个二元组
其中，
：是数据元素的有限集合，
：是
上关系的有限集合。
例3：集合结构。
其中，，
（元素之间没有关系）。
比如：
Python语言中的SetC#语言中的HashSet例4：线性结构。
其中，（除了首尾结点，其余结点只有一个直接前驱，一个直接后继）。
比如：
Numpy中的ndarrayC#语言中的数组Matlab中的矩阵二、基本概念与术语1、数据（Data）
指所有能输入计算机中并被计算机程序处理的符号集合。
可以是数值数据，如整数、实数；也可以是非数值数据，如字符、文字、图形、声音等。
2、数据元素（DataElement）
数据的基本单位，也称为结点，顶点，记录。
在计算机程序中，通常被作为一个整体进行考虑和处理。
3、数据项（DataItem）
具有独立含义的最小标识单位，也称为字段（Field）。
例如：在数据库信息处理系统中，数据表中的一条记录就是一个数据元素。这条记录中的学生学号、姓名、性别、籍贯、出生年月、成绩等字段就是数据项。
可见：数据由数据元素组成，数据元素由数据项组成。
4、逻辑结构（LogicStructure）
对数据之间逻辑关系的描述。（独立于计算机）
逻辑结构5、存储结构（StorageStructure）
逻辑结构在计算机存储器中的实现，即数据在计算机中的存放方式。
顺序：利用数组对数据进行存储。链式：利用指针对数据进行存储。索引：利用索引表来定位数据的存储。散列：利用散列函数，根据数据元素关键字来定位数据的存储。6、数据类型（DataType）
数据类型是数据的取值范围和对数据进行操作的总和。
如：int、long、float、double、bool、char等
7、抽象数据类型（AbstractDataType）
抽象数据类型由一组数据以及在该组数据上的一组操作组成。
抽象数据类型的格式定义如下：
ADTNameisData构成该抽象数据类型所必须的基本数据项OperationsConstructorInitialValues：赋给基本数据项的值Press：初始化对象Operation1Input：操作1要求用户输入的值PreCondition：系统执行操作1前的数据状态Press：操作1的解释说明Output：操作1结束后返回的数据PostCondition：系统执行操作1后的数据状态Operation2……OperationN……EndADTName
例5：矩形结构的ADT描述。
ADTRectangleisDatafloatLengthfloatWidthOperationsConstructorInitialValues：构造矩形时，赋长和宽的值。Press：初始化对象，给矩形的长和宽赋值。SetLengthInput：赋给变量Length的新值PreCondition：无Press：将矩形的长度值修改为新值Output：无PostCondition：矩形的长度值被修改SetWidthInput：赋给变量Width的新值PreCondition：无Press：将矩形宽度值修改为新值Output：无PostCondition：矩形的宽度值被修改GetAreaInput：无PreCondition：矩形的长度和宽度都大于零Press：得到矩形的面积Output：返回矩形面积的值PostCondition：无GetPerimeterInput：无PreCondition：矩形的长度和宽度都大于零Press：得到矩形的周长Output：返回矩形的周长PostCondition：无EndADTRectangle
一旦定义了矩形结构的ADT描述，就可以用代码进行实现了。
publicclassRectangle{publicfloatLength;publicfloatWidth;publicRectangle(floatlength,floatwidth){Length=length0?length:0f;Width=width0?width:0f;}publicvoidSetLength(floatlength){Length=length0?length:0f;}publicvoidSetWidth(floatwidth){Width=width0?width:0f;}publicfloatGetArea(){if(Length*Width==0)thrownewArgumentOutOfRangeException("长度或宽度为零。");returnLength*Width;}publicfloatGetPerimeter(){if(Length*Width==0)thrownewArgumentOutOfRangeException("长度或宽度为零。");return(Length+Width)*2;}}三、算法与算法分析
1、算法的基本概念
1.1算法的定义
为了解决某类特定问题而提出的一组有穷规则，即以某些值或值的集合为输入并产生某些值或值的集合为输出的一系列运算步骤。
1.2算法的五个重要特性
有穷性（Finity）：经过有限的时间可以完成。确定性或无二义性（Unambiguousness）：给相同的输入，即得到相同的输出。可行性（Realizability）输入（Input）：至少有0个输入。输出（Output）：至少1个。1.3算法设计的五点要求
正确性（Correctness）可读性（Readability）健壮性（Robustness）：具有很强的容错能力，对边界情况和异常情况做出处理。运行时间（RunningTime）占用空间（StorageSpace）：完成功能的前提下，时间越少，空间越小，越好。1.4算法与程序的区别
表现形式不同算法：自然语言、伪计算机语言等程序：计算机语言是否具备有穷性2、算法分析
2.1时间复杂度（TimeComplexity）
1）算法耗费的时间
一个算法耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数
语句执行一次所需的时间
一般认为每条语句执行一次所需的时间是单位时间，即：一个算法耗费的时间=所有语句的执行频数之和
例6：计算方阵
算法耗费的时间。
staticdouble[,]MatrixMultiply(double[,]A,double[,]B,uintn){double[,]C=newdouble[n,n];//1for(inti=0;in;i++)//n+1{for(intj=0;jn;j++)//n*(n+1){C[i,j]=0;//n*nfor(intk=0;kn;k++)//n*n*(n+1){C[i,j]+=A[i,k]*B[k,j];//n*n*n}}}returnC;//1}
2）问题的规模
算法求解问题的输入量，一般用一个整数表示。
矩阵求解问题，矩阵的阶数。图论问题，图的结点个数，边的条数。3）算法的时间复杂度
就是该算法的时间耗费，是关于问题规模
的函数。
当
时，与
的同阶的简单函数称为算法的渐进时间复杂度。
例7：
所以
例8：针对一个问题，设计算法
，
其耗费时间
，
，当
时，
，
，即算法
所耗费的时间远小于算法
，在宏观上可通过渐进时间复杂度表示算法的优劣。
一般，我们把渐进时间复杂度
简称为时间复杂度。
表示算法中频数最大语句的频数。
例9：
intx=0;inty=0;for(inti=0;in;i++)x++;for(intj=0;jn;j++)for(intk=0;kn;k++)y++;
例10：
inti=50;intj=60;inttemp=i;i=j;j=temp;
4）常见的时间复杂度
常数阶：对数阶：
线性阶：
线性对数阶：
平方阶：
立方阶：
方阶：
指数阶：
5）最坏时间复杂度
例11：在数组A[n]中查找给定值k。
staticintFind(int[]A,intk){inti;for(i=0;iA.Length;i++)//(#)if(A==k)break;returni==A.Length?-1:i;}当A中没有与k相等的元素，则(#)的频数
；当A中第1个元素与k相等，则(#)的频数
；
最坏时间复杂度：最坏情况下的时间复杂度。
一般不特别说明，所讨论的时间复杂度，都指最坏时间复杂度。
2.2空间复杂度（SpaceComplexity）
指该算法所耗费的存储空间，也是问题规模
的函数，渐进空间复杂度也常常称为空间复杂度。
后台回复「搜搜搜」，随机获取电子资源！欢迎