网站开发研发设计,推广团队,天河网站建设策划,重庆网站推广营销代理要求
#xff08;1#xff09;对数据结构这么课学了哪些知识有个清楚的认知#xff1b;
#xff08;2#xff09;掌握目录结构#xff0c;能复述出来每个知识点下都有哪些内容。
如下图所示#xff0c;可自行制作思维导图#xff0c;针对自己薄弱的地方进行复习。 … 要求
1对数据结构这么课学了哪些知识有个清楚的认知
2掌握目录结构能复述出来每个知识点下都有哪些内容。
如下图所示可自行制作思维导图针对自己薄弱的地方进行复习。 绪论 相关术语
绪论中会介绍数据结构的一些基本概念要对数据模型有基本的了解。
数据Data是信息的载体它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料应用程序处理各种各样的数据。
数据元素Data Element是数据的基本单位。在不同的条件下数据元素又可称为元素、结点、顶点、记录等。
数据对象Data Object或数据元素类Data Element Class是具有相同性质的数据元素的集合。
在某个具体问题中数据元素都具有相同的性质元素值不一定相等属于同一数据对象数据元素类数据元素是数据元素类的一个实例。例如在交通咨询系统的交通网中所有的顶点是一个数据元素类顶点A 和顶点B 各自代表一个城市是该数据元素类中的两个实例其数据元素的值分别为A 和B。
数据结构研究的三个方面
1数据集合中各数据元素之间所固有的逻辑关系即数据的逻辑结构
2在对数据进行处理时各数据元素在计算机中的存储关系即数据的存储结构
3对各种数据结构进行的运算。
数据的逻辑结构和存储结构是密不可分的两个方面一个算法设计取决于所选定的逻辑结构而算法实现依赖于所采用的存储结构。
数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系即从逻辑关系上描述数据它与数据的存储无关是独立于计算机的。数据的逻辑结构分线性结构和非线性结构。 数据的存储结构 存储结构是指数据结构在计算机中的表示又称为映像也叫物理结构。它包括元素的表示和关系的表示。数据的存储结构依赖于计算机数据的存储结构主要有顺序存储、链式存储、索引存储、散列存储。
数据的运算 施加在数据上的运算包括运算的定义与实现。运算的定义是针对逻辑结构的指出运算的功能运算的实现针对存储结构的指出运算的具体操作步骤。 算法及评价
算法是什么
算法是对特定问题求解步骤的描述它是指令的有限序列其中每条指令表示一个或多个操作。算法要求能够对一定规范的输入在有限时间内获得所要求的输出因此一个算法也经常被封装为一个函数用来实现特定的功能。
算法优劣的衡量标准不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法具有五个特性有穷性、确切性、输入、输出、可行性。 一个算法有0个或多个输入。一个算法有一个或多个输出没有输出的算法是毫无意义的。
算法的衡量 算法原地工作指算法所需的辅助空间未常量即O(1)。
例题
例1下面程序的时间复杂度是
x 2;while(x n/2){x 2*x;}答案O(log2N)
每执行一次x以二倍往上增长注意 x n/2与 x n 一个量级。
含有二分的思想在里面二分即倍数增长或倍数下降后重新赋值。因此复杂度为logn。
只要含有二分的思想就有logN。
例2请给出下面程序的时间复杂度
int fact(int n){if(n 1) return 1;return n * fact(n-1);}
求阶乘的递归函数一共执行了n次的量级故时间复杂度为O(N)。
例3下列程序的时间复杂度为
count 0;for(k 1; k n; k*2){for(j 1; jn; j){coun;}}
分析下count的执行次数在什么量级上答案为O(N*logN)。
例4下列程序的时间复杂度为 答案 这个不是二分的思想幂次增长。
