塔里木学计算机算法课程实验报告1

塔里木大学信息工程学院塔里木大学算法程序与分析课程实验报告课程名称：算法程序与分析任课教师：李旭机房：逸夫楼408计算机编号：33实验日期：2015-3-17实验成绩：实验班级：计算机17-5班学生姓名：王琴辉实验名称：分治算法实验设备、设施：MicrosoftVisualC++6.0实验要求：1.首先要理解分治算法思想；2.其次针对问题要认真分析，并进一步掌握分治算法的思想；3.最后进行实际操作，即对给定的问题设计出相应的算法。实验目的：1.理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。2.掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验内容：快速排序堆排序，对其进行插入、删除操作。算法设计思路：1.快速排序的设计思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.堆排序的设计思想：根结点的值最小(最大)，且根结点的子树也为一个堆，称为最小堆(最大堆)算法程序：快速排序代码：#include<stdio.h>intpartions(intl[],intlow,inthigh){intprvotkey=l[low];l[0]=l[low];while(low<high){while(low<high&&l[high]>=prvotkey)--high;l[low]=l[high];while(low<high&&l[low]<=prvotkey)++low;l[high]=l[low];}l[low]=l[0];returnlow;}voidqsort(intl[],intlow,inthigh){intprvotloc;if(low<high){prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high}}voidquicksort(intl[],intn){qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个}voidmain(){inta[11]={0,2,32,43,23,45,36,57,14,27,39};for(intb=1;b<11;b++)printf("%3d",a[b]);printf("\n");quicksort(a,11);for(intc=1;c<11;c++)printf("%3d",a[c]);}二叉堆的实现：#include<stdio.h>#include<stdlib.h>#defineLENGTH(a)((sizeof(a))/(sizeof(a[0])))staticintm_heap[30];//数据staticintm_capacity=30;//总的容量staticintm_size=0;//实际容量(初始化为0)intget_index(intdata){inti=0;for(i=0;i<m_size;i++)if(data==m_heap[i])returni;return-1;}staticvoidmaxheap_filterdown(intstart,intend){intc=start;//当前(current)节点的位置intl=2*c+1;//左(left)孩子的位置inttmp=m_heap[c];//当前(current)节点的大小while(l<=end){//"l"是左孩子，"l+1"是右孩子if(l<end&&m_heap[l]<m_heap[l+1])l++;//左右两孩子中选择较大者，即m_heap[l+1]if(tmp>=m_heap[l])break;//调整结束else{m_heap[c]=m_heap[l];c=l;l=2*l+1;}}m_heap[c]=tmp;}intmaxheap_remove(intdata){intindex;//如果"堆"已空，则返回-1if(m_size==0)return-1;//获取data在数组中的索引index=get_index(data);if(index==-1)return-1;m_heap[index]=m_heap[--m_size];//用最后元素填补maxheap_filterdown(index,m_size-1);//从index位置开始自上向下调整为最大堆return0;}staticvoidmaxheap_filterup(intstart){intc=start;//当前节点(current)的位置intp=(c-1)/2;//父(parent)结点的位置inttmp=m_heap[c];//当前节点(current)的大小while(c>0){if(m_heap[p]>=tmp)break;else{m_heap[c]=m_heap[p];c=p;p=(p-1)/2;}}m_heap[c]=tmp;}intmaxheap_insert(intdata){if(m_size==m_capacity)return-1;m_heap[m_size]=data;//将"数组"插在表尾maxheap_filterup(m_size);//向上调整堆m_size++;//堆的实际容量+1return0;}voidmaxheap_print(){inti;for(i=0;i<m_size;i++)printf("%d",m_heap[i]);}voidmain(){inta[]={10,40,30,60,90,70,20,50,80};inti,len=LENGTH(a);printf("==依次添加:");for(i=0;i<len;i++){printf("%d",a[i]);maxheap_insert(a[i]);}printf("\n==最大堆:");maxheap_print();i=85;maxheap_insert(i);printf("\n==添加元素:%d",i);printf("\n==最大堆:");maxheap_print();i=90;maxheap_remove(i);