退出开设本课程的背景
,数据结构,是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。
它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。
本课程讲述的主要内容本课程将分别讲述数据结构的基本概念、线性表、
栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。
学习本课程的基本方法
l上课认真听讲；
l 仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；
l 独立完成每个章节后面的练习题。
第 1章 数据结构基础概论本章主要介绍以下内容
l 数据结构研究的主要内容
l 数据结构中涉及的基本概念
l 算法的概念、描述方法以及评价标准
1.1 数据结构研究的主要内容
1.2 基本概念和术语
1.3 算法
1.1 数据结构研究的主要内容当今计算机应用的特点：
l 所处理的数据量大且具有一定的关系；
l 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。
应用举例 1—— 学籍档案管理假设一个学籍档案管理系统应包含如下表 1-1所示的学生信息。
学生基本情况学 号 姓 名 性 别 出生年月
......
9 9 0 7 0 1 0 1 李 军 男 80,12
......
9 9 0 7 0 1 0 2 王颜霞 女 81,2
.......
9 9 0 7 0 1 0 3 孙 涛 男 80,9
......
9 9 0 7 0 1 0 4 单晓宏 男 81,3
......
......,.....,.....,.....,.....
表 1-1
特点：
l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；
l 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；
l 对它的操作通常是插入某个学生的信息，
删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。
应用举例 2—— 输出 n个对象的全排列输出 n个对象的全排列可以使用下图 1-1所示的形式描述。
312 132 123
12
321 231 213
21
1
图 1-1 3个对象的全排列过程特点：
l 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；
l 对它的操作有：建立树形结构，输出最低层结点内容等等。
应用举例 3—— 制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表 1-2所示：
计算机专业学生的必修课程课程编号 课程名称 需要的先导课程编号
C1 程序设计基础 无
C2 离散数学 C1
C3 数据结构 C1,C2
C4 汇编语言 C1
C5 算法分析与设计 C3,C4
C6 计算机组成原理 C 1 1
C7 编译原理 C5,C3
C8 操作系统 C3,C6
C9 高等数学 无
C 10 线性代数 C9
C 1 1 普通物理 C9
C 12 数值分析 C9,C 10,C1
表 1-2
课程先后关系的图形描形式：
c1
c9
c4
c2
c12
c10
c11
c5
c3
c6
c7
c8
图 1-2 计算机专业必修课程开设先后关系特点
l 课程之间的先后关系用图结构描述；
l 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。
结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。
要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是,数据结构,这门课程研究的主要内容。
1.2 基本概念和术语数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。
数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。
数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。
数据结构简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、
树形结构和图形结构。
逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。
存储结构（物理结构）
是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。
常见的存储结构顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；
链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。
1.3 算法
1.3.1 算法的概念算法是解决某个特定问题的一种方法或一个过程。
计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；
而在非数值性操作中主要进行的是检索、排序、插入、
删除等等。
设计算法的基本过程
l 通过对问题进行详细地分析，抽象出相应的数学模型；
l 确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；
l 选用某种语言将算法转换成程序；
l 调试并运行这些程序。
算法应该具有下列五个特性
（ 1）有穷性：一个算法必须在执行有穷步之后结束。
（ 2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。
（ 3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。
（ 4）输入：一个算法应该有零个或多个输入。
（ 5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。
举例问题：按从小到大的顺序重新排列 x,y,z三个数值的内容。
算法：
（ 1）输入 x,y,z三个数值；
（ 2）从三个数值中挑选出最小者并换到 x中；
（ 3）从 y,z中挑选出较小者并换到 y中；
（ 4）输出排序后的结果。
1.3.2 算法的描述选择算法描述语言的准则
（ 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-1】 用类 C描述将三个数值排序的算法。
viod Three_Sort( int *x,int *y,int *z)
{//将 x,y,z三个指针所指示的内容按从小到大的顺序重新排列
if (*y<*x&&*y<*z) *x?*y;
//挑选出最小的数值并换到 x指针所指的存储单元中
else if (*z<*x&&*z<*y) *x?*z;
if (*z<*y) *y?*z;
//在 y和 z所指示的存储单元中挑选出较小者换到 y中
}
1.3.3 算法的评价算法的评价标准
(1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。
(2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。
(3) 健壮性：算法中拥有对输入数据、打开文件、
读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。
(4) 时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。
算法的时间效率算法的时间效率主要由两个因素决定：
l 所需处理问题的数据量大小，数据量大，
所花费的时间就多；
l 在解决问题的过程中，基本操作的执行次数。
时间特性的分析如果我们将一个算法所花费的时间设计成一个以数据量 n为自变量的函数 T(n)，这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数据量 n增长的同时，函数 T(n)的增长速度比较缓慢。
空间效率的分析一个算法的空间效率是指在算法的执行过程中，
所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。
,数据结构,是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。
它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。
本课程讲述的主要内容本课程将分别讲述数据结构的基本概念、线性表、
栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。
学习本课程的基本方法
l上课认真听讲；
l 仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；
l 独立完成每个章节后面的练习题。
第 1章 数据结构基础概论本章主要介绍以下内容
l 数据结构研究的主要内容
l 数据结构中涉及的基本概念
l 算法的概念、描述方法以及评价标准
1.1 数据结构研究的主要内容
1.2 基本概念和术语
1.3 算法
1.1 数据结构研究的主要内容当今计算机应用的特点：
l 所处理的数据量大且具有一定的关系；
l 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。
应用举例 1—— 学籍档案管理假设一个学籍档案管理系统应包含如下表 1-1所示的学生信息。
学生基本情况学 号 姓 名 性 别 出生年月
......
9 9 0 7 0 1 0 1 李 军 男 80,12
......
9 9 0 7 0 1 0 2 王颜霞 女 81,2
.......
9 9 0 7 0 1 0 3 孙 涛 男 80,9
......
9 9 0 7 0 1 0 4 单晓宏 男 81,3
......
......,.....,.....,.....,.....
表 1-1
特点：
l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；
l 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；
l 对它的操作通常是插入某个学生的信息，
删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。
应用举例 2—— 输出 n个对象的全排列输出 n个对象的全排列可以使用下图 1-1所示的形式描述。
312 132 123
12
321 231 213
21
1
图 1-1 3个对象的全排列过程特点：
l 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；
l 对它的操作有：建立树形结构，输出最低层结点内容等等。
应用举例 3—— 制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表 1-2所示：
计算机专业学生的必修课程课程编号 课程名称 需要的先导课程编号
C1 程序设计基础 无
C2 离散数学 C1
C3 数据结构 C1,C2
C4 汇编语言 C1
C5 算法分析与设计 C3,C4
C6 计算机组成原理 C 1 1
C7 编译原理 C5,C3
C8 操作系统 C3,C6
C9 高等数学 无
C 10 线性代数 C9
C 1 1 普通物理 C9
C 12 数值分析 C9,C 10,C1
表 1-2
课程先后关系的图形描形式：
c1
c9
c4
c2
c12
c10
c11
c5
c3
c6
c7
c8
图 1-2 计算机专业必修课程开设先后关系特点
l 课程之间的先后关系用图结构描述；
l 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。
结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。
要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是,数据结构,这门课程研究的主要内容。
1.2 基本概念和术语数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。
数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。
数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。
数据结构简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、
树形结构和图形结构。
逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。
存储结构（物理结构）
是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。
常见的存储结构顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；
链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。
1.3 算法
1.3.1 算法的概念算法是解决某个特定问题的一种方法或一个过程。
计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；
而在非数值性操作中主要进行的是检索、排序、插入、
删除等等。
设计算法的基本过程
l 通过对问题进行详细地分析，抽象出相应的数学模型；
l 确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；
l 选用某种语言将算法转换成程序；
l 调试并运行这些程序。
算法应该具有下列五个特性
（ 1）有穷性：一个算法必须在执行有穷步之后结束。
（ 2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。
（ 3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。
（ 4）输入：一个算法应该有零个或多个输入。
（ 5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。
举例问题：按从小到大的顺序重新排列 x,y,z三个数值的内容。
算法：
（ 1）输入 x,y,z三个数值；
（ 2）从三个数值中挑选出最小者并换到 x中；
（ 3）从 y,z中挑选出较小者并换到 y中；
（ 4）输出排序后的结果。
1.3.2 算法的描述选择算法描述语言的准则
（ 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-1】 用类 C描述将三个数值排序的算法。
viod Three_Sort( int *x,int *y,int *z)
{//将 x,y,z三个指针所指示的内容按从小到大的顺序重新排列
if (*y<*x&&*y<*z) *x?*y;
//挑选出最小的数值并换到 x指针所指的存储单元中
else if (*z<*x&&*z<*y) *x?*z;
if (*z<*y) *y?*z;
//在 y和 z所指示的存储单元中挑选出较小者换到 y中
}
1.3.3 算法的评价算法的评价标准
(1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。
(2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。
(3) 健壮性：算法中拥有对输入数据、打开文件、
读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。
(4) 时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。
算法的时间效率算法的时间效率主要由两个因素决定：
l 所需处理问题的数据量大小，数据量大，
所花费的时间就多；
l 在解决问题的过程中，基本操作的执行次数。
时间特性的分析如果我们将一个算法所花费的时间设计成一个以数据量 n为自变量的函数 T(n)，这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数据量 n增长的同时，函数 T(n)的增长速度比较缓慢。
空间效率的分析一个算法的空间效率是指在算法的执行过程中，
所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。
