2023年数据结构实验报告3.docx

《2023年数据结构实验报告3.docx》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告3.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告学号:08055140班级:计算机86姓名： 邓凯提交日期：09 12 1 6#include#i n clud e typedef s t ru c t BN o de(char d a ta;s tru c t BNo d e * 1 ch i Id;st r u ct BNo d e *rc h ild; BTNod e ;1 y p edef BTNode *BinTre e ;v o id C re a te B in T r ee(Bi n Tree *ro o t)/以先序来建立二叉树(char c h ；c h=get c h a r();i f (ch=) 空

2、格*root=NULL； / /建立空二叉树else(*r o ot= (BTN o de*)m a Hoc ( s i z e o f( B TNod e );开辟空间，生成节 点(* r oot)-dat a =c h ；C r e a te B i n T re e (& (*root)-lch i Id);Create B i nTr e e (&(*ro o t ) rc h i 1 d)；)v o i d P reO r der(B i nT r ee r o o t ) 先序遍历if (roo t !=NULL)p rint f (,% c , r o o t -da t a);

3、P r e Or d er(ro o t1 c hild );Pre Order(roo t- r chil d );1)void InO r der(Bi n T r e e root)中序遍历i f(ro o i! =NULL)(P reOrd e r(root-l c hild);p rint f (H% c r o o t - d a t a );P r eOrder(root-rchild);)v o id PostOrder( B inTree r oot) / / 后序遍历if ( root!=NULL)(P reOrde r (ro o t- 1 c hild);P re 0

4、r d er( r oot- r c h i 1 d );)printf(%cM, r oot-d a t a)；) void mai n ()B in T ree r o o t ;Crea t e B inTree(&r o o t); printf (先序遍历:);PreOrder (root);P r intfCn)； printf(中序遍历:)；InOrde r (r o o t)； printf ( * n);printf(后序遍历:);Post Order(root);printf(n)；输入 ab#c#运营结果o t y e k y c c a n b a c a abb c

5、: - : ses ab先中后pro t y e k y c c a n b a c a abb c : - : ses ab先中后prcontinue输入：ab c # # d c#g#f# #输入：ab c # # d c#g#f# #运营结果:abc de g f 先序:abcdegF 中序:bcdegf a 后序:bcdegFaPress any key to continue输入:ab c #dc# # f#i#g# h j # # #运营结果:labc de f i g hj 先序：abc de f ighj 中住:be de F iaghj 后序：bedef ighjaPress

6、 any key to continue六、上机总结课上的速度飞快，还没来得及看书，一章就过去了。现在听课更还是像以前同 样，云里雾里,都快成仙了，但是有些时候还是能听懂，但总也听不完全，因此做这 样的实验真可谓是难啊，先得看上半天的书，然后再在网上看有没有类似的程序, 忙得不可开交，好不容易找到个，编辑器通但是，只是一个错误却半天也找不到, 哎，何苦呢，与其如此还不如自己写，浪费时间，却什么也没学到。这个程序我又 在网上看，看到底怎么个写法，写了半天最后还得请隔壁宿舍的同学帮忙调试，大半天弄不好。但是，还算是搞出来了，这样简朴的一个程序，却也难倒了我, 哎，前路多艰，我将努力学习。七、参考资

7、料清华大学出版社清华大学出版社西安交大出版社1 .数据结构（C语言版）2 .数据结构习题集3 . C+ +面向对象程序设计第三次二、上机实习题目对于十个输入的整形数据进行快速排序,并按照从小到大的顺序输出排序后 结果并测试以下数据：（一）、098 7 6 5 4 3 2 1（二）、12, 23, 89, 9 0 J8, 76,4 5 ,34,43,60（三）、1 , 12 3,1 2,45,8 76, 345,24, 3 7,0,876三组数据。二、相关知识或技术（相应DS部分）C语言,C+的一些基本知识，快速排序的算法以及应用之类的知识。五、算法及数据结构设计（算法设计）快速排序中的一趟：i

