教材： 《数据结构（C语言版）》严蔚敏、吴伟民编著,清华大学出版社 主要参考教材： 《数据结构》 张乃孝编著，高等教育出版社 《DATA STRUCTURES & PROGRAM DESIGN IN C》Robert L.Kruse Prentice-Hall International,Inc.

第一章 绪论

学习数据结构的必要性 信息表示A 信息表示B 计算机 著名计算机科学家 N. Wirth 提出下面的公式： 算法 + 数据结构 = 程序

数据结构的地位 数据结构在计算机科学技术专业课程中起作基础、核心、纽带、桥梁的作用。 是计算机专业的核心基础课。 是理论联系实际、数学与计算机科学、软件与硬件的纽带。 是通往其它专业课程的桥梁。

本章讨论的内容： 1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度

1.1 数据结构讨论的范畴 为一个实际问题开发一个程序，系统通常可以分成以下四个阶段 1。分析阶段 2。设计阶段 （与本课程关系最密切） 3。编码阶段 4。测试和维护

数值计算与非数值计算 例如: 数值计算的程序设计问题：微积分中的计算：求面积，体积，线积分，面积分等； 线性代数中 解方程组； 近似计算，误差估计等等。

非数值计算的程序设计问题 例1: 找一组(n个)整数中的最大值 算法: ? 模型：？ 基本操作是“比较两个数的大小” 取决于整数值的范围

例2：旅馆客房的管理 算法：? 模型：? 先进后出 队列

例3：实际问题中对象之间的关系——学生成绩管理 学生成绩表 学号 姓名 大学英语 C语言 数据结构 … A07001 王萍 90 85 95 A07002 马玲 80 A07003 张兰 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 : ： 关系：线性 特征：一个直接前趋， 一个直接后继 A07001 王萍 90 85 95 A07002 马玲 80 85 90 A07003 张兰 95 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78

例4：“井字棋”的人机对弈 实际问题中对象之间的关系 关系：树型 特征：一个直接前趋， 多个直接后继 × O × O × O × O × O … …

例5：交通控制问题 对于一个多叉路口， 设计一个交通信号灯 的管理系统。首先需 要分析一下所有车辆 的行驶路线的冲突问 题。这个问题可以归 结为对车辆的可能行 驶方向作某种分组， 对分组的要求是使任 一个组中各个方向行 驶的车辆可以同时安 全行驶而不发生碰撞。

问题分析 可通行方向 AB AC A D BA BC BD DA DB DC EA EB EC ED

图1.2 交叉路口的图示模型 有些通行方向显然不能同时进行，相应的结点间画一条连线。 AB AC AD BA BC BD DA D B DC EC ED EA EB 图1.2 交叉路口的图示模型

把图1.2中的结点进行分组，使得有结点相连的结点不在同一个组里。 地图着色问题 如果把上图中的一个结点理解为一个国家， 结点之间的连线看作两国有共同边界，上述问题 就变成著名的“着色问题”：即求出最少要几种颜 色可将图中所有国家着色，使得任意两个相邻的 国家颜色都不相同。 通过上面的分析，我们就获得了该交通管系统的数学模型。

交通控制问题可抽象为图的作色问题： 如何用最少的颜色对一个图着色使得相邻顶点的颜色都不同？ 算法：? 模型：? 图

程序设计 算法设计两种简单的方法： 1. 对n个结点，逐个测试其所有组合； 2. “贪心算法” while 有结点未着色； { 选择一种新颜色； 在未着色的结点中,给尽可能多的彼此结 点之间没有边的点着色； }

着色结果如下： AB AC AD BA BC BD DA D B DC EC ED EA EB 图1.2 交叉路口的图示模型，每组中没有边互连

把上面方法应用于图1.2，得到下面的分组： 绿色：AB, AC, AD, BA, DC, ED 蓝色：BC, BD, EA 红色：DA, DB 白色：EB, EC

算法精化： 假设需要着色的图是G，集合V1包括图中所有未被着色的结点，着色开始时V1是G所有结点集合。NEW表示已确定可以用新颜色着色的结点集合。 　 for 每个v  V1 do 　　 if v与NEW中所有结点间都没有边 　　　 { 从V1中去掉v ; NEW=NEW{v} ; }

