第一章 绪论数据结构（ C语言描述 ）
目录
1。 1 什么 是数据结构
1。 2 算法的 描述
1。 3 算法 分析
1。 4 退出具体问题 数学模型 编写程序 问题最终解决抽象 设计算法 调试
,数据结构,是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
（是介于数学、计算机硬件、计算机软件的一门核心的专业基础学科）
1.1什么是数据结构
1.1.1 数据结构示例学号 姓名 性别 籍贯 电 话 通 讯 地 址
01 张三 男 长沙 8639000 麓山南路 327 号
02 李四 男 北京 23456789 学院路 435 号
03 王五 女 广州 30472589 天河路 478 号
04 赵六 男 上海 4123756 8 南京路 1563 号
05 钱七 女 南京 5013472 南京大学
06 刘八 女 武汉 6154372 6 武汉大学
07 朱九 男 昆明 4089651 云南大学
08 孙十 女 杭州 6154372 西湖路 6 35 号图 1 - 1 学生数据表
1。线性表示例
2。树形结构示例
a
1
a
b c
b
1 a
2
Tt
b
2
c
1
c
2
d
d
1
d
2
d 3
图 1 - 2 树形结构示意图一层二层三层四层
3。图形结构示例
1 2
3
4 5
6
图 1 - 3 图形结构示意图
2,数据元素 （ data element）
数据元素是组成数据的 基本单位 。
数据元素是一个数据整体中相对独立的单位 。 但它还可以分割成若干个具有不同属性的项 （ 字段 ）,故不是组成数据的最小单位,最小单位 是数据项 （ data item） 。
1.1.2基本术语
1,数据 （ data）
数据是客观事物的符号表示，是指能够输入到计算机中，并被计算机识别和处理的符号的集合。
例如：数字、字母、汉字、图形、图像、声音都称为数据。
3,数据对象 （ data object）
性质相同的数据元素组成的集合,数据的一个子集 。
例如,整数数据对象的集合可表示为 N＝ {0,± 1，
± 2……,},字母字符数据对象的集合可表示为
C={‘A’,’B’,… ’Z’}。
4,数据类型 （ data type）
是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称 。
例如,高级语言中用到的整数数据类型,是指由－
32768到 32767中值构成的集合及一组操作 （ 加,减,
乘,除,乘方等 ） 的总称 。
1.1.3 数据结构
1,数据结构 （ data structure）
是指相互之间存在一种或多种特定关系的数据元素所组成的集合 。 具体来说,数据结构包含三个方面的内容,即 数据的逻辑结构,数据的存贮结构 和对数据所施加的 运算 。
D.S = ( D,R)
（ 1） 逻辑结构：是指抽象化地描述数据元素之间的相互关系,独立于计算机,是数据本身所固有的 。
（ 2） 存贮结构：是逻辑结构在计算机存贮器中的映像,
也称为物理结构,必须依赖于计算机 。
（ 3） 运算：是指所施加的一组操作总称 。 运算的设计直接依赖于逻辑结构,但运算的实现必依赖于存贮结构 。
2,从逻辑结构划分数据结构数据结构从逻辑结构划分为：
（ 1） 线性结构元素之间为一对一 （ 线性表 ） 的线性关系,第一个元素无直接前驱,最后一个元素无直接后继,其余元素都有一个直接前驱和直接后继 。
（ 2） 非线性结构元素之间为一对多 (树）或多对多（图）的非线性关系，每个元素有多个直接前驱或多个直接后继。
3,从存贮结构划分数据结构数据结构从存贮结构划分为：
(1)顺序存贮 （ 向量存贮 ）
所有元素存放在一组地址连续的存贮单元中,
逻辑上相邻的元素存放到计算机内存仍然相邻 。
(2) 链式存贮所有元素存放在可以不连续的存贮单元中,但元素之间的关系通过地址 （ 指针 ） 确定,逻辑上相邻的元素存放到计算机内存后不一定是相邻的 。
(3)索引存贮使用该方存放元素的同时,还建立附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是,（ 关键字,地址 ）,其中的关键字是能唯一标识一个结点的那些数据项 。
(4)散列存贮通过构造散列函数,用函数的值来确定元素存放的地址 。
4,数据结构的抽象描述数据结 构可 用二 元组 (D,R) 的形 式来 描述 。 其中,
D={a1,a2,…,an}为元素集合,R={r1,r2,…,rm}为关系的集合 。
例 1,设有一个线性表 (a1,a2,a3,a4,a5)，它的抽象描述可表示为 (D,R),其中 D={a1,a2,a3,a4,a5},
R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，
则它的逻辑结构用图描述：
a1 a2 a3 a4 a5
例 2,设一个数据结构的抽象描述为 （ D,R),其中
D={a,b,c,d,e,f,g,h},
R={<a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<c,g>,<d,h>},
则它的逻辑结构用图描述：
a
b
c
d
e f g
h
例 3,设 一 个 数 据结 构 的 抽 象 描述 为 (D,R),其中
D={1,2,3,4},而 R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)},则它的逻辑结构用图描述,1 2
3 4
图形结构抽象描述示意图
1.2 算法的描述
1.2.1 基本概念
1,算法 （ algorithm）
通俗地讲,算法就是一种解题的方法 。 更严格地说,算法是由若干条指令组成的有穷序列,它必须满足下述条件 （ 也称为算法的五大特性 ）,
（ 1） 输入：具有 0个或多个输入；
（ 2） 输出：至少产生一个输出；
（ 3有穷性：算法必须在有限步骤之内完成,而且每条指令的执行时间必须是有限的；
（ 4)确定性：每条指令的含义都必须明确,无二义性 。
（ 5)可行性：原则上能精确运行 。
2,算法和程序的关系算法的含义与程序十分相似,但二者是有区别的 。 一个程序不一定满足有穷性 （ 死循环 ）,另外,
程序中的指令必须是机器可执行的,而算法中的指令则无此限制 。 一个算法若用计算机语言来书写,
则它就可以是一个程序 。
算法 +数据结构 =程序
1.2.2算法描述
1,用流程图描述算法一个算法可以用流程图的方式来描述,输入输出,判断,处理分别用不同的框图表示,用箭头表示流程的流向 。 这是一种描述算法的较好方法,目前在一些高级语言程序设计中仍然采用 。
2,用自然语言描述算法用我们日常生活中的自然语言（可以是中文形式，
也可以是英形式）也可以描述算法。
3,用其它方式描述算法我们还可以用数学语言或约定的符号语言来描述算法 。
4,用 C语言描述算法在本教材中,我们将采用 C或类 C来描述算法 。 描述算法遵循如下规则：
（ 1） 所有算法的描述都用 C中的函数形式函数类型 函数名 （ 形参及类型说明 ）
{ 内部数据说明函数语句部分
}
（ 2） 函数中的形式参数有两种传值方式单向值传递,双向地址传递 。
（ 3） 输入函数
C中的输入函数调用为 scanf( ),getchar( ),gets( )
（ 4） 输出函数
C中的输出函数调用为 printf( ),putchar( ),puts( )
（ 5） 赋值语句
简单赋值
<变量名 >=<表达式 > ；
<变量名 > ++；
<变量名 > - -；
串联赋值
<变量 1>= <变量 2>= <变量 3>=… = <变量 k>= <表达式 >；
成组赋值
（ <变量 1>,<变量 2>,<变量 3>,…,<变量 k>） =
（ <表达式 1>,<表达式 2>,<表达式 3>,…,<表达式 k>)；
条件赋值
<变量名 >=<条件表达式 >？ <表达式 1>,<表达式 2>；
（ 6） 条件选择语句
if(<表达式 >) 语句；
if(<表达式 >) 语句 1；
else 语句 2；
switch(<表达式 >)
{ case 判断值 1：语句组 1； break；
case 判断值 2：语句组 2； break；
……
case 判断值 n：语句组 n； break；
[default,语句组； break； ]
}
（ 7） 循环语句
for(<表达式 1>； <表达式 2>； <表达式 3>)
{ 循环体语句 }
while(<条件表达式 >)
{ 循环体语句 }
do {循环体语句
} while(<条件表达式 >)；
（ 8） 其它一些语句
return(<表达式 >)；或 return；
break；
continue；
exit；
（ 9）注释语句
/* 注释字符串 */
（ 10）一些基本函数
max( )
min( )
abs( )
eof( )
eoln( )
(11)预定义常量和类型
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define OK 1
#define ERROR 0
1.3 算法分析
1.3.1 算法设计的要求
（ 1）正确性
（ 2）可读性
（ 3）健壮性
（ 4）高效率与低存储量的要求
1.3.2 决定算法执行时间的因素
算法采用何种策略；
程序运行时输入的数据总量；
编译所需时间；
产生机器代码的质量；
执行每条指令所需时间；
指令重复执行次数，等；
1.3.3 衡量算法优劣一,时间复杂度 T(n)
1,时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道 。 但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了 。 并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多 。 一个算法中的语句执行次数称为语句频度或时间频度 。 记为 f(n),
n为问题的规模 。
例：求下列算法段的语句频度
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，
因些,时间频度 f(n)=1+2+3+…+n= n(n+1)/2
2,时间复杂度
T(n)表示成数量级的形式为：
T(n)=Ｏ (f(n))
其中：大写字母Ｏ为英文 Order（ 即数量级 ） （ f(n)和
T(n)是同数量级的函数 ）
注：要计算 T(n)一般只需要分析清楚嵌套在最深层循环体中简单操作的执行次数即可 。
例如,若 f(n)=n(n+1)/2,故它的时间复杂度为
T(n)=Ｏ (n2),即Ｔ (n)与 n2 数量级相同 。
例,分析下列算法段的时间频度及时间复杂度
for （ i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
分析算法规律可知时间频度
T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+… +n)
=
=
= +
= [ + ]
故时间复杂度为Ｏ (n3)。
nk k1 )...321(
nk kk1 2 )1(
nk k122?
n
k
k
12
21 6 )12)(1( nnn 2)1(?nn
注：在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为 O(1),另外,在时间频度不同,
时 间 复 杂 度 有 可 能 相 同,如 T(n)=n2+3n+4 与
T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,
都为 O(n2)。
按数量级递增排列,常见的时间 复杂度有：
常数阶 O(1),对数阶 O(log2n),线性阶 O(n),
线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),...，
k次方阶 O(nk),指数阶 O(2n)。 随着问题规模 n的不断增大,
上述时间复杂度不断增大,算法的执行效率越低 。
二,空间复杂度 S(n)
1,空间频度一个算法在执行时所占有的内存开销,称为空间频度,但我们一般是讨论算法占用的辅助存储空间 。 讨论方法与时间频度类似,不再赘述 。
２,空间复杂度与时间复杂度类似,空间复杂度是指算法在计算机内执行时所占用的内存开销规模 。 但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模 。
讨论方法与时间复杂度类似,不再赘述 。
目录
1。 1 什么 是数据结构
1。 2 算法的 描述
1。 3 算法 分析
1。 4 退出具体问题 数学模型 编写程序 问题最终解决抽象 设计算法 调试
,数据结构,是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
（是介于数学、计算机硬件、计算机软件的一门核心的专业基础学科）
1.1什么是数据结构
1.1.1 数据结构示例学号 姓名 性别 籍贯 电 话 通 讯 地 址
01 张三 男 长沙 8639000 麓山南路 327 号
02 李四 男 北京 23456789 学院路 435 号
03 王五 女 广州 30472589 天河路 478 号
04 赵六 男 上海 4123756 8 南京路 1563 号
05 钱七 女 南京 5013472 南京大学
06 刘八 女 武汉 6154372 6 武汉大学
07 朱九 男 昆明 4089651 云南大学
08 孙十 女 杭州 6154372 西湖路 6 35 号图 1 - 1 学生数据表
1。线性表示例
2。树形结构示例
a
1
a
b c
b
1 a
2
Tt
b
2
c
1
c
2
d
d
1
d
2
d 3
图 1 - 2 树形结构示意图一层二层三层四层
3。图形结构示例
1 2
3
4 5
6
图 1 - 3 图形结构示意图
2,数据元素 （ data element）
数据元素是组成数据的 基本单位 。
数据元素是一个数据整体中相对独立的单位 。 但它还可以分割成若干个具有不同属性的项 （ 字段 ）,故不是组成数据的最小单位,最小单位 是数据项 （ data item） 。
1.1.2基本术语
1,数据 （ data）
数据是客观事物的符号表示，是指能够输入到计算机中，并被计算机识别和处理的符号的集合。
例如：数字、字母、汉字、图形、图像、声音都称为数据。
3,数据对象 （ data object）
性质相同的数据元素组成的集合,数据的一个子集 。
例如,整数数据对象的集合可表示为 N＝ {0,± 1，
± 2……,},字母字符数据对象的集合可表示为
C={‘A’,’B’,… ’Z’}。
4,数据类型 （ data type）
是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称 。
例如,高级语言中用到的整数数据类型,是指由－
32768到 32767中值构成的集合及一组操作 （ 加,减,
乘,除,乘方等 ） 的总称 。
1.1.3 数据结构
1,数据结构 （ data structure）
是指相互之间存在一种或多种特定关系的数据元素所组成的集合 。 具体来说,数据结构包含三个方面的内容,即 数据的逻辑结构,数据的存贮结构 和对数据所施加的 运算 。
D.S = ( D,R)
（ 1） 逻辑结构：是指抽象化地描述数据元素之间的相互关系,独立于计算机,是数据本身所固有的 。
（ 2） 存贮结构：是逻辑结构在计算机存贮器中的映像,
也称为物理结构,必须依赖于计算机 。
（ 3） 运算：是指所施加的一组操作总称 。 运算的设计直接依赖于逻辑结构,但运算的实现必依赖于存贮结构 。
2,从逻辑结构划分数据结构数据结构从逻辑结构划分为：
（ 1） 线性结构元素之间为一对一 （ 线性表 ） 的线性关系,第一个元素无直接前驱,最后一个元素无直接后继,其余元素都有一个直接前驱和直接后继 。
（ 2） 非线性结构元素之间为一对多 (树）或多对多（图）的非线性关系，每个元素有多个直接前驱或多个直接后继。
3,从存贮结构划分数据结构数据结构从存贮结构划分为：
(1)顺序存贮 （ 向量存贮 ）
所有元素存放在一组地址连续的存贮单元中,
逻辑上相邻的元素存放到计算机内存仍然相邻 。
(2) 链式存贮所有元素存放在可以不连续的存贮单元中,但元素之间的关系通过地址 （ 指针 ） 确定,逻辑上相邻的元素存放到计算机内存后不一定是相邻的 。
(3)索引存贮使用该方存放元素的同时,还建立附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是,（ 关键字,地址 ）,其中的关键字是能唯一标识一个结点的那些数据项 。
(4)散列存贮通过构造散列函数,用函数的值来确定元素存放的地址 。
4,数据结构的抽象描述数据结 构可 用二 元组 (D,R) 的形 式来 描述 。 其中,
D={a1,a2,…,an}为元素集合,R={r1,r2,…,rm}为关系的集合 。
例 1,设有一个线性表 (a1,a2,a3,a4,a5)，它的抽象描述可表示为 (D,R),其中 D={a1,a2,a3,a4,a5},
R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，
则它的逻辑结构用图描述：
a1 a2 a3 a4 a5
例 2,设一个数据结构的抽象描述为 （ D,R),其中
D={a,b,c,d,e,f,g,h},
R={<a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<c,g>,<d,h>},
则它的逻辑结构用图描述：
a
b
c
d
e f g
h
例 3,设 一 个 数 据结 构 的 抽 象 描述 为 (D,R),其中
D={1,2,3,4},而 R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)},则它的逻辑结构用图描述,1 2
3 4
图形结构抽象描述示意图
1.2 算法的描述
1.2.1 基本概念
1,算法 （ algorithm）
通俗地讲,算法就是一种解题的方法 。 更严格地说,算法是由若干条指令组成的有穷序列,它必须满足下述条件 （ 也称为算法的五大特性 ）,
（ 1） 输入：具有 0个或多个输入；
（ 2） 输出：至少产生一个输出；
（ 3有穷性：算法必须在有限步骤之内完成,而且每条指令的执行时间必须是有限的；
（ 4)确定性：每条指令的含义都必须明确,无二义性 。
（ 5)可行性：原则上能精确运行 。
2,算法和程序的关系算法的含义与程序十分相似,但二者是有区别的 。 一个程序不一定满足有穷性 （ 死循环 ）,另外,
程序中的指令必须是机器可执行的,而算法中的指令则无此限制 。 一个算法若用计算机语言来书写,
则它就可以是一个程序 。
算法 +数据结构 =程序
1.2.2算法描述
1,用流程图描述算法一个算法可以用流程图的方式来描述,输入输出,判断,处理分别用不同的框图表示,用箭头表示流程的流向 。 这是一种描述算法的较好方法,目前在一些高级语言程序设计中仍然采用 。
2,用自然语言描述算法用我们日常生活中的自然语言（可以是中文形式，
也可以是英形式）也可以描述算法。
3,用其它方式描述算法我们还可以用数学语言或约定的符号语言来描述算法 。
4,用 C语言描述算法在本教材中,我们将采用 C或类 C来描述算法 。 描述算法遵循如下规则：
（ 1） 所有算法的描述都用 C中的函数形式函数类型 函数名 （ 形参及类型说明 ）
{ 内部数据说明函数语句部分
}
（ 2） 函数中的形式参数有两种传值方式单向值传递,双向地址传递 。
（ 3） 输入函数
C中的输入函数调用为 scanf( ),getchar( ),gets( )
（ 4） 输出函数
C中的输出函数调用为 printf( ),putchar( ),puts( )
（ 5） 赋值语句
简单赋值
<变量名 >=<表达式 > ；
<变量名 > ++；
<变量名 > - -；
串联赋值
<变量 1>= <变量 2>= <变量 3>=… = <变量 k>= <表达式 >；
成组赋值
（ <变量 1>,<变量 2>,<变量 3>,…,<变量 k>） =
（ <表达式 1>,<表达式 2>,<表达式 3>,…,<表达式 k>)；
条件赋值
<变量名 >=<条件表达式 >？ <表达式 1>,<表达式 2>；
（ 6） 条件选择语句
if(<表达式 >) 语句；
if(<表达式 >) 语句 1；
else 语句 2；
switch(<表达式 >)
{ case 判断值 1：语句组 1； break；
case 判断值 2：语句组 2； break；
……
case 判断值 n：语句组 n； break；
[default,语句组； break； ]
}
（ 7） 循环语句
for(<表达式 1>； <表达式 2>； <表达式 3>)
{ 循环体语句 }
while(<条件表达式 >)
{ 循环体语句 }
do {循环体语句
} while(<条件表达式 >)；
（ 8） 其它一些语句
return(<表达式 >)；或 return；
break；
continue；
exit；
（ 9）注释语句
/* 注释字符串 */
（ 10）一些基本函数
max( )
min( )
abs( )
eof( )
eoln( )
(11)预定义常量和类型
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define OK 1
#define ERROR 0
1.3 算法分析
1.3.1 算法设计的要求
（ 1）正确性
（ 2）可读性
（ 3）健壮性
（ 4）高效率与低存储量的要求
1.3.2 决定算法执行时间的因素
算法采用何种策略；
程序运行时输入的数据总量；
编译所需时间；
产生机器代码的质量；
执行每条指令所需时间；
指令重复执行次数，等；
1.3.3 衡量算法优劣一,时间复杂度 T(n)
1,时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道 。 但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了 。 并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多 。 一个算法中的语句执行次数称为语句频度或时间频度 。 记为 f(n),
n为问题的规模 。
例：求下列算法段的语句频度
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，
因些,时间频度 f(n)=1+2+3+…+n= n(n+1)/2
2,时间复杂度
T(n)表示成数量级的形式为：
T(n)=Ｏ (f(n))
其中：大写字母Ｏ为英文 Order（ 即数量级 ） （ f(n)和
T(n)是同数量级的函数 ）
注：要计算 T(n)一般只需要分析清楚嵌套在最深层循环体中简单操作的执行次数即可 。
例如,若 f(n)=n(n+1)/2,故它的时间复杂度为
T(n)=Ｏ (n2),即Ｔ (n)与 n2 数量级相同 。
例,分析下列算法段的时间频度及时间复杂度
for （ i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
分析算法规律可知时间频度
T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+… +n)
=
=
= +
= [ + ]
故时间复杂度为Ｏ (n3)。
nk k1 )...321(
nk kk1 2 )1(
nk k122?
n
k
k
12
21 6 )12)(1( nnn 2)1(?nn
注：在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为 O(1),另外,在时间频度不同,
时 间 复 杂 度 有 可 能 相 同,如 T(n)=n2+3n+4 与
T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,
都为 O(n2)。
按数量级递增排列,常见的时间 复杂度有：
常数阶 O(1),对数阶 O(log2n),线性阶 O(n),
线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),...，
k次方阶 O(nk),指数阶 O(2n)。 随着问题规模 n的不断增大,
上述时间复杂度不断增大,算法的执行效率越低 。
二,空间复杂度 S(n)
1,空间频度一个算法在执行时所占有的内存开销,称为空间频度,但我们一般是讨论算法占用的辅助存储空间 。 讨论方法与时间频度类似,不再赘述 。
２,空间复杂度与时间复杂度类似,空间复杂度是指算法在计算机内执行时所占用的内存开销规模 。 但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模 。
讨论方法与时间复杂度类似,不再赘述 。
