数据结构课程设计报告.docx
- 文档编号:14345477
- 上传时间:2023-06-22
- 格式:DOCX
- 页数:34
- 大小:241.41KB
数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告.docx(34页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告
数据结构课程设计
计算机科学与通信工程学院
姓名:
学号:
指导老师:
辛燕
时间:
2013-1-15
目录
一、课程设计目的……………………2
二、课程设计的要求…………………2
三、课程设计具体内容………………2
(一)二叉排序树………………2
(1)需求分析
(2)设计说明
(3)代码
(4)运行结果
(二)排序………………………11
(1)需求分析
(2)设计说明
(3)代码
(4)运行结果
四、心得体会………………………22
五、参考文献………………………22
一、课程设计目的
1、课程设计是一种全面的综合训练,是课堂教学的延续。
2、对学生数据结构知识的全面综合训练,把书上学到的知识用于解决实际问题、培养今后软件开发工作所需的动手实践能力,包括问题分析、总体结构设计、用户界面的设计、程序设计的基本技能和技巧,以及一整套软件工作规范的训练和团体协作精神的培养。
二、课程设计的要求
1、程序运行正确。
2、报告要求:
课程设计报告以书面形式和电子版两种形式提交。
3、遵守诚实代码原则。
三、课程设计具体内容
(一)二叉排序树
(1)需求分析:
1.运行环境:
MicrosoftVisual C++6.0
2.程序所实现的功能:
给出一组关键值,建立相应的二叉排序树,完成:
①结点的删除操作。
要求可以实现删除根节点,叶子节点以及其他任意节点的功能;
②插入一个新结点的操作
对给定的值在二叉排序树进行操作
随时显示操作的结果
(2)设计说明:
1.算法设计思想:
运用结构体建立二叉树,并实现其各个功能。
二叉排序树的输出用中序遍历,则按从小到大的顺序依次输出各元素。
2.流程图:
(3)代码:
#include
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);
else
returnsearch(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->left=insert(r->left,s);
elseif(s->data>r->data)
r->right=insert(r->right,s);
}
else
flag=true;
returnr;
}
BSTree*createBSTree(BSTree*r,int*a,intn)
{
inti;
BSTree*t;
t=r;
for(i=0;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); else sf=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; else sf->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; else sf->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; else sf->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; else father->left=temp->left; } if(r==NULL) cout<<"删除之后,二叉排序树为空! "< else cout<<"删除成功! "< returnr; } BSTree*inorder(BSTree*r) { if(r! =NULL) { inorder(r->left); cout< inorder(r->right); } return0; } intmain(intargc,char*argv[]) { intcases; cout<<"请输入二叉树个数: "; cin>>cases; cout< while(cases--) { intn; flag=false; BSTree*root=NULL; cout<<"请输入元素个数: "; cin>>n; cout< inti; cout<<"请输入这些元素: "; for(i=0;i cin>>a[i]; cout< cout<<"建立二叉排序树! "< root=createBSTree(root,a,n); if(root! =NULL) {cout<<"二叉排序树建立成功! "< else { cout<<"二叉排序树建立失败! "< return0; } cout<<"请选择您要进行的操作(输入括号内的字母,大小写均可): "< cout<<"1.删除(D/d)"< cout<<"2.插入(I/i)"< cout<<"3.查找(S/s)"< cout<<"4.退出(E/e)"< chars; cin>>s; while (1) { if(s=='E'||s=='e') break; elseif(s=='I'||s=='i') { cout<<"请输入您要插入的值: "< 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<<"插入成功! "< else { cout<<"此二叉树中已存在此值! "< flag=false;//恢复原值 } } elseif(s=='S'||s=='s') { cout<<"请输入您要查找的值: "< intx; cin>>x; BSTree*p=search(root,x); BSTree*pfather=getFather(root,p); cout<<"查找的值为: "< if(pfather! =NULL) cout<<"其父节点的值为: "< else cout<<"它是根节点,没有父节点! "< if(p->left==NULL&&p->right==NULL) cout<<"它是叶子节点,没有子节点"< else { if(p->left! =NULL) cout<<"其左儿子节点的值为: "< else cout<<"其左儿子节点为空! "< if(p->right! =NULL) cout<<"其右儿子的值为: "< else cout<<"其右儿子节点为空! "< } } elseif(s=='D'||s=='d') { cout<<"请输入您要删除的节点的值: "< intvalue; cin>>value; cout<<"你确定要删除吗? (Yy/Nn)"< charorder; cin>>order; while (1) { if(order=='Y'||order=='y') { BSTree*node; node=search(root,value); if(node==NULL) cout<<"该节点不存在! "< else {BSTree*nodeDel=deleteNode(root,node); cout< break; } elseif(order=='N'||order=='n') { break; } else { cout<<"命令不正确,请重新输入! "< cin>>order; } } } else { cout<<"命令有误,请重新输入! "< } cout<<"请选择您要进行的操作: "< cin>>s; } } system("pause"); return0; } (4)运行结果 (二)排序 (1)需求分析: 1.运行环境: MicrosoftVisual C++6.0 2.程序所实现的功能: 几种排序算法的演示,要求给出从初始开始时的每一趟的变化情况,并对各种排序算法的排序性能作分析和比较: ①直接插入排序; ②折半插入排序; 冒泡排序; 简单选择排序; 快速排序; 堆排序; 归并排序。 (2)设计说明: 1.算法设计思想: 运用顺序表存放数据元素,7种排序算法均为顺序表类的函数。 主函数中,为了避免前一个排序结果的影响,采取选择排序算法的方法,将各个排序算法分开。 2.流程图: …… (3)代码: #include constintmaxlen=100; intnum=0; template classseqlist { public: intlen; typedata[maxlen]; seqlist(void); ~seqlist(void); intlength(void); voidmerge(seqlist voidinsertionsort(); typeinsert(consttype&item,inti); voidselectsort(); voidhalfsort(); voidbubblesort(); voidswap(type&a,type&b); voidquicksort(intlow,inthigh); voidmergepass(seqlist voidmergesort(seqlist voidprint(); voidfilterdown(constintstart); voidheapsort(); }; template seqlist : seqlist(void): len(0){} template seqlist : ~seqlist(void){} template intseqlist : length(void) {returnlen;} template voidseqlist : swap(type&a,type&b) { typec; c=a; a=b; b=c; } template voidseqlist : print() { for(intx=0;x cout< cout< } template voidseqlist : halfsort() { typetemp; intleft,right; for(inti=1;i { left=0; right=i-1; temp=data[i]; while(left<=right) { intmid=(left+right)/2; if(temp 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 cout< cout< } num=0; } template voidseqlist : selectsort() { intk; for(inti=0;i { k=i; for(intj=i+1;j if(data[j] k=j; if(k! =i) swap(data[i],data[k]); cout<<"第"< "; print(); } } template voidseqlist : quicksort(intlow,inthigh) { inti=low,j=high;staticinta=1; typetemp=data[low];
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告