数据结构介绍

数据结构

定义

没有官方统一定义

引例

例1：如何在书架上摆放图书？

图书的摆放要使得2个相关操作方便实现：

• 操作1：新书怎么插入？
• 操作2：怎么找到某本指定的书？

方法1：随便放

• 操作1：新书怎么插入？
  哪里有空放哪里，一步到位！

• 操作2：怎么找到某本指定的书？
  …累死

方法2：按照书名的拼音字母顺序排放

• 操作2：怎么找到某本指定的书？
  二分查找！

• 操作1：
  新书怎么插入？

方法3：把书架划分成几块区域，每块区域指定摆放某种类别的书；在每种类别内，按照书名的拼音字母顺序排放

• 操作2：怎么找到某本指定的书？

• 先定类别，再二分查找

• 操作1：新书怎么插入？
  先定类别，二分查找确定位置，移出空位

• 问题：空间怎么分配？类别应该分多细？

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

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

• 循环实现

void PrintN(int N)
{
	int i;
	for(i=1; i<=N; i++){
		printf("%d\n", i);
	}
	return;
}
1
2
3
4
5
6
7
8

• 递归实现

void PrintN(int N)
{
	if(N){
		PrintN(N-1)
		printf("%d\n", N)
	}
	return;
}
1
2
3
4
5
6
7
8

递归很容易爆掉

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

例3：写程序计算给定多项式在给定点x处的值

$f(x)=a_0+a_{1}x+...+a_{n-1}{x}^{n-1}+a_n{x}^n$

double f(int n, double a[], double x)
{
	int i;
	double p = a[0];
	for(i=1; i<=m; i++)
		p += (a[i] * pow(x, i));
	return p;
}
1
2
3
4
5
6
7
8

秦九韶算法
$f(x)=a_0+x(a_1+x(...(a_{n-1}+x{a}_n)...))$

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
2
3
4
5
6
7
8

clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。
常数CLK_TCK：机器时钟每秒所走的时钟打点数

#include 
#include 

clock_t start, stop;
/* clock_t是clock()函数返回的变量类型 */
double duration;
/* 记录被测函数运行的时间，以秒为单位 */
int main()
{
	/* 不在测试范围内的准备工作写在clock()调用之前 */
	start = clock();	// 开始计时
	MyFunction();	// 把被测函数加在这里
	stop = clock();	// 停止计时
	duration = ((double)(stop-start))/CLK_TCK;	// 计算运行时间

	/* 其他不在测试范围内的处理写在后面，例如输出duration的值 */
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

让被测函数重复运行多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可！

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

什么是数据结构？

• 数据对象在计算机中的组织方式
  • 逻辑结构
  • 物理存储结构
• 数据对象必定与一系列加在其上的操作相关联
• 完成这些操作所用的方法就是算法

逻辑结构：

• 把书架想象成一长条，除了一头一尾，一头挨着一头，一对一，线性结构
• 把图书分类，给每一类一个编号，一对多，数
• 这些书都由什么人买过，这些人又买过什么书，多对多，图

物理存储结构

• 逻辑结构在机器内存中怎么放，数组或者链表？

抽象数据类型（Abstract Data Type）

• 数据类型

  • 数据对象集
  • 数据集合相关联的操作集

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

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

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

例4：“矩阵”的抽象数据类型定义

算法

定义

• 算法（Algorithm）
  • 一个有限指令集
  • 接受一些输入（有些情况下不需要输入）
  • 产生输出
  • 一定在有限步骤之后终止
  • 每一条指令必须
    • 有充分明确的目标，不可以有歧义
    • 计算机能处理的范围之内
    • 描述应不依赖于任何一种计算机语言以及具体的实现手段

例1：选择排序算法的伪码描述

void SelectionSort(int List[], int N)
{
	*/ 将N个整数List[0]...List[N-1]进行非递减排序 */
	for(i=0; i<N; i++)
		MinPosition = ScanForMin(List, i, N-1);
	/ *从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition */
	Swap(List[i], List[MinPosition]);
	/* 将未排序部分的最小元换到有序部分的最后位置 */
}
1
2
3
4
5
6
7
8
9

抽象 ——
List 到底是数组还是链表（虽然看上去很像数组）？
Swap 用函数还是用宏去实现？

什么是好的算法

• 空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过过高的算法可能导致使用的内存超限，造成程序非正常中断。
• 时间复杂度T(n)——根据算法写成的程序在执行时好费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

例2

void PrintN(int N)
{
	if(N){
		PrintN(N-1)
		printf("%d\n", N)
	}
	return;
}
1
2
3
4
5
6
7
8

例3

多项式分析
分析函数运行效率：机器运算加减法的效率比乘除法高很多，因此统计乘除法次数就好

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

• 最坏情况复杂度 $T_{worst}(n)$
• 平均复杂度$T_{avg}(n)$
  $$T_{avg}(n)\le T_{worst}(n)$$

复杂度的渐进表示

• $T(n)=O(f(n))表示存在常数C>0，n_0>0使得当n\ge n_0时有T(n)\le C\cdot f(n)$
• $T(n)=\Omega (g(n))表示存在常数C>0，n_0>0使得当n\ge n_0时有T(n)\ge C\cdot g(n)$
• $T(n)=\Theta (h(n))表示同时有T(n)=O(h(n))和T(n)=\Omega (h(n))$

一个函数的上界和下界不是唯一的，它可以有很多个