考研期末数据结构第一章绪论_1

1、第一章 绪论1.1 什么是数据结构一般来讲，用计算机解决一个具体问题时，大致需要下列几个步骤：首先从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整直至得到最终答案。例1-1图书馆的书目检索系统自动化问题001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02.高等数学001，003樊映川001,L002,理论力学002,华罗庚003,S001,003,线性代数004,栾汝书004,   图1.1 图书目录文件示例由这四张表构成的文件便是书目自动检索的数学模型，计算机的主

2、要操作便是按照某个特定要求对书目文件进行查询。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。例1-2 计算机和人对弈算法：?对弈的规则和策略模型：?棋盘及棋盘的格局例1-3 多叉路口交通灯的管理问题算法：?需要管理的项目？如何管理？ 用户界面？模型：?各种图概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。或者说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构的发展历史v 1968年美国唐欧克努特教授开

3、创了数据结构的最初体系v 从20世纪70年代中期到80年代初，各种版本的数据结构著作就相继出现。v 未来发展的两个方向：（1）面向各专门领域中特殊问题的数据结构（2）抽象数据类型的观点来讨论数据结构1.2 基本概念和术语一、 数据与数据结构数据:所有能输入到计算机中，且能被计算机程序处理的符号的总称。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。可由若干个数据项组成。数据项：是数据结构中讨论的最小单位。数据元素可以是数据项的集合。例如：描述一个运动员的数据元素可以是称之为组合项姓名俱乐部名称出生日期参

4、加日期职务业绩年月日数据对象：是性质相同的数据元素的集合，是数据的一个子集。 例如，整数数据对象是集合N=0，1，-1，2，-2，字母字符数据对象是集合C=A，B，Z。数据结构：带结构的数据元素的集合。是相互之间存在一种或多种特定关系的数据元素的集合。假设用三个4位的十进制数表示一个含 12 位数的十进制数。例如:3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 <a1,a2>、<a2,a3>3214，6587，93456587，3214，9345a1a2a3 a2a1a3又例，

5、在2行3列的二维数组a1, a2, a3, a4, a5, a6 中六个元素之间存在两个关系:行的次序关系:row = <a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>列的次序关系:col = <a1,a4>,<a2,a5>,<a3,a6>a1a3a5a1a2a3a2a4a6 a4a5a6再例，在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系:<ai, ai+1>| i=1, 2, 3, 4, 5可见，不同的“关系”构成不同的“结构”。或者说，

6、数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构或网状结构集合结构数据结构的形式定义为:数据结构是一个二元组:Data_Structures = (D, S)其中:D 是数据元素的有限集，S 是 D上关系的有限集数据的存储结构：逻辑结构在存储器中的映象“数据元素”的映象 ？“关系”的映象 ？数据元素的映象方法：例：用二进制位(bit)的位串表示数据元素(321)10 = (501)8 = (101000001)2A = (101)8 = (001000001)2关系的映象方法：（表示<x, y>的方法）顺序映象以相对的存

7、储位置表示后继关系。例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C。而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息。 x y链式映象以附加信息(指针)表示后继关系。需要用一个和 x 在一起的附加信息指示 y 的存储位置。 y x在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型。定义长整数为:typedef int Long_int 3二、 数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或

8、表达式，明确说明它们所属的数据类型。例如，C 语言中提供的基本数据类型有:整型 int浮点型 float双精度型 double 实型（ C+语言）字符型 char逻辑型 bool （ C+语言）不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。数据类型:是一个值的集合和定义在此集合上的一组操作的总称。三、 抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，抽象数据类型复数的定义：ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1<e1,e2> | e1是复数的实数部分

