《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)書

目錄實(shí)驗(yàn)一線性表基本操作的編程實(shí)現(xiàn)......................201實(shí)驗(yàn)二堆?；蜿?duì)列基本操作的編程實(shí)現(xiàn)................49實(shí)驗(yàn)四二維數(shù)組基本操作的編程實(shí)現(xiàn)....................18實(shí)驗(yàn)五二叉樹基操作的編程實(shí)現(xiàn)............................20實(shí)驗(yàn)六圖基本操作的編程實(shí)現(xiàn)................................45（特別提示：程序設(shè)計(jì)包含兩個(gè)方面的錯(cuò)誤。其一是錯(cuò)誤，其二是能錯(cuò)誤。為了提高學(xué)生的編程和能力，本完整性，有一些語句已經(jīng)故意刪除，就是要求學(xué)生自己編礎(chǔ)，不要過于依賴給出的參考代碼，這樣才能有所進(jìn)步。如果學(xué)生能夠根據(jù)要求完全自己編制，那就不好了。）指導(dǎo)書給出的程序代碼并的兩種錯(cuò)誤。并且也不保證程序的制完成，這樣才能達(dá)到我們的要求。希望大家以自己所學(xué)高級語言的基本功和點(diǎn)為基

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)一線性表基本操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹烤€性表基本操作的編程實(shí)現(xiàn)要求：線性表基本操作的編程實(shí)現(xiàn)（2學(xué)時(shí)，驗(yàn)證型），掌握線性表的建立查找、逆序、排序等操作，存儲(chǔ)結(jié)構(gòu)可以功能，也可以用菜單進(jìn)行管理完成大部分功能。還鼓勵(lì)學(xué)生利用、遍歷、插入、刪除等基本操作的編程實(shí)現(xiàn)，也可以進(jìn)一步編程實(shí)現(xiàn)在順序結(jié)構(gòu)或鏈表結(jié)分主要基本操作進(jìn)行一些更實(shí)際的應(yīng)用型程序設(shè)計(jì)?！緦?shí)驗(yàn)性質(zhì)】【實(shí)驗(yàn)內(nèi)容】把線性表的順序存儲(chǔ)和鏈表存儲(chǔ)的數(shù)據(jù)插入、刪除運(yùn)算其中某項(xiàng)進(jìn)行程序?qū)崿F(xiàn)。建議實(shí)現(xiàn)鍵盤輸入數(shù)據(jù)以實(shí)現(xiàn)程序的通據(jù)的函數(shù)?！咀⒁馐马?xiàng)】【思考問題】1.線性表的順序存儲(chǔ)和鏈表存儲(chǔ)的差異？優(yōu)缺點(diǎn)分析？2.那些操作引發(fā)了數(shù)據(jù)的移動(dòng)？3.算法的時(shí)間效率是如何體現(xiàn)的？4.鏈表的指針是如何后移的？如何加強(qiáng)程序的健壯性？【參考代碼】（一）利用順序表完成一個(gè)班級學(xué)生課程成績的簡單管理1、預(yù)定義以及順序表結(jié)構(gòu)類型的定義(1)#defineListSize//根據(jù)需要自己設(shè)定一個(gè)班級能夠容納的最大學(xué)生數(shù)(2)typedefstructStu{intnum;//學(xué)生的學(xué)號(hào)charname[10];//學(xué)生的姓名floatwuli;//物理成績floatshuxue;//數(shù)學(xué)成績floatyingyu;//英語成績}STUDENT;//存放單個(gè)學(xué)生信息的結(jié)構(gòu)體類型typedefstructList{stu[ListSize];//存放學(xué)生的數(shù)組定義，靜態(tài)分配空間intlength;//記錄班級實(shí)際學(xué)生個(gè)數(shù)//存放班級學(xué)生信息的順序表類型}LIST;1《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書2、建立班級的學(xué)生信息voidlistcreate(LIST*Li,intm)//m為該班級的實(shí)際人數(shù){inti;Li->length=0;for(i=0;i<m;i++)//輸入m個(gè)學(xué)生的所有信息{printf("pleaseinputthe%dthstudent'sinfoprintf("num=");scanf("%d",);//輸入第i個(gè)學(xué)生的學(xué)號(hào)printf("name=");scanf("%s",);//輸入第i個(gè)學(xué)生的姓名printf("wuli=");scanf("%f",);//輸入第i個(gè)學(xué)生的物理成績printf("shuxue=");scanf("%f",);//輸入第i個(gè)學(xué)生的數(shù)學(xué)成績printf("yingyu=");scanf("%f",);//輸入第i個(gè)學(xué)生的英語成績Li->length++;//學(xué)生人數(shù)加1}}3、插入一個(gè)學(xué)生信息intlistinsert(LIST*Li,inti)//將學(xué)生插入到班級Li的第i個(gè)位置。{intj;STUDENTe;if()//測試存儲(chǔ)空間是否被占滿{printf("無更多的存儲(chǔ)空間!\n");return0;}if()//插入位置檢驗(yàn)，如果錯(cuò)誤就返回0退出程序。return0;else{printf("請輸入插入的學(xué)生信息:");printf("num=");scanf("%d",&e.num);printf("name=");scanf("%s",);printf("wuli=");scanf("%f",&e.wuli);2《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書printf("shuxue=");scanf("%f",&e.shuxue);printf("yingyu=");scanf("%f",&e.yingyu);for(j=;j>=;j--)/從i位置到最后的元素依次往后移動(dòng)Li->stu[j+1]=Li->stu[j];=e;//學(xué)生e放入到i位置Li->length++;//學(xué)生實(shí)際人數(shù)加1return1;}}4、刪除一個(gè)學(xué)生信息intlistdel(LIST*Li,inti)//刪除第i個(gè)學(xué)生的信息{intj;if()//刪除位置檢驗(yàn)，如果錯(cuò)誤就返回0退出程序。return0;else{for(j=;j<;j++)//從刪除位置后一個(gè)到最后的元素依次往前移動(dòng)Li->stu[j-1]=Li->stu[j];Li->length--;return1;}}5、顯示所有學(xué)生信息voidlistdisplay(LISTL){inti;printf("班級學(xué)生信息如下:\n");for(i=0;i<;i++)printf("%10d[學(xué)號(hào)]%10s[姓名]%10.2f[物理成績]%10.2f[數(shù)學(xué)成績]%10.2f[英語成績]\n",L.stu[i].num,L.stu[i].name,L.stu[i].wuli,yu);}6、編寫主函數(shù)main，要求測試以上所編寫的listcreat、listinsert、listdel和listdisplayvoidmain()//自己設(shè)計(jì)主函數(shù)完成3《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書{}（二）利用單鏈表完成一個(gè)班級學(xué)生課程成績的簡單管理1、單鏈表結(jié)構(gòu)體類型的定義typedefstructStu{intnum;//學(xué)生的學(xué)號(hào)charname[10];//學(xué)生的姓名floatwuli;//物理成績floatshuxue;//數(shù)學(xué)成績floatyingyu;//英語成績}STUDENT;//存放單個(gè)學(xué)生信息的結(jié)構(gòu)體類型typedefstructSnode{STUDENTdata;//結(jié)點(diǎn)的值structSnode*link;//指向下一個(gè)結(jié)點(diǎn)的地址}SNODE;2、建立班級學(xué)生信息SNODE*listcreate(intn)//n為該班級的實(shí)際人數(shù){inti;SNODE*head,*p,*q;4《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書if(n==0)returnNULL;//如果要?jiǎng)?chuàng)建的是空表，返回NULLhead=p=(SNODE*)malloc(sizeof(SNODE));//動(dòng)態(tài)建立第一個(gè)結(jié)點(diǎn)，head指針指向printf("pleaseinputthe1thstudent'sinformaprintf("num=");scanf("%d",&p->data.num);//輸入第1個(gè)學(xué)生的學(xué)號(hào)printf("name=");scanf("%s",p->);//輸入第1個(gè)學(xué)生的姓名printf("wuli=");scanf("%f",&p->data.wuli);//輸入第1個(gè)學(xué)生的物理成績printf("shuxue=");scanf("%f",&p->data.shuxue);輸入第1個(gè)學(xué)生的數(shù)學(xué)成績printf("yingyu=");scanf("%f",&p->data.yingyu);輸入第1個(gè)學(xué)生的英語成績for(i=1;i<n;i++)//插入剩下的n-1個(gè)學(xué)生{printf("\nThe%dthelement'sdata:\n",i+1);q=(SNODE*)malloc(sizeof(SNODE));printf("num=");scanf("%d",&q->data.num);printf("name=");scanf("%s",q->);printf("wuli=");scanf("%f",&q->data.wuli);printf("shuxue=");scanf("%f",&q->data.shuxueprintf("yingyu=");scanf("%f",&q->data.yingyuq->link=NULL;}}3、插入一個(gè)學(xué)生信息intlistinsert(SNODE**Li_head,inti)//將學(xué)生插入到班級Li_head的第i個(gè)位置。{SNODE*p,*q,*newsnode;intm=0;//用來統(tǒng)計(jì)學(xué)生位置if(i<1)return0;//插入位置檢驗(yàn)，如果錯(cuò)誤就返回0退出程序newsnode=(SNODE*)malloc(sizeof(SNODE));//產(chǎn)生新結(jié)點(diǎn)printf("pleaseinputthenewstudent'sinformaprintf("num=");scanf("%d",&newsnode->data.numprintf("name=");scanf("%s",newsnode->printf("wuli=");scanf("%f",&newsnode->data.wulprintf("shuxue=");scanf("%f",&newsnode->data.sprintf("yingyu=");scanf("%f",&newsnode->data.yp=*Li_head,q=NULL;//查找第i個(gè)結(jié)點(diǎn)，使p指向，q指向第i-1個(gè)結(jié)點(diǎn)5《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書while(p!=NULL){m++;if()break;else{}}if()//插入在表頭{newsnode->link=p;*Li_head=newsnode;}else{//插入在q和p之間}return1;}6、編寫主函數(shù)main，要求測試以上所編寫的listcreat、listinsert、listdel和listdisplayvoidmain()//自己設(shè)計(jì)主函數(shù)完成{}6《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書7《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(、體會(huì)、收獲)】總結(jié)本次實(shí)驗(yàn)的重難點(diǎn)及心得實(shí)驗(yàn)小結(jié)【得分_____________評閱日期_____________教師簽名____________8《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)二堆棧操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹慷褩：完?duì)列基本操作的編程實(shí)現(xiàn)要求：堆棧和隊(duì)列基本操作的編程實(shí)現(xiàn)（2學(xué)時(shí)，驗(yàn)證型），掌握堆棧和隊(duì)列的建立、進(jìn)棧、出棧、進(jìn)隊(duì)、出隊(duì)等基本操作的編程實(shí)現(xiàn)，存儲(chǔ)結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu)中任選，也可以全部實(shí)現(xiàn)。也鼓勵(lì)學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計(jì)?！緦?shí)驗(yàn)內(nèi)容】內(nèi)容：把堆棧和隊(duì)列的順序存儲(chǔ)（環(huán)隊(duì)）和鏈表存儲(chǔ)的數(shù)據(jù)進(jìn)隊(duì)、出隊(duì)等運(yùn)算其中一部分進(jìn)行程序?qū)崿F(xiàn)?？梢詫?shí)驗(yàn)一的結(jié)果自己實(shí)現(xiàn)數(shù)據(jù)輸入、數(shù)據(jù)顯示的函數(shù)。利用基本功能實(shí)現(xiàn)各類應(yīng)用，如括號(hào)匹配、回文判斷、事物排隊(duì)模擬、數(shù)據(jù)逆序生成、多進(jìn)制轉(zhuǎn)換等?！緟⒖即a】（一）利用順序棧實(shí)現(xiàn)十進(jìn)制整數(shù)轉(zhuǎn)換轉(zhuǎn)換成n進(jìn)制1、算法思想將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法，以N=3456，r=8為例轉(zhuǎn)換方法如下：NN/8（整除）N%8（求余）34564320低我們看到所轉(zhuǎn)換的8進(jìn)制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計(jì)算過程相反，因此轉(zhuǎn)換過程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想如下：當(dāng)N>0時(shí)重復(fù)1，21．若N≠0，則將N%r壓入棧s中，執(zhí)行2;若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。2．用N/r代替N2、轉(zhuǎn)換子程序#defineL_sizevoidconversion(intN，intr){//根據(jù)需要自己定義L_size為順序棧的最大存儲(chǔ)容量//將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)ints[L_size],top;//定義一個(gè)順序棧，top為棧頂指針，注意此處沒有使用結(jié)構(gòu)體類型intx;}//初始化棧while({)//此循環(huán)為出棧操作9《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書printf(“%d”,x);}}3、編寫主函數(shù)驗(yàn)證上述轉(zhuǎn)換子函數(shù)是否正確。voidmain()//自己設(shè)計(jì)主函數(shù)完成{｝（二）用順序棧實(shí)現(xiàn)算術(shù)后綴表達(dá)式求值1、算法思想#defineL_size50voidpostexp(){intst[L_size],top=-1;//定義一個(gè)順序棧，top為棧頂指針intd;//定義用來字符串轉(zhuǎn)換整數(shù)的變量dcharch;printf("請輸入規(guī)范的后綴表達(dá)式(操作數(shù)、運(yùn)算符之間使用空格間隔開，eg:1560422/-3*+):\n");//輸入范例while((ch=getchar())!='\n')//開始輸入字符并賦給ch{if(ch=='')//如果輸入的是空格，不做處理elseswitch(ch){//判斷輸入是否運(yùn)算符，如果時(shí)就進(jìn)行相應(yīng)的操作10《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書case'+':;;break;case'/':if(st[top]!=0){//分母不為零計(jì)算才有效}else{printf("除數(shù)為0!\n");//分母為零計(jì)算無效，退出程序exit(1);}break;default:while(ch>='0'&&ch<='9'){ch=getchar();}}}printf("運(yùn)算結(jié)果是:%d\n",st[top]);}3、編寫主函數(shù)驗(yàn)證上述求值子函數(shù)是否正確。voidmain()//自己設(shè)計(jì)主函數(shù)完成{｝（三）鏈?zhǔn)疥?duì)列基本操作11《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書1、隊(duì)列結(jié)點(diǎn)定義typedefstructnode//隊(duì)列結(jié)點(diǎn)類型定義{structnode*link;//指向后繼結(jié)點(diǎn)的指針}NODE;//定義鏈隊(duì)//定義鏈隊(duì)隊(duì)頭和隊(duì)尾指針}2、入隊(duì)NODE*ldcr(structQueueLk*QL,Elemtypex)//將元素x插入到鏈隊(duì)列rear中，作為rear的新隊(duì)尾{p->data=x;if(QL->front==NULL)//隊(duì)列為空else//將鏈隊(duì)列中最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)//將隊(duì)尾指向新結(jié)點(diǎn)}3、出隊(duì)ElemTypeldsc(structQueueLk*QL)//若鏈隊(duì)列不為空，則刪除隊(duì)頭元素，返回其元素值{NODE*s;ElemTypex;if()//隊(duì)空，退出程序exit(1);//取隊(duì)頭保存在s中//刪除隊(duì)頭結(jié)點(diǎn))//如果刪除后隊(duì)列為空，則處理隊(duì)尾指針x=s->data;//將剛才出隊(duì)的結(jié)點(diǎn)值給x//釋放出對結(jié)點(diǎn)的空間if(returnx;}4、編寫主函數(shù)驗(yàn)證上述子函數(shù)是否正確。voidmain()//自己設(shè)計(jì)主函數(shù)完成{12《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書｝【】總結(jié)本次實(shí)驗(yàn)的重難點(diǎn)及心得、體會(huì)、收獲)(實(shí)驗(yàn)小結(jié)13《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書得分_____________評閱日期_____________14《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)三串操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹績?nèi)容：串基本操作的編程實(shí)現(xiàn)要求：串基本操作的編程建立、遍歷、插入、刪除等基本操作的編程實(shí)現(xiàn)，也可以作進(jìn)行一些應(yīng)用的程序設(shè)計(jì)。【思考問題】1.字符串的順序存儲(chǔ)和鏈表存儲(chǔ)的差異？C語言中是如何實(shí)現(xiàn)字符串的？2.在字符串處理方面主要有什么操作？3.字符串的操作的主要特點(diǎn)是什么？4.舉出幾個(gè)字符串的應(yīng)用范例？【參考代碼】(一)字符串長度計(jì)算intStrlen(char*s){inti;for(i=0;s[i]!='\0';)i++;returni;/*用循環(huán)來計(jì)算字符串長度*//*將累加的i值返回給Strlen()*/}/*主程序：讀取字符串長度后，輸出該字符串的長度*/voidmain(){charstring[50];intlength;/*聲明長度為50的字符串?dāng)?shù)組*//*字符串長度*/printf("\nPleaseinputstring:");gets(string);length=Strlen(string);/*讀取字符串存到變量string*//*計(jì)算字符串string的長度*/printf("\nTheinputstringlengthis%d",length);}/*希望的結(jié)果*//*Pleaseinputstring:Howareyou?/*Theinputstringlengthis12*/*/（二）字符串的替換/*將字符串S2從字符串S1的一某個(gè)位置pos替換S1的子串*/char*Strrep(char*s1,char*s2,intpos){inti,j;for(j=pos;s1[j]!='\0';j++)/*從取代的起始位置開始*/if(s2[i]!='\0'){15《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書s1[j]=s2[i];i++;/*進(jìn)行取代*/}}/*主程序：輸入兩字符串，再進(jìn)行字符串取代*/voidmain(){charstring1[100];charstring2[50];intposition;/*聲明字符串?dāng)?shù)組1/*聲明字符串?dāng)?shù)組2/*進(jìn)行取代的起始位置*/*/*/printf("\nPleaseinputoriginalstring:");gets(string1);/*讀取原始字符串并存入"String1"*/printf("\nPleaseinputsubstitutestring:");gets(string2);/*讀取欲替換的子字符串并存入"String2"*/printf("\nPleaseinputsubstituteposition:");/*讀取進(jìn)行字符串替換的起始位置"*/scanf("%d",&position);Strrep(string1,string2,position);/*進(jìn)行字符串的取代*/printf("\nThefinalstring:%s\n",string1);}/*希望的結(jié)果*//*Pleaseinputoriginalstring:Myfavoritecolorisblack./*Pleaseinputsubstitutestring:white/*Pleaseinputsubstituteposition:22*/*/*//*Thefinalstring:Myfavoritecoloriswhite.*/16《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(、體會(huì)、收獲)】總結(jié)本次實(shí)驗(yàn)的重難點(diǎn)及心得實(shí)驗(yàn)小結(jié)【得分_____________評閱日期_____________17《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)四二維數(shù)組基本操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹慷S數(shù)組基本操作的編程實(shí)現(xiàn)驗(yàn)證性實(shí)驗(yàn)（學(xué)時(shí)數(shù)：2H）【實(shí)驗(yàn)內(nèi)容】設(shè)計(jì)一個(gè)可容納40位數(shù)的求n!的程序。設(shè)計(jì)一個(gè)將稀疏數(shù)組壓縮的程序?！舅伎紗栴}】1.數(shù)組的下標(biāo)從什么地址開始？好處是什么？2.壓縮數(shù)據(jù)主要的思路是什么？3.為什么用數(shù)組可以存儲(chǔ)超出計(jì)算機(jī)數(shù)據(jù)要求的范圍的數(shù)字？4.舉出幾個(gè)數(shù)組的應(yīng)用范例？【參考代碼】（一）設(shè)計(jì)一個(gè)可容納40位數(shù)的求n!的程序/*==============================================/*程序構(gòu)思：*//*依題意可得知，本程序所運(yùn)用的數(shù)據(jù)結(jié)構(gòu)為“數(shù)組”，*//*目的為運(yùn)用數(shù)組來彌補(bǔ)整數(shù)數(shù)據(jù)類型有限的使用范圍。*//*我們預(yù)先聲明變量為一個(gè)大小為40的數(shù)組，負(fù)責(zé)存儲(chǔ)每一個(gè)位數(shù)的數(shù)據(jù)，*//*變量Digit為計(jì)算位數(shù)的變更、變量i,j,r,k為變量。*//*首先先將值零。再令第一位數(shù)為值1，位數(shù)也為1。*//*再將每次相乘的乘積存回?cái)?shù)組中。*//*并循序處理每個(gè)數(shù)組過10的數(shù)，若數(shù)超值過10，/*原來的數(shù)除以10，商數(shù)加前一位數(shù)的數(shù)值后存回前一位數(shù)的數(shù)組/*再將余數(shù)存回原來位數(shù)的數(shù)組中。最后再輸出每次計(jì)算后的結(jié)果。*/循環(huán)中所用的計(jì)數(shù)Data數(shù)組中的數(shù)據(jù)做初始中超則將位數(shù)加一，*/中，*/voidmain(){intData[40];/*存儲(chǔ)40位數(shù)的整數(shù)數(shù)組*/數(shù)據(jù)位數(shù)變量*/循環(huán)計(jì)數(shù)變量*/用戶輸入值*/intDigit;/*inti,j,r,k;/*intN;/*for(i=1;i<40+1;i++)/將數(shù)組初始設(shè)值為0*/Data[i]=0;if(Data[j]>10){for(r=1;r<Digit+1;r++){if(Data[Digit]>10)Digit++;/*當(dāng)數(shù)組中的大值于10時(shí)，則位數(shù)加1*/Data[r+1]+=Data[r]/10;/*前一位數(shù)組值＝前一位數(shù)組值＋此位數(shù)組值除以10*/Data[r]+=Data[r]%10;/*此位數(shù)組值＝此位數(shù)組值＋除10取余數(shù)*/}}}printf("%d!=",i);for(k=Digit;k>0;k--)/*輸出數(shù)組中的內(nèi)容*/printf("%d",Data[k]);printf("\n");}}18《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書/*希望的結(jié)果/*Inputanumberwhatyouwanttocalculus:34/*1!=1/*2!=2/*3!=6/*4!=24/*5!=120/*6!=720/*7!=5040/*8!=40320/*9!=362880/*10!=3628800/*11!=39916800/*12!=479001600/*13!=6227020800/*14!=87178291200/*1*//*21!=51090942171709440000/*22!=1124000727777607680000/*23!=25852016738884976640000/*24!=620448401733239439360000/*25!=15511210043330985984000000/*26!=403291461126605635584000000/*27!=0888869450418352160768000000/*28!=304888344611713860501504000000/*29!=8841761993739701954543616000000/*30!=265252859812191058636308480000000/*31!=8222838654177922817725562880000000/*32!=263130836933693530167218012160000000/*33!=8683317618811886495518194401280000000/*34!=295232799039604140847618609643520000000（二）設(shè)計(jì)一個(gè)將稀疏數(shù)組壓縮的程序/*==============================================/*程序構(gòu)思：*//*依題意可得知，我們需知道原稀疏數(shù)組的大小，*//*及使用的元素個(gè)數(shù)，并聲明另一個(gè)大小為10*3的數(shù)組來存儲(chǔ)原數(shù)組的數(shù)據(jù)。*/9*7，但不知稀疏數(shù)組中有幾個(gè)元素已使用。*//*我們利用一個(gè)兩層的循環(huán)，遍歷原數(shù)組中的每一筆數(shù)據(jù)，*/于新數(shù)組中。*//*已知原數(shù)組的大小為/*當(dāng)數(shù)據(jù)內(nèi)容不為零時(shí)，則記錄其列數(shù)、行數(shù)及內(nèi)容voidmain(){/*默認(rèn)9*7的稀疏矩陣數(shù)據(jù)*/intData[9][7]={0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,1,4,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};intCompressData[10][3];/*存儲(chǔ)壓縮后數(shù)據(jù)數(shù)組*/壓縮數(shù)據(jù)的索引值*/循環(huán)計(jì)數(shù)變量*/數(shù)組索引初始化*/intIndex;/*inti,j;/*Index=0/*printf("Twodimensionalsparsearray:\n");for(i=0;i<9;i++)/*輸出壓縮前數(shù)組數(shù)據(jù)*/{for(j=0;j<7;j++)printf("%3d",Data[i][j]);printf("\n");}19《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書for(i=0;i<9;i++)/*for(j=0;j<7;j++)if(Data[i][j]!=0){進(jìn)行數(shù)組數(shù)據(jù)壓縮*/Index++;/*增加數(shù)組索引值*/CompressData[Index][0]=i;元素行位置*//*元素列位置*//*元素內(nèi)容值*/}CompressData[0][0]=9;/*原數(shù)組的行數(shù)*/CompressData[0][1]=7;/*原數(shù)組的列數(shù)*/CompressData[0][2]=Index;/*使用的元素個(gè)數(shù)*/printf("Twodimensinalcompressarray:\n")for(i=0;i<=Index;i++)/*輸出壓縮后數(shù)組數(shù)據(jù)*/{for(j=0;j<3;j++)printf("%3d",CompressData[i][j]);printf("\n");}}/*希望的結(jié)果*//*Twodimensionalsparsearray:*//*0000000*//*0300000*//*0000000*//*1400000*//*0070000*//*0000050*//*0000000*//*0000000*//*0000000*//*Twodimensionalcompressarray:*//*975*//*113*//*301*//*314*//*427*//*555*/(、體會(huì)、收獲)】總結(jié)本次實(shí)驗(yàn)的重難點(diǎn)及心得實(shí)驗(yàn)小結(jié)【20《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書得分_____________評閱日期_____________教師簽名____________21《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)五二叉樹基本操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹績?nèi)容：二叉樹基本操作的編程實(shí)現(xiàn)要求：1.二叉樹基本操作的編程實(shí)現(xiàn)（2學(xué)時(shí)，驗(yàn)證型），掌握二叉樹的建立、遍歷、插入、刪除等基本操作的編程實(shí)現(xiàn)，也可以進(jìn)一步編程實(shí)現(xiàn)查找等操作，存儲(chǔ)結(jié)構(gòu)主要采用順序或鏈，并計(jì)算出表達(dá)式之結(jié)果?！舅伎紗栴}】1.二叉樹2.三種根序遍歷主要3.如果不用遍歷算法一般啟用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)4.舉出二叉樹的是樹嗎？它的定義為什么是遞歸的？思路是什么？后序遍歷？應(yīng)用范例？【參考代碼】（一）建立二叉樹，并以前序遍歷的方式將結(jié)點(diǎn)內(nèi)容輸出*//*===============================================*//*程序構(gòu)思：/*輸入元素值后建立二叉樹，點(diǎn)－左子－右子樹，并將二叉樹結(jié)點(diǎn)內(nèi)容輸出。*/*/*/以遞歸的方式做前序遍歷，/*其順序?yàn)椋航Y(jié)#include<stdlib.h>structtree{/*聲明樹的結(jié)構(gòu)*/structtree*left;intdata;structtree*right;};/*存放左子樹的指針*//*存放結(jié)點(diǎn)數(shù)據(jù)內(nèi)容*//*存放右子樹的指針*/typedefstructtreetreenode;typedeftreenode*b_tree;/*聲明新型類樹結(jié)構(gòu)*//*聲明二叉樹的鏈表*//*===============================================*//*插入二叉樹結(jié)點(diǎn)*//*==if(root==NULL)returnnewnode;/*返回新結(jié)點(diǎn)的位置*/else{currentnode=root;while(currentnode!=NULL){/*存儲(chǔ)目前結(jié)點(diǎn)指針*/parentnode=currentnode;/*存儲(chǔ)父結(jié)點(diǎn)指針*/if(currentnode->data>node)/*比較結(jié)點(diǎn)的數(shù)值大小*/currentnode=currentnode->left;/*左子樹*/currentnode=currentnode->right;/*右子樹*/else}if(parentnode->data>node)parentnode->left=newnode;else/*將父結(jié)點(diǎn)和子結(jié)點(diǎn)做連結(jié)*//*子結(jié)點(diǎn)為父結(jié)點(diǎn)之左子樹*/parentnode->right=newnode;/*子結(jié)點(diǎn)為父結(jié)點(diǎn)之右子樹*//*返回根結(jié)點(diǎn)之指針*/}returnroot;}22《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書/*===============================================*//*建立二叉樹*//*===============================================*/b_treecreate_btree(int*data,intlen){}}/*==================================================*//*主程序：建立二叉樹，并以前序遍歷輸出二叉樹結(jié)點(diǎn)內(nèi)容*//*==================================================*/voidmain(){b_treeroot=NULL;inti,index;intvalue;intnodelist[20];/*樹根指針*//*讀入輸入值所使用的暫存變量/*聲明存儲(chǔ)輸入數(shù)據(jù)之?dāng)?shù)組*/*/printf("\nPleaseinputtheelementsofbinarytree(Exitfor0):\n);index=0;/**//*Thepreordertraversalresultis(63154978)*/（二）將一個(gè)表示二叉樹的數(shù)組結(jié)構(gòu)轉(zhuǎn)換成鏈表結(jié)構(gòu)/*===============================================*//*程序構(gòu)思：*//*給定一個(gè)二叉樹數(shù)組結(jié)構(gòu)，使用遞歸方式建立一棵二叉樹，*//*并中序遍歷的方式輸出二叉樹結(jié)點(diǎn)內(nèi)容。*/#include<stdlib.h>structtree{/*聲明樹的結(jié)構(gòu)*/structtree*left;/*存放左子樹的指針*//*存放結(jié)點(diǎn)數(shù)據(jù)內(nèi)容*//*存放右子樹的指針*/intdata;structtree*right;};returnnownode;/*返回復(fù)制樹的位置*/}}/*===============================================*//*二叉樹中序遍歷打印結(jié)點(diǎn)內(nèi)容*//*===============================================*/voidinorder_print_btree(b_treepoint){if(point!=NULL){/*遍歷的終止條件*/inorder_print_btree(point->left);/*處理左子樹/*處理打印結(jié)點(diǎn)內(nèi)容*/inorder_print_btree(point->right);/*處理右子樹*/*/printf("%2d",point->data);}}/*================================================*//*主程序：建立鏈表二叉樹，并以中序遍歷打印結(jié)點(diǎn)內(nèi)容*//*================================================*/voidmain(){b_treeroot=NULL;inti;/*樹根指針*/23《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書/*----------------聲明二叉樹數(shù)組結(jié)點(diǎn)數(shù)據(jù)----------------*/intnodelist[16]={0,5,2,9,1,4,7,0,0,0,3,0,6,8,0,0};/*希望的結(jié)果/*Thenodecontentofarray_structureis:/*[0][5][2][9][1][4][7][0][0][0][3][0][6][8][0][0]*//*/*Thenodecontentoflinklist_structureis:/*[1][2][3][4][5][6][7][8][9]*/*/*/*/*/（三）二叉樹的應(yīng)用/*程序構(gòu)思：*//*將表達(dá)式二叉樹方式存入數(shù)組，以遞歸方式建立表達(dá)式之二叉樹狀結(jié)構(gòu)，*//*再分別輸出前序、中序及后序遍歷結(jié)果，并計(jì)算出表達(dá)式之結(jié)果。*/#include<stdlib.h>structtree{/*聲明樹的結(jié)構(gòu)*//*存放左子樹的指針/*存放結(jié)點(diǎn)數(shù)據(jù)內(nèi)容/*存放右子樹的指針*/structtree*left;*/*/chardata;structtree*right;};typedefstructtreetreenode;typedeftreenode*b_tree;/*聲明新類型樹結(jié)構(gòu)*//*聲明二叉樹的鏈表*//*===============================================*//*使用遞歸建立二叉樹/*===============================================*/*/b_treecreate_btree(int*nodelist,intposition){b_treenewnode;/*聲明新結(jié)點(diǎn)指針*/if(nodelist[position]==0||position>7)returnNULL;/*遞歸的終止條件*/else{}/*===============================================*//*二叉樹前序遍歷打印結(jié)點(diǎn)內(nèi)容*//*===============================================*/voidpreorde(b_treepoint){if(point!=NULL){printf("%c",point->data);/*處理左子樹/*遍歷的終止條件*//*處理打印結(jié)點(diǎn)內(nèi)容*//*處理右子樹*/preorder(point->right);*/}}/*===============================================*//*二叉樹中序遍歷打印結(jié)點(diǎn)內(nèi)容/*===============================================*/*/voidinorde(b_treepoint){if(point!=NULL)/*遍歷的終止條件*/*/{*//*===============================================*/voidpostorde(b_treepoint){if(point!=NULL){postorder(point->left);/*遍歷的終止條件/*處理左子樹/*處理右子樹*/*/postorder(point->right);24《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書prin{}switch((char)oper){case'*':return(oper1*oper2);case'/':return(oper1/oper2);case'+':return(oper1+oper2);case'-':return(oper1-oper2);}/*================================================*//*主程序：建立表達(dá)式二叉樹，并計(jì)算結(jié)果*//*================================================*/voidmain(){b_treeroot=NULL;intcal_result;/*----------------聲明二叉樹數(shù)組結(jié)點(diǎn)數(shù)據(jù)intnodelist[8]={'','+','*','/','4','8','6','2'};/*聲明表達(dá)式二叉樹指針*//*計(jì)算結(jié)果*/----------------*/root=create_btree(nodelist,1);/*建立表達(dá)式二叉樹/*----------------前序打印*/----------------*/printf("\nPreorderexpression:[");preorder(root);printf("]\n");/*----------------中序打印printf("\nInorderexpression:[");preorder(root);----------------*/printf("]\n");/*----------------后序打印printf("\nPostorderexpression:[");preorder(root);----------------*/printf("]\n");/*------------計(jì)算表達(dá)式結(jié)果------------*/cal_result=calculate(root);printf("\nCalculateresultis[%2d]\n",cal_result);}/*希望的結(jié)果*/*//*Preorderexpression:[+*48/62]/*Inorderexpression:[4*8+6/2]/*Postorderexpression:[48*62/+]*/*/*//*/*Calculateresultis[35]*/(、體會(huì)、收獲)實(shí)驗(yàn)小結(jié)【】總結(jié)本次實(shí)驗(yàn)的重難點(diǎn)及心得25《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書得分_____________評閱日期_____________教師簽名____________26《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)六圖基本操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹繄D基本操作的編程實(shí)現(xiàn)要求：圖基本操作的編程實(shí)現(xiàn)（2學(xué)時(shí)，驗(yàn)證型），掌握圖的建立、遍歷、插入、刪除等基本操作的編程實(shí)現(xiàn)，存儲(chǔ)結(jié)構(gòu)可以在順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、聯(lián)合使用多種結(jié)構(gòu)等中任選，也可以全部實(shí)現(xiàn)。也鼓勵(lì)學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計(jì)。【實(shí)驗(yàn)性質(zhì)】驗(yàn)證性實(shí)驗(yàn)（學(xué)時(shí)數(shù)：2H）【實(shí)驗(yàn)內(nèi)容】編程對圖進(jìn)行存儲(chǔ)（鄰接矩陣或鄰接表都可以，由學(xué)生自由選擇），之后可以詢問任何兩個(gè)結(jié)點(diǎn)之間是否有通路和路徑數(shù)。設(shè)計(jì)一個(gè)將圖形轉(zhuǎn)成鄰接鏈表的程序。設(shè)計(jì)一個(gè)深度優(yōu)先搜索法來查找圖形的程序。設(shè)計(jì)一個(gè)廣度優(yōu)先搜索法來查找一個(gè)圖形的程序。鼓勵(lì)開發(fā)出難度更高的程序?！舅伎紗栴}】1.圖的定義和特性？2.圖的主要存儲(chǔ)結(jié)構(gòu)是什么？是獨(dú)立的某種還是多種數(shù)據(jù)結(jié)構(gòu)的綜合？3.圖的主要遍歷思路是哪些？舉出圖的應(yīng){inti,j;printf("Vertice")；for(i=0;i<Max；i++)printf("％3d"，i)；printf("\n")；for(i=0;i<Max；i++){printf(；％4d",i)；j++)％3d",Graph[i][j])for(j=0;j<Maxprintf("；printf("\n")；}}/*==============================================/*以鄰接矩陣建立圖形=============================*//*==============================================voidCreate_M_Graph(intVerticel，intVertice2){Graph[Verticel][Vertice2]=1;/*將矩陣內(nèi)容設(shè)為1*/}/*==============================================/*主程序=========================================*//*==============================================voidmain(){intSource；/*起始頂點(diǎn)*/27《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書intDestination；/*終止頂點(diǎn)*/intif(Source==Destination)/*出錯(cuò)：自身循環(huán)*/：SelfLoop!!\n”)；出錯(cuò)：超出范圍*/：outofrange!!\n")printf("***Error***elseif(Source>=Max||Destination>=Maprintf("***Error***；else/*調(diào)用建立鄰接數(shù)組*/Create_M_Graph(Source，Destination);}printf("##Graph##\n");print_M_Graph()；/*調(diào)用輸出鄰接數(shù)組數(shù)據(jù)*／}/*希望的結(jié)果*//*pleaseinputtheEdge'ssource：0*/：4*/：1*/：0*/：1*/：4*/：2*/：1*/：3*/：2*/：4*/：3*/：-1*//*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*##Graph##*//*Vertice012345*//*0000010*//*1100010*//*2010000*//*30/*程序構(gòu)思：*//*用戶輸入結(jié)點(diǎn)與各個(gè)邊，再將邊轉(zhuǎn)成鄰接鏈表。*/#include<stdlib.h>#definevertexnum6/*定義最大可輸入的結(jié)點(diǎn)個(gè)數(shù)*/structnode/*定義圖形的頂點(diǎn)結(jié)構(gòu)*/{intvertex;structnode*next;}/*==============================================/*以鄰接鏈表建立圖形=============================*//*==============================================voidCreate_l_Graph(intVertexl，intVertex2){GraphsearchP;/*結(jié)點(diǎn)聲明*/Graphnew;/*新結(jié)點(diǎn)聲明*/new=(searchP->next=new;}}/*==============================================/*輸出鄰接鏈表的數(shù)據(jù)===============================*//*==============================================voidprint_l_graph(structnode*head){graphsearchP;searchP=head->next;28《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書while(searchP!=NULL){printf("[%d]",searchP->vertex);searchP=searchP->next;}printf("\n")；}/*==============================================/*主程序=========================================*//*==============================================voidmain(){intSource；/*起始頂點(diǎn)*/intDestination；/*終止頂點(diǎn)*/inton：")；scanf("%d”,&Destination)；if(Source==Destination)/*出錯(cuò)：自身循環(huán)*/printf("***Error***：SelfLoop!!\n”)；elseif(Source>=vertexnum||Destination>=/*出錯(cuò)：超出范圍*/printf("***Error***：outofrange!!\n")；elso/*調(diào)用建立鄰接鏈表*/Create_l_Graph(Source，Destination);}printf("##Graph##\n");for(i=0;i<=vertexnum;i++){print（"vertex[%d]:",i);print_l_Graph(&head[i])；/*調(diào)用輸出鄰接鏈表數(shù)據(jù)*／}}/*希望的結(jié)果*//*pleaseinputtheEdge'ssource：2*/：1*/：2*/：3*/：3*/：4*/：4*/：1*/：4*/：2*/：4*/：5*/：5*/：1*/：-1*//*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*PleaseinputtheEdge'sDestination/*pleaseinputtheEdge'ssource/*##Graph##*//*Vertex[0]:*//*Vertex[1]:*//*Vertex[2]:[1][3]*//*Vertex[3]:[4]*//*Vertex[4]:[1][2][5]*//*Vertex[5]:[1]*/[2]:[1][3]*//*Vertex[3]:[4]*//*Vertex[4]:[1][2][5]*/29《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書/*Vertex[5]:[1]*/（三）設(shè)計(jì)一個(gè)深度優(yōu)先搜索法來查找一個(gè)圖形的程序。*//*程序構(gòu)思：/*遞歸調(diào)用深度優(yōu)先搜索法，往下一個(gè)頂點(diǎn)查找，直到查找到列表尾端為止。*/#include<stdlib.h>#defineVertexNum9/*定義頂點(diǎn)數(shù)*/聲明圖形頂點(diǎn)結(jié)構(gòu)*/鄰接頂點(diǎn)數(shù)據(jù)*/structNode/*{intVertex;/*structNode*Next;/*下一個(gè)鄰接頂點(diǎn)*/};typedefstructNode*Graph;/*定義圖形結(jié)構(gòu)*/strprintf("[%d]==>",Vertex);SearchP=Head[Vertex].Next;while(SearchP!=NULL){if(Visited[SearchP->Vertex]==0)/*遞歸調(diào)用*/SearchP=SearchP->Next;/*下一個(gè)鄰接點(diǎn)*/}}/*==========================================*//*建立鄰接頂點(diǎn)至鄰接列表內(nèi)==================*//*==========================================*/voidCreate_L_Graph(intVertex1,intVertex2){GraphSearchP;/*結(jié)點(diǎn)聲明*/GraphNew;/*新頂點(diǎn)聲明*/New=(Graph)malloc(sizeof(structNode));配置內(nèi)存