第一章绪论。
1.1 数据结构讨论的范畴。
niklaus wirth
algorithm + data structures = programs
程序设计：为计算机处理问题编制一组指令集。
算法：处理问题的策略。
数据结构：问题的数学模型。
例如： 数值计算的程序设计问题
结构静力分析计算 ─━线性代数方程组。
全球天气预报 ─━环流模式方程。
非数值计算的程序设计问题
例一： 求一组(n个)整数中的最大值。
算法： 基本操作是“比较两个数的大小”
模型：？例二：计算机对弈。
算法：对弈的规则和策略。
模型：？例三：足协的数据库管理。
算法：需要管理的项目？如何管理？用户界面？
模型：？概括地说，
数据结构描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中的表示。
和实现。1.2 基本概念
一、数据与数据结构
数据： 所有能被输入到计算机中，且被计算机处理的符号的集。
合计算机操作的对象的总称。
是计算机处理的信息的某种特定的符号表示形式。
数据元素：数据中的一个“个体”，数据结构中讨论的基本单位。
数据项：?/b>数据结构中讨论的最小单位。
数据元素是数据项的集合。
例如： 运动员（数据元素）
其中 是组合项。
数据结构：带结构的数据元素的集合
例如，一个含12位数的十进制数可以用三个4位的十进制数表示。
3214,6587,9345 ─a1(3214),a2(6587),a3(9345)
在a1、a2和a3 之间存在“次序”关系< a1,a2> 、a2,a3>
a1 a2 a3 a2 a1 a3
又例，2行3列的二维数组
行的次序关系：row =
列的次序关系：col =
再例，一维数组 中存在。
次序关系：数据的逻辑结构可归结为以下四类：
线性结构。树形结构。
图状结构。集合结构。
数据结构的形式定义为：
数据结构是一个二元组
data_structures = d, s)
其中：d是数据元素的有限集，s是d上关系的有限集。
严格地讲，以上定义仅是数据的逻辑结构的定义。
数据的存储结构─━ 逻辑结构在存储器中的映象。
数据元素的映象方法：
用二进制位(bit)的位串表示数据元素。
a = 101)8 = 001000001)2
关系的映象方法：（表示的方法）
顺序映象以存储位置的相邻表示后继关系。
y的存储位置和x的存储位置之间差一个常量c
而c是一个隐含值，整个存储结构中只含数据元素本身的信息。
链式映象以附加信息(指针)表示后继关系。
需要用一个和x在一起的附加信息指示y的存储位置。
在不同的编程环境中，存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。
例如：以三个带有次序关系的整数表示一个长整数时，可利用c语言中提供的整数数组类型，定义长整数为：
typedef int long_int [3]
二、数据类型
在用高级程序语言编写的程序中，必须对程序**现的每个变量、常量或表达式，明确说明它们所属的数据类型。因为类型明显或隐含地规定了，在程序执行期间，变量或表达式所有可能取值的范围，以及在这些之上允许进行的操作。
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
三、抽象数据类型(abstract data type 简称adt)
是指一个数学模型以及定义在此数学模型上的一组操作。
adt有两个重要特征：
数据抽象。用adt描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）
数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
例如抽象数据类型复数的定义：
adt complex
数据关系：r1＝
基本操作：initcomplex( &z, v1, v2 )
操作结果：构造复数z,其实部和虚部分别被赋以参数v1和。
v2的值。destroycomplex( &z)
操作结果：复数z被销毁。
getreal( z, &realpart )
初始条件：复数已存在。
操作结果：用realpart返回复数z的实部值。
getimag( z, &imagpart )
初始条件：复数已存在。
操作结果：用imagpart返回复数z的虚部值。
add( z1,z2, &sum )
初始条件：z1,z2是复数。
操作结果：用sum返回两个复数z1,z2的和值。
adt complex
假设：z1和z2是上述定义的复数，则add(z1,z2,z3)操作的结果将得到z3=z1+z2
抽象数据类型的描述方法
抽象数据类型可用（d，s，p）三元组表示。
其中，d是数据对象，s是d上的关系集，p是对d的基本操作集。
adt抽象数据类型名 {
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义〉
基本操作：〈基本操作的定义〉
adt 抽象数据类型名。
其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为。
基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉
基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头， 除可提供输入值外，还将返回操作结果。
初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。
操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。
抽象数据类型的表示和实现。
抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。
1.3 算法和算法衡量
一、算法。算法是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性：
1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；
2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；
3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；
4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；
5．有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。
二、算法设计的原则
设计算法时，通常应考虑达到以下目标：
1．正确性。
首先，算法应当满足以特定的“规格说明”方式给出的需求。
其次，对算法是否“正确”的理解可以有以下四个层次：
a．程序中不含语法错误；
b．程序对于几组输入数据能够得出满足要求的结果；
c．程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满。
足要求的结果；
d．程序对于一切合法的输入数据都能得出满足要求的结果；
通常以第c层意义的正确性作为衡量一个算法是否合格的标准。
2.可读性
算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；
3．健壮性。
当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4．高效率与低存储量需求。
通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。
三、算法效率的衡量方法和准则
通常有两种衡量算法效率的方法：
事后统计法。
缺点：1。必须执行程序。
2．其它因素掩盖算法本质。
事前分析估算法。
和算法执行时间相关的因素：
1．算法选用的策略。
2．问题的规模。
3．编写程序的语言。
4．编译程序产生的机器**的质量。
5．计算机执行指令的速度。
一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。
假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：
t (n) =o(f(n))
称t (n) 为算法的(渐近)时间复杂度。
如何估算算法的时间复杂度？
算法 = 控制结构 + 原操作。
固有数据类型的操作）
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间。
算法的执行时间与原操作执行次数之和成正比。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
例一 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];
基本操作： 乘法操作。
时间复杂度： o(n3)
例二。void select_sort(int a,int n) {
/ 将a中整数序列重新排列成自小至大有序的整数序列。
for( i = 0; i< n-1; +i )
j = i;
for ( k = i+1; k < n; +k )
if(a[k] if ( j !=i ) a[j] ←a[i] // select_sort 基本操作： 比较(数据元素)操作。 时间复杂度： o(n2) 本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中... 学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指... 1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...数据结构与算法
算法与数据结构
算法与数据结构