第1章绪论.docx
《第1章绪论.docx》由会员分享，可在线阅读，更多相关《第1章绪论.docx（42页珍藏版）》请在冰点文库上搜索。
第1章绪论
第1章绪论
教学要点
数据结构与算法是一门讨论如何在计算机中描述现实世界实体的数学模型并实现其操作的学科。
数据的表示组织和处理方法直接关系到软件的工程化程度和软件的运行效率，所以软件设计时要考虑的首要问题是数据的表示、组织和处理方法。
软件设计是计算机学科各个领域的主体任务，而数据结构设计和算法设计是软件系统设计的核心。
在计算机领域流传着一句经典名言，就是“数据结构+算法=程序”（瑞士NiklausWirth教授）。
这句话简洁明了地指明了程序和数据结构与算法的关系，因而也说明了数据结构课程的重要性。
本章是整个课程的绪论，将讨论数据结构与算法学科中重要的基本概念，如数据、数据类型、数据结构、算法等，以及算法分析的基本方法。
此外还将介绍C#程序设计语言的最基本的内容。
建议本章授课6-9学时，其中数据结构与算法的基本概念部分3学时，C#语言3-6学时。
1.1数据结构的基本概念
1.1.1数据类型与数据结构
1.数据、数据项和数据元素
数据（data）是计算机程序的处理对象，它可以是任何能输入到计算机的符号集合，例如描述客观事物数量特征的数值以及名称特性的字符。
例如，学生信息管理程序处理的数据是每个学生的情况，包括学号、姓名、年龄和各科成绩等；科研设备管理程序处理的数据是每台设备的信息，包括设备号、设备类型、名称和保管人等；图像和视频处理软件接受和处理的数据是经过专业设备采集的图像和视频信号。
随着技术的进步，数据的形式也越来越多。
数据的基本单位是数据元素（dataelement），它是表示一个事物的一组数据，有时又称为结点；构成数据元素的某个成分的数据称作该数据元素的数据项（dataitem），有时又称为域（datafield），数据项是数据元素的基本组成单位。
2.数据类型
在用高级程序语言（如C语言）编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。
数据类型（datatype）是一个“值”的集合和定义在此集合上的“一组操作”的总称。
它定义了所属类型的数据元素的性质、取值范围以及对数据元素所能进行的各种操作。
例如，C#语言中整数类型int的值域是{-231，…，-2，-1，0，1，2，…，231-1}，对这些值进行的操作包括加减乘除和求模操作。
高级程序设计语言都提供了一些基本数据类型，如C#中有int、long、float、double、char、string等基本数据类型。
利用这些基本数据类型，软件设计人员还可以设计出各种复杂的数据类型，称为自定义数据类型。
例如可以定义“学生”类型，它是一种复合类型，包括学号、姓名和成绩等信息，学生姓名可以用字符串类型string表示，年龄可以用整数类型int表示，成绩可以用浮点类型float表示等。
3.抽象数据类型
为了描述更广泛范围的数据实体，数据结构和算法描述中使用的数据类型不仅仅局限于程序设计语言中的数据类型，而更多地是指某种抽象数据类型（AbstractDataType，ADT）。
抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。
抽象数据类型不仅仅局限于编程语言中的数据类型，它的范畴更为广泛。
一般地说，数据类型指的是高级程序设计语言支持的数据类型，又称为固有数据类型；而抽象数据类型是数据与算法在较高层次的描述中用到的概念，指的是在固有数据类型支持下用户新设计的数据类型。
抽象数据类型具有“数据抽象”和“数据封装”两个重要特征。
数据抽象特征表现在：
用抽象数据类型描述程序处理的实体时，强调的是数据的本质特征、其所能完成的功能以及它和外部接口（即外界使用它的方法）。
数据封装特征表现在：
抽象数据类型将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
我们将要讨论表、栈、队列、串、数组、树和二叉树、图等典型的数据结构，在描述它们时，这些典型的数据结构就是一个个不同的抽象数据类型，在实现它们时，我们就定义了相应的数据类型。
所以，实质上数据类型和抽象数据类型是相同的。
4.数据结构
计算机处理的数据一般很多，但它们不是杂乱无章的，众多的数据间往往存在着内在的联系，对大量的、复杂的数据进行有效处理的前提是分析清楚它们的内在联系。
数据结构（datastructure）是指数据元素之间存在某种关系的数据集合。
例如，一个按学号排列的学生信息数据集合，就是一个具有“顺序”关系的数据结构，这种关系不因数据的改变而改变。
数据结构可以看成是关于数据集合的数据类型，它关注三个方面的内容：
数据元素的特性、它们之间的关系以及由这些数据元素组成的数据集合所允许进行的操作。
例如，前面提到的学生数据结构具有顺序关系；而由祖父、父亲、我、儿子、孙子等成员组成的家族数据结构具有层次关系。
数据结构课程主要讨论三方面的问题：
数据的逻辑结构、数据的存储结构和数据的操作。
后面的小节将陆续介绍相关的概念。
【例1.1】用C#语言描述学生信息和学生信息表数据结构。
假设要描述的学生信息包括学生的学号、姓名、性别、年龄等数据。
每个学生的相关信息一起构成学生信息表中的一个数据元素，其中学号、姓名、性别、年龄等数据就构成学生情况描述的数据项。
表1.1是一个有3个数据元素的学生信息表。
表1.1学生信息表
学号
姓名
性别
年龄
200518001
王兵
男
18
200518002
李霞
女
19
200518003
张飞
男
19
表1.1的学生信息可以用C#语言声明为如下的类型：
publicclassStudent{
publicstringstudentID;
publicstringname;
publicstringgender;
publicintage;
}
学生信息表是由Student类型的数据元素组成的、能够进行特定操作的数据集合，即学生信息表是一种特定类型的数据结构。
学生信息表用C#语言声明为如下的类型：
classStudentInfoTable{
Student[]studentList;//学生信息表内部存储块
publicintAdd（Studentst）;//将新学生添加到表的结尾处
publicboolContains（Studentst）;//确定某个学生是否在表中
publicvoidSort（）;//对表中元素进行排序
}
1.1.2数据的逻辑结构
数据的逻辑结构侧重于数据集合的抽象特性，它用一个数据元素的集合和定义在此集合上的若干关系来表示数据元素之间的逻辑关系。
数据结构这一术语很多时候指的就是数据的逻辑结构。
基本的数据结构按照它们的数据元素之间存在的不同特性的逻辑关系，可以分为三种：
线性结构、树结构和图结构。
1.线性结构
线性结构具有的特性是：
数据集合的第一个数据元素没有前驱数据元素，最后一个数据元素没有后继数据元素，其他的每个元素只有一个前驱元素和一个后继元素。
线性结构如图1.1（a）所示，其中数据元素B有一个前驱数据元素A，有一个后继数据元素C。
2.树结构
树结构具有的特性是：
数据集合有一个特殊的数据元素称为根结点，它没有前驱数据元素；树中其他的每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。
树结构如图1.1（b）所示，其中数据元素A是根结点，数据元素B有一个前驱数据元素A，有两个后继数据元素D和E。
3.图结构
图结构具有的特性是：
数据集合的每个数据元素可有零个或若干个前驱数据元素，可有零个或若干个后继数据元素。
图结构如图1.1（c）所示，其中数据元素C有两个前驱数据元素A和B。
图1.1三种基本的数据结构
经常用图1.1那样的图示法表示数据的逻辑结构。
在图示法中，圆圈表示一个数据元素，圆圈中的字符或数字表示数据元素的标记或值，连线表示数据元素间的关系。
1.1.3数据的存储结构
数据的逻辑结构是编程人员从逻辑关系的角度观察数据，为了在计算机中实现对数据的操作，还需按某种方式在计算机中存储和表示这些数据。
数据在计算机中的存储表示方式称为数据的存储结构，也称为物理结构。
数据的逻辑结构具有独立于计算机的抽象特性，数据的存储结构则依赖于计算机，它是逻辑结构在计算机中的实现。
1.顺序存储结构和链式存储结构
基本的数据存储结构有两种形式：
顺序存储结构和链式存储结构。
顺序存储结构将数据集合的元素存储在一块地址连续的内存空间中，并且逻辑上相邻的元素在物理上也相邻。
例如，用C语言中的数组可以实现顺序存储结构，数组元素之间的顺序体现了线性结构中元素之间的逻辑次序，数据元素的存储位置由其在集合中的逻辑位置确定。
链式存储结构使用称为结点（node）的扩展类型存储各个数据元素，结点由数据元素域和指向其他结点的指针域组成，链式存储结构使用指针把相互关联的结点链接起来。
数据集合中逻辑上相邻的元素在物理上不一定相邻，元素间的逻辑关系表现在结点的链接关系上。
在顺序存储结构中，所有的存储空间都被数据元素占用了；而链式存储结构中，每个结点至少由两部分组成：
数据域和指针域，数据域保存数据，指针域指向相关结点。
指针域保存指向相关结点的链信息，因此又称为链域。
顺序存储结构和链式存储结构是两种常用的基本存储结构。
利用这两种基本存储结构的组合，可以产生复杂的存储结构。
【例1.2】线性表的两种存储结构。
对于数据元素是{A，B，C}的线性结构，其顺序和链式存储结构如图1.2所示。
图1.2两种不同的存储结构
2.存储密度
一个数据结构所需的存储空间不仅用来存放数据本身，也可能存放其他的信息。
数据结构的存储密度定义为数据本身所占用的存储量和整个数据结构所占的存储量的比值，即：
如果结构所有的存储空间都用来存储数据元素，则这种存储结构是紧凑结构，紧凑结构的存储密度为1，顺序存储结构是紧凑结构。
如果结构的所有存储空间不仅用来存储数据本身，也存储其他的信息，则这种存储结构是非紧凑结构，它的存储密度小于1。
存储密度越大，则存储空间的利用率越高；存储密度底，说明附加的信息可能较多，这可能会带来操作上的便利。
链式存储结构是非紧凑结构。
3.数据存储结构的选择
计算机运行任何程序都要花费一定的时间和占用一定的内存空间，所以在软件设计时，除了用正确的逻辑结构描述要解决的问题外，还应选择一种合适的存储结构，使得所实现的程序在以下两方面的综合性能最佳：
数据操作所花费的时间和程序所占用的存储空间。
两者都是越少越好。
例如，对于线性表的存储，可以按下面两种情况分别处理：
1）当不需要频繁插入和删除时，可以采用顺序存储结构，此时占用的空间少。
2）当插入和删除操作很频繁时，需要采用链式存储结构。
此时虽然占用的空间较多，但操作的时间效率高。
这种方案以存储空间为代价换取了时间效率。
1.1.4数据的操作
数据的操作指的是对属于一种数据类型的任意对象所能进行的某种处理，对一种数据类型的数据对象进行的所有操作构成该种数据类型的操作集合。
数据的操作是定义在数据的逻辑结构上的，每种逻辑结构都有一个操作集合，不同的逻辑结构有不同的操作。
操作的具体实现与存储结构有关。
例如对于一个线性结构，尽管它的存储结构可能有多种方式，该数据集合上可以定义以下几种常用的操作：
●获取或设置数据集合某元素的值。
●统计数据集合的元素个数。
●插入新的数据元素。
●删除某数据元素。
●在数据结构中查找满足一定条件的数据元素。
●将数据集合的元素按某种指定的顺序重新排列。
1.2算法与算法分析
1.2.1算法
算法（Algorithm）是对特定问题求解过程的一种描述，是解决该问题的一个确定的、有限长的操作序列。
1.算法定义：
数据结构与算法领域的经典著作《TheArtofComputerProgramming》的作者、著名计算科学家D.Knuth对算法做过一个为学术界广泛接受的描述性的定义：
算法是一个有穷规则的集合，其规则确定了一个解决某一特定类型问题的操作序列。
算法的规则具有如下5个重要特征：
●确定性—对于每种情况下所应执行的操作，在算法中都有确切的规定，算法的执行者或阅读者都能明确其含义，并且在任何条件下，算法都只有一条执行路径。
●可行性—算法中的所有操作都必须是足够基本的，都可以通过已经实现的基本操作运算有限次予以实现。
●有穷性—对于任意一组合法输入值，算法必须在执行有穷步骤之后结束。
算法中的每个步骤都能在有限时间内完成。
●有输入—算法有零个或多个输入数据，即算法的加工对象。
有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。
●有输出—算法有一个或多个输出数据，它是算法进行信息加工后得到的结果，与“输入”有确定关系，这种关系体现算法的功能。
2.算法的描述
算法可用文字、流程图、高级程序设计语言或类同于高级程序设计语言的伪码描述。
无论哪种描述形式，都要体现出算法是由语义明确的操作步骤组成的有限序列，它精确地指出怎样从给定的输入信息得到要求的输出信息，算法的执行者或阅读者都能明确其含义。
【例1.3】线性表的顺序查找（sequentialsearch）算法。
在线性表中，按关键字进行顺序查找的算法思路为：
对于给定值k，从线性表的一端开始，依次与每个元素的关键字进行比较，如果存在关键字与k相同的数据元素，则查找成功；否则查找不成功。
顺序表的顺序查找过程如图1.3所示。
图1.3顺序存储线性表的顺序查找过程
3.算法与数据结构
数据的逻辑结构、存储结构以及对数据所进行的操作三者是相互依存的。
在研究一种数据结构时，总是离不开研究对这种数据结构所能进行的各种操作，因为，这些操作从不同角度体现了这种数据结构的某种性质，只有通过研究这些操作的算法，才能更清楚地理解这种数据结构的性质。
反之，每种算法都是建立在特定的数据结构上的。
数据结构和算法之间存在着本质的联系，失去一方，另一方就没有意义。
（1）同样的逻辑结构因为存储结构的不同而采用不同的算法。
线性表可以用顺序存储结构或链式存储结构实现，不同存储结构的线性表上的排序算法是不同的。
例如，冒泡排序、折半插入排序等算法适用于顺序存储结构的线性表；适用于链式存储结构线性表的排序算法有直接插入排序、简单选择排序等（详见第九章“排序算法”）。
（2）同样的逻辑结构和存储结构，因为要解决问题的要求不同而采用不同的算法。
【例1.4】大规模线性表的分块查找（blockingsearch）算法
在前面的例子中介绍的顺序查找算法适合于数据量较小的线性表，如学生成绩表。
一部按字母顺序排序的字典也是一个顺序存储的线性表，具有与学生成绩表相同的逻辑结构和存储结构，但数据量较大，采用顺序查找算法的效率会很低，此时可以采用分块查找算法。
一部字典是按词条的字母顺序排好序的线性表，它也可以看成是由首字母相同、大小不等的若干块（block）所组成的，为使查找方便，每部字典都设计了一个索引表，指出每个字母对应单词的起始页码。
字典分块查找算法的基本思想：
将所有单词排序后存放在数组dict中，并为字典设计一个索引表index，index的每个数据元素由两部分组成：
首字母和下标，它们分别对应于单词的首字母和以该字母为首字母的单词在dict数组中的起始下标。
这样，通过索引表index，将较长的单词表dict划分成若干个数据块，以首字母相同的的若干单词构成一个数据块，因此每个数据块的大小不等，每块的起始下标由index中对应“首字母”列的“下标”标明。
使用分块查找算法，在字典dict中查找给定的单词token，必须分两步进行：
●根据token的首字母，查找索引表index，确定token应该在dict中的哪一块。
●在相应数据块中，使用顺序查找算法查找token，得到查找成功与否的信息。
1.2.2算法设计的要求
一个好的算法设计应达到以下目标：
●正确性（Correctness）—算法应确切地满足具体问题的需求，这是算法设计的基本目标。
对算法是否“正确”的理解可以有四个层次：
1）不含语法错误；2）对于某几组输入数据能够得出满足要求的结果；3）程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；4）程序对于一切合法的输入数据都能得出满足要求的结果；
●可读性（Readability）—算法既是为了计算机执行，也是为了人的阅读与交流。
算法的描述应有利于人们的理解，这既有利于程序的调试和维护，也有利于算法的交流和移植。
算法的可读性主要体现在两方面：
一是被描述算法中的类名、对象名、方法名等的命名要见名知意；二是要有足够多的注释。
相反，晦涩难读的程序易于隐藏较多错误而难以调试。
●健壮性（Robustness）—当输入非法数据时，算法要能做出适当的处理，而不应产生不可预料的结果。
一般地，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
●高效性（Efficiency）—算法的执行时间应满足问题的需求，执行时间短的算法称为高时间效率的算法；算法在执行时一般要求额外的内存空间，内存要求低的算法称为高空间效率的算法。
算法应满足高时间效率与低存储量需求的目标，对于同一个问题，如果有多个算法可供选择，应尽可能选择执行时间短和内存要求低的算法。
但算法的高时间效率和高空间效率通常是矛盾的，在很多情况下，首先考虑算法的时间效率目标。
1.2.3算法效率分析
1．算法的时间复杂度
一个算法由控制结构和原操作构成，算法的执行时间等于所有语句执行时间的总和，它取决于控制结构和原操作两者的综合效果。
为了便于比较同一问题的不同算法，通常选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。
算法的执行时间是算法所处理的数据个数n的某种函数，表示为O（f（n）），我们称O（f（n））为该算法的时间复杂度（timecomplexity），通常用算法的时间复杂度来表示算法的时间效率。
O
（1）表示算法执行时间是一个常数，不依赖于n；O（n）表示时间与n成正比，是线性关系，O（n2）、O（n3）、O（2n）分别称为平方阶、立方阶和指数阶；O（log2n）为对数阶。
若两个算法的执行时间分别为O
（1）和O（n），当n充分大时，显然O
（1）的执行时间要少。
同样，O（n）和Ｏ（log2n）相比较，当n充分大时，因log2n的值远比n小，则O（log2n）所对应的算法速度要快得多。
时间复杂度随n变化情况的比较如表1.2所示。
表1.2时间复杂度随n变化情况的比较
时间复杂度
n=8（23）
N=10
n=100
n=1000
O
（1）
1
1
1
1
O（log2n）
3
3.322
6.644
9.966
O（n）
8
10
100
1000
O（nlog2n）
24
33.22
664.4
9966
O（n2）
64
100
10000
106
【例1.5】分析算法片段的时间复杂度。
（1）时间复杂度为O
（1）的简单语句。
n=10;
该语句的执行时间是一常量，时间复杂度为O
（1）。
（2）时间复杂度为O（n）的单重循环。
intn=100,sum=0;
for（inti=0;i该for语句循环体内语句的执行时间是一常量，共循环执行n次，所以该循环的时间复杂度为O（n）。
（3）时间复杂度为O（n2）的二重循环。
intn=100;
for（inti=0;ifor（intj=0;jConsole.Write（i*j）;
外层循环执行n次，每执行一次外层循环时，内层循环执行n次。
所以，二重循环中的循环体语句执行n×n次，时间复杂度为O（n2）。
如果
intn=100;
for（inti=0;ifor（intj=0;jConsole.Write（i*j）;
外层循环执行n次，每执行一次外层循环时，内层循环执行i次。
此时，二重循环的执行次数为
，则时间复杂度仍为O（n2）。
（4）时间复杂度为O（nlog2n）的二重循环。
intn=64;
for（inti=1;i<=n;i*=2）
for（intj=1;j<=n;j++）
Console.Write（i*j）;
外层循环执行log2n次，外层循环每执行一次，i就乘以2，直至i＞n。
内层循环执行次数恒为n。
此时，总的循环次数为
，则时间复杂度为O（nlog2n）。
（5）时间复杂度为O（n）的二重循环。
intn=64;
for（inti=1;i<=n;i*=2）
for（intj=1;j<=i;j++）
Console.Write（i*j）;
外层循环执行log2n次。
内层循环执行i次，随着外层循环的增长而成倍递增。
此时，总的循环次数为
，则时间复杂度为O（n）。
2．算法的空间复杂度
算法的执行除了需要存储空间来寄存本身所用指令、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现算法所需的辅助空间。
与算法的时间复杂度概念类似，算法在执行时要求的额外内存空间称为算法的空间复杂度（spacecomplexity），分析从略。
1.3C#语言简介
在以Pascal和C为代表的结构化程序设计语言中，数据的描述和对数据的操作两者是分离的，数据的描述用数据类型表示，对数据的操作则用过程或函数表示。
例如，在描述字符串时，先定义字符串的数据表示，再用过程实现对字符串的操作。
这种程序设计方式虽然可行，但所设计的代码往往具有重用性差、可移植性差、数据维护困难等缺点。
针对这个问题逐渐发展出了面向对象的程序设计思想。
面向对象技术具有抽象、信息隐藏和封装、继承和多态等特性。
在数据结构的理论中，数据的逻辑结构、存储结构以及对数据所进行的操作三者实际上是是相互依存、互为一体的，所以用封装、继承和多态等面向对象的特性能够更深入地刻画数据结构。
例如，将字符串声明为一个String类，而串连接、串比较等操作则声明为该类的方法。
字符串类的设计者设计这个类并实现其中的方法。
此时数据的描述和对数据的操作两者封装在同一个以类为单位的模块中，因此增强了代码的重用性、可移植性，使数据易于维护。
String类的使用者，只需要知道该类对外的接口，即类中的公共方法即可使用该类。
MicrosoftC#（读作Csharp）是一种新的编程语言，它是为生成运行在.NETFramework平台上的、广泛的企业级应用程序而设计的。
在面向对象的编程语言中，C#具有精确、简单、类型安全、面向对象、跨平台互用的特点；用C#开发的应用软件在可移植性、健壮性、安全性方面大大优于已存在的其他编程语言。
.NETFramework为C#提供了丰富的类库，利用这个庞大的类库，可进行面向对象的事件描述、处理和综合，极大地方便了众多领域的应用开发。
C#语言从C和C++语言演化而来。
它在语句、表达式和运算符方面使用了许多C++功能。
C#语言在类型安全性、版本转换、事件和垃圾回收等方面进行了相当大的改进和创新。
C#提供了对象的自引用方式用以实现数据的链式存储结构，这种方式避免直接使用指针所带来的安全隐患，使C#语言可以实现面向对象的数据结构。
1.3.1C#的安装、编辑、编译和
升级会员 