算法精化： int colorUp( Graph G) { int color=0; V1=G.V; while(!isSetEmpty(V1)) { emptySet(NEW); while(vV1&& notAdjacentWithSet(NEW,v,G)) { addToSet(NEW,v); removeFromSet(V1,v); } ++color; return(color);

由上述实例，抽象出数据结构的概念： 概括地说， 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。

《数据结构课程》所处的地位：

1.2 基本概念 一、数据与数据结构 二、数据类型 三、抽象数据类型

一、数据与数据结构 数据: 所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。 是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。

数据元素: 是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。 如:整数“5”,字符“N”等。 ----是不可分割的“原子”

数据元素也可以由若干款项构成。 例如： 描述一个学生的数据元素 其中每个款项称为一个“数据项” 它是数据结构中讨论的最小单位 姓 名 学 号 班 号 性别 出生日期 入学成绩 年 月 日 原子项 称之为组合项

数据结构： 有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。 带结构的数据元素的集合 指的是数据元素之间存在的关系

例如，在 2 行 3 列的二维数组中六个元素 {a1, a2, a3, a4, a5, a6} 之间存在两个关系: a1 a2 a3 a4 a5 a6 行的次序关系: row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>} 列的次序关系: col = {<a1,a4>,<a2,a5>,<a3,a6>}

若在 6 个数据元素{a1, a2, a3, a4, a5, a6} 之间存在如下的次序关系: {<ai, ai+1>| i=1, 2, 3, 4, 5} 则构成一维数组的定义。 可见，不同的“关系”构成不同的“结构” 数据结构是相互之间存在着某种逻辑关系的数据元素的集合。

从关系或结构分，数据结构可归结为以下四类: 线性结构 树形结构 图状结构 集合结构

数据结构包括“逻辑结构” 和“物理结构”两个方面(层次): 逻辑结构 是对数据元素之间的逻辑关系的描述，它可以应一个数据元素的集合和定义在此集合上的若干关系来表示; 物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构” 。

数据结构的形式定义描述为: 数据结构是一个二元组 Data_Structures = (D, S) 其中:D 是数据元素的有限集， S 是 D上关系的有限集。

例如:定义 “班集体”为一个数据结构 Class = (D, S) D = { a, b1,…,bn, c1,…cn, d1,…dn } S = { R1, R2 } R1 = { <a, b1>,<a, c1>,<a, d1>} R2 = { <b1, bj>, <c1, cj>, <d1, dj> | j = 2, 3, …, n }

数据的存储结构 —— 逻辑结构在存储器中的映象 “数据元素”的映象 ？ “关系”的映象 ？

数据元素的映象方法： 用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2

关系的映象方法： （表示x, y的方法） 顺序映象 以相对的存储位置表示后继关系 例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C 而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息 x y

链式映象 以附加信息(指针)表示后继关系 需要用一个和 x 在一起的附加信息指示 y 的存储位置 y x

在不同的编程环境中， 存储结构可有不同的描述方法， 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。

例如: 以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型， 定义长整数为: typedef int Long_int[3]

定义“日期”为: typedef struct { int y; // 年号 Year int m; // 月号 Month int d; // 日号 Day } DateType; // 日期类型 定义“学生”为: typedef struct { char id[8]; // 学号 char name[16]; // 姓名 char sex; // 性别‘M/F’:男/女 DateType bdate; // 出生日期 } Student; // 学生类型

二、数据类型 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所 属的数据类型。

例如，C 语言中提供的基本数据类型有: 整型 int 浮点型 float 实型（ C++语言） 双精度型 double 字符型 char 逻辑型 bool （ C++语言）

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 例如：整型 值的范围是：-32768 - 32767 操作是：+，-，*，/，% 数据类型 是一个 值的集合和定义在此集合上的一组操作的总称。

各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。 从“数学抽象”的角度看，可称它为一个“抽象数据类型” 。

三、抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作

例如: “整数”是一个抽象数据类型。 其数学特性和具体的计算机或语言无关。 “抽象”的意义在于强调数据类型的数学特性。

抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。 在构造软件系统的各个相对独立的模块时，定义一组数据和施与这些数据之上的一组操作，并在模块内部给出它们的表示和实现细节，在模块外部使用的只是抽象的数据和抽象的操作。

例如，定义抽象数据类型“复数” ADT Complex { 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{<e1,e2> | e1是复数的实数部分, | e2 是复数的虚数部分 }

基本操作： AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 DestroyComplex( &Z) 操作结果：复数Z被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。

GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 }ADT Complex

# include <iostream.h> # include "complex.h"   void main() { } … …

complex z1,z2,z3,z4,z; float RealPart,ImagPart; InitComplex(z1,8.0,6.0); InitComplex(z2,4.0,3.0); Add(z1,z2,z3); Multiply(z1,z2,z4); if (Division (z4,z3,z)) { GetReal (z, RealPart); GetImag (z, ImagPart); }//if

ADT 有两个重要特征: 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法） 数据抽象 数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节

抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示 其中，D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。

ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

赋值参数 只为操作提供输入值； 引用参数 以&打头，除可提供输入值外，还将返回操作结果。 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。

// -----存储结构的定义 抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数

// -----存储结构的定义 typedef struct { float realpart； float imagpart； }complex； // -----基本操作的函数原型说明 void Assign( complex &Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值

float GetReal( cpmplex 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 = z1.imagpart + z2.imagpart; } { 其它省略 }

1.3 算法和算法的衡量 一、算法 二、算法设计的原则 三、算法效率的衡量方法和准则 四、算法的存储空间需求

一、算法 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性： 1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出

1．有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即： 算法中的每个步骤都能在有限时间内完成； 2．确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；

3．可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之； 4．有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中； 5．有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

本书算法的描述 选择算法描述语言的准则 （1）该语言应该具有描述数据结构和算法的基本功能； （2）该语言应该尽可能地简捷，以便于掌握、理解； （3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。 “类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。

1. 预定义常量及类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 数据元素被约定为EntryType 类型，用户需要根据具体情况，自行定义该数据类型。

2. 算法描述为以下的函数形式： 函数类型 函数名（函数参数表） { 语句序列； } 为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。

3. 在算法描述中可以使用的赋值语句形式有： 简单赋值 变量名 = 表达式； 串联赋值 变量名1 = 变量名2 = ... = 变量名n = 表达式； 成组赋值 （变量名1，...，变量名n）=（表达式1，...， 表达式n）； 结构赋值 结构名1 = 结构名2； 结构名 =（值1，值2，...，值n）； 条件赋值 变量名 = 条件表达式 ? 表达式1：表达式2； 交换赋值 变量名1  变量名2；

4. 在算法描述中可以使用的选择结构语句形式有： 条件语句1 if （表达式） 语句； 条件语句2 if （表达式） 语句； else 语句； 开关语句1 switch （表达式） { case 值1：语句序列1；break； case 值2：语句序列2；break； ... case 值n：语句序列n；break； default：语句序列n+1； }

开关语句2 switch { case 条件1：语句序列1；break； case 条件2：语句序列2；break； ... case 条件n：语句序列n；break； default：语句序列n+1； }

5. 在算法描述中可以使用的循环结构语句形式有： for循环语句 for （表达式1；循环条件表达式；表达式2） 语句； while循环语句 while （循环条件表达式） 语句； do-while循环语句 do { 语句序列； } while （循环条件表达式）； 6. 在描述算法中可以使用的结束语句形式有： 函数结束语句 return 表达式；return; case或循环结束语句 break; 异常结束语句 exit（异常代码）；

7. 在算法描述中可以使用的输入输出语句形式有： 输入语句 scanf([格式串]，变量名1，...,变量名n)； 输出语句 printf( [格式串]，表达式1，...，表达式n); 方括号（[ ]）中的内容是可以省略的部分。 8. 在算法描述中使用的注释格式为： 单行注释 //文字序列 9. 在算法描述中可以使用的扩展函数有： 求最大值 max（表达式1，...，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值。 求最小值 min（表达式1，...，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值。

二、算法设计的原则 设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求

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)的执行时间 算法的执行时间 与 原操作执行次数之和 成正比

从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。

例 一 两 个 矩 阵 相 乘 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)

