数据结构算法与应用C++ 语言描述.ppt

1、张翰山东省大学计算机科学和技术学院2009-2010年秋季学期动画08，数据结构算法和应用程序-C语言说明，数据结构是什么？在计算机科学中，数据结构是在计算机上存储和组织数据的方法。什么是算法？算法是指完成任务所需的具体步骤和方法。也就是说，通过给定的初始状态或输入数据，可以获得所需的结束状态或输出数据。-维基百科，C简介，C是应用非常广泛的计算机程序设计语言。贝尔实验室比亚尼斯特劳斯特鲁普博士在20世纪80年代发明并实现了C。1998年，国际标准组织(ISO)公布了C编程语言国际标准ISO/IEC 14882-1998。c语言开发可以分为大约三个阶段。从20世纪80年代到1995年：在牙齿阶

2、段，C语言基本上是传统类型的面向对象的语言。从1995年到2000年，在泛型计算机编程C中占有越来越多的比重。从2000年到现在，生产式编程和模板元编程。c成为当今主流编程语言中最复杂的一员。存储维基百科、第二章节目性能、运行程序所需的内存大小和时间分析方法实验方法、运行程序所需的内存大小、运行程序所需的时间、编译的节目命令所需的空间、存储所有常量和所有变量值所需的空间，以及在函数调用返回时恢复执行所需的信息。首先选择一个或多个关键任务，然后确定每个关键任务运行了多少次，并统计节目/函数内所有部分的时间开销，导致对一个程序中空间的复杂性感关注的主要原因是：如果：程序在多用户电脑系统上运行，则可

3、能需要显示分配给该程序的内存大小。我想事先知道在任何电脑系统上是否有足够的内存运行程序。一个茄子问题可能有多个具有不同内存要求的茄子解决方案。利用空间复杂性可以估计一个程序能解决的问题的最大规模。节目复杂的性感兴趣的主要原因是。有些计算机需要用户提供程序运行时间的上限，一旦达到牙齿上限，程序将强制退出。正在开发的程序可能需要提供满意的实时响应。如果有多个茄子选项可以解决问题，则必须具体决定哪一个主要基于这些方案之间的性能差异。(威廉莎士比亚，哈姆雷特，谚语)，渐进符号，大写O符号提供函数F的上限。F(n)=O(g(n):只有存在正常数c和n0牙齿时，所有nn0的f(n)cg(n)才存在。符号类

4、似于用于估计函数f下限的大o符号。F(n)=(g(n):只有存在正常数c和n0牙齿时，所有nn0的f(n) cg(n)才存在。符号适用于相同函数G可以是F的上限和F的下限的情况。F(n)=(g(n):只有在正常数量C1、C2和n0牙齿存在的情况下，所有nn0的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 r

5、eturn 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，示例2顺序搜索，节目2-1顺序搜索执行template int sequential search (t a，const，节目2-2顺序搜索的重复函数template int sequential search (t a，cc)需要n 2字节。需要I双字节常量。0需要双字节常量。-需要12字节ai。需要2个字节。所需

6、的总数据空间为12字节。牙齿空间独立于n，因此s顺序搜索(n)=0，节目2-1顺序搜索template int sequential search (t a，const，节目2-1的空间复杂性，注：数组a所需的空间已定义，示例2顺序节目2-1的主要工作是比较两个元素。示例2顺序搜索，要计算平均祖怀数，假定所有数组元素牙齿不同，并且每个元素牙齿查询的概率相同。成功查询的平均比较次数为：确定平均操作数通常很困难。示例3计数排序，节目2-5计算排名template void rank (t a，int n，int r)/计算a 03360n-1中的n个元素排名for(int I=1；I n；I)ri

7、=0；/初始化/比较所有元素对for(int I=1；I n；I)for(int j=0；j I；j)if(a j=a I)r I；Else rj，第一步：排名计算。可以将队列的元素排名定义为队列中所有较小的元素数和出现在左侧的相同元素数。示例3计数排序，节目2-5计算排名template void rank (t a，int n，int r)/计算a 03360n-1中的n个元素排名for(int I=1；I n；I)ri=0；/初始化/比较所有元素对for(int I=1；I n；I)for(int j=0；j I；j)if(a j=a I)r I；Else rj，第一步：计算排名的时间复

8、杂度，仍然计算主要任务，主要任务是元素比较，外部循环运行数n-1 I主要内部循环运行数为I总比较数3360 1 2。(n-1)=(n-1)n/2，范例3计数排序，节目2-6使用其他阵列重新排列阵列元素样板void rearrange (t a，int n，int r)/I n；I)uri=ai；/移回a for(int I=0；I n；I)a I=u I；delete u；步骤2:按排名排序。(使用其他阵列)、范例3计数排序、节目2-6使用其他阵列，依序重新排列阵列元素template void rearange (t a，int n，int r)/阵列a的元素顺序，并使用其他阵列u t *

9、u=newI n；I)uri=ai；/移回a for(int I=0；I n；I)a I=u I；delete u；步骤2:按排名排序(使用附加数组)时间复杂度，仍然计算主要作业，主要作业元素移动，第一个循环运行数N第二个循环运行数N第二个循环运行数N移动总数：N=2n，总时间复杂度=排名计算排名排序(使用附加数组):(示例3计数排序，)I n；I) /ai中必须存在的元素while (ri！=I)int t=ri；Swap(ai，at)；Swap(ri，rt)；步骤2:按排名排序。(在原地重新排列阵列元素)，示例3在原地对齐，节目2-11在原地阵列元素templatevoid rearran

10、ge (t a，int n，int r)/在原地元素阵列for(int I=0；I n；I) /ai中必须存在的元素while (ri！=I)int t=ri；Swap(ai，at)；Swap(ri，rt)；步骤2:按排名排序(在原地重新排列阵列元素)时间复杂性，仍然重要的任务计算，主要任务是元素更换，最小更换次数为0(初始阵列已经按顺序排列)更换的最大次数为2(n-1) (1)。包括排名更换2。每次更换要移动3次。），示例3计数排序，在原地重新排序阵列元素与使用附加阵列相比，在最坏的情况下，需要的执行时间会增加，这相当于计算排名阶段。(n-1)n/2比较对齐步骤附加阵列：2n移动原地重新对齐

11、：2(n-1)辅助更换=3*2(n-1)辅助移动站示例4选择排序，节目2-7选择排序templatevoidsize 0；Size-) int j=max (a，size)；Swap(aj，asize-1)；程序1-31寻找最大元在template int Max(T a，int n) /a 03360n-1中寻找最大元int pos=0；for(int I=1)；I n；I)if(apos ai)pos=I；返回pos，示例4选择排序，节目2-7选择排序templatevoid selectionsort (t a，int n)/阵列a 03360n-1中的n个元素排序for(int siz

12、e=n-1；size 0；Size-) int j=max (a，size)；Swap(aj，asize-1)；程序1-31寻找最大元在template int Max(T a，int n) /a 03360n-1中寻找最大元int pos=0；for(int I=1)；I n；I)if(apos ai)pos=I；返回pos、主要任务计算、排序过程中的主要任务是元素交换。更换次数为n-1，每个交换需要移动3次，因此需要移动3次(N-1)。选择排序时间复杂性，查找最大元元素的重要任务是元素比较。比较次数为：1 2 (n-1)=(n-1)n/2，比其他阵列计数排序多移动50%。示例4选择排序，节

