【数据结构】数据结构

本文是基于中国MOOC平台上，华中科技大学的《数据结构》课程和浙江大学的《数据结构》课程所作的一篇课程笔记，便于后期讲行系统性查阅和复习。

从个人感受而言，华中科技大学的课程讲解更适合初学者（缺点在于，从概念到应用之间的衔接生硬不易懂），浙江大学的课程更适合对基础概念有所了解的初学者（缺点在于，对完全不懂的初学者很不友好）。两个课程搭配学习，有奇效。

一、基础概念

1.1 什么是数据结构

1.1.1 解决问题方法的效率，与什么有关？

解决问题方法的效率，跟数据的组织方式有关。

解决问题方法的效率，跟空间的利用效率有关。

解决问题方法的效率，跟算法的巧妙程度有关。

引入案例：如何在书架上摆放书架？

分析案例：图书的摆放要使得两个操作方便实行

1.新书怎么插入？

2.怎么找到某本指定的书？

算法一：随便放。

操作1有空就放，一步到位。操作2需要遍历书架，复杂度高。

算法二：按照书名的拼音字母顺序排放。

操作1每插入一本新书就要把后面的书进行调整，复杂度高。操作2二分查找。

算法三：分而治之法，书架按块放不同类别的书，每一类里按拼音字母顺序排放。

操作1先定类别，二分查找位置，移出空位。操作2先定类别，再二分查找。

对比之下，算法三更优。

优化：空间如何分配？类别应该分多细？

解决问题方法的效率，跟数据的组织方式有关。

引入案例：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。

算法一：for循环
void PrintN(int N) {
	for (int i = 1; i < N + 1; i++) {
		printf("%d\n", i);
	}
	return;
}
算法二：递归函数
void PrintN(int N) {
	if (N) {
		PrintN(N - 1);
		printf("%d\n", N);
	}
	return;
}
实际上，在测试代码过程中，N的取值有10、100、1000、10000，而在10、100、1000时两种代码均能跑通。在10000时，递归函数出现了错误，原因是内存不足。

解决问题方法的效率，跟空间的利用效率有关。

引入案例：写程序计算给定多项式在给定点x处的值。

算法一：傻瓜法
double f(int n, double a[], double x) {
	int i;
	double p = a[0];
	for (i = 1; i <= n; i++) 
		p += (a[i] * pow(x, i));
		return p;
}
算法二：秦久韶算法
double f(int n, double a[], double x) {
	int i;
	double p = a[n];
	for (i = n; i >0; i--) 
		p = a[i - 1] + x * p;
		return p；
}
对比算法：算法二的运行时间更短。

解决问题方法的效率，跟算法的巧妙程度有关。

1.1.2 什么是数据结构？

数据结构是数据对象在计算机中的组织方式。

（数据对象的逻辑结构，数据对象在计算机中的物理存储结构）

•数据对象必定与一系列加在其上操作相关联

•实现这些操作所用的方法就是算法。

抽象数据类型

•抽象数据类型是对数据的逻辑描述，而数据结构是对数据的物理描述。抽象数据类型定义了数据的操作和语义，而数据结构实现了这些操作和语义。因此，可以说抽象数据类型是数据结构的一种实现方式。

•数据类型：数据对象集+数据集合相关联的操作集

•抽象：描述数据类型的方法不依赖于具体实现。

（与存放数据的机器无关，与数据存储的物理结构无关，与实现操作的算法编程语言无关）

（只描述数据对象集和相关操作集”是什么“，并不涉及”如何做到“的问题）

1.2 什么是算法

1.2.1 算法的定义

•算法

•一个有限指令集

•接收一些输入（有些情况不需要输入），产生输出

•有穷性：一定在有限步骤之后终止

•确定性：每一条指令必须有充分明确的目标，不可以有歧义

•可行性：每一条指令必须计算机能处理的范围之内

•伪代码：算法描述应不依赖于任何一种计算机语言以及具体的实现手段

1.2.2 什么是好的算法

•衡量好算法的指标：空间复杂度S(n)，时间复杂度T(n)。

•在分析一般算法的效率时，经常关注下面两种复杂度：

1.最坏情况复杂度： $T_{_{_{worst}}}(n)$

2.平均复杂度： $T_{_{avg}}(n)$

通常 $T_{avg}(n)\leq T_{worst}(n)$ ，我们更常用 $T_{_{_{worst}}}(n)$ 。

1.2.3 复杂度的渐进表示

•T(n)=O(f(n))最坏情况复杂度

表示存在常数C>0，n0>0，使得n>=n0时有 $T(n)\leq C*f(n)$

•T(n)=Ω(g(n))最好情况复杂度

表示存在常数C>0，n0>0，使得n>=n0时有 $T(n)\geq C*g(n)$

•T(n)=Θ(h(n))平均复杂度

表示同时有(n)=O(h(n))和T(n)=Ω(h(n))

复杂度分析小窍门

•若两段算法分别有复杂度 $T_{1}(n)=O(f_{1}(n))$ 和 $T_{2}(n)=O(f_{2}(n))$ ，则