8、 nt par tition（i n t a ,in t 1 o w, int h i gh）1 n t pivotk e y;pi v otk e y= a low;whi 1 e(lo wh i gh)w h ile( 1 o w=pivo t key) high;a low =a h ig h ;whil e (1 o w h igh&a 1 ow=piv o t k ey)+ +low;ah i gh=alow;Ia 1 o w=p i v otk e y ；r e turn low;)快速排序的递归形式：vo i d qs o rt ( int a,int low,int hi g

9、h)int p ivot 1 oc;i f(low h i g h)p i v o tlo c = p a rt i t i o n(a, low,hi g h)； /一趟排序结果的调用q s ort(a, low,p i v o tloc-1);q s o r t (a,p i v o t 1 o c+ 1, high);四、Mi c r osof t vs6.0五、源程序(带注释或说明)、运营结果(数据或屏幕显示、结 果分析、讨论T(n)i nc 1 u d e stdio. h # inc 1 ude std 1 ib. h# d efi n e N 10i n c lu d e io

10、s t r earn, h int p a rtit i o n( i nt a,int 1 ow, i nt h i gh) /快速排序中的一趟 i nt pivotkey;p i votkey= a low;w h ile(l o whig h )while(low= p i vol k ey)-high;alow=a high；while(lowhigh&a 1 ow=p i vo t key)+ 1 ow;a h i gh =alow；)alow=pivotke y ；retu r n 1 ow;)void q s o r t(int a, in t 1 o w, i n t high

11、) /快速排序的递归形式 int p ivotlo c ;if(l o whigh)pivot! o c =p a r tit i on(a, low, high);一趟排序结果的调用qsort( a ,low, p i v o tlo c -1)；q s o rt(a,p i v o t 1 oc+ 1 ,high);)V o id ini t (i o t a )输入要拍的数据int i；cout”请输入将要排序的十个数字“Vendl;f or(i=0;ia i ;)v o i d m a i n() (o int aN, i ;o i n it(a);。 q s ort( a ,0,N)

12、;。print。排序后的结果n)；for( i =1; i V=N;i+)输出排序后的数据 printf(n% d , a i- 1 );if(i%10=0)。 pr i ntf(n n )；pr i n t f (”nn );)测试数据1 .输入:0 98 76 5 4 3 2 1运营结果：请输入将要排序的十个数字0987654321排序后的结果0123456789Press any key to continue.输入:12, 23,89, 9 0 , 78, 7 6,45, 3 4,4 3,60运营结果：情输入将要排序的十个数字12 23 89 90 78 76 45 34 43 60P

13、ress any key to continue.2 .输入:1, 1 23,12, 45,8 7 6,345,24, 3 7, 0, 876运营结果：请输入将要排序的十个数字1 123 12 45 876 345 24 37 0 876Press any key to continue六、上机总结课终于上完了，但这门课还没有结束，除了实验尚有考试，迄今为止，还是很 不懂，费了大半天的功夫,也只能做出这类的极其简朴的程序，还是多半用的过去 的知识，真是惭愧啊。但是总还算是有些收获，至少这个程序所运用的快速排序 还是学会了。也只有慢慢来了，前路多艰，也不仅仅是数据结构这门课程，其实 好多事情也正

14、如数据结构这门课程，难，但是不得不学,对于计算机的同学，应当是 不得不学会。选择了计算机就无可避免的选择了数据结构，选择了人生也就选择 了努力与奋斗，这算是这次实验的一点心得吧。七、参考资料清华大学出版社清华大学出版社西安交大出版社1 .数据结构（C语言版）2 .数据结构习题集3 .C+面向对象程序设计第一次一、上机实习题目运用链表实现数据的排序，并检测：（一）、1 2、21、34、56、23、3 6、87、13、98 7。（二）、9、2、4、1、5、3、6、7、8、12、13、11、10。（三）、2 34、162、289、99 9、435、90三组数据。二、相关知识或技术（相应DS部分）C+

15、的一些基本知识，以及链表的创建以及应用之类的知识。三、算法及数据结构设计（算法设计）void sort（Lnod e *L） / /链表中元素按递增排序Ln o de*p, * q ,*r,*s；i f （L-next! =NULL）p=L-next-next；L- n ext-n e x t=NULL；wh i le （ p ）（q = p;p = p-ne x t；r二 L;第四次三、上机实习题目实现树与二叉树的转化，并测试一组数据。二、相关知识或技术(相应DS部分)c语言,C+的一些基本知识，树、二又树的基本知识。六、算法及数据结构设计(算法设计)void ChangeToBin a r