9、 | e2 是复数的虚数部分 基本操作：AssignComplex( &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返回两个复

10、数z1, z2 的和值 ADT Complex假设:z1和z2是上述定义的复数则 Add(z1, z2, z3) 操作的结果即为用户企求的结果z3 = z1 + z2ADT 有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关

11、系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 赋值参数 只为操作提供输入值。引用参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。例16 抽象数据类型三元组的定义：ADT Triplet 数据对象：D= e1,e2,e3|e1,e2,e3ElemSet (定义了关系运算的某个集合) 数据关

12、系：R1=<e1,e2>,<e2,e3> 基本操作： InitTriplet( &T,v1,v2,v3) 操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数 v1，v2 和 v3 的值。 DestroyTriplet( &T) 操作结果：三元组T被销毁。 Get(T,I,&e) 初始条件：三元组已存在，i<=3. 操作结果：用e返回的第i元的值Put(&T,i,e) 初始条件：三元组已存在，i 操作结果：改变的第i元的值为eIsAscending(T) 初始条件：三元组已存在 操作结果：如果的个元素按升序排列，则返回，否则

13、返回IsDescending(T) 初始条件：三元组已存在 操作结果：如果的个元素按降序排列，则返回，否则返回Ma(T,&e) 初始条件：三元组已存在 操作结果：用e返回的个元素中的最大值ADTTriplet多形数据类型是指其值的成分不确定的数据类型。例如，例16中定义的抽象数据类型Triplet，其元素e1、e2和e3可以是整数或字符或字符串，甚至更复杂的由多种成分构成。从抽象数据类型的角度看，具有相同的数学抽象特性，故称之为多形数据类型。1.3 抽象数据类型的表示与实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。以下对类C语言的描述作简要说明。（1）预

14、定义常量和类型/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status 是函数的类型，其值是函数结果状态代码Typedef int Status; （2）数据结构的表示（存储结构）用类型定义（typedef)描述。数据元素类型约定ElemType,由用户在使用该数据类型时自行定义。（3）基本操作的算法都用以下形式的函数描述：函数类型 函数名（函数参数表） / 算法说明 语名序列 / 函数名 除了函数的参数需要说明类型外，算法中使

15、用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般而言，a、b、c、d、e等用作数据元素名，i、j、k、l、m、n等用作整形变量名，p、q、r等用作指针变量名。当函数返回值为函数结果状态代码时，函数定义为Status类型。为了便于算法描述，除了值调用方式外，增添了C+语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。（4）赋值语名有简单赋值 变量名=表达式；串联赋值 变量名 1=变量名2=变量名k=表达式；成组赋值 （变量名1，变量名k）=（表达式1， ，表达式k）； 结构名=结构名； 结构名=（值1，值k）； 变量名 =表达式； 变量名起始下标.终止下标=

16、变量名起始下标.终止下标；交换赋值 变量名（）变量名；条件赋值 变量名=条件表达式？表达式T：表达式F；（5）选择语句有条件语句1 if (表达式) 语句；条件语句2 if (表达式) 语句； else 语句；开关语句1 switch （表达式） case值1: 语句序列break; case 值n：语句序列n;break ; default; 语句序列n+1； 开关语句2 switch case 条件1：语句序列1;break; default:语句序列n+1； （6）循环语句有for语句 for（赋初值表达式序列；条件；修改 表达式序列）语句；while语句 while（条件）语句； do

17、-while语句 do 语句序列； while（条件）；（7）结束语句有函数结束语句 return表达式； return; case结束语句 break;异常结束语句 exit（异常代码）；（8）输入和输出语句有输入语句 scanf（格式串，变量1，变量n）；输出语句 printf （格式串，表达式1，表达式n）；通常省略格式串。（9）注释单行注释 / 文字序列（10）基本函数有求最大值 max（表达式1，表达式n)求最小值 min（表达式1，表达式n） 求绝对值 abs（表达式）求不足整数值 floor（表达式）求进位整数值 ceil （表达式）判定文件结束 eof（文件变量）或eof判定行

