《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)北京郵電大學(xué)遠(yuǎn)程教育計算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書實驗一線性表的插入和刪除一、實驗?zāi)康?、掌握用ＴurboＣ上機(jī)調(diào)試線性表的基本方法;2、掌握線性表的基本操作，插入、刪除、查找,以及線性表合并等運(yùn)算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的運(yùn)算。二、實驗內(nèi)容線性表基本操作的實現(xiàn)當(dāng)我們要在線性表的順序存儲結(jié)構(gòu)上的第i個位置上插入一個元素時，必須先將線性表的第ｉ個元素之后的所有元素依次后移一個位置，以便騰空一個位置，再把新元素插入到該位置。若要刪除第ｉ個元素時,也必須把第i個元素之后的所有元素前移一個位置。程序?qū)崿F(xiàn):tyｐｅｄｅｆNuｌl０；typｅdefintdataｔypｅ;ｍaxsiｚe１０24；strucｔ＃ｄefｉnetｙｐedef｛datatypｅｄatａ[maxｓizｅ];intlast；}sequｅnliｓｔ;intinｓeｒt(L,x,ｉ）sequenlｉｓt*L;ｉnti;{intj;if((*L).laｓt=＝mａxsｉze-1){ｐｒiｎｔf(“overfｌow”)；ｒeturnNｕｌｌ；

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)}elseif((i＜1）‖(i>(*L).last+1)｛priｎｔf（“eｒｒor”)；reｔｕｒnNull;｝elsｅ{for（j＝(＊L）.last;ｊ>=ｉ-１；ｊ-－）(＊L)．ｄaｔａ[j＋1］=（*Ｌ).ｄatａ［ｊ］;(*L).data[i－1］＝x;(*L).last=(*L).laｓｔ+1;}ｒetuｒn(1)；}ｉｎtdelｅtｅ（L,i)seｑuｅnlistｉnti;*L；{ｉntｊ；if((ｉ<１)‖（i＞(*L).last＋1)){pｒintｆ(“eｒror”)retuｒnNull;｝elｓe{for(j=i,j＜=（＊Ｌ)．ｌａst;j+＋)(*L)．data[j-1］＝(*L).datａ[ｊ];(*Ｌ).data-－；}rｅtuｒn(1）;｝

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)ｖoidcreatｌisｔ（){sequenlisｔ＊L；intn,ｉ,j;printf(“請輸入n個數(shù)據(jù)\n”）;sｃanｆ（“%d”，&n);for（i＝０;ｉ<ｎ;ｉ++）{pｒintｆ（“ｄata［%ｄ］=”，i);scanf（“％d”,（＊L）.ｄata[ｉ]）;｝(*L）．last=n-1；printｆ(“＼ｎ”);}printout(L)seqｕeｎｌist*L；{inti;for(ｉ=0;i<(*L).ｌast;ｉ++){ｐｒｉnｔf(“data［%d]=”,ｉ)；prｉｎtf(“％ｄ”,(*L).ｄａt(yī)a[i]);}｝mａin(){seqｕｅnlist*L;ｃharcｍd;inti,ｔ;clscr();priｎtf(“i,Ｉ…..插入\n”）；printf（“d,D….．刪除\n”);

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)prinｔｆ(“q,Ｑ……退出\ｎ”)ｄo{do{ｃｍd=getchar(）;｝‘D’)‖(ｃmｄ?。健畄’)‖（ｃmd!=‘I’)）；ｗｈｉle((cmd!=‘d’)‖（ｃmd!＝（cmd!=‘Q’）‖（ｃｍｄ!＝‘ｉ’)‖swｉtch(cmd){case‘i’,‘Ｉ’;sｃanf(&x);scanf(&ｉ);ｉnsert(Ｌ,x,i);ｐrintｏut(L）;bｒeａk;case‘d’，‘D’；scanｆ(&i)；ｄeｌeｔe(Ｌ，i）;ｐrintout(Ｌ);breａk；}}while（(cmｄ!=‘q’)&&(cｍd！=‘Q’）);}實驗二二叉樹的操作一、實驗?zāi)康?/p>

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)1、進(jìn)一步掌握指針變量、動態(tài)變量的含義;2、掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及適用范圍；3、掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。二、實驗內(nèi)容已知以二叉鏈表作存儲結(jié)構(gòu)，試編寫按層次順序遍歷二叉樹的算法。算法思想:本算法要采用一個隊列q,先將二叉樹根結(jié)點入隊列，然后退隊列,輸出該結(jié)點；若它有左子樹,便將左子樹根結(jié)點入隊列；若它有右子樹,便將右子樹根結(jié)點入隊列,直到隊列空為止。因為隊列的特點是先進(jìn)先出,從而達(dá)到按層次順序遍歷二叉樹的目的。程序?qū)崿F(xiàn)：#dｅfineM100＃dｅfineＮull０typeｄefｓｔrｕｃtｎｏｄe｛iｎtdata;stuucｔnoｄｅ*lchｉｌd，*rchｉｌd;}biｔree;bitree＊que[M];intfronｔ=0,rｅaｒ=0;biｔrｅe＊creａt(yī)(）｛bｉtｒee*ｔ;inｔx;scanｆ(“%d”，&x);if(x=＝0）t=Null;else{ｔ＝ｍalloc（sizeof(bitｒee));t→dａt(yī)a=x;ｔ→lcｈilｄ=ｃreat()；t→rchild＝cｒeaｔ();

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)}ｒeturnt;}voidiｎｏrder(t)bｉtree*t;{iｆ(t?。剑危鮨l){inoｒder(t→lchild)；printf(“%４ｄ”，t→datａ);ｉnorder(t→rｃhild）;}}vｏiｄｅｎqueue(t)bitｒeｅ*t;{if(fｒont！=（rｅaｒ＋1)%M){reaｒ=（reaｒ+1)%M;qｕe[ｒｅar］=t;}｝ｂｉｔree＊delｑuｅuｅ(）{ｉf(fｒont＝＝rear)returnＮull;ｆront=(froｎt+1）％Ｍ;returｎ(ｑue[fronｔ]);｝voidｌevoｒｄeｒ(ｔ)

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)bｉtree＊ｔ；{bitｒee*p；ｉf(t!＝Ｎull){enquｅue(t);ｗhilｅ(froｎｔ!=rｅar）｛p＝dｅlqueue();ｐriｎtf（“%4d”，p→data)；if(p→lchild!=Nｕll)ｅnqueue（p→ｌchild);iｆ(p→rchilｄ!＝Ｎｕll)eｎqueｕe(p→rcｈiｌd）;｝｝}main(){bitree*ｒooｔ;ｐrintf(“\n”)root=creat（);iｎordeｒ（rｏot);ｐrintf(“\n”)lｅｖorder(rooｔ）;}實驗三圖的操作一、實驗?zāi)康?、掌握圖的基本存儲方法；2、掌握有關(guān)圖的操作算法并用高級語言實現(xiàn)；3、熟練掌握圖的兩種搜索路徑的遍歷方法。

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)二、實驗內(nèi)容假設(shè)以一個帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點代表一些區(qū)域中的重要場所，弧代表已有的公交線路,弧上的權(quán)表示該線路上的票價（或搭乘所需時間）,試設(shè)計一個交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價或最少的時間從區(qū)域中的某一場所到達(dá)另一場所。算法思想:下面是R、W、Floyd求每對頂點之間最短路徑算法的C語言程序，程序中矩陣A用來進(jìn)行ｎ次迭代，矩陣P用來記錄路徑,P［i][j]為迭代過程中當(dāng)前已經(jīng)求得的從頂點i到頂點j的最短路徑上最后被插入的那個頂點。算法實現(xiàn):ｔypedeｆstruｃtｎｏde{iｎtnｏ；floａt(yī)ｗgt;ｓtructnoｄe*neｘt;｝edgeｎode;tｙｐeｄｅfstruｃt{chａrvｔx;edｇenode*lｉnk;}ｖｅxｎｏde;ｔypｅdefvexｎodeGrａph［n]；ｖｏidFloyd(GraphG,ｆlｏaｔA[n][ｎ],intp[ｎ］[n］){inti,j,ｋ;fｏｒ(i=0;i<ｎ；i+＋)fｏr（ｊ=0;ｊ＜n;j++)｛A[ｉ][ｊ]＝G[i］[j];P[i］[j]＝－1;}

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)for(k=０;ｋ＜n；ｋ++）ｆor(i=0;ｉ<n;i＋+）for（ｊ=0；j<n;j++)ｉｆ(Ａ[i］［k]+A[k］[ｊ]<A[i]［j]){Ｐ［i]［j]=k;A[i]［j]＝A[i]［k］+A[k][j］；｝}實驗四排序一、實驗?zāi)康?、掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法;2、深刻理解排序的定義和各種排序方法的特點,并能加以靈活應(yīng)用;3、了解各種方法的排序過程及其依據(jù)的原則,并掌握各種排序方法的時間復(fù)雜度的分析方法。二、實驗內(nèi)容統(tǒng)計成績［問題描述]給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計一個算法:（1）按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2）按名次列出每個學(xué)生的姓名與分?jǐn)?shù)。[基本要求]學(xué)生的考試成績表必須通過鍵盤輸入數(shù)據(jù)而建立,同時要對輸出進(jìn)行格式控制。[算法實現(xiàn)]下面給出的是用直接選擇排序算法實現(xiàn)的Ｃ語言程序。#definen30

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)ｔyｐedｅfstructstudｅnt{cｈａrname[8];intsｃore;}ｓtｕdentR［n];main（){ｉntnｕｍ，i，j，ｍａx,temp;printf(“\ｎ請輸入學(xué)生成績:\n”);for(i=0;i<n;ｉ＋+)｛ｐｒｉntf(“姓名：”);scanf(“%s”,&stu［i]．naｍe）；ｓcaｎf(“%4ｄ”,&sｔu[ｉ］．score);}ｎuｍ=1;foｒ（i＝0;i＜ｎ；i＋+)｛max＝i;for(ｊ=i+1;j＜n;j++)ｉｆ(R［j].scｏrｅ＞R[maｘ].scorｅ）mａｘ=j;ｉf(mａx!=i）{teｍp＝R［max］;R［max］=R[i];R[i]=temp；}if（（ｉ>0)&&（Ｒ［i]．scｏrｅ<R[i-１].scｏre))nuｍ=nｕm+1;printｆ(“%4d%s%4d”,nｕm,R[i].nａme,Ｒ［i]．ｓcｏre)；}

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)}實驗五查找一、實驗?zāi)康?、掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法；2、熟練掌握二叉樹的構(gòu)造和查找方法。二、實驗內(nèi)容設(shè)計一個讀入一串整數(shù)構(gòu)成一棵二叉排序樹的算法。[實現(xiàn)提示］二叉排序樹的構(gòu)成,可從空的二叉樹開始,每輸入一個結(jié)點數(shù)據(jù)，就建立一個新結(jié)點插入到當(dāng)前已生成的二叉排序樹中，所以它的主要操作是二叉排序樹插入運(yùn)算。在二叉排序樹中插入新結(jié)點，只要保證插入后仍符合二叉排序樹的定義即可。［算法實現(xiàn)］tyｐeｄｅfｓｔructnｏde｛intkeｙ;ｉｎtoｔher;sｔrucｔnode*ｌｃhild，＊rcｈilｄ;}bsｔｎｏde;voｉdinｏrdｅr(t)bｓtｎode*ｔ;｛if(t!＝Ｎｕｌl)｛inorder(ｔ→ｌchｉｌd)；prinｔf(“%4d”,t→key);ｉnorder（t→rchild）;}｝

《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)ｂstnode＊ｉnsertｂｓt(ｔ，s）ｂｓtnｏde＊s,*t;｛bｓｔｎodｅ*f,*p；p=ｔ;whiｌe（p!=Null){ｆ=p;if（s→kｅｙ==ｐ→keｙ)returnｔ;ｉf(ｓ→key<p→key）p=p→lｃｈild；elsep=ｐ→rchiｌd;｝if（t==Null)returｎs;ｉf(s→ｋey<f→key)f→lchｉｌd＝s；elsef→rchild=s;reｔurnｔ;}bｓtnｏde*ｃreatord(){bstｎodｅ*ｔ,*s;inｔkeｙ;t