void select_sort(int& a[], int n) { 例 二 选 择 排 序 for ( i = 0; i< n-1; ++i ) { if ( j != i ) a[j] ←→ a[i] } j = i; // 选择第 i 个最小元素 for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k; 基本操作: 比较(数据元素)操作 时间复杂度: O(n2)

void bubble_sort(int& a[], int n) { for (i=n-1, change=TRUE; i>1 && change; --i) } // bubble_sort 例 三 起 泡 排 序 { change = FALSE; // change 为元素进行交换标志 for (j=0; j<i; ++j) if (a[j] > a[j+1]) { a[j] ←→ a[j+1]; change = TRUE ;} } // 一趟起泡 基本操作: 赋值操作 时间复杂度: O(n2)

算法时间效率的度量分析 图1-7 常见函数的增长率

四、算法的存储空间需求 算法的空间复杂度定义为: S(n) = O(g(n)) 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。

算法的存储量包括: 1．输入数据所占空间 2．程序本身所占空间； 3．辅助变量所占空间。

若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入， 则通常按最坏情况考虑。

本章学习要点 本章主要讲解了两个大的问题，一是数据结构的定义和相关概念，二是算法的定义和算法分析。需要掌握的重点内容包括： 1、数据结构的定义：数据结构是一门研究非数值应用问题中数据的物理结构、逻辑结构和对数据的操作即计算机算法的学科。 2、数据的逻辑结构包括两大类：线性结构和非线性结构，并且非线性结构又分为树形结构和图形结构。通常我们还将集合这种结构增加进来，因此也可以说数据的逻辑结构包括：集合结构、线性结构、树形结构、图形结构四种类型。 3、数据的物理结构主要包括：顺序结构、链式结构、索引结构和散列结构四种。

本章学习要点 4、算法是解决某一类问题的特定方法，一个算法我们可以用计算机语言、自然语言、框图、类语言等多种形式来描述。一段计算机程序可以用来表示一个算法，但是算法并不一定是用计算机程序描述的。 5、任何一个算法都必须满足五个特性，即正确性、确定性、有限性、输入和输出，其中正确性是进行算法分析的前提。一个算法可以在程序中初始化一些变量，所以可以没有输入，但是一定要有输出。 6、当解决一个问题都多种算法时，我们可以通过算法分析进行优化选择。通常算法分析要包括时间复杂度分析和空间复杂度分析两种。时间复杂度并不是具体的算法运行时间，而是算法的运行时间的数量级度量，通常有O(1)、O(n)、O(nlog2n)、O(n2)、O(n3)几种。空间复杂度是算法运行时需要的附加空间的数量级度量，常见的有O(1)、O(log2n)、O(n)几种。

课后作业及习题 1.1简述下列术语 ：数据、数据元素、数据对象、存储结构、数据类型和抽象数据类型。 1.2设有数据结构（D,R）,其中 D={d1,d2,d3,d4},R={r}r={(d1,d2),(d2,d3),(d3,d4)}。 试按图论中图的画法惯例画出其逻辑结构图。 1.3设n为正整数。试确定下列各程序段中前置以记号＠的语句的频度； （1）i=1;k=0;while(i<=n-1){＠ k+=10*i;i++;} （2）i=1;k=0;do{ ＠ k+=10*i;i++; } while(i<=n-1);

（3）i=1;k=0;while(i<=n-1){i++; ＠ k+=10*i;} for(i=1;i<=n;i++){ for(j=i;j<=n;j++) ＠k++;} （6）x=n;y=0;//n是不小于1的常数 While(x>=(y+1)*(y+1)){＠ y++;} （5）for(i=1;i<=n;i++){ for(j=1;j<=i;j++) for(k=1;k<=j;k++) ＠ x+=delta;} （7）x=91;y=100; While(y>0){ ＠ if(x>100){x-=10;y--;} else x++; }

1.4按增长率由小至大的顺序排列下列各函数 2100 ,(3/2)n ,(2/3)n ,(4/3)n ,nn ,n3/ 2,n2/3 , n1/2 ,n! ,n ,㏒2n ,n/ ㏒2n , ㏒22n , ㏒2 (㏒2n), n ㏒2n,n ㏒2n 1.5试写一算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值。