基础数据结构：围绕数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定的基本应用描述。
应用数据结构：以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理清晰，轮廓分明。
学习目标：
掌握基本的数据结构
工具箱-复用、修改、重组
掌握数据结构的经典算法
折半查找、快速排序、最短路径、最小生成树
理解算法的设计思想
掌握初步的算法分析技术
时间分析和空间分析
评价算法、改进算法
掌握不同数据结构的实现方式
线性结构、树结构和图结构
第一章绪论
1.1数据结构的研究内容
计算机解决具体问题的步骤
（1）建立数学模型
设计数据对象的表示结构（信息结构层次）
（2）算法设计
解决待定问题的具体步骤描述（求解策略层次）
（3）编码
（语言层次）
（4）调试与测试
数据结构的定义：
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
-描述非数值问题的数学模型，不再是数学方程，而是线性结构、树状结构和图状结构。
1.2基本概念和术语
数据（data）：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
-例如：数字、字符、声音、图形、图像等信息。
数据元素（dataelement）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也称为结点（node）或记录（record）
数据项：是数据不可分割的最小单位，也称为域（field）
数据对象：性质相同的数据元素的集合，是数据的一个子集。
-如：整数数据对象N={0，+1，-1，+2，-2...}
四者之间的数据关系：
数据数据对象数据元素数据项
数据结构：
相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合。
“结构”是指数据元素之间存在的关系
数据结构的定义形式：
Data_Structure=(D,R)
D是数据元素的有限集
R是D上关系的有限集
数据结构的两个层次：
逻辑结构
描述数据元素之间的逻辑关系
与数据的存储无关，独立于计算机
是从具体问题抽象出来的数学模型
物理结构（存储结构）
数据元素及其关系在计算机存储器中的存储方式
数据结构在计算机中的表示
可分为4大类：顺序、链式、索引、散列
逻辑结构：
集合
数据元素间除“同属于一个集合”外，无其他关系
线性结构
数据元素间存在一个对一个的关系
树形结构
一对多
图状结构
多对多
存储结构：
顺序存储结构
借助元素在存储器中的相对位置来表示数据元素间的逻辑关系
用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
链式存储结构
借助指示元素存储地址的指针表示数据元素间的逻辑关系
用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
数据的运算：
在数据的逻辑结构上定义操作算法，而在存储结构上进行实现
最常用的5种运算：插入、删除、修改、查找、排序
⑴插入：在数据结构中的指定位置上增添新的数据元素；
⑵删除：删去数据结构中某个指定数据元素；
⑶更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；
⑷查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值）；
⑸排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。
逻辑结构和存储结构相同，但运算不同，则数据结构不同
-例如栈和队列
运算的实现依赖于存储结构
总结：
数据的逻辑结构是数据的机外表示，数据的存储结构是数据的机内表示。
一种数据结构可以用多种存储结构来存储。
任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采取的存储结构
采用不同的存储结构，其数据处理的效率往往是不同的。
1.3抽象数据类型的表示与实现
数据类型：
在一种程序设计语言汇总，变量所具有的数据种类
C语言：
基本数据类型：charintfloatdouble
构造数据类型：数组、结构体、共用体
明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这个值上允许的操作。
因此，数据类型是一组值的集合以及定义于这个值集上的一组操作的总称。
一些最基本的数据结构可以用数据类型来实现，如数组、字符串等；
而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型表示。
抽象数据类型（AbstractDataType，ADT）：
一个数据模型以及定义在该模型上的一组操作。
由用户定义，从问题抽象出数据模型（逻辑结构）
还包括定义在数据模型上的一组抽象运算（相关操作）
不考虑计算机内的具体存储结构与运算的具体实现算法
ADT的两个重要特征：
数据抽象
通过数据抽象，将一个数据对象的规格说明与其实现分离，对外提供简洁、清晰的接口。
数据封装
通过数据封装，将一个数据对象的内部结构和实现细节对外屏蔽
抽象数据类型的表示：
可以用三元组进行表示：
ADT=(D,R,P)
D：数据对象，R：D上的关系集，P：D上的操作集
ADT常用定义格式：
基本操作的定义格式：
基本操作名(参数)
初始条件：（初始条件描述）
操作结果：（操作结果描述）
赋值参数：只为操作提供输入值
引用参数：以开头，除提供输入值外，还将返回操作结果
初始条件：描述了操作执行前数据结构和参数应满足的条件，若不满足，操作失败，并返回相应出错信息。若初始条件为空，则省略之。
操作结果：说明操作正常完成之后，数据结构的变化情况和应返回的结果。
注：初始条件可以为空，并可以省略。
ADT实现的含义：
将ADT转换成程序设计语言的说明语句，加上对应于该ADT中的每个操作的函数。
用适当的数据结构来表示ADT中的数学模型，并用一组函数来实现该模型上的各种操作。
抽象数据类型如何实现：
抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示实现。
即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。
在C中定义一个结构体类型要用typedef:
typedefstructStudent
{
inta;
}Stu;
于是在声明变量的时候就可：Stustu1;(如果没有typedef就必须用structStudentstu1;来声明)
这里的Stu实际上就是structStudent的别名。Stu==structStudent
另外这里也可以不写Student（于是也不能structStudentstu1;了，必须是Stustu1;）
typedefstruct
{
inta;
}Stu;
但在c++里很简单，直接
structStudent
{
inta;
};
于是就定义了结构体类型Student，声明变量时直接Studentstu2；
预定义常量和类型：#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//status是函数的类型，其值是函数结果状态代码
关于引用：
注意：C语言不支持引用类型
引用运算符：
引用是个别名，建立引用时，程序用另一个已定义的变量的名字初始化它，从那时起，引用作为目标的别名而使用，对引用的改动实际是对目标的改动。
引用常常用于函数形参中，采用引用型形参时，实现数据双向传递
例如：inta=4;/*a为普通的整型变量*/intb=a;/*b是a的引用变量*/b变量是变量a的引用,b也等于4,这两个变量同步改变值传递：voidswap(intx,inty){inttemp;temp=x;x=y;y=temp;}当执行语句swap(a,b)时：a和b的值没有发生交换地址传递：voidswap(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}当执行语句swap(a,b)时：a和b的值发生了交换
ADT实现中的几个问题：
类C语言与C程序之间的差别
算法中除形式参数外，变量不作定义，在C程序中必须定义
算法中使用的元素类型（ElemType）没有定义，C程序中必须定义；常量OK,ERROR,OVERFLOW等在第一章统一定义
算法中的比较运算符（equal、less）未作定义，C程序中必须定义
必要的头文件（用作输入输出的stdio.h及内存申请的stdlib.h），在C程序中必须包含
1.4算法和算法分析
1.4.1算法的定义及特性
定义：对特定问题求解步骤的一种描述，是指令的有限序列。
算法的特性：
输入：一个算法有0个或多个输入
输出：一个算法有1个或多个输出
有穷性：一个算法不需总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中的每一条指令必须有确切的含义，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出（无二义性）
可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
1.4.2评价算法优劣的基本标准
正确性（Correctness）
有四个层次：
程序中不含语法错误
程序对于几组输入数据能够得出满足要求的结果
程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
程序对于一切合法的输入数据都能得出满足要求的结果。
通常以第三层意义上的正确性作为衡量一个算法是否合格的标准。
可读性（Readability）
算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该易于人的理解
另一方面，晦涩难读的算法易于隐藏较多错误而难以调试
健壮性（Robustness）
指当输入数据非法时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果
处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
高效性（Effectiveness）
包括时间和空间两个方面
时间高效指算法设计合理，执行效率高，可以用时间复杂度来度量。
空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。
两者都与问题的规模有关。
1.4.3算法效率的度量
算法效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。
两种度量方法：
事后统计
将算法实现、测算其时间和空间开销
缺点
编写程序实现算法将花费较多的时间和精力
所得实验结果依赖于计算机的软硬件等环境因素
事前分析
对算法所耗资源的一种估算方法
一个高级语言程序在计算机上运行所消耗的时间取决于
算法选用的策略
问题的规模
编写程序的语言
编译程序产生的机器代码质量
机器执行指令的速度
同一个算法用不同的语言、不同的编译程序在不同的计算机上运行，效率均不同。因此，使用绝对时间单位衡量算法效率是不合适的。
一个特定算法的“运行工作量”大小，只依赖于问题的规模（通常用整数n表示），即它是问题规模的函数。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)
随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作T(n)=O(f(n))
称T(n)为算法的渐近时间复杂度。
算法的构成=控制结构+原操作（固有数据类型的操作）
算法的执行时间=
算法的执行时间与原操作执行次数之和成正比
算法的运行时间由算法中所有语句的频度（语句重复执行的次数）之和构成。
算法的时间复杂度是由嵌套最深层语句的频度决定的。
运算规则1、O(f(n))+O(g(n))=O(max(f(n),g(n)))2、O(cf(n))=O(f(n)),c是正整数3、O(f(n))*O(g(n))=O(f(n)*g(n))
分析算法时间复杂度的基本方法
找出语句频度最大的那条语句作为基本语句
计算基本语句的频度得到问题规模n的某个函数f(n)
取其数量级用符号"O"表示
有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
例如：
冒泡排序
最好情况下，T(n)=O(1)
最坏情况下，T(n)=
对这类算法的分析，一种解决办法是计算平均值，即考虑它对所有可能的输入数据集的期望值。
但是，很多情况下，各种输入数据集出现的概率难以确定。
1.4.4算法的空间复杂度
算法开始运行至结束过程中所需要的最大存储资源开销的一种度量
表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。
算法占据的存储空间：
输入数据所占空间
程序本身所占空间
辅助变量所占空间
一维数组的空间复杂度是O(n)
若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间
原地工作：若额外空间相对于输入数据量来说是常数，则称此算法为原地工作
注：若额外空间所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。
预览时标签不可点收录于话题#个上一篇下一篇