18、结束 eoln（文件变量）或eoln(11)逻辑运算约定 与运算&&：对于A&&B，当A的值为0时，不再对B求值。 或运算|：对于A|B，当A的值为非0时，不再对B求值。例如，对以上定义的复数。/ -存储结构的定义typedef struct float realpart； float imagpart；complex；/ -基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval )；/ 构造复数 Z,其实部和虚部分别被赋以参数 / realval 和 imagval 的值floa

19、t GetReal( cpmplex Z )； / 返回复数 Z 的实部值float Getimag( cpmplex Z )； / 返回复数 Z 的虚部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回两个复数 z1, z2 的和 / -基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart

20、= z1.imagpart + z2.imagpart; 其它省略 例1-7 抽象数据类型Triplet的表示和实现。 /- - - - 采用动态分配的顺序存储结构- - - - - typedef ElemType *Triplet; / 由InitTriplet分配3个元素存储空间/- - - - 基本操作的函数原型说明- - - - - Status InitTriplet (Triplet &T, ElemType v1, ElemType v2, ElemType v3); /操作结果：构造了三元组，元素e1,e2和e3分别被赋以参数 v1，v2 和 v3 的值。 Statu

21、s DestroyTriplet ( Triplet &T); /操作结果：三元组T被销毁。Status Get ( Triplet T , int i , ElemType &e); /初始条件：三元组已存在，<=i<=3. /操作结果：用e返回的第i元的值Status Put (Triplet &T , int i , ElemType e); /初始条件：三元组已存在，<=i<= /操作结果：改变的第i元的值为e Status IsAscending (Triplet T); / 初始条件：三元组已存在 / 操作结果：如果的个元素按升序排列

22、，则返回，否则返回Status IsDescending (Triplet T); / 初始条件：三元组已存在 / 操作结果：如果的个元素按降序排列，则返回，否则返回Status Max (Triplet T, ElemType &e) / 初始条件：三元组已存在/ 操作结果：用e返回的个元素中的最大值Status Min (Triplet T, ElemType &e) / 初始条件：三元组已存在 / 操作结果：用e返回的个元素中的最小值/- - - - 基本操作的函数原型说明- - - - -Status InitTriplet (Triplet &T, ElemT

23、ype v1, ElemType v2, ElemType v3) /构造了三元组，依次置T的三个元素的初值 v1，v2 和 v3 。 T=(ElemType *) malloc(3 *sizeof (ElemType ); /分配三个元素的存储空间 if (!T) exit ( OVERFLOW ) ; /分配存储空间失败 T0=v1; T1=v2; T2=v3; return OK; / InitTripletStatus DestroyTriplet ( Triplet &T) /销毁三元组T。 free ( T ); T = NULL; return OK; / InitTri

24、pletStatus Get ( Triplet T , int i , ElemType &e) /1<=i<=3,用e返回的第i元的值 if ( i<1 | i>3 ) return ERROR; e = Ti-1; return OK; / GetStatus Put (Triplet &T , int i , ElemType e) /1<=i<=3,置的第i元的值为e if ( i<1 | i>3 ) return ERROR; Ti-1 = e; return OK; / PutStatus IsAscending (

25、Triplet T) / 如果的个元素按升序排列，则返回，否则返回 return ( T0 <=T1)&& T1 <=T2); / IsAscending Status IsDescending (Triplet T) / 如果的个元素按降序排列，则返回，否则返回 return ( T0 >=T1)&& T1 >=T2); / IsDescendingStatus Max (Triplet T, ElemType &e) / 用e返回的个元素中的最大值e = ( T0 >=T1)?( T0 >=T2)? T0 :T2)

26、:(T1 >=T2)? T1 :T2);return OK; / MaxStatus Min (Triplet T, ElemType &e) / 用e返回的个元素中的最小值e = ( T0 <=T1)?( T0 <=T2)? T0 :T2):(T1 <=T2)? T1 :T2);return OK; / Min1.4 算法和算法分析1.4.1 算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1有穷性 2确定性 3可行性4有输入 5有输出1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤

27、都能在有限时间内完成。2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径，不允许有二义性。例如下面这句话：张三对李四讲，他的儿子考上了大学。 确切含义？3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

