2023年数据结构实验报告3_第1页
2023年数据结构实验报告3_第2页
2023年数据结构实验报告3_第3页
2023年数据结构实验报告3_第4页
2023年数据结构实验报告3_第5页
已阅读5页,还剩21页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构实验报告学号:08055140班级:计算机86姓名:邓凯

提交日期:091216#include<stdio.h>#include<stdlib.h>typedefstructBNode(chardata;structBNode*1chiId;structBNode*rchild;}BTNode;ypedefBTNode*BinTree;voidCreateBinTree(BinTree*root)//以先序来建立二叉树(charch;ch=getchar();if(ch==~)〃空格*root=NULL;//建立空二叉树else(*root=(BTNode*)maHoc(sizeof(BTNode));〃开辟空间,生成节点(*root)->data=ch;CreateBinTree(&((*root)->lchiId));CreateBinTree(&((*root)—>rchi1d));))voidPreOrder(BinTreeroot)〃先序遍历if(root!=NULL)printf(',%c",root->data);PreOrder(root—>1child);PreOrder(root->rchild);1)voidInOrder(BinTreeroot)〃中序遍历{if(rooi!=NULL)(PreOrder(root->lchild);printf(H%croot->data);PreOrder(root->rchild);})voidPostOrder(BinTreeroot)//后序遍历{if(root!=NULL)(PreOrder(root->1child);Pre0rder(root->rchi1d);)printf("%cM,root->data);)voidmain()

BinTreeroot;CreateBinTree(&root);printf("先序遍历:");PreOrder(root);PrintfC\n");printf("中序遍历:");InOrder(root);printf(*'\n");printf("后序遍历:");PostOrder(root);printf("\n");}输入ab##c###运营结果otyekyccanbacaabbc:--:s运营结果otyekyccanbacaabbc:--:sesab先中后protyekyccanbacaabbc:--:sesab先中后otyekyccanbacaabbc:--:sesab先中后prcontinue输入:abc##dc#g##f###输入:abc##dc#g##f###

输入:abc##dc#g##f###运营结果:abcdegf先序:abcdegF'中序:bcdegfa后序:bcdegFaPressanykeytocontinue输入:abc#dc##f##i##g#hj###

运营结果:labcdefighj先序:abcdefighj中住:bedeFiaghj后序:bedefighjaPressanykeytocontinue六、上机总结课上的速度飞快,还没来得及看书,一章就过去了。现在听课更还是像以前同样,云里雾里,都快成仙了,但是有些时候还是能听懂,但总也听不完全,因此做这样的实验真可谓是难啊,先得看上半天的书,然后再在网上看有没有类似的程序,忙得不可开交,好不容易找到个,编辑器通但是,只是一个错误却半天也找不到,哎,何苦呢,与其如此还不如自己写,浪费时间,却什么也没学到。这个程序我又在网上看,看到底怎么个写法,写了半天最后还得请隔壁宿舍的同学帮忙调试,