算法相接： $T_{1}(n)+T_{2}(n)=max(O(f_{1}(n)),O(f_{2}(n)))$

算法嵌套： $T_{1}(n)\times T_{2}(n)=O(f_{1}(n)\times f_{2}(n))$

•若T(n)是关于n的k阶多项式，那么 $T(n)=\circleddash (n^{k})$

•一个for循环的时间复杂度=循环次数*循环体代码复杂度

•if-else语句的时间复杂度=max{if的条件判断复杂度，if分支的复杂度，else分支的复杂度}

1.3 应用实例

1.3.1 最大子列和问题

问题：给定N个整数的序列{ $A_{1},A_{2},...,A_{N}$ }，求函数f(i,j)=max{0, $\sum_{k=i}^{j}A_{k}$ }的最大值。

算法一：暴力破解（三个嵌套for循环，复杂度 $N^{3}$ ， $T(N)=O(N^{^{3}})$ ）
int MaxSubseqSum1(int A[], int N) {
	int ThisSum=0, MaxSum = 0;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = i; j < N; j++) {
			for (k = i; k <= j; k++) {
				ThisSum += A[k];
			}
			if (ThisSum > MaxSum) {
				MaxSum = ThisSum;
			}
		}
	}
	return MaxSum;
}
算法二：暴力破解改良版（两个嵌套for循环，复杂度 $N^{2}$ ， $T(N)=O(N^{^{2}})$ ）
int MaxSubseqSum1(int A[], int N) {
	int ThisSum=0, MaxSum = 0;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = i; j < N; j++) {
				ThisSum += A[j];
			if (ThisSum > MaxSum) {
				MaxSum = ThisSum;
			}
		}
	}
	return MaxSum;
}
算法三：分而治之（复杂度 $T(n)=O(N*log(N))$ ）

思想上，将大的问题划分为小的块，逐层划分到最小单位。行动上，从最小单位逐层解决问题，直到解决问题。

算法四：在线处理（复杂度 $T(n)=O(N)$
int MaxSubseqSum4(int A[], int N)
{
	int thissum = 0, maxsum = 0;
	int i;

	for (i = 0; i < N; i++)
	{
		thissum += A[i];
		if (thissum > maxsum)
			maxsum = thissum;
		else if (thissum < 0)
			thissum = 0;
	}
	return maxsum;
}

二、线性结构

2.1 线性表及其实现

2.1.1 线性表的概念

线性表的定义

•线性表是一种数据结构，是由n(n≥0)个数据元素(a1,a2,…，an)构成的有限序列。

记作：L=(a1,a2,…,an)

a1——首元素，an——尾元素

•表的长度(表长)——线性表中数据元素的数目。

•空表——不含数据元素的线性表。

•对于线性表L=(a1,a2,…,a(i-1),ai,a(i+1),...,an)，前驱和后驱：

a(i-1)在ai之前，称a(i-1)是ai的直接前驱(1<i≤n)

a(i+1)在ai之后，称a(i+1)是ai的直接后继(1≤i<n)

a1没有前驱，an没有后继

ai(1<i<n)有且仅有一个直接前驱和一个直接后继

常见线性表举例

•字母表：L1=(A,B,...,Z)，表长为26

•姓名表：L2=(李明,翠菊,方宏名,王林)表长为4

•表格

2.1.2 线性表的基本操作

线性表的基本操作函数

IniList(&L)//构造空表L

ListLength (L)//求表L的长度

GetElem(L,i,&e)//取元素ai,由e返回ai

PriorElem(L,ce,&pre_e)//求ce的前驱,由pre_e返回

InsertElem(&L,i,e)//在元素ai之前插入新元素e

DeleteElem(&L,i)//删除第i个元素

EmptyList(L)//判断L是否为空表

删除操作：DeleteElem(&L,i)

1.删除表中的第i个数据元素（ $1\leq i\leq n$ ），记作DeleteElem(&L,i)

即删去表中第i个元素 $a_{i}$ 。

( $a_{1},a_{2},...,a_{i-1},a_{i},a_{i+1},...,a_{n}$ )——>( $a_{1},a_{2},...,a_{i-1},a_{i+1},...,a_{n}$ )

2.指定元素值x，删除表L中的值为x的元素，记作：DeleteElem(&L,x)

即删去表中值为x的元素。若 $a_{i-1}$ =x,则

( $a_{1},a_{2},...,a_{i-1},a_{i},a_{i+1},...,a_{n}$ )——>( $a_{1},a_{2},...,a_{i},a_{i+1},...,a_{n}$ )

插入操作：InsertElem(&L,i,e)

在元素ai之前插入新元素e(1<=i<=n+1)，记作： InsertElem(&L,i,e)

( $a_{1},a_{2},...,a_{i-1},a_{i},a_{i+1},...,a_{n}$ )——>( $a_{1},a_{2},...,a_{i-1},e,a_{i},a_{i+1},...,a_{n}$ )