第一章 概论

引言

数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作

计算机解决具体问题的步骤如下：

• 从具体问题中抽象出一个适当的数学模型
• 设计一个求解该数学模型的算法
• 用某种计算机语言编写实现该算法的程序，调试和运行程序直到问题得到解决。

注：

• 原始数据：实际问题中的数据
• 逻辑结构：原始数据之间按照逻辑关系组织起来，人为因素大
• 存储结构：原始数据实实在在在计算机中是如何存储的

此处可以以一个人处理有经验事情拿来类比，首先再次处理已经处理过的事情我们会先思考上回我们是这么做的（模型），这回我该怎么做（算法），付诸实践（编写程序直到解决）；原始数据可以理解为该问题本身如：我要去办一个XXX证书，我需要XXX做；逻辑结构就是我的这些申请材料应该给XXX，存储结构就是我的这些申请材料实际给了XXX（理想与现实的差别）

19761年瑞士尼克劳斯·维尔特（Wirth）提出：算法+数据结构=程序

基本概念和术语

数据、数据元素和数据项

• 数据：所有被计算机存储、处理的对象
• 数据元素：数据的基本单位，数据元素通常简称为元素
• 数据项：数据元素的组成部分，是不可分割的最小标识单位；在数据库中又称为字段或域

下面以二维表为例，具体解释：

• 一行即是一个数据元素；即827这一行数据代表一个数据元素
• 一行中的每一列都是一个数据元素；即单827一个单元格代表一个数据项
• 整张表代表数据；

数据可以由若干个数据元素组成，而数据元素又可由若干个数据项组成

数据的逻辑结构

• 数据的逻辑结构是指数据之间的逻辑关系（数据元素之间的关联方式或“邻接方式”）
• 四类基本结构如下图所示：

• 集合：组织形式松散，两个结点之间没有邻接关系
• 线性结构：结点按逻辑关系依次排列形成“链”，结点之间一个一个依次邻接
• 树形结构：分支、层次
• 图：任何两个结点都可以邻接，最复杂

数据的存储结构（物理结构）

• 数据的存储结构定义：数据的逻辑结构在计算机中的实现
• 存储结构包括：
  • 存储数据元素（存）
  • 数据元素之间的关联方式（怎么存）
• 存储方式举例：
  • 顺序存储方式：所有结点存储在一个连续的存储区里，利用结点在存储器的相对位置来表达数据元素之间的逻辑关系
  • 链式存储方式：除数据元素外还有一个指针，每个指针指向下一个与本结点有逻辑关系的结点
    注： 顺序和链式最常用，除了上述两种，还有索引存储方式和散列存储方式
• 存储结构的描述
  • 机器级：讨论存储结构在计算机存储器里的表现形式，直接以内存地址来描述存储结构
  • 语言级：用程序设计中的类型说明，变量说明等手段来描述存储结构；如数组、结构体和指针等

语言级可以经编译器转换为机器级

运算

运算：在某种逻辑结构上施加的操作，即对逻辑的加工

注：基本运算包括：建立、查找、读取、插入和删除等

算法及描述

C语言基本语法：

• 函数描述形式

函数类型 函数名（函数参数表）
//算法说明
{
语句序列
}
1
2
3
4
5

• 输入、输出语句

//输入
scanf(格式串,变量1,...,变量n);
//输出
printf(格式串,变量1,...,变量n);
1
2
3
4

• 赋值语句

变量名=表达式
1

• 选择语句

//if
if(表达式) 语句;
//if ...else...
if(表达式) 语句;
else 语句;
//switch
switch
{
case 条件1：语句序列;break;
......
default: 语句序列;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 循环语句

//for
for(赋初值表达式序列;条件;修改表达式序列)语句;
//while
while(条件) 语句;
//do...while
do
{
语句;
}while(条件);
1
2
3
4
5
6
7
8
9

• 结束语句

//函数结束
return 表达式;
//case结束
break;
//异常结束语句
exit(异常代码);
1
2
3
4
5
6

• 出错语句

error("错误描述")
1

• 注释

单行注释：//注释内容
多行注释：/* 注释内容 */
1
2

算法分析

评价算法好坏的因素：

• 正确性：能正确实现预定的功能，满足具体问题的需要
• 易读性：易于阅读、理解和交流，便于调试、修改和扩充
• 健壮性：即使输入非法数据，算法也能适当的做出反应或处理，不会产生预料不到的结果
• 时空性：该算法的时间性能和空间性能，前者是算法包含的计算量，后者是算法所需要的存储量

时间复杂度

• 时间复杂度常见阶数：常数阶O（1）——与输入规模无关；对数阶O（log₂ n）、线性阶O（n）、多项式阶O（n^C）、指数阶O（Cⁿ）;其中C为大于1的正整数
• 具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的
• 最坏时间复杂度：对于相同输入数据量的不同输入数据，算法时间用量的最大值
• 平均时间复杂度：对所有相同输入数据量的各种不同输入数据，算法时间用量的平均值
• 时间复杂度的计算看下图（由C知道支持）：

空间复杂度

• 空间复杂度：由程序代码所占用的空间、输入数据所占用的空间、辅助变量所占用的空间组成，一般只需分析辅助变量占用的空间即可

• 算法f1、f2均是实现逆置的算法
• 算法f1仅需2个辅助变量i，temp；与问题规模无关，空间复杂度为O（1）
• 算法f2所需辅助变量为1个i和n为100的数组，与问题规模相关），空间复杂度为O（n）

牛刀小试

• 在一般情况下，一个算法的时间复杂度是______的函数
• 下列算法的时间复杂度T（n）=______

for(i=1;j<=n;i++)
{
k++;
for(j=1;j<=n;j++)
m+=k;
}
1
2
3
4
5
6

• 与数据元素本身的形式、内容、相对位置、个数无关的是数据的_____