28、1.4.2 算法设计的原则 设计算法时，通常应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量需求1正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。2. 可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程

29、序易于隐藏较多错误而难以调试。3健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。1.4.3 算法效率的度量通常有两种衡量算法效率的方法:事后统计法缺点：1必须执行程序 2其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令

30、的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T(n) = O(f(n)称T(n) 为算法的(渐近)时间复杂度。如何估算算法的时间复杂度？算法 = 控制结构 + 原操作 （固有数据类型的操作）算法的执行时间 =原操作(i)的执行次数×原操作(i)的执行时间算法的执行时间与 原操作执行次数之和成正比 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。例一：

31、两个矩阵相乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i<=n; +i) for (j=1; j<=n; +j) ci,j = 0; for (k=1; k<=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法操作时间复杂度: O(n3)例二：选择排序void select_sort(int& a, int n) / 将 a 中整数序列重新排列成自小至大有序的整数序列。 for ( i = 0; i< n-1; +i

32、) j = i; / 选择第 i 个最小元素for ( k = i+1; k < n; +k ) if (ak < aj ) j = k; if ( j != i ) aj ai / select_sort基本操作: 比较(数据元素)操作时间复杂度: O(n2)例三：起泡排序void bubble_sort(int& a, int n) / 将 a 中整数序列重新排列成自小至大有序的整数序列。for (i=n-1, change=TRUE; i>1 && change; -i) change = FALSE; / change 为元素进行交换标志 fo

33、r (j=0; j<i; +j) if (aj > aj+1) aj aj+1; change = TRUE ; / 一趟起泡 / bubble_sort基本操作: 赋值操作时间复杂度: O(n2)1.4.4 算法的存储空间需求算法的空间复杂度定义为:S(n) = O(g(n)表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。算法的存储量包括:1输入数据所占空间2程序本身所占空间3辅助变量所占空间若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为

34、原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。1.5 英特尔多核技术简介1.5.1 多核计算发展趋势1. 单核CPU的发展限制提高CPU性能的方法：1) 不二法则：提高处理器的主频。困难：高发热问题，会导致芯片运行不稳定，因此主频的提升空间不大。2) 用superscalar（超标量）处理器的方式，让处理器在一个时钟周期内执行多条指令。问题：超标量处理器通常有两个或多个处理单元，利用这些硬件资源，需要对软件进行精心设计；要适应多流水线，需要对软件进行大量的修改，这些都会影响软件的可移植性。3) 通过超流水线方式提高频率。问题：目前超流水线已经达到饱和，再增加超流水线是很困难的。

35、因此，从指令级上提升CPU性能已经达到极限。单纯提高单核CPU速度，还面临着存储器访问速度匹配问题：如果CPU速度高于存储器访问速度，那么CPU的性能同样无法发挥。而实际使用中存储器访问速度并不能与处理器速度同步提高，因此，单纯提高单核CPU速度并不能促进计算机系统整体性能的提高。提高单核CPU处理能力的方法来提升计算机系统性能，已经到达瓶颈状态。2. 对高性能计算的需求越来越高例如：网络服务器软件需要同时响应大量用户的请求；多媒体游戏软件需要对图形、动画进行大量运算；实时嵌入式系统的快速发展使其对计算能力的需求每年都在增长；客户端杀毒软件中杀毒软件、安全软件等对计算能力的需求也在逐年增加。3. 多核计算将成为发展趋势单个CPU的计算能力是无法与多个CPU的计算能力相比的，计算机硬件中仍然需要有多个CPU以获取更高的性能，软件中仍需要采取多核计算以取得更高的性能。多核计算将成为未来的发展趋势，多核编程将成为程序员必须掌握的技术。1.5.2 什么是多核技术多内核是指在一枚处理器中集成两个或多个完整的计算引擎(内核)。多核技术的开发源于工程师们认识到，仅仅提高单核芯片的速度会产生过多