文档介绍：蒋瀚
山东大学计算机科学与技术学院
2009-2010年度秋季学期动漫08
数据结构算法与应用--C++ 语言描述
什么是数据结构？
在计算机科学中，数据结构（data structure）是计算机中存储、组织数据的方式。
什么是算法？
算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。
--维基百科
数据结构算法与应用
--C++ 语言描述
第一部分预备知识
第二部分数据结构
第1章 C++程序设计
第2章程序性能
第3章数据描述
第4章数组和矩阵
第5章堆栈
第6章队列
第7章跳表和散列
第8章二叉树和其他树
第9章优先队列
第10章竞赛树
第11章搜索树
第12章图
第三部分算法设计方法
第13章贪婪算法
第14章分而治之算法
第15章动态规划
第16章回溯
第17章分枝定界
C++ 简介
C++是一种使用非常广泛的计算机程序设计语言。
贝尔实验室的比雅尼·斯特劳斯特鲁普博士在20世纪80年代发明并实现了C++。
1998年国际标准组织（ISO）颁布了C++程序设计语言的国际标准ISO/IEC 14882-1998。
C++语言发展大概可以分为三个阶段
80年代到1995年：这一阶段C++语言基本上是传统类型上的面向对象语言。
1995年到2000年，泛型程序设计在C++中占据了越来越多的比重。
从2000年至今，产生式编程和模板元编程。
C++已经成为当今主流程序设计语言中最复杂的一员
--维基百科
第2章程序性能
程序
性能
空间
复杂性
时间
复杂性
指令
空间
数据
空间
环境栈
空间
操作
计数
执行
步数
运行一个程序所需要的内存大小和时间
分析的方法
实验的方法
运行完一个程序所需要的内存大小
运行完该程序所需要的时间
存储经过编译之后的程序指令所需的空间
存储所有常量和所有变量值所需的空间
保存函数调用返回时恢复运行所需要的信息
首先选择一种或几种关键操作，然后确定关键操作分别执行了多少次
要统计程序/函数中所有部分的时间开销
对一个程序的空间复杂性感兴趣的主要原因如下:
如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。
对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。
一个问题可能有若干个内存需求各不相同的解决方案。
可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。
对一个程序的时间复杂性感兴趣的主要原因如下：
有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。
正在开发的程序可能需要提供一个满意的实时响应。
如果有多种可选的方案来解决一个问题，那么具体决定采用哪一个主要基于这些方案之间的性能差异。
渐进符号
大写O 符号给出了函数f的一个上限。
f(n)=O(g(n))：当且仅当存在正的常数c和n0，使得对于所有的n≥n0 , 有f(n)≤cg(n)。
Ω符号与大O 符号类似，它用来估算函数f 的下限值。
f(n)= Ω (g(n))：当且仅当存在正的常数c 和n0，使得对于所有的n≥n0，有f(n) ≥cg(n)。
Θ符号适用于同一个函数g 既可以作为f 的上限也可以作为f 的下限的情形。
f(n)=Θ(g(n))：当且仅当存在正常数c1 , c2 和某个n0，使得对于所有的n≥n0 ,有c1g(n)≤f(n)≤c2g(n)。
小写o符号
f(n)=o(g(n) )：当且仅当f(n)=O(g(n))且f(n)≠ Ω(g(n))。
例一递归问题
递归函数是一个自己调用自己的函数。
递归函数包括两种
直接递归
间接递归
例一递归问题
程序1-7 计算n！的递归函数
int Factorial (int n)
{
//递归计算n！
if (n<=1) return 1;
else return n * Factorial(n- 1 ) ;
}
P36 练习7 计算n！的非递归程序
int factorial (int n)
{
//非递归计算n！
if (n <= 1) return 1;
int fact = 2;
for (int i = 3; i <= n; i++)
fact *= i;
return fact;
}