數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告模板

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告書專業(yè)班級(jí)網(wǎng)133學(xué)號(hào)139074333姓名江文杰教師王喜鳳

實(shí)驗(yàn)一：用棧判斷字符串是否回文1.實(shí)驗(yàn)日期2015年4月11日2.實(shí)驗(yàn)?zāi)康臑榱烁玫乩斫鈼５暮x和應(yīng)用3.實(shí)驗(yàn)內(nèi)容用棧判斷字符串是否回文4.設(shè)計(jì)思路利用棧的特殊儲(chǔ)存方式來(lái)判斷字符串是否回文；5.主要程序代碼#include<iostream>#include<string>usingnamespacestd;classzhan{public: chardata; zhan*next; zhan(){next=NULL;}};classlinkzhan{public: chara[100]; zhan*top; linkzhan(){top=NULL;} voidcreate1(); intcreate2(); voidpaiduan(intnum);};voidlinkzhan::create1(){ inti=0; zhan*p; cout<<"請(qǐng)輸入字符串(以#結(jié)束標(biāo)志)"<<endl; cin>>a;while(a[i]!='#') { p=newzhan; p->data=a[i]; p->next=top; top=p; i++; }}intlinkzhan::create2(){ zhan*p; inti=0,flag=1; while(top->data!=NULL) { p=newzhan; p=top; if(p->data!=a[i]) { flag=0; break; } top=top->next; deletep; i++; } returnflag;}voidmain(){ inta; linkzhanl; l.create1(); a=l.create2(); if(a==0)cout<<"該字符串不是回文結(jié)構(gòu)"<<endl; elseif(a==1)cout<<"該字符串是回文結(jié)構(gòu)"<<endl;} 6.運(yùn)行與測(cè)試心得或感想：通過(guò)本次試驗(yàn)我從中熟悉掌握了棧和隊(duì)列的特點(diǎn)，掌握與應(yīng)用棧和隊(duì)列的基本操作算法，訓(xùn)練和提高結(jié)構(gòu)化程序設(shè)計(jì)能力及程序調(diào)試能力。實(shí)驗(yàn)二1.實(shí)驗(yàn)日期2015年5月28日2.實(shí)驗(yàn)?zāi)康睦斫鈽涞慕Y(jié)構(gòu)3.實(shí)驗(yàn)內(nèi)容1、求二叉樹中度為1的結(jié)點(diǎn)數(shù)2、求結(jié)點(diǎn)在二叉排序樹中層次3、判斷此二叉樹是否是二叉排序樹4.設(shè)計(jì)思路利用樹的特性以及遞歸的思想進(jìn)行解題。每一個(gè)節(jié)點(diǎn)都可以看成一棵樹。主要程序代碼#include<iostream>#include<string>usingnamespacestd;classbonde{public: intdata; bonde*lchild,*rchild; bonde(){lchild=NULL;rchild=NULL;}};classtree{public: bonde*head; tree(){head=NULL;} ~tree(){deletetree(head);} voiddeletetree(bonde*current); bonde*createtree(); intchazhao(bonde*p);//求節(jié)點(diǎn)為一的節(jié)點(diǎn) intcengci(bonde*p,charnum1);//節(jié)點(diǎn)所在的層次 intpaixu(bonde*p);//判斷是否為二叉排序樹； intheight(bonde*p); intMAX(inta,intb) {if(a>b)returna; elsereturnb; }};bonde*tree::createtree(){bonde*p;charch;cin>>ch;if(ch=='0') p=NULL;else{p=newbonde;p->data=ch; p->lchild=createtree(); p->rchild=createtree();}head=p;returnp;}voidtree::deletetree(bonde*current){ if(current!=NULL) { deletetree(current->lchild);deletetree(current->rchild);deletecurrent; }}inttree::chazhao(bonde*p){intl,r;if(p==NULL)return0;//if(p->lchild==NULL&&p->rchild==NULL)return0;l=chazhao(p->lchild);r=chazhao(p->rchild);if(p->lchild==NULL||p->rchild==NULL) returnl+r+1;}inttree::cengci(bonde*p,charnum1){ if(p==NULL) return0; else { if(p->data==num1) returnMAX(cengci(p->lchild,num1),cengci(p->rchild,num1))+1; elsereturn0; }}inttree::paixu(bonde*p){ p=head; if(head>p->lchild||head<p->rchild||p!=NULL)return0; else { paixu(p->lchild); paixu(p->rchild); } return1;}voidmain(){intnum;charnum1; bonde*p=newbonde; treel; cout<<"請(qǐng)輸入樹:"<<endl; l.head=l.createtree();num=l.chazhao(l.head); cout<<"節(jié)點(diǎn)為1的"<<num<<endl; cout<<"請(qǐng)輸入你要查找的數(shù)"<<endl;cin>>num1; l.cengci(p,num1); cout<<"該節(jié)點(diǎn)在第"<<l.cengci(p,num1)<<"層次(0代表不是)"<<endl; l.paixu(l.head); cout<<"該二叉樹二叉排序樹是"<<l.paixu(l.head)<<"(0代表不是)"<<endl;}6.運(yùn)行與測(cè)試7.心得或感想遞歸的步驟很多要仔細(xì)，編寫是要注意遞歸與循環(huán)的互通之處。實(shí)驗(yàn)三：1.實(shí)驗(yàn)日期2015年6月1日2.實(shí)驗(yàn)?zāi)康臑榱烁玫乩斫飧鞣N排序算法和在數(shù)據(jù)很多的情況下所用的時(shí)間和二叉排序數(shù)3.實(shí)驗(yàn)內(nèi)容試編寫程序：從鍵盤隨機(jī)輸入（或隨機(jī)產(chǎn)生）20個(gè)整數(shù)（1）用順序查找算法查找給定的某個(gè)數(shù)（2）對(duì)20個(gè)排序后進(jìn)行折半查找（3）建立這20個(gè)數(shù)的二叉排序樹，并進(jìn)行查找。從鍵盤輸入（或隨機(jī)數(shù)產(chǎn)生）20個(gè)數(shù)，試用下列算法進(jìn)行排序（1）直接插入排序（2）直接選擇排序（3）快速排序（4）歸并排序（5）堆排序（可選）4.設(shè)計(jì)思路利用不同的排序?qū)崿F(xiàn)主要程序代碼#include<iostream>#include<ctime>#include<cstdlib>usingnamespacestd;classadc{ public: intlength; intdata[100]; intsuiji(); intzhijie(intk); voidpaixu1();//直接插入排序 voidpaixu2();//直接選擇排序 voidpaixu3(intdata[100],intn);//快速排序 voidpaixu4(intdata[100],intn);//歸并排序 voidpaixu5();//堆排序 intchaozhao(intk); intpartition(intdata[100],intlow,inthigh); voidqsort(intdata[100],ints,intt); voidmsort(intdata[100],ints,intt);};intadc::suiji(){ doublerandom(double,double);srand(unsigned(time(0)));for(inti=1;i<=20;i++) { data[i]=int(random(0,100));cout<<"No."<<i<<":"<<data[i]<<endl; }return0;}doublerandom(doublestart,doubleend){returnstart+(end-start)*rand()/(RAND_MAX+1.0);}intadc::zhijie(intk){ inti=1; for(i=1;i<20;i++) if(data[i]==k){returni;} return-1;}voidadc::paixu1(){ inti,j; for(i=2;i<=20;i++) { data[0]=data[i]; for(j=i-1;data[0]<data[j];j--) data[j+1]=data[j]; data[j+1]=data[0]; } for(i=1;i<=20;i++) cout<<"No."<<i<<":"<<data[i]<<endl;}intadc::chaozhao(intk){ intlow,high,mid; low=0; high=20; while(low<=high) { mid=(low+high)/2; if(k==data[mid]) returnmid; elseif(k<data[mid]) high=mid-1; else low=mid+1; } return-1;}voidadc::paixu2(){ inti,j; for(i=1;i<=20;i++) { for(j=i+1;j<=20;j++) { if(data[j]<data[i]) {data[-1]=data[j];data[j]=data[i];data[i]=data[-1];} } }for(i=1;i<=20;i++)cout<<"No."<<i<<":"<<data[i]<<endl;}intadc::partition(intdata[100],intlow,inthigh){if(low==high)returnlow; data[0]=data[low]; while(low<high) { while(low<high&&data[high]>=data[0])high--; if(low<high){data[low]=data[high];low++;} while(low<high&&data[low]<=data[0])low++; if(low<high){data[high]=data[low];high--;} }data[low]=data[0];returnlow;}voidadc::qsort(intdata[100],ints,intt){ inti; if(s>=t)return; i=partition(data,s,t); qsort(data,s,i-1); qsort(data,i+1,t);}voidadc::paixu3(intdata[100],intn){ qsort(data,1,n); for(inti=1;i<=20;i++) cout<<"No."<<i<<":"<<data[i]<<endl;}voidmer(intdata[100],intdata1[100],ints,intm,intt){ inti,j,k; i=s;j=m+1;k=s; while(i<=m&&j<=t) if(data[i]<=data[j]){data1[k]=data[i];i++;k++;} else{data1[k]=data[j];j++;k++;} while(i<=m)data1[k++]=data[i++]; while(j<=t)data1[k++]=data[j++];}voidadc::msort(intdata[100],ints,intt){ intdata1[100]; intm; if(s==t)return; else { m=(s+t)/2; msort(data,s,m); msort(data,m+1,t); mer(data,data1,s,m,t); mer(data1,data,s,t,t); }}voidadc::paixu4(intdata[100],intn){ msort(data,1,n); for(inti=1;i<=20;i++) cout<<"No."<<i<<";"<<data[i]<<endl;}intmain(){intk,p; adca; a.suiji(); cout<<"輸入查找的數(shù)"<<endl; cin>>k;intl=a.zhijie(k); cout<<"在第No:"<<l<<"個(gè)位置""（-1表示未找到）"<<endl;cout<<"排序之后"<<endl; a.paixu1();cout<<"輸入查找的數(shù)"<<endl; cin>>p; cout<<"在第"<<a.chaozhao(p)<<"個(gè)位置"<<endl; cout<<"隨機(jī)產(chǎn)生20個(gè)數(shù)"<<endl; a.suiji(); cout<<"排序之后"<<endl; a.paixu3(a.data,20); cout<<"隨機(jī)產(chǎn)生20個(gè)數(shù)"<<endl; a.suiji(); cout<<"排序之后"<<endl; a.paixu4(a.data,20);}intmain(){ time_tst_t=time(NULL),ed_t;adca; a.suiji(); a.paixu1();ed_t=time(NULL);cout<<(double)(ed_t-st_t)/CLOCKS_PER_SEC<<endl;}intmain(){ time_tst_t=time(NULL),ed_t;adca; a.suiji(); a.paixu2();ed_t=time(NULL);cout<<(double)(ed_t-st_t)/CLOCKS_PER_SEC<<endl;}intmain(){ time_tst_t=time(NULL),ed_t;adca; a.suiji(); a.paixu3(a.data,n);ed_t=time(NULL);cout<<(double)(ed_t-st_t)/CLOCKS_PER_SEC<<endl;}intmain(){ time_tst_t=time(NULL),ed_t;adca; a.suiji(); a.paixu4(a.data,n);ed_t=time(NULL);cout<<(double)(ed_t-st_t)/CLOCKS_PER_SEC<<endl;}二叉排序樹：#include<iostream>usingnamespacestd;classbinstreenode{public: intdata; binstreenode*lchild;binstreenode*rchild; binstreenode(){lchild=NULL;rchild=NULL;}};classbinstree{public: binstreenode*head; binstree(){head=NULL;}binstreenode*serach(binstreenode*bt,intk,binstreenode*&p);voidinsert(binstreenode*&bt,intk); voidcreate(intnum);};binstreenode*binstree::serach(binstreenode*bt,intk,binstreenode*&p){ binstreenode*q; q=bt;while(bt){ q=bt; if(bt->data==k){p=bt;returnbt;} elseif(bt->data>k)bt=bt->lchild;