数据结构算法和应用-C++-语言描述

蒋瀚山东大学计算机科学与技术学院2009-2019年度秋季学期动漫08数据结构算法与应用--C++语言描述什么是数据结构？

在计算机科学中，数据结构（datastructure）是计算机中存储、组织数据的方式。

什么是算法？

算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。--维基百科数据结构算法与应用--C++语言描述第一部分预备知识第二部分数据结构第1章C++程序设计第2章程序性能第3章数据描述第4章数组和矩阵第5章堆栈第6章队列第7章跳表和散列第8章二叉树和其他树第9章优先队列第10章竞赛树第11章搜索树第12章图第三部分算法设计方法第13章贪婪算法第14章分而治之算法第15章动态规划第16章回溯第17章分枝定界C++简介C++是一种使用非常广泛的计算机程序设计语言。贝尔实验室的比雅尼·斯特劳斯特鲁普博士在20世纪80年代发明并实现了C++。2019年国际标准组织（ISO）颁布了C++程序设计语言的国际标准ISO/IEC14882-2019。C++语言发展大概可以分为三个阶段80年代到2019年：这一阶段C++语言基本上是传统类型上的面向对象语言。2019年到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！的递归函数intFactorial(intn){//递归计算n！

if(n<=1)return1;

elsereturnn*Factorial(n-1);}P36练习7计算n！的非递归程序intfactorial(intn){//非递归计算n！if(n<=1)return1;intfact=2;for(inti=3;i<=n;i++)

fact*=i;returnfact;}例二顺序搜索程序2-1顺序搜索template<classT>intSequentialSearch(Ta[],constT&x,intn){//在未排序的数组a[0:n-1]中搜索x//如果找到，则返回所在位置，否则返回-1inti;for(i=0;i<n&&a[i]!=x;i++);if(i==n)return-1;returni;}在未排序的数组a[0:n-1]中寻找x，如找到则返回第一个x的位置，否则返回-1。例在下面寻找5a[0]a[1]a[2]a[3]a[4]a[5]a[6]6243579程序2-2执行顺序搜索的递归函数template<classT>intSequentialSearch(Ta[],constT&x,intn){//在未排序的数组a[0:n-1]中查找x//如果找到则返回所在位置，否则返回-1if(n<1)return-1;if(a[n-1]==x)returnn-1;returnSequentialSearch(a,x,n-1);}例二顺序搜索假定T为int

类型x需要2个字节n需要2个字节i需要2个字节常量0需要2个字节常量-1需要2个字节a[i]需要2个字节

则所需要的总的数据空间为12字节。因为该空间独立于n，所以S顺序搜索(n)=0程序2-1顺序搜索template<classT>intSequentialSearch(Ta[],constT&x,intn){//在未排序的数组a[0:n-1]中搜索x//如果找到，则返回所在位置，否则返回-1inti;for(i=0;i<n&&a[i]!=x;i++);if(i==n)return-1;returni;}程序2-1的空间复杂度注：数组a所需要的空间已在定义实际参数的函数中分配，所以，不需要把该数组所需要的空间加到函数所需要的空间上去。例二顺序搜索程序2-1顺序搜索template<classT>intSequentialSearch(Ta[],constT&x,intn){//在未排序的数组a[0:n-1]中搜索x//如果找到，则返回所在位置，否则返回-1inti;for(i=0;i<n&&a[i]!=x;i++);if(i==n)return-1;returni;}程序2-1的时间复杂度对程序2-1使用关键操作计数的方法分析时间复杂度。程序2-1中的关键操作为两个元素的比较。例二顺序搜索在未排序的数组a[0:n-1]中寻找x，最好的情况x=a[0]，只需比较一次例在下面寻找5a[0]a[1]a[2]a[3]a[4]a[5]a[6]5243679在未排序的数组a[0:n-1]中寻找x，最坏的情况x=a[n-1

]，或者x找不到，需比较n次例在下面寻找5a[0]a[1]a[2]a[3]a[4]a[5]a[6]6243975要计算平均查找次数，假定所有的数组元素都是不同的，并且每个元素被查找的概率是相同的。成功查找的平均比较次数如下：确定平均操作数通常是十分困难。例三计数排序下标01234元素a[]43937名次r[]20413程序2-5计算名次template<classT>voidRank(Ta[],intn,intr[]){//计算a[0:n-1]中n个元素的排名for(inti=1;i<n;i++)r[i]=0;//初始化//逐对比较所有的元素for(inti=1;i<n;i++)for(intj=0;j<i;j++)if(a[j]<=a[i])r[i]++;elser[j]++;}第一步：计算名次。

元素在队列中的名次可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。例三计数排序程序2-5计算名次template<classT>voidRank(Ta[],intn,intr[]){//计算a[0:n-1]中n个元素的排名for(inti=1;i<n;i++)r[i]=0;//初始化//逐对比较所有的元素for(inti=1;i<n;i++)for(intj=0;j<i;j++)if(a[j]<=a[i])r[i]++;elser[j]++;}第一步：计算名次的时间复杂度仍然计算关键操作，关键操作为元素的比较外循环执行次数n-1第i次内循环执行次数为i总的比较次数为:1+2+。。。+(n-1)=(n-1)n/2例三计数排序下标01234元素a[]43937名次r[]20413附加数组u[]33479程序2-6利用附加数组重排数组元素template<classT>voidRearrange(Ta[],intn,intr[]){//按序重排数组a中的元素，使用附加数组uT*u=newT[n+1];//在u中移动到正确的位置for(inti=0;i<n;i++)u[r[i]]=a[i];//移回到a中for(inti=0;i<n;i++)a[i]=u[i];delete[]u;}第二步：按名次排序。（利用附加数组）例三计数排序程序2-6利用附加数组重排数组元素template<classT>voidRearrange(Ta[],intn,intr[]){//按序重排数组a中的元素，使用附加数组uT*u=newT[n+1];//在u中移动到正确的位置for(inti=0;i<n;i++)u[r[i]]=a[i];//移回到a中for(inti=0;i<n;i++)a[i]=u[i];delete[]u;}第二步：按名次排序（利用附加数组）时间复杂度仍然计算关键操作，关键操作为元素的移动第一次循环执行次数n第二次循环执行次数为n总的移动次数为:n+n=2n总的时间复杂度=计算名次+按名次排序（利用附加数组）:

(n-1)n/2次比较操作和2n次移动操作例三计数排序下标01234元素a[]43937名次r[]2

400

41421

4334重排4

933

93943

9779程序2-11原地重排数组元素template<classT>voidRearrange(Ta[],intn,intr[]){//原地重排数组元素for(inti=0;i<n;i++)//获取应该排在a[i]处的元素while(r[i]!=i){intt=r[i];Swap(a[i],a[t]);Swap(r[i],r[t]);}}第二步：按名次排序。（原地重排数组元素）例三计数排序程序2-11原地重排数组元素template<classT>voidRearrange(Ta[],intn,intr[]){//原地重排数组元素for(inti=0;i<n;i++)//获取应该排在a[i]处的元素while(r[i]!=i){intt=r[i];Swap(a[i],a[t]);Swap(r[i],r[t]);}}第二步：按名次排序（原地重排数组元素）时间复杂性仍然计算关键操作，关键操作为元素的交换最少交换次数为0（初始数组已经是按序排列）最大的交换次数为2(n-1)(1.包括名次交换;2.每次交换需要移动3次)。例三计数排序原地重排数组元素与利用附加数组相比最坏情况下所需要的执行时间将增加计算名次阶段两者相同：(n-1)n/2次比较排序阶段附加数组：2n次移动原地重排：2(n-1)次交换=3*2(n-1)次移动所需要的内存减少附加数组：需要一个数组u[]=n个元素空间原地重排：需要一个元素空间例四选择排序程序2-7选择排序template<classT>voidSelectionSort(Ta[],intn){//对数组a[0:n-1]中的n个元素进行排序for(intsize=n-1;size>0;size--){intj=Max(a,size);Swap(a[j],a[size-1]);}}程序1-31寻找最大元素template<classT>intMax(Ta[],intn){//寻找a[0:n-1]中的最大元素intpos=0;for(inti=1;i<n;i++)if(a[pos]<a[i])pos=i;returnpos;}首先找出a[0,n-1]中最大元素，将其与a[n-1]互换位置；找出a[0,n-2]重最大元素，将其与a[n-2]互换位置；……下标01234元素a[]4339

7

343779例四选择排序程序2-7选择排序template<classT>voidSelectionSort(Ta[],intn){//对数组a[0:n-1]中的n个元素进行排序for(intsize=n-1;size>0;size--){intj=Max(a,size);Swap(a[j],a[size-1]);}}程序1-31寻找最大元素template<classT>intMax(Ta[],intn){//寻找a[0:n-1]中的最大元素intpos=0;for(inti=1;i<n;i++)if(a[pos]<a[i])pos=i;returnpos;}计算关键操作排序过程中，关键操作为元素的交换：交换次数为n-1，每次交换需要3次移动，因此需要3(n-1)次移动。选择排序的时间复杂性寻找最大元素中，关键操作为元素的比较：比较次数为:1+2+…+(n-1)=(n-1)n/2与利用附加数组计数排序相比，比较次数相同，移动次数多50%。例四选择排序程序2-12及时终止的选择排序template<classT>voidSelectionSort(Ta[],intn){//及时终止的选择排序boolsorted=false;for(intsize=n;!sorted&&(size>1);size--){

intpos=0;

sorted=true;

//找最大元素

for(inti=1;i<size;i++)

if(a[pos]<=a[i])pos=i;

elsesorted=false;//未按序排列

Swap(a[pos],a[size-1]);}}及时中止的选择排序程序2-7中选择排序函数的一个缺点是：即使元素已经按序排列，程序仍然继续运行。为了终止不必要的循环，在查找最大元素期间，可以顺便检查数组是否已按序排列。例五冒泡排序程序2-8一次冒泡template<classT>voidBubble(Ta[],intn){//把数组a[0:n-1]中最大的元素通过冒泡移到右边for(inti=0;i<n-1;i++)if(a[i]>a[i+1])Swap(a[i],a[i+1]);}采用冒泡策略将最大元素移到右边。一次冒泡：对相邻元素比较，如果左>右，则左右元素交换。采用递归完成n-1次冒泡，最终完成排序。下标01234元素a[]43937程序2-9冒泡排序voidBubbleSort(Ta[],intn){//对数组a[0:n-1]中的n个元素进行冒泡排序for(inti=n;i>1;i--)Bubble(a,i);}在程序2-9的冒泡排序中，元素比较的次数为(n-1)n/2，与选择排序相同在程序2-9的冒泡排序中，元素移动的次数不定，与输入的数组a[]的实例相关。可分析最好、最坏移动次数。平均移动次数的分析较难。例五冒泡排序程序2-13及时终止的冒泡排序template<classT>boolBubble(Ta[],intn){//把a[0:n-1]中最大元素冒泡至右端boolswapped=false;//尚未发生交换for(inti=0;i<n-1;i++)if(a[i]>a[i+1])

{

Swap(a[i],a[i+1]);

swapped=true;//发生了交换

}returnswapped;}template<classT>voidBubbleSort(Ta[],intn){//及时终止的冒泡排序for(inti=n;i>1&&Bubble(a,i);i--);}及时中止的冒泡排序如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列，没有必要再继续进行冒泡过程。例六插入排序程序2-10向一个有序数组中插入元素template<classT>voidInsert(Ta[],int&n,constT&x){//向有序数组a[0:n-1]中插入元素x//假定a的大小超过ninti;for(i=n-1;i>=0&&x<a[i];i--)a[i+1]=a[i];a[i+1]=x;n++;//添加了一个元素}第一步：向有序数组中插入元素。a中的元素在执行插入之前和插入之后都是按递增顺序排列的。我们为新元素找到欲插入的位置时，必须把该位置右边的所有元素分别向右移动一个位置。组a[0:5]=[1,2,6,8,9,11]中插入4，所得到的结果为a[0:6]=[1,2,4,6,8,9,11]。例六插入排序因为只有一个元素的数组是一个有序数组，所以可以从仅包含欲排序的n个元素的第一个元素的数组开始。通过把第二个元素插入到这个单元数组中，可以得到一个大小为2的有序数组。插入第三个元素可以得到一个大小为3的有序数组。按照这种方法继续进行下去，最终将得到一个大小为n的有序数组例六插入排序程序2-14插入排序template<classT>voidInsert(Ta[],intn,constT&x){//向有序数组a[0:n-1]中插入元素xinti;for(i=n-1;i>=0&&x<a[i];i--)a[i+1]=a[i];a[i+1]=x;}template<classT>voidInsertionSort(Ta[],intn){//对a[0:n-1]进行排序for(inti=1;i<n;i++){Tt=a[i];Insert(a,i,t);}}程序2-15另外一种插入排序template<classT>voidInsertionSort(Ta[],intn){for(inti=1;i<n;i++){//将a[i]插入a[0:i-1]Tt=a[i];intj;for(j=i-1;j>=0&&t<a[j];j--)a[j+1]=a[j];a[j+1]=t;}}例七折半搜索用来在有序数组a[0:n-1]中查找元素x搜索过程从x与数组中间元素的比较开始。如果x等于中间元素，则查找过程结束。如果x小于中间元素，则仅需要查找数组的左半部分。如果x大于中间元素，则仅需要在数组的右半部分进行查找。程序2-30折半搜索template<classT>intBinarySearch(Ta[],constT&x,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//如果找到，则返回所在位置，否则返回-1intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if