13、目2-12选择立即终止的选择排序模板void(t a，int n)/立即终止的选择排序bool sorted=falsefor(int size=n；Sorted、及时中断的选择排序、节目2-7的选择排序函数缺点之一是，即使元素排序，程序也会继续执行。为了退出不需要的循环，可以在查找最大元的过程中检查阵列是否按顺序排列。5冒泡排序，节目2-8冒泡template void Bubble (T a，int n) /通过阵列a03360n-1中最大的元素冒泡，转到右侧for (int I=0)。I ai 1) Swap(ai、ai 1)；节目2-9冒泡排序void BubbleSort (T a，

14、int n) /阵列a 03360n-1的n个元素冒泡排序for(int I=n；i1；I-)波波星人(a，I)；节目2-9的冒泡排序中元素比较数为(n-1)n/2，等于选择排序数。在节目2-9的冒泡排序期间，元素移动的次数与输入阵列A的实例相关数不相等。可以分析最好和最差的移动次数。平均移动次数的分析更加困难。示例5冒泡排序，节目2-13牙齿及时结束的冒泡排序模板布尔(T a，intn)/a 03360n-1中，最大元冒泡到右侧的圆周率=false/未发生交换for(int I=0；I ai 1) Swap(ai、ai 1)；Swapped=true/交换return swapped发生。Templatevoid bubblesort (t a，int n)/按时结束的冒泡排序for(int I=n；I 1，及时中断的冒泡排序，如果在一次冒泡过程中没有发生元素交换，则阵列是按顺序排列的，无需继续冒泡过程。示例6插入排序，节目2-10将元素template void Insert(T a，int /)插入