数 据 结 构 相 关
———
在有些时候可能会有点用。 。 。
灯 下 野 狐
mail: dengxiayehu@yeah.net
2 0 1 0 – 8 – 28 at JUST
先说点让人 ... 的东西。
数据结构和算法是程序设计最重要的两个内容。 数据结构是数据的组织、 存储和运算 的
总和。 他是信息的一种组织方式， 是以数据按某种组织关系联系起来的一批数据， 其目的 是
提高算法的效率，然后用一定的方式存储到计算机中，并且通常与一组算法的集合相对应，
通过这组算法集合可以对数据结构中的数据进行某种操作。
例如：学生信息检索系统。
问题：查找某个学生的有关情况，或者想询问某个专业或年级的学生的有关情况。
解决：建立相关数据结构，按照某种算法编写相关程序，就可以实现自动检索。由此，
可以在学生信息检索系统中建立一张按学号排序的顺序表和分别按照姓名， 专业及年纪顺 序
排序的索引表。 如图， 由这 4 张表构成的文件便是学生信息索引的数学模型， 计算机的主 要
操作是按照某个特定的要求（如给定姓名）对学生信息文件进行查询。
总结：这类数学模型可称为线性的数据结构。
例如：计算机和人对弈问题。
问题：计算机是如何与人为敌的。
解决：将对弈的策略事先存入计算机。由于对弈的过程是在一定的规则下随机进行的，
所以为使计算机能够灵活对弈就必须对对弈过程中所有可能发生的情况以及相应的对策都
考虑周全， 并且， 一个好的棋手在对弈时不仅要看当前棋盘的状态， 还应能预测棋局的趋
势，
甚至最后的结局。 因此， 在对弈过程中， 计算机操作的对象是对弈过程中可能出现的棋局 状
态 —— 格局， 然后对相应的格局进行相应的处理。 通常， 格局与格局之间的关系不像上面 是
线性的，通常可能是树状结构的，从某种格局可以分支出好几种格局，见下图：
总结：树可以是某些非数值计算问题的数学模型，它也是一种很重要数据结构。
基本概念和术语
这些基本术语包括：数据，数据元素，数据对象，数据结构等。
算法的评价
算法就是解决问题而采取的步骤和方法。所谓 程序 = 算法 + 数据结构，可见算法在程序
设计中的重要性。 以前很多人刚开始进行编程时都是力求 “ 不择手段
”
将目标达成，这样 也
有利有弊，希望在后来能够多往数据结构和算法上想想。
算法分析
算法分析主要是指分析算法的效率。 算法效率主要的度量有两个方面： 算法的运行时 间
和算法所需的存储空间。 在大多数情况下， 对于算法时间的要求更为重要。 但是算法运行 速
度和所需的存储空间并不能兼顾， 想要算法运行得快就得牺牲相应的空间， 反之亦然。 要 想
解决两者的矛盾，就需要掌握算法分析的方法。
1 ）分析以下程序的时间复杂度。
for ( i = 0; i < n; ++i )
for (j = 0; j < m; ++j)
A[i][j] = i + j;
算法复杂度为 O(m*n) 。
2 ）分析以下程序的时间复杂度。
i = s = 0; ①
while (s < n) {
++i; ②
s += i; ③
}
语句 ① 为赋值语句，执行次数为 1 次，所以其时间复杂度为 O(1) 。
语句 ② 和 ③ 构成 while 循环语句的循环体，它们的执行次数由循环控制条件中的 s 与 n
的值确定。假定循环重复执行了 x 次后结束，则语句 ② 和 ③ 各自重复执行了 x 次，其 时
间复杂度按线性累加规则为 O(x) 。此时 s 与 n 满足关系 s >= n, 而 s = 1 + 2 + 3 ...+ x 。 所
以 1 + 2 + 3 + ...x >= n ， >= n, 解得 x = ，最后可算出 x 与 n 之间满足的是根号（开方）
的关系，故时间复杂度为 O() 。
3 ）分析以下程序的时间复杂度。
i = 1; ①
while (i <= n)
i = 2 * i; ②
语句 ① 的执行次数为 1 ，设语句 ② 的执行次数为 f(n) ，则。
解得时间复杂度为 O() 。
4 ）递归调用函数的时间复杂度分析。
若程序中含有递归调用的话，则令每个递归过程对应于一个未知的时间开销 T(n) ，其
中 n 是过程参数的长度，然后列出一个关于 T 的递归方程求解。
请看下面这个 order 函数，存在递归，主要分析它（原书的例子有点小错误） 。
#include <stdio.h>
#define ARRAY_SIZE 10
int a[ARRAY_SIZE] = {1, 5, 6, 3, 2, 9, 8, 0, 4, 7};
void order(int j, int m) {
int i;
if (j < m) {
for (i = j + 1 ; i <= m; ++i)
if (a[i] < a[j]) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
++j;
order(j, m);
}
} /* end order */
int main(void)
{
int i;
printf("Original array is: ");
for (i = 0; i < ARRAY_SIZE; ++i)
printf("%d ", a[i]);
order(0, ARRAY_SIZE - 1);
printf("\nNow array is: ");
for (i = 0; i < ARRAY_SIZE; ++i)
printf("%d ", a[i]);
printf("\n");
return 0;
} /* end main */
运行结果：
分析： order 函数是一个递归排序过程，设 T(n)(n = m + 1) 是排序 n 个元素的时间，
在进行排序时，算法的计算时间主要花在了递归调用上。第一次调用时处理的元素个数为 n-
1 ，也就是对于下的 n-1 个元素进行排序，这部分所需的计算时间为 T(n-1) 。
又因为在循环中， 需要进行 n-1
比较， 所以排序
n 个元素所需的时间为 T(n) = T(n-1) + n – 1
。
这样的到如下方程：
求解过程为：
T(n) = T(n-1) + (n-1)
= [T(n-2) + (n-2)] + (n-1)
= [T(n-3) + (n-3)] + (n-2) + (n-1)
= [T(1) + 1] + 2 + 3 + 4 + ... (n-3) + (n-2) + (n-1)
= 0 + 1 + 2 + 3 + ... (n-1)
= n(n-1)/2
= O()
5) 阶乘（递归）函数时间复杂度分析。
#include <stdio.h>
int fact(int n)
{
if (n <= 1)
return 1; /* 语句 1 */
else
return (n * fact(n - 1)); /* 语句 2 */
} /* end fact */
int main(void)
{
printf("5! = %d\n", fact(5));
return 0;
} /* end main */
运行结果：
主要看上面的 fact 函数，设 fact(n) 的运行时间为 T(n) 。该函数中语句 1 的运行时间
是 O(1) ，语句 2 运行时间是 T(n-1) + O(1) ，说明没一次调用它的运行时间都是 O(1) ，则相对
与传入的参数 n ，那么就有 n 个 O(1) ，故时间复杂度为 O(n) 。
评论1
最新资源