数据结构课程设计报告

数据结构课程设计计算机科学与通信工程学院姓名：学号：指导老师：时间：目录课程设计目的……2课程设计的要求…2课程设计具体内容………………2二叉排序树………………2（1）需求分析（2）设计说明（3）代码（4）运行结果（二）排序………11（1）需求分析（2）设计说明（3）代码（4）运行结果心得体会………22参考文献………22一、课程设计目的课程设计是一种全面的综合训练，是课堂教学的延续。对学生数据结构知识的全面综合训练，把书上学到的知识用于解决实际问题、培养今后软件开发工作所需的动手实践能力，包括问题分析、总体结构设计、用户界面的设计、程序设计的基本技能和技巧，以及一整套软件工作规范的训练和团体协作精神的培养。二、课程设计的要求程序运行正确。报告要求：课程设计报告以书面形式和电子版两种形式提交。遵守诚实代码原则。三、课程设计具体内容（一）二叉排序树(1)需求分析：1.运行环境：MicrosoftVisual

C++6.02.程序所实现的功能：给出一组关键值，建立相应的二叉排序树，完成：①结点的删除操作。要求可以实现删除根节点，叶子节点以及其他任意节点的功能；②插入一个新结点的操作=3\*GB3③对给定的值在二叉排序树进行操作=4\*GB3④随时显示操作的结果(2)设计说明：1.算法设计思想：运用结构体建立二叉树，并实现其各个功能。二叉排序树的输出用中序遍历，则按从小到大的顺序依次输出各元素。2.流程图：建立建立二叉排序树删除结点插入删除结点插入结点查找查找输出二叉排序树输出二叉排序树(3)代码：#include<iostream>usingnamespacestd;structBSTree{intdata;BSTree*left;BSTree*right;};boolflag=false;inta[100];//查找操作BSTree*search(BSTree*r,intx){if(r==NULL)returnNULL;else{if(r->data==x)returnr;elseif(r->data>x)returnsearch(r->left,x);elsereturnsearch(r->right,x);}}BSTree*insert(BSTree*r,BSTree*s)//插入操作{BSTree*p=search(r,s->data);//首先查找树中是否已存在此节点if(p==NULL){if(r==NULL){r=s;}elseif(s->data<r->data)r->left=insert(r->left,s);elseif(s->data>r->data)r->right=insert(r->right,s);}elseflag=true;returnr;}BSTree*createBSTree(BSTree*r,int*a,intn){inti;BSTree*t;t=r;for(i=0;i<n;i++){BSTree*s=(BSTree*)malloc(sizeof(BSTree));s->data=a[i];s->left=NULL;s->right=NULL;t=insert(t,s);}returnt;}BSTree*getFather(BSTree*r,BSTree*s){BSTree*sf;if(r==NULL||r==s)sf=NULL;else{if(s==r->left||s==r->right)sf=r;elseif(s->data>r->data)sf=getFather(r->right,s);elsesf=getFather(r->left,s);}returnsf;}BSTree*deleteNode(BSTree*r,BSTree*s)//删除操作{BSTree*temp,*father,*sf;sf=getFather(r,s);if(s->left==NULL&&s->right==NULL&&sf!=NULL)//被删除结点是叶子结点,不是根结点if(sf->left==s)sf->left=NULL;elsesf->right=NULL;elseif(s->left==NULL&&s->right==NULL&&sf!=NULL)//被删除结点是叶子结点,又是根结点r=NULL;elseif(s->left==NULL&&s->right!=NULL&&sf!=NULL)if(sf->left==s)sf->left=s->right;elsesf->right=s->right;elseif(s->left==NULL&&s->right!=NULL&&sf==NULL)//被删除结点有右孩子,无左孩子.删结点是根结点r=s->right;elseif(s->left!=NULL&&s->right==NULL&&sf!=NULL)//被删结点有左孩子,无右孩子.删结点不是根结点if(sf->left==s)sf->left=s->left;elsesf->right=s->left;elseif(s->left!=NULL&&s->right==NULL&&sf==NULL)//被删结点有左孩子,无右孩子.删结点是根结点r=s->left;elseif(s->left!=NULL&&s->right!=NULL){temp=s->left;father=s;while(temp->right!=NULL)//找出左子树最大的节点{father=temp;temp=temp->right;}s->data=temp->data;if(father!=s)father->right=temp->left;elsefather->left=temp->left;}if(r==NULL)cout<<"删除之后，二叉排序树为空！"<<endl;elsecout<<"删除成功！"<<endl;returnr;}BSTree*inorder(BSTree*r){ if(r!=NULL) { inorder(r->left); cout<<r->data<<""; inorder(r->right); } return0;}intmain(intargc,char*argv[]){intcases;cout<<"请输入二叉树个数：";cin>>cases;cout<<endl;while(cases--){intn;flag=false;BSTree*root=NULL;cout<<"请输入元素个数：";cin>>n;cout<<endl;inti;cout<<"请输入这些元素：";for(i=0;i<n;i++)cin>>a[i];cout<<endl;cout<<"建立二叉排序树!"<<endl;root=createBSTree(root,a,n);if(root!=NULL){cout<<"二叉排序树建立成功！"<<endl<<inorder(root)<<endl;}else{cout<<"二叉排序树建立失败！"<<endl;return0;}cout<<"请选择您要进行的操作(输入括号内的字母，大小写均可)："<<endl;cout<<"1.删除(D/d)"<<endl;cout<<"2.插入(I/i)"<<endl;cout<<"3.查找(S/s)"<<endl;cout<<"4.退出(E/e)"<<endl;chars;cin>>s;while(1){if(s=='E'||s=='e')break;elseif(s=='I'||s=='i'){cout<<"请输入您要插入的值："<<endl;intx;cin>>x;BSTree*p=(BSTree*)malloc(sizeof(BSTree));p->data=x;p->left=NULL;p->right=NULL;root=insert(root,p);if(flag==false)cout<<"插入成功！"<<endl<<inorder(root)<<endl;else{cout<<"此二叉树中已存在此值！"<<endl;flag=false;//恢复原值}}elseif(s=='S'||s=='s'){cout<<"请输入您要查找的值："<<endl;intx;cin>>x;BSTree*p=search(root,x);BSTree*pfather=getFather(root,p);cout<<"查找的值为："<<p->data<<endl;if(pfather!=NULL)cout<<"其父节点的值为："<<pfather->data<<endl;elsecout<<"它是根节点，没有父节点！"<<endl;if(p->left==NULL&&p->right==NULL)cout<<"它是叶子节点，没有子节点"<<endl;else{if(p->left!=NULL)cout<<"其左儿子节点的值为："<<p->left->data<<endl;elsecout<<"其左儿子节点为空！"<<endl;if(p->right!=NULL)cout<<"其右儿子的值为："<<p->right->data<<endl;elsecout<<"其右儿子节点为空！"<<endl;}}elseif(s=='D'||s=='d'){cout<<"请输入您要删除的节点的值："<<endl;intvalue;cin>>value;cout<<"你确定要删除吗？(Yy/Nn)"<<endl;charorder;cin>>order;while(1){if(order=='Y'||order=='y'){BSTree*node;node=search(root,value);if(node==NULL)cout<<"该节点不存在！"<<endl;else {BSTree*nodeDel=deleteNode(root,node); cout<<inorder(root)<<endl;}break;}elseif(order=='N'||order=='n'){break;}else{cout<<"命令不正确，请重新输入！"<<endl;cin>>order;}}}else{cout<<"命令有误，请重新输入！"<<endl;}cout<<"请选择您要进行的操作："<<endl;cin>>s;}}system("pause");return0;}(4)运行结果（二）排序(1)需求分析：1.运行环境：MicrosoftVisual

