数据结构进阶 - 第1章 绪论
408考研大纲 绪论
(一) 数据结构的基本概念
(二) 算法的基本概念
本章内容
1.1 基本概念
- 数据，数据对象，数据元素，数据项
- 数据类型（原子、构造、抽象）
- 数据结构
1.2 数据结构三要素：逻辑结构、物理结构与运算集合
1.3 算法及其评价
- 算法的定义、特性、设计要求
- 算法评价——时空复杂度
1.1 基本概念
基本定义
数据：能输入计算机且被处理的各种符号的集合。
数据元素：组成数据的基本单位，是数据集合的个体。本课程讨论的最小单位。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据结构：带有某种结构关系的、性质相同的数据元素的集合，包括逻辑关系、物理存储和操作。
数据类型
原子类型：值不可再分的数据类型。如
int,char,double等。结构类型：值可以再分解为若干成分的数据类型。如
struct、union。抽象数据类型 ADT：
- 数组是什么类型？构造
- 枚举是什么类型？原子
- 指针是什么类型？原子
抽象数据类型（Abstract Data Type）
抽象数据类型定义了一个数据对象、数据对象中各元素间的结构关系和一组操作。可用一个三元组表示：(数据对象、关系、基本操作)
抽象是一种思维方式，抽取问题的本质特征，隐藏了复杂的细节，让使用者只关注应用而不关注实现细节。
经典案例：哥尼斯堡七桥问题
欧拉回路条件：
- 图形必须是连通的。
- "奇点"个数是0或2。
1.2 数据结构三要素
逻辑结构
数据元素间的逻辑关系，分为：
- 线性结构
- 非线性结构（集合、树和图结构）
物理结构
数据元素及其关系在计算机上的映像。
存储方式分类：
- 顺序存储：存储地址连续
- 链式存储：存储地址不一定连续
- 索引存储：需要另外建立索引表
- 散列存储：哈希存储
运算（操作）
施加在数据对象上的一组运算。基于逻辑结构定义，基于存储结构实现。
示例ADT操作：
ADT Records of student
select, insert, delete, update
1.3 算法特性与性能分析
算法基本概念
算法定义：解决特定问题的一系列操作。
算法特性：输入(≥0)、输出(≥1)、确定性、可行性和有限性。
算法设计要求：正确、可读性、健壮性(鲁棒性)、高效低存储。
算法描述：自然语言、伪代码、流程图、高级语言等。
时间复杂度
定义： 时间复杂度 T(n) = O(f(n))：算法的时间耗费度量，与输入数据的规模有关。表示当n逐渐增大时，算法运行的时间耗费增长率与f(n)增长率相同。
时间复杂度分析步骤：
- 找算法中的基本语句（执行频率最高）
- 计算其执行次数，整理成问题规模n的函数f(n)
- 保留最高次幂，作为（渐进）时间复杂度
复杂度等级排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
时间复杂度分析实例
实例1：简单算法
// -1,1,-1,1,-1,1,...,(-1)^n
if(n%2==0) sum=0;
else sum=-1;
时间复杂度： O(1)
实例2：循环算法
int i=0,sum=0;
while(sum<n) {
i++;
sum+=i;
}
return sum;
分析：
- 基本语句：while
- 执行次数：设while循环语句执行次数为m，i从1开始递增，最后取值为m
- sum=1+2+…+m=m(m-1)/2，即m(m-1)/2 < n
- 时间复杂度： O(√n)
实例3：归并排序
void mergesort(int a[],int i,int j) {
int m;
if (i!=j) {
m=(i+j)/2;
mergesort(a,i,m);
mergesort(a,m+1,j);
merge(a,i,j,m); //O(n)
}
}
递归方程分析：
T(n)=2T(n/2)+n
= 2[2T(n/2²)+n/2]+n
= 2²T(n/2²)+2n
= 2³T(n/2³)+3n
...
= 2ᵏT(n/2ᵏ)+kn
= nO(1)+nlog₂n=n+nlog₂n
= O(nlog₂n)
假设n=2ᵏ，则k=log₂n
递归算法时间复杂度分析
方法1：替换法（迭代替换）
方法2：主方法
利用主定理。设a≥1，b>1为常数，T(n)=aT(n/b)+f(n)
主定理应用实例：
- T(n)=4T(n/2)+n 当n>1
- T(n)=2T(n/2)+n² 当n>1
实例：查找算法
int Find(int a[],int n,int x) {
int i=0;
while (i<n) {
if (a[i]==x) break;
i++;
}
if (i<n) return i;
else return -1;
}
时间复杂度： T(n)=O(n)（最坏情况）
空间复杂度
定义： 空间复杂度S(n)=O(f(n))：算法运行时所占用的存储量，包括形参和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间。
S(n)=O(1)的含义： 常量空间复杂度，表示算法执行时需要的辅助空间与问题规模无关，也称为算法原地工作。
空间复杂度分析实例
实例1：斐波那契数列（非优化版）
long long Fib(int n) {
long long *F=(long long*)malloc(n*(sizeof(long long)+1));
F[0]=F[1]=1;
for(int i=2;i<=n;i++)
F[i]=F[i-1]+F[i-2];
return F[n];
}
空间复杂度： S(n)=O(n)
实例2：斐波那契数列（优化版）
long long Fib(int n) {
long x=1, y=1,t;
for(int i=2;i<=n;i++) {
t=x; x=y; y=x+t;
}
return y;
}
空间复杂度： S(n)=O(1)
实例3：递归求最大值
int maxElem(int a[], int i, int j) {
int mid=(i+j)/2, max1, max2;
if (i<j) {
max1=maxelem(a, i, mid);
max2=maxelem(a, mid+1, j);
return (max1>max2)?max1:max2;
}
else return a[i];
}
递归算法空间复杂度计算：
每层需要的辅助空间（进层时不仍需保留的）× 递归深度
实例4：归并排序空间复杂度分析
/*r数组中，low到mid单元为一有序序列，mid+1到high为另一有序序列，
将二者合并为一个新的有序序列，并放入r数组的low到high单元*/
void Merge(RecordType r[], int low, int mid, int high){
int i,j,k;
RecordType *A=(RecordType*)malloc(sizeof(RecordType)*(high-low+1));
i=low; j=mid+1; k=0;
while ( (i<=mid)&&(j<=high) ) {
if ( r[i]<=r[j] ) { A[k]=r[i]; i++; k++; }
else { A[k]=r[j]; j++; k++;}
}
while( i<=mid ) { A[k]=r[i]; k++; i++; }
while( j<=high) { A[k]=r[j]; k++; j++; }
//合并好的数据在辅助空间中，平移到原数组r中，并释放辅助空间
for(i=low,k=0;i<=high;i++,k++) r[i]=A[k];
free(A);
}
void MergeSort(RecordType r[], int low, int high) {
int mid;
if (low<high) {
mid=(low+high)/2;
MergeSort(r,low, mid);
MergeSort(r,mid+1,high);
Merge (r,low,mid,high);
}
}
空间复杂度分析：
- Merge算法中，申请了辅助空间A，该空间的大小为high-low+1。最大时为n，用完即释放。
- 算法递归深度为logn，所以还用了logn的栈空间。
- 因此空间复杂度为 O(n+logn)=O(n)。
算法复杂度分析练习
非递归算法实例
实例A
i=1;
while (i<n) {
for(j=1;j<=n;j++)
x=x+i;
i=i*2;
}
时间复杂度： T(n)=O(nlogn)
实例B
i=1; j=0;
while(i+j<=n) {
if(i>j) j++;
else i++;
}
时间复杂度： T(n)=O(n)
实例C
i=1;
while (i<n) {
for(j=1;j<=i;j++)
x=x+1;
i=i*2;
}
时间复杂度： T(n)=O(n)
递归算法实例
实例1：二叉树先序遍历
void PreOrder(BiTree T) {
if (T) {
visit(T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
时间复杂度： T(n)=O(n)
实例2：汉诺塔问题
void hanoi(int n, char a, char b, char c) {
if (n==1)
move (a, 1, c);
else {
hanoi(n-1, a, c, b);
move(a, n, c);
hanoi(n-1, b, a, c);
}
}
时间复杂度： T(n)=O(2ⁿ)
408考研真题分析
2019年真题
问题： 折半查找采用递归和非递归的时间复杂度分别为（）。
答案： A. O(logn) 和 O(logn)
问题： 折半查找采用递归和非递归的空间复杂度分别为（）。
答案： B. O(logn) 和 O(1)
2022年真题
int sum = 0;
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < i; j++)
sum++;
分析： 设r为外循环执行次数，当i=2ʳ=n时结束，则r=logn
时间复杂度： O(nlogn)
2023年真题
问题： 下列对顺序存储的有序表(长度为n)实现给定操作的算法中，平均时间复杂度为O(1)的是（）
答案： D. 获取第i(1≤i≤n)个元素的算法
2025年真题
int count = 0;
for (int i = 0; i*i< n; i ++)
for (int j = 0; j < i; j++)
count++;
时间复杂度： O(n)
综合应用题
2018年408真题：寻找缺失的第一个正整数
问题描述： 给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。
算法1：哈希法
// 基本思想：
// 1) 定义临时数组temp，大小为n，初值均为0；
// 2) 遍历原数组A，当A[i]>0&&A[i]<=n时，temp[A[i]]=1。
// 3) 从下标1开始遍历temp数组，第一次值为0的下标i为最小未出现正整数i；
// 若temp数组均不为0，则为n+1。
复杂度： T(n)=O(n)，S(n)=O(n)
算法2：置换法
int firstMissPNum(int A[], int n){
for(int i=1;i<=n;i++){
while(A[i]>0&&A[i]<=n &&(i!=A[i]) ){
if(A[A[i]]==A[i]) break;
int tmp = A[i];
A[i]=A[A[i]];
A[A[i]] = tmp;
}
}
for(int i =1;i<=n;i++)
if( i!=A[i] ) return i;
return n+1;
}
复杂度： T(n)=O(n)，S(n)=O(1)
算法3：原地哈希
int firstMiss(int A[], int n) {
// 1) 将数组中所有小于或等于0的数修改为n+1；
for (int i = 1; i <= n; ++i)
if (A[i] <= 0) A[i] = n + 1;
// 2) 遍历数组中的每一个数x。如果1<= |x|<= n，
// 那么就置A[|x|]的元素为负数，标记该元素出现过。
for (int i = 1; i <= n; ++i) {
int x = abs(A[i]);
if (x <= n) A[x] = -abs(A[x]);
}
// 3) 重新遍历数组A，第一个正数的下标即为答案；
// 如果每一个数都是负数，则为n+1。
for (int i = 1; i <= n; ++i)
if (A[i] > 0) return i;
return n + 1;
}
复杂度： T(n)=O(n)，S(n)=O(1)
2025年408真题：乘积最大值问题
问题描述： 有两个长度均为n的一维整型数组A[n]、res[n]，计算A[i]与Aj乘积的最大值，并将其保存到res[i]中。
算法实现：
void CalMulMax(int A[], int res[], int n) {
if (n == 0) return;
// 1. 找出全局最大值和最小值
int max_val = A[0], min_val = A[0];
for (int i = 1; i < n; i++) {
if (A[i] > max_val) max_val = A[i];
if (A[i] < min_val) min_val = A[i];
}
// 2. 计算res[i]
for (int i = 0; i < n; i++) {
if (A[i] >= 0)
res[i] = A[i] * max_val;
else
res[i] = A[i] * min_val;
}
}
复杂度： T(n)=O(n)，S(n)=O(1)
算法性能实际应用
算法效率对比
假设某计算机运行速度为10亿次/秒运算：
- 10万个数据快速排序： 10⁵×log₂10⁵/10⁹ ≈ 1.7×10⁶/10⁹ = 1.7ms
- 1万个顶点求单源最短路径： (10⁴)²/10⁹ = 0.1s
- 100个顶点求最大团： 100×2¹⁰⁰/10⁹ ≈ 1.8×10²¹秒，约5.7×10¹⁵年
常用算法复杂度总结
- 快速排序算法： T(n)=O(nlog₂n)
- Dijkstra算法： T(n)=O(n²)
- 最大团算法： T(n)=O(n×2ⁿ)
本章小结
数据结构的基本概念：理解数据、数据对象、数据元素等基本概念，掌握抽象数据类型的定义。
数据结构三要素：逻辑结构、物理结构和运算集合是数据结构的核心要素。
算法复杂度分析：时间复杂度和空间复杂度是评价算法性能的重要指标，需要熟练掌握各种算法的复杂度分析方法。
递归算法分析：递归算法的复杂度分析需要建立递归方程，通过替换法或主方法求解。
实际应用：算法复杂度分析在实际问题求解中具有重要的指导意义。