nullnull第1章 绪 论1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示与实现
1.4 算法和算法分析1.1 什么是数据结构1.1 什么是数据结构Niklaus Wirth：
Algorithm + Data Structures = Programs程序设计:为计算机处理问题编制
一组“指令集” 算法:
数据结构:处理问题的策略问题的数学模型null例如: 数值计算的程序设计问题
"鸡兔同笼"问题 ─━ 二元一次方程组 结构应力分析计算 ─━ 线性代数方程组 ─━ 环流模式方程
(球面坐标系)全球天气预报 null例1-1 公司员工信息管理。
某公司现有“王清”、“李丽圆”、“张娟”、“张爱民”等员工。现公司想要用计算机管理其员工信息。
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
能够做以下操作：
当招聘新员工时，能够把员工信息添加进来；
当有员工辞职时，能够删除该员工信息；
可以修改员工信息；
能够以某种方式检索员工信息。
非数值计算的程序设计问题null 计算机处理的对象之间存在着最简单的线性关系
模型——线性表 例1-2 计算机与人对弈例1-2 计算机与人对弈 计算机操作的对象是对弈过程中可能出现的棋盘状态——格局模型——树例1-3 煤气管道的铺设例1-3 煤气管道的铺设 计算机操作的对象是顶点及顶点之间铺设管道的费用模型——图null 由上述3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。概括地说：1.2 基本概念和术语1.2 基本概念和术语所有能被输入到计算机中，且能被计算机处理的符号的集合。1.数据是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。null 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。 2.数据元素:是数据（集合）中的一个“个体”null 数据项：是数据的不可分割的最小单位一个数据元素可由若干个数据项组成例如：描述一个运动员的数据元素可以是称之为组合项原子项3.数据对象：3.数据对象： 是性质相同的数据元素的集合，是数据的一个子集。如：整数、实数等。null例，在2行3列的二维数组{a1, a2, a3, a4, a5, a6}
中六个元素之间
存在两个关系:行的次序关系:
列的次序关系:row = {
,,,}col = {,,} a1 a3 a5
a2 a4 a6 a1 a2 a3
a4 a5 a6 null再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系:{| i=1, 2, 3, 4, 5} 或者说，数据结构是相互之间存在一种或多种特定关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”
这种数据元素之间的关系称为结构null数据结构：带结构的数据元素的集合假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。3214,6587,9345 ─ a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a33214，6587，9345
a1 a2 a3 6587，3214，9345
a2 a1 a3≠例如:null数据结构应该包括数据的"逻辑结构"和数据的"物理结构"两个方面（层次）。null数据的逻辑结构即数据元素之间的逻辑关系。有下列四类基本结构:线性结构树形结构图状结构
（网状结构）集合结构null数据结构的形式定义为:数据结构是一个二元组 Data_Structures = (D, S)其中:D 是数据元素的有限集，
S 是 D上关系的有限集。null数据的物理结构 数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。包括：“数据元素”的表示（映象） ？“关系”的（表示）映象 ？null数据元素的映像方法：用二进制位(bit)的位串表示数据元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2通常称这个位串为元素或结点。当数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域。null关系的映象方法：顺序映象 借助元素在存储器中的相对位置来表示元素之间的逻辑关系。顺序存储结构链式映象链式存储结构 借助指示元素存储地址的指针表示元素之间的逻辑关系。null顺序结构表示复数：
Z1=3.0-2.3i
Z2=-0.7+4.8i链式结构表示复数：
Z=-0.7-2.3inull在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。null例如: 以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整型数组类型。 typedef int Long_int [3];定义长整数为:null5.数据类型 在用高级程序语言编写的程序中，
必须对程序中出现的每个变量、
常量或表达式，明确说明它们所
属的数据类型。null例如，C 语言中提供的基本数据类型有:整型 int浮点型 float字符型 char逻辑型 bool （ C++语言）双精度型 double实型（ C++语言）null 数据类型 是一个 值的集合
和定义在此集合上的 一组操作
的总称。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。null6.抽象数据类型
(Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。null抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。
其中：D 是数据对象；
S 是 D 上的关系集；
P 是对 D 的基本操作集。 nullADT 抽象数据类型名 {
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义〉
基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉 null基本操作有两种参数：
赋值参数 只为操作提供输入值。
引用参数 以&打头，除可提供输入值外，
还将返回操作结果。初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。null例如，抽象数据类型复数的定义： 数据对象：
D＝{e1,e2｜e1,e2∈RealSet }
数据关系：
R1＝{ | e1是复数的实数部分
| e2 是复数的虚数部分 } ADT Complex {null基本操作： AssignComplex( &Z, v1, v2 )
操作结果：构造复数 Z,其实部和虚部
分别被赋以参数 v1 和 v2 的值。 DestroyComplex( &Z)
操作结果：复数Z被销毁。 GetReal( Z, &realPart )
初始条件：复数已存在。
操作结果：用realPart返回复数Z的实部值。null GetImag( Z, &ImagPart )
初始条件：复数已存在。
操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum )
初始条件：z1, z2是复数。
操作结果：用sum返回两个复数z1, z2 的
和值。 } ADT ComplexnullADT 有两个重要特征:数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。null1.3抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。nulltypedef struct {
float realpart；
float imagpart；
}complex；// -----存储结构的定义// -----基本操作的函数原型说明void Assign( complex &Z,
float realval, float imagval )；
// 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值nullfloat GetReal( complex Z )；
// 返回复数 Z 的实部值float Getimag( complex Z )；
// 返回复数 Z 的虚部值void add( complex z1, complex z2,
complex &sum )；
// 以 sum 返回两个复数 z1, z2 的和 null// -----基本操作的实现void add( complex z1, complex z2,
complex &sum ) {
// 以 sum 返回两个复数 z1, z2 的和
sum.realpart = z1.realpart + z2.realpart;
sum.imagpart = z1.imagpart + z2.imagpart;
} { 其它省略 }null1.3 算法和算法分析一、算法二、算法设计的要求三、算法效率的度量四、算法的存储空间需求null 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令代表一个或多个操作。一个算法必须满足以下五个重要特性：1．有穷性 2．确定性 3．可行性
4．有输入 5．有输出一、算法null 1．有穷性 对于任意一组合法输入值，一个算法必须总是在执行有穷步骤之后结束，即：算法中的每个步骤都能在有限时间内完成。 2．确定性 算法中每一条指令必须有确切的含义，不能产生二义性。并且在任何条件下，算法都只有一条执行路径，即对相同的输入只能得出相同的输出。null3．可行性 算法中描述的所有操作都是可以通过已经实现的基本运算执行有限次来实现的。4．有输入 一个算法有零个或多个输入。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。null 5．有输出 一个算法有一个或多个输出。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。null二、算法设计的要求设计算法时，通常应考虑达到以下目标：1．正确性2. 可读性3．健壮性4．高效率与低存储量需求null1．正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；null c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
。 d．程序对于一切合法的输入数据都能得出满足要求的结果；null2. 可读性 算法主要是为了人的阅读与交流，
其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。
null3．健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。null4．高效率与低存储量需求 通常，效率指的是算法执行时间；
存储量指的是算法执行过程中所需的
最大存储空间，两者都与问题的规模
有关。null三、算法效率的度量通常有两种衡量算法效率的方法: 事后统计法事前分析估算法缺点：1．必须执行程序
2．其它因素掩盖算法本质null和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度null 一个特定算法的“运行工作量”
的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。
因此比较不同算法的优劣主要应该以其"增长的趋势"为准则。 null 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))称T (n) 为算法的(渐近)时间复杂度。null如何估算
算法的时间复杂度？null算法 = 控制结构 + 原操作
（固有数据类型的操作）算法的执行时间 =
原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间
与
原操作执行次数之和 成正比 null 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。null例
一
两
个
矩
阵
相
乘void mult(int a[], int b[], int c[] ) {
// 以二维数组存储矩阵元素，c 为 a 和 b 的乘积
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j) {
c[i][j] = 0;
for (k=1; k<=n; ++k)
c[i][j] += a[i][k]*b[k][j];
} //for
} //mult基本操作: 乘法操作时间复杂度: O(n3)null例
二
选
择
排
序 void select_sort(int a[], int n) {
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
} // select_sort基本操作:
比较(数据元素)操作时间复杂度: O(n2)j = i; // 选择第 i 个最小元素
for ( k = i+1; k < n; ++k )
if (a[k] < a[j] ) j = k;for ( i = 0; i< n-1; ++i ) {
if ( j != i ) a[j] ←→ a[i]
}null例
三
起
泡
排
序void bubble_sort(int& a[], int n) {
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
for (i=n-1, change=TRUE; i>1 && change; --i)
} // bubble_sort基本操作: 赋值操作时间复杂度: O(n2){ change = FALSE; // change 为元素进行交换标志
for (j=0; j a[j+1])
{ a[j] ←→ a[j+1]; change = TRUE ;}
} // 一趟起泡null 从这三个例子可见，算法时间复杂度取决于最深循环内包含基本操作的语句的重复执行次数，称语句重复执行的次数为语句的"频度"。null四、算法的存储空间需求算法的空间复杂度定义为: 表示随着问题规模 n 的增大，
算法运行所需存储量的增长率
与 g(n) 的增长率相同。S(n) = O(g(n))null算法的存储量包括:1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间null 若输入数据所占空间只取决于问题
本身，和算法无关，则只需要分析除
输入和程序之外的辅助变量所占额外
空间。 若所需额外空间相对于输入数据量
来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，
则通常按最坏情况考虑。null1. 熟悉各名词、术语的含义，掌握基本概念。2. 理解算法五个要素的确切含义。本章学习要点3. 掌握计算语句频度和估算算法时间复杂度的方法。
浙公网安备 33021202002483