大半天弄不好。但是,还算是搞出来了,这样简朴的一个程序,却也难倒了我,哎,前路多艰,我将努力学习。七、参考资料清华大学出版社清华大学出版社西安交大出版社.数据结构(清华大学出版社清华大学出版社西安交大出版社.数据结构习题集.C++面向对象程序设计第三次二、上机实习题目对于十个输入的整形数据进行快速排序,并按照从小到大的顺序输出排序后结果并测试以下数据:(一)、0987654321(二)、12,23,89,90J8,76,45,34,43,60(三)、1,123,12,45,876,345,24,37,0,876三组数据。二、相关知识或技术(相应DS部分)C语言,C++的一些基本知识,快速排序的算法以及应用之类的知识。五、算法及数据结构设计(算法设计)快速排序中的一趟:intpartition(inta[],int1ow,inthigh){ntpivotkey;pivotkey=a[low];whi1e(low<high)while(1ow<high&&a[high]>=pivotkey)—high;a[low]=a[high];while(1ow<high&&a[1ow]<=pivotkey)++low;a[high]=a[low];Ia[1ow]=pivotkey;returnlow;)快速排序的递归形式:voidqsort(inta[],intlow,inthigh){intpivot1oc;if(low<high){pivotloc=partition(a,low,high);//一趟排序结果的调用qsort(a,low,pivotloc-1);qsort(a,pivot1oc+1,high);}四、Microsoftvs6.0五、源程序(带注释或说明)、运营结果(数据或屏幕显示、结果分析、讨论T(n))inc1ude"stdio.h"#inc1ude"std1ib.hdefineN10include"iostrearn,h"intpartition(inta[],int1ow,inthigh){//快速排序中的一趟intpivotkey;pivotkey=a[low];while(low<high){while(low<high&&a[high]>=pivolkey)-high;a[low]=a[high];while(low<high&&a[1ow]<=pivotkey)++1ow;a[high]=a[low];)a[low]=pivotkey;return1ow;)voidqsort(inta[],int1ow,inthigh){//快速排序的递归形式intpivotloc;if(low<high){pivot!oc=partition(a,low,high);〃一趟排序结果的调用qsort(a,low,pivotloc-1);qsort(a,pivot1oc+1,high);})Voidinit(iota[]){〃输入要拍的数据inti;cout«”请输入将要排序的十个数字“〈Vendl;for(i=0;i<N;i++)cin>>a[i];)voidmain()◎(ointa[N],i;oinit(a);。qsort(a,0,N);。print。排序后的结果\n");for(i=1;iV=N;i++){〃输出排序后的数据printf(n%d",a[i-1]);if(i%10==0)。printf("\n\n");}printf(”\n\n");)测试数据.输入:0987654321运营结果:请输入将要排序的十个数字0987654321排序后的结果0123456789Pressanykeytocontinue

.输入:12,23,89,90,78,76,45,34,43,60运营结果:情输入将要排序的十个数字12238990787645344360Pressanykeytocontinue..输入:1,123,12,45,876,345,24,37,0,876运营结果:请输入将要排序的十个数字1123124587634524370876Pressanykeytocontinue六、上机总结课终于上完了,但这门课还没有结束,除了实验尚有考试,迄今为止,还是很不懂,费了大半天的功夫,也只能做出这类的极其简朴的程序,还是多半用的过去的知识,真是惭愧啊。但是总还算是有些收获,至少这个程序所运用的快速排序还是学会了。也只有慢慢来了,前路多艰,也不仅仅是数据结构这门课程,其实好多事情也正如数据结构这门课程,难,但是不得不学,对于计算机的同学,应当是不得不学会。选择了计算机就无可避免的选择了数据结构,选择了人生也就选择了努力与奋斗,这算是这次实验的一点心得吧。七、参考资料清华大学出版社清华大学出版社西安交大出版社.数据结构(清华大学出版社清华大学出版社西安交大出版社.数据结构习题集.C++面向对象程序设计第一次一、上机实习题目运用链表实现数据的排序,并检测:(一)、12、21、34、56、23、36、87、13、987。(二)、9、2、4、1、5、3、6、7、8、12、13、11、10。(三)、234、162、289、999、435、90三组数据。二、相关知识或技术(相应DS部分)C++的一些基本知识,以及链表的创建以及应用之类的知识。三、算法及数据结构设计(算法设计)voidsort(Lnode*L)//链表中元素按递增排序{Lnode*p,*q,*r,*s;if(L->next!=NULL){p=L->next->next;L->next->next=NULL;}while(p)(q=p;p=p->next;r二L;第四次三、上机实习题目实现树与二叉树的转化,并测试一组数据。二、相关知识或技术(相应DS部分)c语言,C++的一些基本知识,树、二又树的基本知识。六、算法及数据结构设计(算法设计)voidChangeToBinary(Node*pNode)(if(pLChiId==NULL)return;Node*pL=newNode(pLChi1d->val);pNode—>pLeft=pL;pLChild—>ChangeToBinary(pNode->pLeft);if(pLChi1d->pRSibling)(Node*pR=newNode(pLChi1d->pRSibling->val);pNode—>pRight=pR;pLChild->pRSib1ing->ChangeToBinary(pNode->pRighl);)四、Microsoftvs6.0五、源程序(带注释或说明)、运营结果(数据或屏幕显示、结果分析、讨论T(n))#inc1ude<iostream>usingnamespacestd;structNode;structTreeNode;structNode(charva1;Node*pLeft;Node*pRight;Node(){pLeft=NULL;pRight=NULL;)Node(charch)(val=ch;pLeft=NULL;PRight=NULL;1〜Node()(if(pLeft)pLeft->-Node();if(pRight)pRight->-Node();deletethis;voidInsert(charch)(if(ch>=va1){if(pRight)pRight->Insert(ch);eIse{Node*add=newNode(ch);pRight=add;))else(if(pLeft)pLeft->Insert(ch);eIse(Node*add=newNode(ch);pLeft=add;voidShow()cout<<val«endI;if(pLeft)pLeft->Show();if(pRighl)pRight->Show();}卜structTreeNode{charval;TreeNode*pLChild;TreeNode*pRSibling;TreeNode()(pLChi1d=NULL;pRSibling=NULL;)TreeNode(charch)(val=ch;pLChild=NULL;pRSibling=NULL;)〜TreeNode()if(pLChild)pLChild->~TreeNode();if(pRSibling)pRSibling—>-TreeNode();deletethis;}voidInsert(charch){if(ch>=val)(if(pRSib1ing)pRSibling—>Insert(ch);else(TreeNode*pR=newTreeNode(ch);pRSibling=pR;))else{if(pLChild)pLChi1d->Insert(ch);eIseTreeNode*pL=newTreeNode(ch);pLChi1d=pL;)))voidShow()(cout<<val<<endl;if(pLChild)pLChi1d->Show();if(PRSibling)pRSibling->Show();)voidChangeToBinary(Node*pNode)(if(pLChild==NULL)return;Node*pL=newNode(pLChi1d->val);pNode->pLeft=pL;pLChild->ChangeToBinary(pNode—>pLeft);if(pLChi1d->pRSibling)(Node*pR=newNode(pLChi1d->pRSibling->val);pNode->pRight=pR;

pLChi1d->pRSibling->ChangeToBinary(pNode->pRight);}};c1assBinaryTree;classTree;classBinaryTree(public:Node*root;pub1ic:BinaryTree()(root=NULL;)-BinaryTree(){if(root)root—>-Node();(voidInsert(charch)(if(!root)rootnewNode(ch);elseroot->Insert(ch);}voidShow()(if(root)root->Show();)};classTree(publie:TreeNode*root;public:Tree()(root=NULL;)〜Tree()(if(root)root—>-TreeNode();1voidInsert(charch)if(1root)root=newTreeNode(ch);eIseroot->Insert(ch);)voidShow(){if(root)root->Show();)BinaryTree*ChangeToBinary(){if(root==NULL)returnNULL;BinaryTree*pBT=newBinaryTree();pBT—>root=newNode(root—>val);root->ChangeToBinary(pBT->root);returnpBT;};inimain()(◎Treetree1;tree1.Insert('s');®tree1.Insert('e');treel.Insert('f7);(reel.Insert(*c');Hreel.Insert('d*);//tree1.Insert(");//treel.Insert(");//treel.Insert(");。//treel.Insert(");scout«"树输出:"Vvend1;nreel.Show();®BinaryTree*bTree=tree1.ChangeToBinary();cout«"二叉树输出:Vendl;dbTree—>Show();。return0:}运营结果:硼□□:<-*recd三叉树输出:3ecdfPressanykeytocontinue六、上机总结四个小时的上机时间,居然没有编出一个像样的程序,最终也只得回去做,并s=L->next;while(s&&s->data.shuju<=q->data.shuju)(r=s;s=s->next;)r->next=q;q->next=s;)四、上机环境和使用语言(计算机程序实现)Microsoftvisua1c++;使用c++语言五、源程序(带注释或说明)、运营结果(数据或屏幕显示、结果分析、讨论T(n))#inc1ude<iostream>usingnamespacestd;structData(intshuju;intinfo;};structLnodeDatadata;且还得被扣分,其实我是写出来一个的,只是与别人的相比完全可以说是相形见细,完全得靠c语言的知识。一棵树的构造完全的在主程序里,繁琐之极,最重要的是没有一般性,只能就题而言,没办法,只得被扣分。实话说今天才是第一次看这部分的内容,可谓是临时抱佛脚啊。上课期间就完全同课本脱离了,期末了,也有复习,可还没有看到这里,哎,真可谓是“时运不济”啊。但是,终于还是借助着辅导书做出来了。由于忘掉了题目,测试只得随便找了几个。七、参考资料.数据结构(C语言版)清华大学出版社.数据结构习题集清华大学出版社.C++面向对象程序设计西安交大出版社.数据算法大全最后总结与感悟:数据结构不易,人生更不易,难的数据结构只是更难的人生的开始。最后衷心地感谢老师。Lnode*next;};Lnode*creat();voidsort(Lnode*L);voidprint(Lnode*head);intmain(){Lnode*L;L=creat();sort(L);Print(L);return0;)Lnode*ereat()//链表的创建{Lnode*L,*p,*q;L=ncwLnode;inti,n;coutVV”请输入该链表的长度”VVend1;cin»n;coutvV”输入数据项shuju的值“VVendl;q=L;for(i=0;i<n;i++)(p=newLnode;cin>>p—>data.shuju;q->next=p;q=p;)q->next=NULL;relurnL;)voidsort(Lnode*L)〃链表中元素按递增排序(Lnode*p,*q,*r,*s;if(L->next!=NULL)(p=L—>next->next;L->next—>next=NULL;)while(p)(q二p;p=p->next;r=L;s=L->next;while(s&&s->data.shuju<=q->data.shuju)(r=s;s=s->next;)r->next=q;q->next=s;)voidprint(Lnode*L)//递增输出L=L->next;cout«”递增输出数据的值”<vendl;while(L!=NULL)cout<<L->data.shuju<<nu;L=L—>next;)输入12、21、34、56、23、36、87、13、987运营结果:请输入该链表的长度输入数据项shuju的值1221345623368713987递增输出key的值1213212334365687987Pressanykeytocontinue输入:9、2、4、1、5、3、6、7、8、12、13、11、1()运营结果:调输入该链表的长度13匐入数据项s皿娘的值924367812131110递增输出key的值彳234B6f2a910111213anukeutncnntainue输入:234、162、289、999、435、90运营结果:请输入该链表的长度

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论