C++6.02.程序所实现的功能：几种排序算法的演示，要求给出从初始开始时的每一趟的变化情况，并对各种排序算法的排序性能作分析和比较：①直接插入排序；②折半插入排序；=3\*GB3③冒泡排序；=4\*GB3④简单选择排序；=5\*GB3⑤快速排序；=6\*GB3⑥堆排序；=7\*GB3⑦归并排序。(2)设计说明：1.算法设计思想：运用顺序表存放数据元素，7种排序算法均为顺序表类的函数。主函数中，为了避免前一个排序结果的影响，采取选择排序算法的方法，将各个排序算法分开。2.流程图：选择排序类型选择排序类型退出排序冒泡排序选择排序归并排序退出排序冒泡排序选择排序归并排序……建立顺序表建立顺序表退出输出已排序的顺序表按所选排序类型排序退出输出已排序的顺序表按所选排序类型排序（3）代码：#include<iostream.h>constintmaxlen=100;intnum=0;template<classtype>classseqlist{public: intlen; typedata[maxlen]; seqlist(void); ~seqlist(void); intlength(void); voidmerge(seqlist<type>&sourcetable,seqlist<type>&mergedtable,constintleft,constintmid,constintright);voidinsertionsort(); typeinsert(consttype&item,inti); voidselectsort(); voidhalfsort(); voidbubblesort(); voidswap(type&a,type&b); voidquicksort(intlow,inthigh); voidmergepass(seqlist<type>&sourcetable,seqlist<type>&mergedtable,constintlen); voidmergesort(seqlist<type>&table); voidprint(); voidfilterdown(constintstart); voidheapsort();};template<classtype>seqlist<type>::seqlist(void):len(0){}template<classtype>seqlist<type>::~seqlist(void){}template<classtype>intseqlist<type>::length(void){returnlen;}template<classtype>voidseqlist<type>::swap(type&a,type&b){ typec; c=a; a=b; b=c;}template<classtype>voidseqlist<type>::print(){ for(intx=0;x<len;x++) cout<<data[x]<<""; cout<<endl;}template<classtype>voidseqlist<type>::halfsort(){ typetemp; intleft,right; for(inti=1;i<len;i++) { left=0; right=i-1; temp=data[i]; while(left<=right) { intmid=(left+right)/2; if(temp<data[mid]) right=mid-1; elseleft=mid+1; } for(intk=i-1;k>=left;k--) data[k+1]=data[k]; data[left]=temp; cout<<"第"<<++num<<"趟折半插入排序:"; for(intx=0;x<len;x++) cout<<data[x]<<""; cout<<endl; } num=0;}template<classtype>voidseqlist<type>::selectsort(){ intk; for(inti=0;i<len-1;i++) { k=i; for(intj=i+1;j<len;j++) if(data[j]<data[k]) k=j; if(k!=i) swap(data[i],data[k]); cout<<"第"<<i+1<<"趟选择排序:"; print(); } }template<classtype>voidseqlist<type>::quicksort(intlow,inthigh){ inti=low,j=high;staticinta=1; typetemp=data[low]; if(i<j) { while(i<j) { while(i<j&&temp<data[j]) j--; if(i<j) { data[i]=data[j]; i++; } while(i<j&&temp>=data[i]) i++; if(i<j) { data[j]=data[i]; j--; } } data[i]=temp; cout<<"第"<<a++<<"趟快速排序:"; print(); quicksort(low,i-1); quicksort(i+1,high); } }template<classtype>voidseqlist<type>::bubblesort(){ inti=1; intfinish=0; while(i<len&&!finish) { finish=1; for(intj=0;j<len-i;j++) if(data[j]>data[j+1]) { swap(data[j],data[j+1]); finish=0; } cout<<"第"<<++num<<"趟冒泡排序:"; for(intx=0;x<len;x++) cout<<data[x]<<""; cout<<endl; i++; } num=0;}template<classtype>voidseqlist<type>::merge(seqlist<type>&sourcetable,seqlist<type>&mergedtable,constintleft,constintmid,constintright){ inti=left,j=mid+1,k=left; while(i<=mid&&j<=right) if(sourcetable.data[i]<=sourcetable.data[j]) { mergedtable.data[k]=sourcetable.data[i]; i++; k++; } else { mergedtable.data[k]=sourcetable.data[j]; j++; k++; } if(i<=mid) for(intp=k,q=i;q<=mid;p++,q++) mergedtable.data[p]=sourcetable.data[q]; elsefor(intp=k,q=j;q<=right;p++,q++) mergedtable.data[p]=sourcetable.data[q];}template<classtype>voidseqlist<type>::mergepass(seqlist<type>&sourcetable,seqlist<type>&mergedtable,constintlen){ inti=0; while(i+2*len<=length()-1) { merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1); i+=2*len; } if(i+len<=length()-1) merge(sourcetable,mergedtable,i,i+len-1,length()-1); elsefor(intj=i;j<=length()-1;j++) mergedtable.data[j]=sourcetable.data[j]; if(len<=length()-1) {if(num<length()) { cout<<"第"<<++num<<"趟归并排序结果为:"; for(intt=0;t<length();t++) cout<<mergedtable.data[t]<<""; cout<<endl; } }}template<classtype>voidseqlist<type>::mergesort(seqlist<type>&table){ seqlist<type>temptable; intlen=1; while(len<table.length()) { mergepass(table,temptable,len); len*=2; mergepass(temptable,table,len); len*=2; }}template<classtype>voidseqlist<type>::insertionsort(){ typetemp; intj; for(inti=1;i<len;i++) { temp=data[i]; j=i; while(j>0&&data[i]<data[j-1]) { data[j]=data[j-1]; j--; } data[j]=temp; cout<<"第"<<i<<"趟直接插入排序:"; print(); }}template<classtype>voidseqlist<type>::filterdown(constintstart){ inti=start,j=2*i+1; inttablesize=len; typetemp=data[i]; while(j<=len-1) { if(j<len-1&&data[j]<data[j+1]) j++; if(temp>=data[j])break; else{data[i]=data[j];i=j;j=2*j+1; } } data[i]=temp; }template<classtype>voidseqlist<type>::heapsort(){ inttablesize=len; for(inti=(len-2)/2;i>=0;i--) filterdown(i); for(i=len-1;i>=1;i--) { swap(data[0],data[i]); len--; filterdown(0); cout<<"第"<<++num<<"趟堆排序结果为:"; for(intx=0;x<tablesize;x++) cout<<data[x]<<""; cout<<endl; } num=0; len=tablesize;}#include<iostream.h>#include"seqlist.h"intmain(){ inta=1; while(a!=0) { intm; cout<<"选择排序类型"<<endl<<"1冒泡排序"<<endl<<"2快速排序"<<endl<<"3直接插入排序"<<endl; cout<<"4折半插入排序"<<endl<<