河北工業(yè)大學(xué)2014數(shù)據(jù)結(jié)構(gòu)實驗報告

河北工業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2014版實驗報告實驗一、約瑟夫環(huán)【源代碼】#include<stdio.h>#include<stdlib.h>structLnode{intnumber;intpassword;structLnode*next;}Lnode,*p,*q;intmain(){intn;inti;intm;intj;printf("pleaseenterthenumberofpeoplen:");scanf("%d",&n);if(n<=0||n>30){printf("niserorr!\n");printf("pleaseenterthenumberofpeopleagain:");scanf("%d",&n);}for(i=1;i<=n;i++){if(i==1){p=q=(structLnode*)malloc(sizeof(structLnode));}else{ q->next=(structLnode*)malloc(sizeof(structLnode));q=q->next;}printf("pleaseenterthe%dpeople'spassword:",i);scanf("%d",&(q->password));q->number=i;}q->next=p;printf("pleaseenterthenumberm:");scanf("%d",&m);printf("Thepasswordis:\n");for(j=1;j<=n;j++){for(i=1;i<=m-1;i++) {q=p;p=p->next;}m=p->password;printf("%d",p->number);q->next=p->next;free(p);p=q->next;}printf("\n");}【實驗感想】這次編寫約瑟夫環(huán)程序雖然用了很長時間，但是當(dāng)程序正確運行的時候，真的感覺特別開心！我一邊畫圖，一邊分析，一邊調(diào)試，在許多次的調(diào)試過程中，我注意到了好多問題，有很多細(xì)節(jié)真的是有一點不對就會滿盤皆輸，而且每次感覺能成功編好的情況下，把代碼敲進(jìn)機(jī)器卻總是得不到正確的答案，感覺很郁悶，也想放棄過，但是最后還是堅持下來了。總共用了一天的時間?？赡苁且驗槲艺n本知識掌握的不扎實，而且很久沒有編寫程序了，第一次上機(jī)感覺有困難。編代碼的時候走了好多彎路，其中有一個彎路就是我設(shè)立了一個頭節(jié)點，然后還自以為很聰明的把頭節(jié)點繞了過去，等等。很多類似的錯誤，都是以前覺得自己沒問題，一上機(jī)才知道原來還存在很多問題。這是第一次數(shù)據(jù)結(jié)構(gòu)上機(jī)課，以前跟老師上課的時候總是感覺對這種類C語言很陌生，不像和以前學(xué)C/C++語言那樣，書上的程序一看就知道什么意思，而且這些算法是包含思想的，必須要自己想的特別明白。簡單總結(jié)一下思路：我覺得程序大致分三塊是用結(jié)構(gòu)體定義節(jié)點類型，每個節(jié)點有3個域，兩個數(shù)據(jù)域，一個指針域定義好節(jié)點之后，利用指針形成鏈表，但有一點要注意就是不需要頭節(jié)點，并且最后一個節(jié)點的指針要指向第一個節(jié)點，從而構(gòu)成循環(huán)鏈表刪除節(jié)點，但關(guān)鍵點是指針的位置一定要移動正確，我覺得這部分一定要想的非常明白才能正確的編出程序通過這次編程，首先我把約瑟夫環(huán)問題的算法弄的非常明白，也通過實驗夯實了課內(nèi)學(xué)到的許多知識，在計算機(jī)上得到了印證，現(xiàn)在對于定義鏈表還有對節(jié)點進(jìn)行刪除、插入操作也弄的非常明白?？傊蠙C(jī)能很好的鞏固上課學(xué)到的知識，正確的編出程序也會覺得很有成就感，很開心，收獲頗多！實驗二、停車場管理【源代碼】#include<iostream>#definen2//將停車場的容量設(shè)為2#definecost10//將單位時間的停車費設(shè)為10，車道里不收費#defineOVERFLOW-2#defineERROR0//分配棧的存儲空間失?。籾singnamespacestd;typedefstructElem{//定義元素數(shù)據(jù)結(jié)構(gòu)類型intcarnum;inttime;}Elem;typedefstructQNode{//隊列structQNode*next;ElemQelem;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//隊頭指針QueuePtrrear;//隊尾指針}LinkQueue;voidinitqueue(LinkQueue&Q){//構(gòu)造一個空隊列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=Q.rear->next=NULL;}voidenqueue(LinkQueue&Q,intcarnum,inttime){//入隊操作QueuePtrp=(QueuePtr)malloc(sizeof(QNode));p->Qelem.carnum=carnum;p->Qelem.time=time;p->next=NULL;Q.rear->next=p;Q.rear=p;}intlengthqueue(LinkQueueQ){ inti=0; QueuePtrp; p=Q.front->next; while(p!=Q.rear) { i++; p=p->next; } i++; returni;}voiddequeue(LinkQueue&Q,Elem&e){//從對頭離隊操作，并返回其值QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(Q.front==Q.rear) cout<<"車道中沒有車輛"<<endl;if(Q.front!=Q.rear){p=Q.front->next;e=p->Qelem;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);}}typedefstruct{ Elem*base; Elem*top; intstacksize;}Sqstack;voidinitStack(Sqstack&S){//創(chuàng)建一個空棧 S.base=(Elem*)malloc(n*sizeof(Elem)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=n;}intpush(Sqstack&S,Elem&e)//插入新的元素{ Elem*temp; if(S.top-S.base==S.stacksize) return1; else { temp=S.top; temp->carnum=e.carnum; temp->time=e.time; S.top++; return0; }}intlengthstack(SqstackS){//當(dāng)前棧的長度 returnS.top-S.base;}intpop(Sqstack&S,Elem&e){//刪除棧頂元素，并返回其值if(S.top==S.base)returnERROR; e=*--S.top; return1;}voidcarin(Sqstack&S,LinkQueue&Q,Elemcar){ intk=0;//輸入數(shù)據(jù)正確 QueuePtrr; Elem*temp; temp=S.base; while(temp!=S.top)//在棧中尋找是否有同一編號的車； { if(temp->carnum==car.carnum) { cout<<"該車號在停車場中已存在，請重新輸入"<<endl; k=1;//找到了有同一編號的車 break; } temp++; } if(k==0&&Q.front!=Q.rear) {//在棧中未找到，從隊列中查找 r=Q.front->next;//隊頭 while(r&&r->Qelem.carnum!=car.carnum) {r=r->next;} if(r&&r->Qelem.carnum==car.carnum){cout<<"該車號在車道中已存在,請重新輸入"<<endl;k=1;} } if(k==0)//說明經(jīng)檢查輸入數(shù)據(jù)正確； { if(S.top-S.base!=S.stacksize)//說明棧未滿， { S.top->carnum=car.carnum; S.top->time=car.time; S.top++; cout<<"請進(jìn)入停車場"<<lengthstack(S)<<"號車位"<<endl; } else { enqueue(Q,car.carnum,car.time); cout<<"請進(jìn)入便道"<<lengthqueue(Q)<<"號車位"<<endl; } }}voidcarleave(Sqstack&S,LinkQueue&Q,Elemcar){ intture=0;//在棧中沒有找到與要離開的車 Eleme,em,*temp;QueuePtrp,r; temp=S.base; if(ture==0) { while(temp!=S.top)//先在棧中尋找； {if(temp->carnum==car.carnum) { inttemp_cost; temp_cost=(car.time-temp->time)*cost; ture=1;//在棧中找到 cout<<"您的停車時間為"<<car.time-temp->time<<"請交納費用"<<temp_cost<<endl; break; } temp++; } if(ture==1)//備用棧 { Sqstackspear; initStack(spear); while(S.top!=temp+1)//先在棧中尋找； { pop(S,em); push(spear,em); } pop(S,*temp); if(spear.top!=spear.base) { while(spear.top!=spear.base) { pop(spear,em); push(S,em); } } } if(ture==1&&Q.front!=Q.rear)//棧中有車離開，將隊列中的車進(jìn)入棧中 { dequeue(Q,e);//離隊，并返回數(shù)據(jù)e S.top->carnum=e.carnum; S.top->time=car.time; S.top++; cout<<endl<<"請便道車牌號為"<<e.carnum<<"號車轉(zhuǎn)入停車場停車起始時間是"<<car.time<<"停車位置為"<<lengthstack(S)<<endl; } } if(ture==0&&Q.front!=Q.rear)//棧中沒找到要離開的車 { p=Q.front; r=Q.front->next;//隊頭 while(r&&r->Qelem.carnum!=car.carnum) { p=r; r=r->next; } if(r&&r->Qelem.carnum==car.carnum) ture=2;//在隊列中找到要離開的車 if(r&&r->Qelem.carnum==car.carnum) { ture=2; cout<<"便道"<<r->Qelem.carnum<<"號車離開,不收取費用"<<endl; p->next=r->next; free(r); } }//直接從隊列離開 if(ture==0) cout<<"沒有該輛車"<<endl;}intmain(){ charc; intj=0,temp_time,i=1;//i==0，判斷臨時記錄時間的temp_time應(yīng)該去該次的值，還是上次的值。j==0，表示第一次輸入數(shù)據(jù)，不需要檢測數(shù)據(jù)是否正確 LinkQueueQ; SqstackS; Elemcar; initqueue(Q); initStack(S); cout<<"請輸入車輛信息（到達(dá)離開或退出標(biāo)志ADE，車牌號，當(dāng)前時間）"<<endl; while(cin>>c>>car.carnum>>car.time) { if(j==1) { if(S.top==S.base) cout<<"停車場中沒有車"<<endl; else { temp_time=car.time; i=1; } if(i==1)//正確的數(shù)據(jù) { if(c=='A')//到達(dá) carin(S,Q,car); elseif(c=='D') { if(S.top==S.base); else carleave(S,Q,car); } } j=1; } if(j==0)//第一次輸入數(shù)據(jù)不需要檢測 { if(c=='A')//到達(dá) carin(S,Q,car); elseif(c=='D') { if(S.top==S.base) cout<<"停車場中沒有車"<<endl; else carleave(S,Q,car); } j=1; temp_time=car.time; } if(c=='E') { cout<<"輸入結(jié)束"<<endl; break; } } return0;}【實驗心得】本次實驗較復(fù)雜，應(yīng)先梳理好思路，把整個大程序分成三個小模塊，最后拼接起來，再進(jìn)行整體調(diào)試與分析。模塊一：Carin函數(shù)：如果車來，判斷停車場（棧1）是否滿。不滿則壓入停車場；滿則進(jìn)隊列模塊二：Carleave函數(shù)：如果車離開，首先判斷車的位置。先在停車場進(jìn)行遍歷，如果找到此車，則彈出此車上方的車輛，壓入另一個棧（棧2），計算此車的時間以及金錢，并刪除此車輛，再把棧2的車輛彈出，壓入棧1，再讓隊頭元素出隊列，壓入棧中；若停車場中沒有遍歷到該車輛，則繼續(xù)在隊列中遍歷，找到此車輛之后，刪除此車輛即可模塊三：main函數(shù)：判斷A、D、EA：調(diào)用carin函數(shù)B：調(diào)用carleave函數(shù)E：輸入結(jié)束End還有幾個實驗中需要用到的函數(shù)：Initstack函數(shù)//生成一個棧Stacklength函數(shù)//計算棧的長度Pop函數(shù)//元素出棧Push函數(shù)//元素進(jìn)棧Initqueue函數(shù)//生成一個隊列Queuelength函數(shù)//計算隊列長度Enqueue函數(shù)//進(jìn)隊列Dequeue函數(shù)//出隊列實驗三、哈夫曼編/譯碼器【源程序】#include<iostream.h>#include<iomanip.h>#include<string.h>#include<malloc.h>#include<stdio.h>constintUINT_MAX=1000;charstr[50];typedefstruct{intweight,K;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;HuffmanTreeHT;HuffmanCodeHC;intw[50],i,j,n;charz[50];intflag=0;intnumb=0;//求哈夫曼編碼structcou{chardata;intcount;}cou[50];intmin(HuffmanTreet,inti){intj,flag;intk=UINT_MAX;for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;returnflag;}voidselect(HuffmanTreet,inti,int&s1,int&s2){intj;s1=min(t,i);s2=min(t,i);if(s1>s2){j=s1;s1=s2;s2=j;}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start;intc,f;HuffmanTreep;char*cd;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p)p->parent=0;for(i=n+1;i<=m;++i)//建哈夫曼樹{select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間strcpy(HC[i],&cd[start]);}free(cd);}//---------------------獲取報文并寫入文件---------------------------------intInputCode(){FILE*tobetran;if((tobetran=fopen("tobetran.txt","w"))==NULL){cout<<"不能打開文件"<<endl;return0;}cout<<"請輸入你想要編碼的字符"<<endl;gets(str);fputs(str,tobetran);cout<<"獲取報文成功"<<endl;fclose(tobetran);returnstrlen(str);}//--------------初始化哈夫曼鏈表---------------------------------voidInitialization(){inta,k,flag,len;a=0;len=InputCode();for(i=0;i<len;i++){k=0;flag=1;cou[i-a].data=str[i];cou[i-a].count=1;while(i>k){if(str[i]==str[k]){a++;flag=0;}k++;if(flag==0)break;}if(flag){for(j=i+1;j<len;j++){if(str[i]==str[j])++cou[i-a].count;}}}n=len-a;for(i=0;i<n;i++){cout<<cou[i].data<<"";cout<<cou[i].count<<endl;}for(i=0;i<=n;i++){*(z+i)=cou[i].data;*(w+i)=cou[i].count;}HuffmanCoding(HT,HC,w,n);//------------------------打印編碼-------------------------------------------cout<<"字符對應(yīng)的編碼為:"<<endl;for(i=1;i<=n;i++){puts(HC[i]);}//--------------------------將哈夫曼編碼寫入文件------------------------FILE*htmTree;charr[]={'','\0'};if((htmTree=fopen("htmTree.txt","w"))==NULL){cout<<"cannotopenfile"<<endl;return;}fputs(z,htmTree);for(i=0;i<n+1;i++){fprintf(htmTree,"%6d",*(w+i));fputs(r,htmTree);}for(i=1;i<=n;i++){fputs(HC[i],htmTree);fputs(r,htmTree);}fclose(htmTree);cout<<"已成功將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt中"<<endl;}//---------------------編碼函數(shù)---------------------------------voidEncoding(){cout<<"下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼"<<endl;FILE*tobetran,*codefile;if((tobetran=fopen("tobetran.txt","rb"))==NULL){cout<<"不能打開文件"<<endl;}if((codefile=fopen("codefile.txt","wb"))==NULL){cout<<"不能打開文件"<<endl;}char*tran;i=99;tran=(char*)malloc(100*sizeof(char));while(i==99){if(fgets(tran,100,tobetran)==NULL){cout<<"不能打開文件"<<endl;break;}for(i=0;*(tran+i)!='\0';i++){for(j=0;j<=n;j++){if(*(z+j-1)==*(tran+i)){fputs(HC[j],codefile);if(j>n){cout<<"字符錯誤，無法編碼!"<<endl;break;}}}}}cout<<"編碼工作完成"<<endl<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl;fclose(tobetran);fclose(codefile);free(tran);}//-----------------譯碼函數(shù)---------------------------------voidDecoding(){cout<<"下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼"<<endl;FILE*codef,*txtfile;if((txtfile=fopen("txtfile.txt","w"))==NULL){cout<<"不能打開文件"<<endl;}if((codef=fopen("codefile.txt","r"))==NULL){cout<<"不能打開文件"<<endl;}char*work,*work2,i2;inti4=0,i,i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char));fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char));i3=2*n-1;for(i=0;*(work+i-1)!='\0';i++){i2=*(work+i);if(HT[i3].lchild==0){*(work2+i4)=*(z+i3-1);i4++;i3=2*n-1;i--;}elseif(i2=='0')i3=HT[i3].lchild;elseif(i2=='1')i3=HT[i3].rchild;}*(work2+i4)='\0';fputs(work2,txtfile);cout<<"譯碼完成"<<endl<<"內(nèi)容寫入根目錄下的文件txtfile.txt中"<<endl<<endl;free(work);free(work2);fclose(txtfile);fclose(codef);}//-----------------------打印編碼的函數(shù)----------------------voidCode_printing(){cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl;FILE*CodePrin,*codefile;if((CodePrin=fopen("CodePrin.txt","w"))==NULL){cout<<"不能打開文件"<<endl;return;}if((codefile=fopen("codefile.txt","r"))==NULL){cout<<"不能打開文件"<<endl;return;}char*work3;work3=(char*)malloc(51*sizeof(char));do{if(fgets(work3,51,codefile)==NULL){cout<<"不能讀取文件"<<endl;break;}fputs(work3,CodePrin);puts(work3);}while(strlen(work3)==50);free(work3);fclose(CodePrin);fclose(codefile);}//-------------------------------打印譯碼函數(shù)---------------------------------------------voidCode_printing1(){cout<<"下面打印根目錄下文件txtfile.txt中譯碼字符"<<endl;FILE*CodePrin1,*txtfile;if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL){cout<<"不能打開文件"<<endl;return;}if((txtfile=fopen("txtfile.txt","r"))==NULL){cout<<"不能打開文件"<<endl;return;}char*work5;work5=(char*)malloc(51*sizeof(char));do{if(fgets(work5,51,txtfile)==NULL){cout<<"不能讀取文件"<<endl;break;}fputs(work5,CodePrin1);puts(work5);}while(strlen(work5)==50);free(work5);fclose(CodePrin1);fclose(txtfile);}//------------------------打印哈夫曼樹的函數(shù)-----------------------voidcoprint(HuffmanTreestart,HuffmanTreeHT){if(start!=HT){FILE*TreePrint;if((TreePrint=fopen("TreePrint.txt","a"))==NULL){cout<<"創(chuàng)建文件失敗"<<endl;return;}numb++;coprint(HT+start->rchild,HT);cout<<setw(5*numb)<<start->weight<<endl;fprintf(TreePrint,"%d\n",start->weight);coprint(HT+start->lchild,HT);numb--;fclose(TreePrint);}}voidTree_printing(HuffmanTreeHT,intw){HuffmanTreep;p=HT+w;cout<<"下面打印哈夫曼樹"<<endl;coprint(p,HT);}//------------------------主函數(shù)------------------------------------voidmain(){charchoice;while(choice!='q'){cout<<"******************************"<<endl;cout<<"歡迎使用哈夫曼編譯碼器系統(tǒng)"<<endl;cout<<"******************************"<<endl;cout<<"(1)初始化哈夫曼鏈表請輸入'I'"<<endl;cout<<"(2)編碼請輸入'E'"<<endl;cout<<"(3)譯碼請輸入'D'"<<endl;cout<<"(4)打印編碼請輸入'P'"<<endl;cout<<"(5)打印譯碼請輸入'Y'"<<endl;cout<<"(6)打印哈夫曼樹請輸入'T'"<<endl;cout<<"******************************"<<endl;cin>>choice;switch(choice){case'I':Initialization();break;case'E':Encoding();break;case'D':Decoding();break;case'P':Code_printing();break;case'T':Tree_printing(HT,2*n-1);break;case'Y':Code_printing1();break;default:cout<<"inputerror"<<endl;}}free(z);free(w);free(HT);}【實驗結(jié)果】