16、 y(No d e * p Node)(if (pLCh i Id = NULL)re t urn;Node * p L = ne w Nod e ( p LChi 1 d- v al)；pNodepLeft = pL;pLChildChang e T o Bi n ary(pN o d e-pLe f t);if(pLCh i 1 d -p R Si b lin g )(Node * pR = new Node (pLChi 1 d-p R S ibling- v al);pNodepRig h t = pR;pLC hild- p RSib 1 ing-Ch a ng e ToBina r

17、 y( p Nod e -pRighl);)四、M icrosof t v s 6.0五、源程序(带注释或说明)、运营结果(数据或屏幕显示、 结果分析、讨论T(n)# i n c 1 u d e u s i ng nam e s p a ce st d ;s tr u c t Node;struct Tre e Node;s tru c t No d e(ch a r v a 1；Nod e * pL e f t ；Nod e * pR i g ht；Node()pLef t = NULL;pRigh t = NULL;)Node(ch a r ch)(v al = ch;pLef t = N

18、ULL;P Right =NULL;1Node ()(i f ( p L e ft) pLeft-Node();if(pRight)p R i ght-No d e ();d e lete th i s ；void Insert (cha r c h)(i f ( c h = va 1 )i f (pRi g ht)p Right- I n s ert( c h);e IseN o de * a dd = n e w No d e(c h )；p R ight = ad d ;)else(if(pLeft)pLeft-In s e rt (c h )；e Is e(N o de * a d d

19、 = n e w N o de(ch);pLe f t = add;v o i d S h ow()cout Show();i f (p R i ghl)p Righ t -Show ();卜s truct Tree Nodechar val;Tree Node * pLC h ild;TreeNode * p R S ibl i ng；TreeNode ()(pLC h i 1 d = NULL；p RSibling = NULL;)Tr e e N o de( c h a r c h)(v al = ch;pLChild = NULL;p R Sibl i ng = NULL;)TreeN

20、 o de()if( pLCh ild)pLChild- T r eeNode();if(pR S i bl i ng)pR S i bling -T r e eNode();d e lete t his;v o id Inser t (char c h)if(ch = val)(i f (pRS i b 1 i ng)p RSibli n g Insert (ch)；els e(Tre e Node * p R = n e w Tr e eNo d e(ch);p RSi b ling = p R;)elseif(pLC h ild)pLCh i 1 d-Insert(c h );e Ise

21、TreeNode * pL = n e w T reeNode(c h );pLChi 1 d = pL;)voi d S how()(cout val S h ow();if(P RSibl i ng )pR S ibl i ng-Show()；)v oid Chan g eToBinar y (Node * pN o de)(if(p LChild = NULL)return;Node * p L = new No d e(pLChi 1 d- v al);pNo d e-pLeft = p L;p LC h ild-Ch a ng e T oBina r y(pN o depLeft);

22、if ( p LChi 1 d-pR S ibl i ng)(No d e * pR = new No d e ( p L C hi 1 d- p RS i bli n g-val);pN o de-p R i g ht = pR;pLChi 1 d -p RSibli n g-C h ang e ToBinary (pNode-pRi g ht)；c 1 as s Binar y T r e e;clas s Tree；c las s B i na r y Tr e e(p ubli c :Nod e * r o o t;pub 1 ic:B inaryTr e e()(roo t = N

23、UL L;)-Bin a r yTree ()i f (roo t )root-No d e ()；(vo i d I n ser t (c h ar ch)(if(! root)r oo tnew Node(ch);elser o ot-Inser t (ch);void S h ow()(if(r o o t )r o ot- S h ow ();)；clas s Tree(pub lie:TreeNode * r oot;publ i c:Tree()(r o o t = NULL;)Tre e ()(i f (ro o t )root-Tr e eN o d e();1void Ins

24、 e r t ( c har ch)i f (1 roo t )r oot = new Tre e No d e (ch);e Iser oot-In s e r t (ch);)void Sh o w()if(root)r o ot-Show();)Binar y Tre e * C hangeToBi n a r y()i f ( r oot = N U L L )r eturn NU L L;B i n ary T re e * p BT = n e w B in a ryTree ();p BTr oot = n e w Node(r o otval)； roo t-Ch a ng e

25、 T o Binary(pBT- r oot)；re t u r n pBT;；i n i main()(Tree t r e e 1;tree 1. I n se r t ( s)；tre e 1. Insert(e)；tr e el.In s e r t ( f 7 );(reel. I n s e rt(* c );Hreel. I nsert(d*);/ /tree 1 . I n ser t ()；/ / tr e e l.Insert();/tr e el.In s ert();。/treel.Insert();s c out 树输出:Vvend 1 ;nreel.Sh o w()

26、；Bi n ary Tree * bTr e e = tr e e 1 .Cha n g e ToB inary();cou t 二叉树输出:V e n dl;dbT ree S h ow();。r eturn 0：运营结果：硼： n ext;w h i le(s&s- d a t a . s h uju d a ta. shuju)(r=s;s=s-ne x t;)r- n ext=q;q-next=s;)四、上机环境和使用语言(计算机程序实现)Microso f t v isua 1 c +;使用 c +语言五、源程序(带注释或说明)、运营结果(数据或屏幕显示、结 果分析、讨论T(n)#i

27、n c 1 u deu s ing namesp ace s td；str u ct D ata(int shuju;int info;；s t ruct L n o deDa t a d ata; 且还得被扣分，其实我是写出来一个的，只是与别人的相比完全可以说是相形见 细，完全得靠c语言的知识。一棵树的构造完全的在主程序里，繁琐之极,最重要 的是没有一般性,只能就题而言，没办法，只得被扣分。实话说今天才是第一次看 这部分的内容，可谓是临时抱佛脚啊。上课期间就完全同课本脱离了，期末了， 也有复习，可还没有看到这里，哎，真可谓是“时运不济”啊。但是，终于还是 借助着辅导书做出来了。由于忘掉了题目

28、，测试只得随便找了几个。七、参考资料1 .数据结构（C语言版）清华大学出版社2 .数据结构习题集清华大学出版社3 . C+面向对象程序设计西安交大出版社4 .数据算法大全最后总结与感悟：数据结构不易，人生更不易，难的数据结构只是更难的人生的开始。最后衷心地感谢老师。L n o de* next；L no d e*c r e at();voi d sort(Lnode*L);void prin t (Lno d e*head);i n t main() Lno d e*L；L= c r e at();sort (L)；Print (L);return 0;)Ln o de * ere at()

29、/ /链表的创建Lnode* L,*p,*q；L=nc w Lno d e ;i nt i ,n;coutVV ”请输入该链表的长度”VVend 1 ;ci n n;co u t vV”输入数据项shuju的值“VVendl； q =L;f o r( i =0; i pd a t a.sh u ju;q-next=p;q = p;)q- n ext = NULL;r elur n L;)void s ort(Lnod e *L) 链表中元素按递增排序(Lnode*p, *q, *r, *s;if(L- n ext!=N U LL)(p =Lnext- n ext；L- nex t ne x t

30、=N UL L ;)w h il e ( p )(q 二 p；p =p-n ext;r=L；s=L-ne x t ;wh i le(s&s-data. s hu j udata.s h uju)(r= s ;s=s-next；)r-n e xt= q ;q -ne x t=s;)vo i d prin t (Lnode* L) / / 递增输出L= L - n ex t ;co u t ”递增输出数据的值”v e n dl;wh i le (L!=NULL)c outdat a . s h u j unext;)输入 12、2 1、34、56、23、36、87、13、9 87运营结果：请输入该

31、链表的长度输入数据项shuju的值1221345623368713987递增输出key的值12 13 21 23 34 36 56 87 987 Press any key to continue输入：9、2、4、1、5、3、6、7、8、12、13、11、1()运营结果：调输入该链表的长度13匐入数据项s皿娘的值924367812131110递增输出key的值彳 234B 6f2a 9 10 11 12 13an u ke u tn cnnt ainue输入:234、16 2、2 89、9 99、43 5、90运营结果：请输入该链表的长度输入数据项shuju的值2341622899994359

32、0递增输出key的值90 162 234 289 435 999 Press anu key to continueT(n) = n：六、上机总结本最近正在学线性表、栈、对列之类，我对这些知识真是陌生,尝试着写了, 可总是调试但是，总会出现大堆的问题。有时候没有错误，可也没有运营结果，已经 到了最后的期限了，也只能和老师打个擦边球，运用以前还算熟悉的链表，也就 是线性表做了做编程最为基础，最为常见的事情，排序。但是，虽说如此但也是有 所感悟，线性表大都会用到指针，而用指针则往往会犯错，也就是说，学习数据结 构,犯错是在所难免的。并且学习一定要学个清楚，在这里，只要有一丝模糊，就会犯错，一定要认

33、真对待。清华大学出版社清华大学出版社西安交大出版社七、参考资料1 .数据结构（C语言版）2 .数据结构习题集3 . C+面向对象程序设计第二次一.上机实习题目建立二叉树，并对其进行先序、中序、后序三种不同的遍历，并测试以下数据（一）、ab#c #（二）、abc#de#g#f#（三）、a b c#de# f # i #g#h j #三组数据。二、相关知识或技术（相应DS部分）C语言,C+的一些基本知识，树的建立、遍历以及应用之类的知识。四、算法及数据结构设计（算法设计）先序遍历v o id P reOrd e r （BinT r ee ro o t）/（if （root!=NULL）p rint

34、f （% c n,root-d a ta）；Pre Ordcr(root- 1 child);P reOr d e r ( r o o t- r chil d );)I中序遍历v oid I nO r der(BinT r e e ro o t)/if(root! = NULL)P r cOrd e r(r o otIc h ild);pri n tf (%c, roo t -data);P r cOr d er(r o ot-rchild);)/后序遍历void Po s 10 r d e r(BinT r ee root)/(if(root!=NULL)(Pre Ord e r( roo t 1 child);Pr e Ord e r ( r oot- r c hild);)p rintf (%c,r o ot- d at a );1四、M i cro s o f t v s6. 0五、源程序(带注释或说明)、运营结果(数据或屏幕显示、结果分析、讨论T(n)