【編程體會】再編了約瑟夫環(huán)和停車場管理兩個程序之后，發(fā)現(xiàn)現(xiàn)在寫的雖然都是綜合性很強(qiáng)的程序，似乎很有難度，但是大的程序都是很多小模塊拼起來的，就本次試驗來說，首先要寫好主函數(shù)，知道以后要解決哪些具體問題，然后再解決具體問題。主函數(shù)：初始化哈夫曼鏈表編碼譯碼打印編碼打印譯碼打印哈夫曼樹首先應(yīng)該定義節(jié)點和樹的結(jié)構(gòu)類型，然后針對2~6，把每一個問題具體化到一個函數(shù)，然后整合拼湊就可以完成實驗，只是最后再加一些修飾工作，讓程序看起來比較美觀。這次試驗遇到的最大的問題就是對于文件的知識掌握的不好，編程的時候帶來了大的麻煩，然后我找出上學(xué)期的課本好好復(fù)習(xí)了一下與文件有關(guān)的知識，一點一點的看明白，逐步解決問題?？傊看螌懘蟪绦蚨紩泻艽笫斋@，不僅能很好的復(fù)習(xí)鞏固以前所學(xué)的知識，還能培養(yǎng)細(xì)心地習(xí)慣，許多小錯誤都是由于粗心造成的，以后要多加注意。圖的遍歷【源程序】#include<stdio.h>#include<malloc.h>#include<stdlib.h>#defineMAX30typedefstructQNode{intdata;structQNode*next;}QNode;typedefstruct{QNode*rear;QNode*front;}LinkQueue;voidInitQueue(LinkQueue*Q){Q->front=Q->rear=(QNode*)malloc(sizeof(QNode));Q->front->next=NULL;}voidEnQueue(LinkQueue*Q,intv){QNode*p;p=(QNode*)malloc(sizeof(QNode));p->data=v;p->next=NULL;Q->rear->next=p;Q->rear=p;}voidDeQueue(LinkQueue*Q,int*v){QNode*p;if(Q->front==Q->rear)return;p=Q->front->next;*v=p->data;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);}typedefstructEdgeNode{intivex,jvex;structEdgeNode*ilink,*jlink;}EdgeNode;typedefstructVexNode{intmarkV;charinfo;//頂點信息intnum;//頂點編號EdgeNode*firstedge;}VexNode;typedefstruct{VexNodeadjlist[MAX];intvexnum,edgenum;}Graph;//初始化voidInitilized(Graph*graph){graph=(Graph*)malloc(sizeof(Graph));graph->vexnum=0;graph->edgenum=0;}//創(chuàng)建圖voidCreateGraph(Graph*graph){EdgeNode*p,*q,*e;inti;printf("請輸入連通無向圖的頂點個數(shù):");scanf("%d",&graph->vexnum);printf("請輸入連通無向圖的邊的條數(shù):");scanf("%d",&graph->edgenum);for(i=1;i<=graph->vexnum;i++){printf("請輸入第%d個頂點的信息：\n",i);scanf("%s",&graph->adjlist[i].info);graph->adjlist[i].num=i;graph->adjlist[i].firstedge=NULL;graph->adjlist[i].markV=0;}for(i=1;i<=graph->edgenum;i++){p=(EdgeNode*)malloc(sizeof(EdgeNode));printf("請輸入每條邊依附的兩個頂點(用頂點的編號表示)\n");scanf("%d%d",&p->ivex,&p->jvex);while(p->ivex==p->jvex||p->ivex<1||p->ivex>graph->vexnum||p->jvex<1||p->jvex>graph->vexnum){printf("輸入的頂點有誤，請重新輸入!\n");scanf("%d%d",&p->ivex,&p->jvex);}p->ilink=p->jlink=NULL;if(graph->adjlist[p->ivex].firstedge==NULL)graph->adjlist[p->ivex].firstedge=p;else{q=graph->adjlist[p->ivex].firstedge;while(q!=NULL){e=q;if(q->ivex==p->ivex)q=q->ilink;elseq=q->jlink;}if(e->ivex==p->ivex)e->ilink=p;elsee->jlink=p;}if(graph->adjlist[p->jvex].firstedge==NULL)graph->adjlist[p->jvex].firstedge=p;else{q=graph->adjlist[p->jvex].firstedge;while(q!=NULL){e=q;if(q->ivex==p->ivex)q=q->ilink;elseq=q->jlink;}if(e->ivex==p->ivex)e->ilink=p;elsee->jlink=p;}}}//設(shè)置訪問標(biāo)記voidSetMark(Graph*graph){inti;for(i=1;i<=graph->vexnum;i++)graph->adjlist[i].markV=0;}//深度遍歷voidDFS(Graph*graph,intv){EdgeNode*p;printf("%d",v);graph->adjlist[v].markV=1;p=graph->adjlist[v].firstedge;while(p!=NULL){if(p->ivex==v){if(graph->adjlist[p->jvex].markV==0){printf("<%d,%d>\n",p->ivex,p->jvex);DFS(graph,p->jvex);}p=p->ilink;}else{if(graph->adjlist[p->ivex].markV==0){printf("<%d,%d>\n",p->jvex,p->ivex);DFS(graph,p->ivex);}p=p->jlink;}}}//廣度遍歷voidBFS(Graph*graph,intu){LinkQueueQ;EdgeNode*p;InitQueue(&Q);printf("%d",u);graph->adjlist[u].markV=1;EnQueue(&Q,u);while(Q.front!=Q.rear){DeQueue(&Q,&u);p=graph->adjlist[u].firstedge;while(p!=NULL){if(p->ivex==u){if(graph->adjlist[p->jvex].markV==0){EnQueue(&Q,p->jvex);graph->adjlist[p->jvex].markV=1;printf("<%d,%d>\n",p->ivex,p->jvex);printf("%d",p->jvex);}p=p->ilink;}else{if(graph->adjlist[p->ivex].markV==0){EnQueue(&Q,p->ivex);graph->adjlist[p->ivex].markV=1;printf("<%d,%d>\n",p->jvex,p->ivex);printf("%d",p->ivex);}p=p->jlink;}}}}voidmain(){intu,v;Graphgraph;charorder;Initilized(&graph);CreateGraph(&graph);printf("輸入命令（C/c：重新創(chuàng)建連通無向圖T/t深度遍歷廣度遍歷E/e：結(jié)束）：\n");scanf("%s",&order);while(order!='E'&&order!='e'){switch(order){case'C':case'c':Initilized(&graph);CreateGraph(&graph);break;case'T':case't':printf("\n輸入深度廣度遍歷的起始點：\n");scanf("%d",&v);u=v;printf("\n深度遍歷序列及相應(yīng)的生成樹:\n頂點序列：生成樹邊集：\n");SetMark(&graph);DFS(&graph,v);printf("\n廣度遍歷序列及相應(yīng)生成樹：\n頂點序列：生成樹邊集：\n");SetMark(&graph);BFS(&graph,u);break;}printf("\n輸入命令（C：創(chuàng)建連通無向圖T/t：深度廣度遍歷E：結(jié)束）：\n");scanf("%s",&order);}}【實驗結(jié)果】【實驗體會】本次實驗比較簡單，需要用到的存儲結(jié)構(gòu)是鄰接多重鏈表，首先應(yīng)該會畫鄰接多重鏈表，其次應(yīng)該再畫的基礎(chǔ)上在計算機(jī)上用語言實現(xiàn)。只有把圖存進(jìn)計算機(jī)，才可以實現(xiàn)各種算法。深度優(yōu)先遍歷和廣度優(yōu)先遍歷需要使用到全局遍歷應(yīng)該提前定義好，深度優(yōu)先遍歷需要用到棧，因為這是一個遞歸算法；廣度優(yōu)先搜索需要用到隊列。本次實驗比較簡單，沒有遇到大的問題，就是圖的定義，存儲，全局變量定義，深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法的拼湊，即可完成程序。實驗五、查找1.源程序#include<iostream.h>#include<stdlib.h>#include<string.h>#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)>(b))typedefintKeytype;typedefstruct{Keytypekey;//關(guān)鍵字域}ElemType;typedefstructBSTnode{ElemTypedata;intbf;structBSTnode*lchild,*rchild;}BSTnode,*BSTree;voidInitBSTree(BSTree&T){T=NULL;}voidR_Rotate(BSTree&p){BSTnode*lc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}voidL_Rotate(BSTree&p){BSTnode*rc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}voidLeftbalance(BSTree&T){BSTnode*lc,*rd;lc=T->lchild;switch(lc->bf){case+1:T->bf=lc->bf=0;R_Rotate(T);break;case-1:rd=lc->rchild;switch(rd->bf){case1:T->bf=-1;lc->bf=0;break;case0:T->bf=lc->bf=0;break;case-1:T->bf=0;lc->bf=1;break;}rd->bf=0;L_Rotate(T->lchild);R_Rotate(T);}}voidRbalance(BSTree&T){BSTnode*lc,*ld;lc=T->rchild;switch(lc->bf){case1:ld=lc->lchild;switch(ld->bf){case1:T->bf=0;lc->bf=-1;break;case0:T->bf=lc->bf=0;break;case-1:T->bf=1;lc->bf=0;break;}ld->bf=0;R_Rotate(T->rchild);L_Rotate(T);case-1:T->bf=lc->bf=0;L_Rotate(T);break;}}intInsertAVL(BSTree&T,ElemTypee,bool&taller){if(!T){T=(BSTree)malloc(sizeof(BSTnode));T->data=e;T->lchild=T->rchild=NULL;T->bf=0;taller=true;}else{if(EQ(e.key,T->data.key)){taller=false;cout<<"結(jié)點"<<e.key<<"不存在。"<<endl;return0;}if(LT(e.key,T->data.key)){if(!InsertAVL(T->lchild,e,taller)){return0;}if(taller)switch(T->bf){case1:Leftbalance(T);taller=false;break;case0:T->bf=+1;taller=true;break;case-1:T->bf=0;taller=false;break;}}else{if(!InsertAVL(T->rchild,e,taller)){return0;}if(taller)switch(T->bf){case1:T->bf=0;taller=false;break;case0:T->bf=-1;taller=true;break;case-1:Rbalance(T);taller=false;break;}}}return1;}boolSearchBST(BSTreeT,ElemTypekey,BSTreef,BSTree&p){if(!T){p=f;cout<<"結(jié)點不存在。"<<endl;returnfalse;}elseif(EQ(key.key,T->data.key)){p=T;cout<<"查找成功，存在結(jié)點";cout<<p->data.key<<endl;returntrue;}elseif(LT(key.key,T->data.key))returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}voidLeftbalance_div(BSTree&p,int&shorter){BSTreep1,p2;if(p->bf==+1)//p結(jié)點的左子樹高，刪除結(jié)點后p的bf減1,樹變矮{p->bf=0;shorter=1;}elseif(p->bf==0)//p結(jié)點左、右子樹等高，刪除結(jié)點后p的bf減1,樹高不變{p->bf=-1;shorter=0;}else{p1=p->rchild;//p1指向p的右子樹if(p1->bf==0)//p1結(jié)點左、右子樹等高,刪除結(jié)點后p的bf為-2,進(jìn)行左旋處理，樹高不變{L_Rotate(p);p1->bf=1;p->bf=-1;shorter=0;}elseif(p1->bf==-1)//p1的右子樹高，左旋處理后，樹變矮{L_Rotate(p);p1->bf=p->bf=0;shorter=1;}else{p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){p->bf=0;p1->bf=0;}elseif(p2->bf==-1){p->bf=+1;p1->bf=0;}else{p->bf=0;p1->bf=-1;}p2->bf=0;p=p2;shorter=1;}}}voidRbalance_div(BSTree&p,int&shorter){BSTreep1,p2;if(p->bf==-1){p->bf=0;shorter=1;}elseif(p->bf==0){p->bf=+1;shorter=0;}else{p1=p->lchild;if(p1->bf==0){R_Rotate(p);p1->bf=-1;p->bf=+1;shorter=0;}elseif(p1->bf==+1){R_Rotate(p);p1->bf=p->bf=0;shorter=1;}else{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0){p->bf=0;p1->bf=0;}elseif(p2->bf==1){p->bf=-1;p1->bf=0;}else{p->bf=0;p1->bf=1;}p2->bf=0;p=p2;shorter=1;}}}voidDelete(BSTreeq,BSTree&r,int&shorter){if(r->rchild==NULL){q->data=r->data;q=r;r=r->lchild;free(q);shorter=1;}else{Delete(q,r->rchild,shorter);if(shorter==1)Rbalance_div(r,shorter);}}ElemTypeDeleteAVL(BSTree&p,ElemTypekey,int&shorter){ElemTypek,a,b;a.key=1;b.key=0;BSTreeq;if(p==NULL){cout<<"結(jié)點不存在。"<<endl;returnb;}elseif(LT(key.key,p->data.key))//在p的左子樹中進(jìn)行刪除{k=DeleteAVL(p->lchild,key,shorter);if(shorter==1)Leftbalance_div(p,shorter);returnk;}elseif(LQ(key.key,p->data.key))//在p的右子樹中進(jìn)行刪除{k=DeleteAVL(p->rchild,key,shorter);if(shorter==1)Rbalance_div(p,shorter);returnk;}else{q=p;if(p->rchild==NULL)//右子樹空則只需重接它的左子樹{p=p->lchild;free(q);shorter=1;}elseif(p->lchild==NULL)//左子樹空則只需重接它的右子樹{p=p->rchild;free(q);shorter=1;}else{Delete(q,q->lchild,shorter);if(shorter==1)Leftbalance_div(p,shorter);p=q;}returna;}}voidPrint_BSTTree(BSTreeT,inti){if(T){if(T->rchild)Print_BSTTree(T->rchild,i+1);for(intj=1;j<=i;j++)cout<<"";cout<<T->data.key<<endl;if(T->lchild)Print_BSTTree(T->lchild,i+1);}}intmain(){BSTreeT;ElemTypee;InitBSTree(T);booltall=false;boolchoice=true;chary;while(choice){cout<<"輸入要插入結(jié)點(數(shù)字):";cin>>e.key;InsertAVL(T,e,tall);Print_BSTTree(T,0);cout<<"是否繼續(xù)，是選y，否選n:";cin>>y;if(y=='Y'||y=='y')choice=true;elsechoice=false;}BSTreef,p;choice=true;while(choice){cout<<"輸入要查找的結(jié)點:";cin>>e.key;SearchBST(T,e,f,p);cout<<"是否繼續(xù)，是選y，否選n：";cin>>y;if(y=='Y'||y=='y')choice=true;elsechoice=false;}intshorter;choice=true;while(choice){cout<<"輸入要刪除的結(jié)點:";cin>>e.key;DeleteAVL(T,e,shorter);Print_BSTTree(T,0);cout<<"是否繼續(xù)，是選y，否選n：";cin>>y;if(y=='Y'||y=='y')choice=true;elsechoice=false;}return0;}2.實驗結(jié)果3.實驗體會通過本次實驗，我掌握了順序查找，折半查找以及二叉排序樹的建立，并能在二叉排序樹上進(jìn)行查找，插入，刪除操作。這次實驗采用的存儲結(jié)構(gòu)是二叉鏈表，通過建立二叉排序樹來進(jìn)行相應(yīng)的操作。初始狀態(tài)是建立一棵空樹，先插入節(jié)點，建立好二叉排序樹之后，每次插入和刪除都要更新二叉樹的顯示。感覺每次做數(shù)據(jù)結(jié)構(gòu)的實驗都不是很簡單，但是通過自己的努力，一點一點的弄明白每條語句并在計算機(jī)上實現(xiàn)成功的時候，都會十分欣喜，并且自己的編程能力也有了提高，以后要多寫算法，爭取達(dá)到熟能生巧的程度。實驗六、排序1.源程序#include<iostream.h>#include<malloc.h>#include<stdlib.h>#include<time.h>#defineLS(a,b)((a)<(b))#defineLL(a,b)((a)>(b))#defineMAXSIZE10000typedefintKeyType;typedefstruct{KeyTypekey;}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;intcompare=0;intchange=0;intCreate_Sq(SqList&L){intk;cout<<"請輸入隨機(jī)產(chǎn)生的元素個數(shù):";cin>>k;L.length=k;srand(time(NULL)); for(intx=1;x<=k;x++) { L.r[x].key=rand()%k; }return1;}voidBubble_sort(SqList&L)//起泡排序{cout<<endl<<"******************************"<<endl;inti,j,l,k=L.length,m=0,n=0;for(i=1;i<=L.length-1;++i){for(j=1;j<=k-1;++j){++m;if(LL(L.r[j].key,L.r[j+1].key)){l=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=l;++n;}}--k;}cout<<endl<<"起泡排序后的序列"<<endl;for(i=1;i<=L.length;i++)cout<<""<<L.r[i].key;cout<<endl;cout<<"起泡排序的比較次數(shù):";cout<<m<<endl;cout<<"起泡排序的交換次數(shù):";cout<<n<<endl;cout<<"******************************"<<endl<<endl;}voidInsertSort(