1數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題2要的環(huán)節(jié)。目前各種“數(shù)據(jù)結(jié)構(gòu)”教材較為注重理論的敘述與介紹，算法描述上的原因編寫了這本“數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題”。本參考書包括C語言基礎(chǔ)知識、上機(jī)實(shí)驗(yàn)習(xí)題和書面作業(yè)練習(xí)題三部分。在C語言基礎(chǔ)知識部分，主要介紹了輸入/輸出、函數(shù)及參數(shù)傳遞和結(jié)構(gòu)體的概念應(yīng)用。這部分內(nèi)容非常重要，掌握的是否熟練會直接影響“數(shù)據(jù)結(jié)構(gòu)“的學(xué)習(xí)。在實(shí)驗(yàn)部分，包括有完整的C語言源程序例題，介紹了一些設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)題目所需程序，或者擴(kuò)充已經(jīng)給出的源程序，也有需獨(dú)立思考設(shè)計(jì)的綜合實(shí)驗(yàn)題。答分析題。并且配有部分練習(xí)題的答案供學(xué)生自學(xué)、練習(xí)、參考。由于時(shí)間倉足、水平有限，書中難免存在錯誤和不妥之處，敬請讀者指正。3 1 3 5 8 10 12 20 28 30 32 34 40 42第三部分書面作業(yè)練習(xí)題 48 51 54 57 58 60 69 75 784言，由于該語言語法規(guī)范、嚴(yán)謹(jǐn)，非常適用于數(shù)據(jù)結(jié)構(gòu)課程教學(xué)。在Windows環(huán)境下涌現(xiàn)出一系列的功能強(qiáng)大、面向?qū)ο蟮某绦蜷_發(fā)工具，如：VisualC++,BorlandC++,VBasic,VisualFoxpro等。由于VisualDelphi法描述工具。近年來在計(jì)算機(jī)科學(xué)研究、系統(tǒng)開發(fā)、教學(xué)以及應(yīng)用開發(fā)中，C語言的使用越來越廣泛。因此，本教材采用類C語言進(jìn)行算法描述。基礎(chǔ)好，可以越過這一部分內(nèi)容不看。算法程序，如果數(shù)據(jù)不能正確輸入，算法設(shè)計(jì)得再好也無法正常運(yùn)行。C語言的輸入是由系統(tǒng)提供的scanf()等函數(shù)實(shí)現(xiàn)，在程序的首部一般要求寫入：函數(shù)scanf()的功能很豐富，輸入格式也是多種多樣，這是大家較為熟悉的知識，這里不做詳細(xì)介紹。在使用中需要注意以下幾個問題。（1）一條scanf()語句有多個變量、并且都是數(shù)值型（int,float,double）時(shí)，在輸入數(shù)據(jù)時(shí)應(yīng)該在一行之內(nèi)鍵入多個數(shù)據(jù)，數(shù)據(jù)之間空格分隔。例如：scanf(“%d%f”,&n,&x);就是在兩個數(shù)據(jù)之間使用空格鍵為分隔符，最后打回車鍵。5如果語句中在%d和%f之間有一個逗號：（2）在需要字符型變量或字符串輸入時(shí)，要單獨(dú)寫一條輸入語句，這樣不易出錯。如果在同一條scanf()語句中將字符型和數(shù)值型混合輸入常常會出錯。因?yàn)殒I盤輸入時(shí)在數(shù)符，而不能起到‘分隔符’的作用。所以將它們混在一起容易出錯。（3）在scanf()語句中變量寫法應(yīng)該是該變量的地址，這一點(diǎn)常被忽視。請看下列程序：4:printf(“\n請輸入姓名：”);scanf(“%s”,n5:printf(“\n請輸入性別：”);scanf(6:printf(“\n請輸入學(xué)號和成績：”);scanf}為了方便說明問題程序中加了行號，運(yùn)行時(shí)當(dāng)然不允許行號。一般情況下在scanf()語句中的變量名之前要加上求地址符&，上述程序第5，6行之中就是這地址，是該數(shù)組的首地址，所以name前面不加&。在本程序中把字符串、字符、數(shù)值型變量分別寫入不同的scanf()語句，輸入數(shù)據(jù)的具體形式如下：被忽略，還會影響后面的輸入語句無法正確讀入數(shù)據(jù)。因此，應(yīng)該充分重視數(shù)據(jù)的輸入技術(shù)。C語言的輸出是由系統(tǒng)提供的printf()等函數(shù)來實(shí)現(xiàn)，在程序的首部一般要求寫入：輸出函數(shù)printf()的語法一般容易掌握，這里強(qiáng)調(diào)的是怎樣合理巧妙的使用它。1.在連續(xù)輸出多個數(shù)據(jù)時(shí)，數(shù)據(jù)之間一定要有間隔，不能連在6行符。這樣使光標(biāo)與提示信息出現(xiàn)在同一行上，光標(biāo)停在問號后邊：X=?。。幾個數(shù)據(jù)在同一行輸出，不能換行掉這些輔助輸出語句。者之之所以感到編程難，就是忽視了這個基倡模塊化結(jié)構(gòu)化程序設(shè)計(jì)，不論BASIC、FONFTRAN、PASCAL還是其他高級語言，最終要涉及到子函數(shù)的設(shè)計(jì)和使用。C語言的源程序是由一個主函數(shù)和若干（或零個）子函數(shù)構(gòu)成函數(shù)直接或間接的調(diào)用自身時(shí)，這樣的函數(shù)稱為遞歸函數(shù)。是否能夠熟練的設(shè)計(jì)和使用函數(shù)，是體現(xiàn)一個有必要回顧和復(fù)習(xí)C語言函數(shù)的基本概念。函數(shù)設(shè)計(jì)的一般格式是：而函數(shù)體內(nèi)所需處理的數(shù)據(jù)往往通過形參表傳送，函數(shù)也可以不設(shè)形參表，此時(shí)寫為：例1.2設(shè)計(jì)一個函數(shù)計(jì)算三個整數(shù)之和，再設(shè)計(jì)一個函數(shù)7調(diào)用兩個函數(shù)。intsumx(inta,intb,intc)}}voidmain()printf(“\nsum=%d”,sumx(x,y,z));printf(“\n%6d%6d%6d”,x,y,z);printf(“\n“sum=%d”,sa);printf(“\n%6d%6d%6d”,x,y,z);運(yùn)行結(jié)果：/*在賦值語句中調(diào)用函數(shù)sumx()函數(shù)在被調(diào)用時(shí)，由主調(diào)程序提供實(shí)參，將信息傳遞給形參。在調(diào)法通常分為傳值和傳址兩大類。相同。傳值調(diào)用的主要特點(diǎn)是數(shù)據(jù)的單向傳遞，由實(shí)參通過形參將數(shù)據(jù)代入被調(diào)用函數(shù)，不論在調(diào)用期間形參值是否改變，調(diào)用結(jié)束返回主調(diào)函數(shù)之后，實(shí)參值都不會改變。8在不同的算法語言中，傳址調(diào)用的語法有所不同。在PASCAL語言中用變參實(shí)現(xiàn)傳址。不變，但是該地址中的數(shù)據(jù)發(fā)生相應(yīng)改變。這就是數(shù)據(jù)的雙向傳遞。現(xiàn)看一例題：例1.3設(shè)計(jì)一個函數(shù)實(shí)現(xiàn)兩個數(shù)據(jù)的交換，在主程序中調(diào)用。voidmain()printf(“\n%6d%6d”,x,y);}運(yùn)行結(jié)果：參地址中的內(nèi)容，而作為主函數(shù)變量x,y的地址仍然沒有改變。從整數(shù)交換的角度看，本例題實(shí)現(xiàn)了雙向數(shù)據(jù)傳遞。若從指針地址角度看，調(diào)用前后指針地址不變。如果需要在函數(shù)體中改變指針的地址，這就需要在原指針基礎(chǔ)之上再加一級指針：雜。不如PASCAL的變量參數(shù)簡便，也不如C++是數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)的重要語法基礎(chǔ)。定義結(jié)構(gòu)體的一般格式：9{變量名2；??結(jié)構(gòu)體類型的變量，聲明創(chuàng)建一個結(jié)構(gòu)體變量的方法是：例如：structElemTypestructElemType使得書寫更加簡便。例如：typedefstructElemType就是一個新的類型名，并且是結(jié)構(gòu)體類型名。聲明變量x的語一個結(jié)構(gòu)體中可以包含多個數(shù)據(jù)子域。數(shù)據(jù)子域的類型名一般指基本數(shù)據(jù)類型（intchar等也可是已經(jīng)定義的另一結(jié)構(gòu)體名。數(shù)據(jù)子域變量名可以是簡單變量，也可以是數(shù)組。它們也可以稱為結(jié)構(gòu)體的數(shù)據(jù)成員。通過“結(jié)構(gòu)體變量名.數(shù)據(jù)子域”可以訪問數(shù)據(jù)子域。例1.6設(shè)計(jì)Student結(jié)構(gòu)體，在主程序中運(yùn)用。typedefstruct/*定義結(jié)構(gòu)體Student*/voidmain()s1.num=1001;printf(“\n姓名：%s”,s1.nprintf(“\n學(xué)號：%d”,s1.}}構(gòu)體的指針，通過以下語句段可以說明結(jié)構(gòu)體指針的一般用法。p->num=101;p->x=83;printf(“\n%10s%6d%6d”,p->name,p->num,p->x);}設(shè)計(jì)一個一維數(shù)組，每個數(shù)組元素是Student結(jié)構(gòu)體類型，通過以下語句段可以說明結(jié)構(gòu)體數(shù)組的一般用法。可以通過“結(jié)構(gòu)體數(shù)組名[下標(biāo)].數(shù)據(jù)子域”訪問數(shù)據(jù)域。/inti;printf(“\nprintf(“\n姓名：%s”,a[i].name)；printf(“\n}}以上是關(guān)于結(jié)構(gòu)體的基本概念和簡單運(yùn)用。第二部分上機(jī)實(shí)驗(yàn)習(xí)題），體實(shí)習(xí)步驟如下：充分地分析和理解問題本身，弄清要求做什么（而不是怎么做），限制條件是什么。？），），結(jié)構(gòu)設(shè)計(jì)。詳細(xì)設(shè)計(jì)是對函數(shù)（模塊）的進(jìn)一步求精，用偽高級語言（寫出算法框架，這時(shí)不必確定很多結(jié)構(gòu)和變量。編碼，即程序設(shè)計(jì)，是對詳細(xì)設(shè)計(jì)結(jié)果的進(jìn)一步求精，即用某種差錯矯正，在程序成功后再刪去它們。熟悉高級語言用法，如C語言。熟悉機(jī)器（即操作系統(tǒng)），基本的查主要有兩條路徑，一是用一組測試數(shù)據(jù)手工執(zhí)行程序（或分模塊進(jìn)行二是通過閱讀言。如果程序中邏輯概念清楚，后者將比前者有效。序，表面上的麻煩工作可以大大降低調(diào)試時(shí)所面臨的復(fù)雜性，提高工作效率。在上機(jī)實(shí)開始之前要充分準(zhǔn)備實(shí)驗(yàn)數(shù)據(jù)，在上機(jī)實(shí)踐過程中要及時(shí)記錄實(shí)驗(yàn)數(shù)據(jù)，在上機(jī)實(shí)踐完成之后必須及時(shí)總結(jié)分析。寫出實(shí)驗(yàn)報(bào)告。一般性、較小規(guī)模的上機(jī)實(shí)驗(yàn)題，必須遵循下列要求。養(yǎng)成良好的習(xí)慣。實(shí)驗(yàn)者必須重視這一環(huán)節(jié)，否則等同于沒有完成實(shí)驗(yàn)任務(wù)。這里可以體現(xiàn)個人特色、何解決的；經(jīng)驗(yàn)和體會等。二、實(shí)驗(yàn)習(xí)報(bào)告的提高要求：階段性、較大規(guī)模的上機(jī)實(shí)驗(yàn)題，應(yīng)該遵循下列要求。養(yǎng)成科學(xué)的習(xí)慣。a.設(shè)計(jì)思想：存儲結(jié)構(gòu)（題目中限定的要描述）；主要算法基本思可以通過調(diào)用關(guān)系圖表達(dá)。c.實(shí)現(xiàn)注釋：各項(xiàng)功能的實(shí)現(xiàn)程度、在完成基本要求的基礎(chǔ)上還有什么功能。（3）用戶手冊：即使用說明。時(shí)間復(fù)雜度、空間復(fù)雜度分析；改進(jìn)設(shè)想；經(jīng)驗(yàn)和體會等。1.了解抽象數(shù)據(jù)類型（ADT）的基本概念，及描述2.通過對復(fù)數(shù)抽象數(shù)據(jù)類型ADT的實(shí)現(xiàn)，熟悉C語言語法及程序設(shè)計(jì)。學(xué)習(xí)打下基礎(chǔ)。復(fù)數(shù)抽象數(shù)據(jù)類型ADT的描述及實(shí)現(xiàn)。數(shù)據(jù)對象：D={c1,c2c1,c2□FloatSet}數(shù)據(jù)關(guān)系：R={<c1,c2>c1/*存儲表示，結(jié)構(gòu)體類型的定義*/typedefstructfloaty;voidoutputc(compa);compadd(compk,comph);printf("輸入實(shí)部realx=?");scanfprintf("輸入虛部xvpuy=?");scanfvoidoutputc(compa){printf("\n%f+%fi\n\n",a.x,a.y);}compadd(compk,comph)l.x=k.x+h.x;l.y=必需的語句（例如函數(shù)原型聲明、主函數(shù)中的調(diào)用等）。提示：//求兩個復(fù)數(shù)相乘之積的函數(shù)再次調(diào)試運(yùn)行程序。輸入數(shù)據(jù)，記錄結(jié)果，最后完成實(shí)驗(yàn)報(bào)告。1.了解線性表的邏輯結(jié)構(gòu)特性，以及這種特性在計(jì)算機(jī)內(nèi)的兩種存儲2.重點(diǎn)是線性表的基本操作在兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)；其中以鏈表的操作為側(cè)重點(diǎn)；并進(jìn)一步學(xué)習(xí)結(jié)構(gòu)化的程序設(shè)計(jì)方法。1.線性表的順序存儲表示（結(jié)構(gòu)）及存儲地址中也是相鄰的,既地址連續(xù)。不同的教材有不同的表示，有的直接采用一維數(shù)組，typedefstructintlength;/}SqList;（2）本程序是一個完整的、子函數(shù)較多的源程序。目的為學(xué)生提供一個示范，提供順序存儲表示的資料，供學(xué)生參考。比如，主函數(shù)中簡單“菜技術(shù)，同學(xué)們可以在main()函數(shù)中直接寫幾個簡單的調(diào)用語句，就象前面的復(fù)中的main()一樣。但是隨著學(xué)習(xí)的深入，盡早學(xué)會使用“菜單設(shè)計(jì)”技術(shù)，會明顯提高編程和運(yùn)行效率。#defineMAXSIZE20typedefintElemType;/*數(shù)據(jù)元素類型typedefstructintlength;/}SqList;voidout_list(SqListLvoidinsert_sq(SqList*L,inti,ElemTypee);ElemTypedelete_sq(SqList*L,inti);intlocat_sq(SqListL,ElemTyp{inti,k,loc;ElemTypee,x;charch;printf("\n1.建立線性表");printf("\nprintf("\n3.刪除第iprintf("\nprintf("\n6.結(jié)束程序運(yùn)行");printf("\n======================================");case2:{printf("\ni,e=?");scanf("%d,%d",&i,&e);insert_sq(&a,i,e);out_case3:{printf("\ni=?");scanf("%d",&i);x=delete_sq(&a,i);out_listprintf("\nx=%d",x);case4:{printf("\ne=?");scanf("%d",&e);if(loc==-1)printf("\n未找到%d",locprintf("\n再見！");printf(“\n打回車鍵，返回。“);ch=getch();/*建立線性表*/{inti;printf("\nn=?");scanf("%d",&L->length);for(i=0;i<L->length;i++){printf("\ndata}voidout_list(SqList{inti;charch;printf("\n");for(i=0;i<=L.length-1;i++)printf("%10dprintf("\n\n打回車鍵，繼續(xù)。“);ch=getch();voidinsert_sq(SqList*L,inti,ElemTypee){intj;if(L->length==MAXSIZE)printf("\noverflow!");elseif(i<1||i>L->length+1)printf("\nerroei!");else{for(j=L->length-1;j>i-1;j--)L->a[j+1]=L-L->a[i-1]=e;}ElemTypedelete_sq(SqList*L,inti){ElemTypex;intj;if(L->length==0)printf("\n是空表。underflow!");elseif(i<1||i>L->length){printf("\nerrori!");for(j=i;j<=L->length-1;j++)L->a[j-1]=L->a[j];}intlocat_sq(SqListL,Ele{inti=0;while(i<=L.length-1&&L.a[i]!=e)i+if(i<=L.length-1)retur2.線性表的鏈表存儲表示（結(jié)構(gòu)）及實(shí)現(xiàn)。存儲地址中可以不相鄰,既地址不連續(xù)。不同的教材的表示基本是一致的。typedefstructLNode（2）本程序是一個完整的、子函數(shù)較多的源程序。目的為學(xué)生提供一個示范，提供關(guān)于鏈表操作的資料，供學(xué)生參考。可以看到本程序的main(結(jié)構(gòu)十分相似。稍加改動還可為其他題目的源程序所用。typedefintElemType;typedefstructLNodevoidinsert_L(LNode*L,inti,ElemTypee);ElemTypedelete_L(LNode*L,inti);{inti,k,loc;ElemTypee,x;charch;printf("\n\n1.建立線性鏈表");printf("\n\nprintf("\n\n3.刪除第iprintf("\n\nprintf("\n\n5.結(jié)束程序運(yùn)行");printf("\n======================================");printf("\n請輸入您的選擇(1,2,3,4,5)")case2:{printf("\ni,e=?");scanf("%d,%d",&i,&e);insert_L(L,i,e);ocase3:{printf("\ni=?");scanf("%d",&i);x=delete_L(L,i);out_L(L); if(x!=-1)printf("\nx=%d\n",x);case4:{printf("\ne=?");scanf("%d",&e);if(loc==-1)printf("\n未找到%d",locprintf("\n----------------");printf("\nprintf(“\n/*建立線性鏈表再見！"); p=h;printf("\ndata=?");scanf("%d",&x);p->next=s;p=s;□printf("data=?(-111end)");scanf("%d",&x);}□ □建成后的鏈表h/*輸出單鏈表中的數(shù)據(jù)元素*/p=L->next;printf("\n\n");while(p!=NULL){pprintf("\n\n打回車鍵，繼續(xù)。“);ch=getch();voidinsert_L(LNode*L,inti,ElemTypee){LNode*s,*p,*q;intj;j=0;while(p!=NULL&&j<i-1)if(p==NULL||j>i-1)printf("\niERROR!");p->next=s;}ElemTypedelete_L(LNode*L,inti){LNode*p,*q;intj;ElemTypex;p=L;j=0;while(p->next!=NULL&&j<i-1){p=p->next;j++;}if(p->next==NULL){printf("\niERROR!");return(p->next=q->next;free(q);}{LNode*p;intj=1;p=L->next;while(p!=NULL&&p->data!=e)if(p!=NULL)return(j);elseretu3.約瑟夫問題的一種描述：編號為1，2，??,n的n個人按順時(shí)針方向圍坐一圈，開始按順時(shí)針方向自1開始順序報(bào)數(shù)。方法1．報(bào)m的人出列（將其刪除從他在順時(shí)針方向上的下一個人開始重新從一報(bào)數(shù)，??,如此下去，直到所有人全部出列為止。試設(shè)計(jì)一個程序求出出列順序。要求利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序打印出各人的編號和此人密碼。方法2.報(bào)m的人出列（將其刪除將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個人開始重新從一報(bào)數(shù)，??,如此下去，直到所有人全部出列為止。試設(shè)計(jì)一出各人的編號和此人密碼。typedefstructnode/*結(jié)點(diǎn)的結(jié)構(gòu)定義//*密碼子域/*指針域/voidouts(JOS*h,intm);printf(“\nenterthebeginsecretcode,m=（m>1）”);scanf(“%d”,&m);h=(JOS*)malloc(sizeof(JOS));h->link=h;pre=h;printf(“\n個人密碼=?”);scanf(“%d”,i++;new->num=i;new->sm=mi;/*結(jié)點(diǎn)送值*/pre->link=new;pre=new;/*形成循環(huán)鏈表*/printf(“\n個人密碼=?”);spre->link=h->link;free(h);h=pre->link;return(h);/*頭指voidouts(JOS*h,intm){inti;JOS*q=h,p;printf(“\n“);printf(“%6d%6d”,q->num,q->sm);p->link=q->link;free(q);}printf(“%6d%6d\n”,q->num,q->sm);麻煩同學(xué)們可以試一試，加進(jìn)頭結(jié)點(diǎn)如何實(shí)現(xiàn)并不是任何時(shí)候有頭結(jié)點(diǎn)都能使程序操作簡化，要根據(jù)實(shí)際情況，決定用是否使用頭結(jié)點(diǎn)。感興趣的同學(xué)可以設(shè)計(jì)一個程序?qū)崿F(xiàn)約瑟夫環(huán)的方在一般情況下默認(rèn)使用頭結(jié)點(diǎn)。不論是單向鏈表還是循環(huán)鏈表，頭指針不能丟。1.用順序存儲表示（數(shù)組）實(shí)現(xiàn)約瑟夫環(huán)2.一個線性表有n個元素（n<MAXSIZE,MAXSIZE指線性表的最大長度且遞增序?qū)崿F(xiàn)。要求：采用順序存儲表示實(shí)現(xiàn)；采用鏈?zhǔn)酱鎯Ρ硎痉椒▽?shí)現(xiàn)；比劣。要求1）指定的值x由鍵盤輸入2）程序能處理空鏈表的情況。4.用鏈表建立通訊錄。通訊錄內(nèi)容有：姓名、通訊地址、電話號碼。要求1）通訊錄是按姓名項(xiàng)的字母順序排列的；（2）能查找通訊錄中某人的信息；[提示]可用鏈表來存放這個通訊錄，一個中的‘當(dāng)前結(jié)點(diǎn)’的數(shù)據(jù)小，就插在其前面。否則，再看后面是否還有結(jié)點(diǎn)，若沒有結(jié)點(diǎn)了就插在其后面成為末結(jié)點(diǎn)；若后面還有結(jié)點(diǎn)，再與后面的結(jié)點(diǎn)逐一比較處理。5.超長正整數(shù)的加法，設(shè)計(jì)一個程序?qū)崿F(xiàn)放在鏈表的最后一個結(jié)點(diǎn)中，表頭結(jié)點(diǎn)值規(guī)定位-1。例如：大整數(shù)“567890987654321”可用如下的頭結(jié)點(diǎn)的鏈表表示：按照此數(shù)據(jù)結(jié)構(gòu)，可以從兩個表頭結(jié)點(diǎn)開始，順序依次對應(yīng)相加，求出所需要的進(jìn)位后，將其代入下一個結(jié)點(diǎn)進(jìn)行運(yùn)算。1.掌握棧這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。2.掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。3.了解和掌握遞歸程序設(shè)計(jì)的基本原理和方法。詳細(xì)。為了減輕學(xué)生上機(jī)實(shí)驗(yàn)的困難，在此給出幾個例題供參考。1.棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)。#defineMAXSIZE20typedefintElemType;/*數(shù)據(jù)元素類型typedefstruct{ElemTypea[MAXSIZE];inttop;/*}SqStack;voidout_s(SqStacks);{intk;ElemTypee,x;charch;init_s(&s1);printf("\n\n2.出棧一個元素，返回其值")；printf("\n\n3.結(jié)束程序運(yùn)行");printf("\n======================================");printf("\nprintf("\n----------------");printf("\n再見！")printf(“\n打回車鍵，返回。“);ch=getch(); voidout_s(SqStacks){charch;inti;/*千萬不能修改棧頂指針top*/if(s->top==-1)printf(“\nStackisNwhile(i!=-1){printf(“\ndata=%d”,s->a[i}printf(“\n打回車鍵，繼續(xù)。“);ch=getch();{if(s->top==MAXSIZE-1)printf}if(s->top==-1){printf(“\nStackisUnderf2.循環(huán)隊(duì)列（即隊(duì)列的順序存儲結(jié)構(gòu)）實(shí)現(xiàn)。typedefintElemType;typedefstructvoidout_Q(SqQueueQvoidEnQueue(SqQueu{intk;ElemTypee,x;charch;init_Q(&Q1);printf("\n\n2.出隊(duì)一個元素，返回其值")；printf("\n\n3.結(jié)束程序運(yùn)行");printf("\n======================================");printf("\nEnQueue(SqQueue&Q1,e);out_printf("\n----------------");printf("\n再見！");printf(“\n打回車鍵，返回。“);ch=getch(); {charch;inti;45350201if(Q->front==Q->rear)printf(“\nQueueisNULL.“);else{i=(Q->front+1)%while(i!=Q->rear){printf(“\ndata=%d”,Q->a[i]);printf(“\ndata=%d”,Q->a[i]);}printf(“\n打回車鍵，繼續(xù)。“);ch=getch();voidEnQueue(SqQueu{if((Q->rear+1)%MAXSIZE==Q->front)printelse{Q->rear=(Q->rear+1)%}400}}typedefintElemType;typedefstructQNodetypedefstruct}L_Queue;voidout_Q(L_QueueQvoidEnQueue(L_QueueQ,ElemTypee);ElemTypeDeQueue(L_Queue{intk;ElemTypee,x;charch;init_Q(&Q1);printf("\n\n2.出隊(duì)一個元素，返回其值")；printf("\n\n3.結(jié)束程序運(yùn)行");printf("\n======================================");printf("\nEnQueue(SqQueue&Q1,e);out_printf("\n----------------");printf("\n再見！");printf(“\n打回車鍵，返回。“);ch=getch(); p->next=NULL;∧∧voidout_Q(L_QueueQ){QNode*p;charch;p=Q.front->next;p=p->next;}printf(“\n打回車鍵，繼續(xù)。“);ch=getch();voidEnQueue(L_QueueQ,ElemTypeQ.rear->next=s;ElemTypeDeQueue(L_QuIf(Q.rear==p)Q.rear=Q基礎(chǔ)上修改程序，實(shí)現(xiàn)十進(jìn)制數(shù)據(jù)M向N進(jìn)制（2或8或（1）采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)棧。（2）采用鏈表結(jié)構(gòu)實(shí)現(xiàn)棧。2.阿克曼函數(shù)（Ackermann’sfunction）定義如下：人們之所以研究該函數(shù)，是因?yàn)閙和n值的較小增長都會引起函數(shù)值的極快增長。（1）設(shè)計(jì)運(yùn)用遞歸算法的源程序，上機(jī)運(yùn)行。（2）寫一個非遞歸算法的源程序，上機(jī)運(yùn)行。并進(jìn)行比較。3．二項(xiàng)式(a+b)n展開后，其系數(shù)構(gòu)成楊輝三角形，利用隊(duì)列寫出打印楊輝三角形的前n行的程序。11.熟悉串類型的實(shí)現(xiàn)方法，了解簡單文字處理的設(shè)計(jì)2.熟悉C語言的字符和把字符串處理的原理和方法。下面(1)字符：charch;ch是單個字符變量ch=’a’;’(2）字符串：S2=(char)malloc(si個串最多容10個字符；下列賦值語句是錯誤的：應(yīng)該使用串拷貝函數(shù)：strcpy(S1,“abcdefghi”);strcpy(S3[0],”123456789”);strcpy(S3[1],”用雙引號括起來的是字符串常量，在處理字符串常量時(shí)，注意總是有一個字符‘\0’作是1，??,s3[0][8]里是9,s3[0][9]里是‘\0’（串尾標(biāo)志）。(3)常見的字符函數(shù)：當(dāng)str1<str2，函數(shù)結(jié)果<0；接后的新串。實(shí)現(xiàn)字符串置換操作。{intk;char*s,t[]="abc",*v="%%%";printf("\ns=?");gets(s);printf("\ns=%s\n",s);printf("\nt=%sv=%s\n",t,v);replace(s,t,v);printf("\n\nnewstring=%s\n",s);{inti,j,k,po,sl,tl;printf("\nsl=%dtl=%d\n",sl,tl);po=0;printf("\nk=%2d",k);po=k+tl;printf("pos=%2d",po);}{inti,j,sl,tl;i=pos;j=1;sl=strlen(s);tl=strlen(t);while(i<=sl&&j<=tl)字符串常量的提供有多種手段。可以在定義串類型同時(shí)初始化串值：的方法修改、調(diào)試、運(yùn)行程序。熟悉稀疏矩陣的“三元組表”和“十字鏈表”存儲結(jié)構(gòu)，運(yùn)用它們進(jìn)行矩陣簡單運(yùn)算處理。稀疏矩陣的十字鏈表存儲與輸出。#include<stdio.h>#include<stdltypedefintEtype;typedefstructOLnode{inti,j;/*行號、列號域*/Etypee;}OLnode;typedefstruct}Crosslist;voidout_M(CrosslistMvoidout_M(Crosslist{inti;OLnode*p;charch；printf("\nm=%dn=%dt=%d\n",M.mu,M.nu,M.tu);if(p){printf("\ni=%d",i);while(p){printf("(%3d%3d%4d)",p=p->right;}}printf("\n");}printf(“\n打回車鍵，返回。“);ch=getch();}printf("\nm,n,t=?");scanf("%d,%d,%d",&m,&n,&t);for(i=1;i<=m;i++)M->rfor(j=1;j<=n;j++)M->ch[j]=NULL;M->mu=m;M->nu=n;M->tu=t;/*建立成空十字鏈表*/{printf("\ni,j,e=?");scp->i=row;p->j=col;p->e=va;q=M->rh[row];s=q;while(q!=NULL&&q->j<col){s=q;q=p->right=q;if(q==M->rh[row])M->rh[row]=p;elses->rwhile(q&&q->i<row){s=q;q=q->dowp->down=q;if(q==M->ch[col])M->ch[col]=p;elses-1.編寫用“三元組表”存儲（參見教科書P98頁）稀疏矩陣，進(jìn)行矩陣處理的程序。（1）矩陣轉(zhuǎn)置（2）矩陣加2.上機(jī)調(diào)試上面給出的十字鏈表的程序，在此基礎(chǔ)上增加查找功能：3.實(shí)現(xiàn)迷宮求解程序。1.熟練掌握二叉樹在二叉鏈表存儲結(jié)構(gòu)中的常用遍歷方法：先序遞歸遍歷、中序遞遞歸遍歷。2.用樹解決實(shí)際問題，如哈夫曼編碼等。加深對“數(shù)據(jù)結(jié)構(gòu)+算法=程序”的理解和認(rèn)識，提高編寫較復(fù)雜程序的能力。的序號（按滿二叉樹編號）和數(shù)據(jù)同時(shí)給出：序號數(shù)據(jù)元素。結(jié)合下圖的二叉樹數(shù)的輸要輸入。結(jié)合下圖的二叉樹數(shù)的輸入據(jù)順序應(yīng)該是：點(diǎn)的左右子樹。下列程序中的統(tǒng)計(jì)二叉樹結(jié)點(diǎn)的函數(shù)，是對二叉樹遍歷方法的應(yīng)用模仿練習(xí)。#include<stdio.h>/#include<stdlib.h>typedefstructBiTNode/*樹結(jié)點(diǎn)結(jié)構(gòu)*/\/\typedefstructBiTNode/*樹結(jié)點(diǎn)結(jié)構(gòu)*/\/\BiTNode*t;intn,n0,n1,n2,;{charch;intk;printf("\n\n1.建立二叉樹方法1");printf("\n\n2.建立二叉樹方法2");printf("\n\n3.中序遞歸遍歷二叉樹");printf("\n\n4.計(jì)算樹中結(jié)點(diǎn)個數(shù)");printf("\n\n5.結(jié)束程序運(yùn)行");printf("\n======================================");printf("\n請輸入您的選擇(1,2,3,4,5,6)"){case1:t=creat_bt1()case2:t=creat_bt2();break;/*調(diào)用遞歸建立二叉樹算法printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();printf(“\n二叉樹結(jié)點(diǎn)總數(shù)n=%d”,nprintf(“\n二叉樹葉子結(jié)點(diǎn)數(shù)n0=%d”,n0printf(“\n度為2的結(jié)點(diǎn)printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();printf("\n----------------");printf("\n再見！");printf(“\n打回車鍵，返回。“);ch=getch();/*利用二叉樹性質(zhì)5，借助一維數(shù)組V建立二叉樹*/{BiTNode*t,*p,*v[20];inti;Etypee;printf("\ni,data=?");scanf("%d%d",&i,&e);p->data=e;p->lch=NULL;p->rch=NULL;v[i]=p;if(i==1)t=p;else{j=i/2;if(i%2==0)v[j]->lch=p;/*序號為偶數(shù)elsev[j]->rch=p;/*序號為}printf("\ni,data=?");scanf("%d,%d",&i,&e);}printf("\ndata=");scanf("%d",&e);if(e==0)t=NULL;t->lch=creat_bt2(); t->rch=creat_bt2();}printf("%3d",p->data);}/*讀者可以試著運(yùn)用先序或后序遞歸if(p->lch==NULL&&p->lch==NULLif((p->lch==NULL&&p->lch!(p->lch!=NULL&&p->lch==Nif(p->lch!=NULL&&p->lch!=NULL}1.建立一棵二叉樹，要求用先序非遞歸方法遍歷二叉樹。2.建立一棵二叉樹，要求用“按層遍歷”的方法遍歷二叉樹”的函數(shù)。3.給定一組值，建立一棵二叉樹，求二叉數(shù)的樹深。4.哈夫曼樹問題。利用哈夫曼編碼進(jìn)行通訊可以大大提高信道利用率，縮短信息傳輸時(shí)間，的數(shù)據(jù)進(jìn)行解碼（復(fù)原）對于雙工信道（即可以雙向傳輸?shù)男诺烂慷硕家幸粋€完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。文，再輸出該文的二進(jìn)制碼。[測試數(shù)據(jù)]用下表中給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建ABCDEFGHIJKLMN15OPQRSTUVWXYZ1811并實(shí)現(xiàn)以下報(bào)文的譯碼和輸出：“THISPROGRAMISMYFAVORITE”。度優(yōu)先遍歷和廣度優(yōu)先遍歷。進(jìn)一步掌握遞歸算法的設(shè)計(jì)方法。程設(shè)計(jì)。（邊上帶權(quán)值的圖）的鄰接矩陣表示。typedefintVexType;typedefVexTypeMgraph[MAX][MAX];/*Mgraph是二維數(shù)組類型標(biāo)識符*/voidcreat_mg(Mgraphvoidout_mg(MgraphMgraphG1;/*建立鄰接矩陣*/voidcreat_mg(Mgraph{inti,j,k;for(j=1;j<=n;j++)G/*如果是網(wǎng)，G[i][j]=0該為G[i][j]=32767for(k=1;k<=e;k++)scanf(“%d%d”,&i,&j);G[i][j]=1;G[j][i]=1;}{inti,j,k;charch;for(i=1;i<=n;i++)for(j=1;j<=n;j++)printf(“%5d”}if(G[i][j]==1)printf(“\n存在邊<%d,%d>printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();2.圖的鄰接鏈表存儲及遞歸深度優(yōu)先遍歷。typedefintVexType;typedefstructVnode}Vnode;typedefVnodeLgraph[MAX];/*Lgraph是一維數(shù)組類型標(biāo)識符*/voidcreat_L(Lgraphvoidout_L(LgraphGvoiddfsL(LgraphG,intv);LgraphGa;for(i=0;i<MAX;i++)vis[i]=0;/*頂點(diǎn)訪問的標(biāo)志數(shù)組*/creat_L(Ga);/*建立圖鄰接鏈表Ga*/out_L(Ga);printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();/*建立鄰接鏈表*/voidcreat_L(Lgraph{Vnode*p,*q;inti,j,k;printf("輸入n,e=?");scanf("%d,%d",&n,&ep->data=i;p->next=G[j].next;G[j].next=p;/*p結(jié)點(diǎn)鏈接到第j條鏈*/}voidout_L(LgraphG){inti;Vnode*p;charch;{printf("\ni=%d",i);p=G[i].next;}printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();voiddfsL(LgraphG,intv) printf("%3d",G[v].data);p=G[v].next;p=p->next;的更加具體詳細(xì)）供參考。voidbfsL(Lgraphg,int{charch;printf("\n%d",g[v].data);vis[v]=1;enque(Q,v);while(Q.front!=Q.rep=g[x].next;vis[v]=1;enque(Q,}p=p->next;}}printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();1.閱讀理解上面第一個關(guān)于圖的鄰接矩陣的程序，做下列題目。提示：無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣是非對稱的。提示：城市名暫時(shí)用代號（1，2，??)表示，在程序中以數(shù)組的下標(biāo)表示城市名。它的鄰接矩陣如下：12345670∞∞∞0∞615∞∞∞∞∞02.調(diào)試運(yùn)行上面第二個程序，即圖的鄰接鏈表存儲的程序。解決下列問題。提示：有向圖的鄰接鏈表分為正鄰接鏈表和逆鄰接鏈表。運(yùn)行調(diào)試程序。法的特點(diǎn)、使用范圍和效率有進(jìn)一步的了解。typedefintEtype;typedefstructBiTNode/*BiTNode*t;intn,n0,n1,n2,;{charch;intk;t=creat_bt();/*inorder(t);printf("\n輸入data:");scanprintf(“\n打回車鍵，返回。“);ch=getch();33{intk;BiTNode*t=NULL,*s;{intk;BiTNode*t=NULL,*s;/inti,e; printf(“\nkey=?”);scanf(“%d”,&k);inti,e; {s=(BiTNode*)malloc(sizeof(BiTNode));建立后的二叉排序樹s->data=k;s->lch=NULL;f=search(t,k);/*調(diào)用查找算法，f是待找結(jié)點(diǎn)的父結(jié)點(diǎn)指elsef->rch=s;}printf(“\nKey=?”);scanf(“%d”,&k);}/*查找算法，返回的是待找結(jié)點(diǎn)（e）的父結(jié)點(diǎn)指針，為插入提供條件*/p=NULL;q=root;}return(p);/*返回值是待voidsearchx(BiTNode*root,inte)p=NULL;q=root;elseif(k<=q->data)q=q->lch;}if(tag==1)printf(“\nyes!”);elseprintf(“\nno!”);/*中根遍歷二叉排序樹，結(jié)果應(yīng)該是有printf(“name:%s\ttel:%s\n”,t□name,t□tel);display(t□rc);2.設(shè)有一組關(guān)鍵字(19,14,23,1,68,20,84,27,56,11,10,79)建,立一個哈希查找表。法解決沖突。熟悉幾種典型的排序方法，并對各種算法的特點(diǎn)、使用范圍了解。有廣泛的應(yīng)用。下面給出的是冒泡排序、快速排序的實(shí)現(xiàn)與比較。/*源程序的頭文件sort.hvoidgetrandat(Dataary[],intcount)/*{longinta=100001;inti;for(i=0;i<count;i++){a=(a*125}voidprdata(Dataary[],intcount){inti;charch;printf(“\n”);for(i=0;i<count;i++)printf(“%6d”,arprintf(“\n”);printf(“\n\n打回車鍵，結(jié)束顯示。“);ch=getch();#defineMAX1000typedefintElemType;/*關(guān)鍵字的類型typedefstructintshu;}Data;Dataar[MAX],br[Typedefstruct{intlo,hi;}Selem;typedefstructinttop;/*}SqStack;voidbubble(Dataary[],intn)voidqksort(Dataary[],intn)voidhoare(Dataary[],intl,inth)voidpush(SqStack*s,Seleme)/*進(jìn)棧一個元素*/intempty(SqStacks){intk,n,j;j;charch;printf("\n\n1.printf("\n\n2.一般情況的起泡排序")；printf("\n\n3.有序情況的起泡排序")；printf("\n\n4.一般情況的快速排序")；printf("\n\n5.有序情況的快速排序")；printf("\n\n6.結(jié)束程序運(yùn)行");printf("\n======================================");for(j=0;j<n;j++)br[j]prdata(ar,n);case2:{for(j=0;j<n;j++)ar[j]=br[j];bubble(ar,n);prdata(ar,n);prdata(ar,n);case4:{for(j=0;j<n;j++)ar[j]qksort(ar,n);prdata(ar,n);case5:{qksort(ar,n);prdata(ar,n);printf("\n----------------");printf("\n再見！")printf(“\n打回車鍵，返回。“);ch=getch();voidbubble(Dataary[],intn){inti,j,tag;Dtatax;if(ary[j].key>ary[j+1].key)voidqksort(Dataary[],intn)init_s(&s1);push(&s1,x);}}voidhoare(intary[],intl,inth){inti,j;Datax;i=l;j=h;x=ary[l];do{while((i<j)&&ary[j]>=x)j--;while((i<j)&&ary[i]<=x)iary[i]=x;return(i);/voidinit_s(SqStack*s)voidpush(SqStack*s,Seleme){if(s->top==MAX-1)prin}if(s->top==0){printf(“\nsatckEmpty!\n”);} 中左分區(qū)中的數(shù)據(jù)均小于等于ary[i].key，而右分區(qū)中的數(shù)據(jù)均大于等于ary[i].key（l≤i≤例：入棧時(shí)，要兩個參數(shù)即右區(qū)首、尾指針組成的結(jié)構(gòu)體變量入棧。快速排序的最壞情況亦即各元素已有序時(shí)，再進(jìn)行快速排序，這種情況下錄關(guān)鍵字無序的情況。排序因其應(yīng)用廣泛，所以人們在排序找方面的研究經(jīng)久不衰。1.編寫程序?qū)崿F(xiàn)簡單選擇排序、堆排序（或歸并排序），進(jìn)行比較分析。2.編寫程序?qū)崿F(xiàn)簡單插入排序、希爾排序（或基數(shù)排序），進(jìn)行比較分析，第三部分書面作業(yè)練習(xí)題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的□以及它們之間的□和運(yùn)算等的學(xué)科。2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R其中K是□的有限集合，R是K上的□有限集合。3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成□。4.線性表的順序存儲結(jié)構(gòu)是一種□的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種□的存儲結(jié)構(gòu)。5.算法分析的目的是□,算法分析的兩個主要方面是□。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性6.計(jì)算機(jī)算法指的是□,它必具備輸入、輸出和□等五個特性。□A.計(jì)算方法B.排序C.解決問題的有限運(yùn)算序列D.調(diào)度方法□A.可行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性7.線性表的邏輯順序與存儲順序總是一致的，這種說法□。8.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址□。C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以9.在以下的敘述中，正確的是□。B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出10.每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運(yùn)算：插入、刪除和查找，這種說法□。1.數(shù)據(jù)邏輯結(jié)構(gòu)包括□、□和□三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為□。2.在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)□前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有□個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn)□后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有□個后續(xù)結(jié)點(diǎn)。3.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有□結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有□個前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有□結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以□。4.在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以□。5.線性結(jié)構(gòu)中元素之間存在□關(guān)系，樹形結(jié)構(gòu)中元素之間存在□關(guān)系，圖形結(jié)構(gòu)中元素之間存在□關(guān)系。6.算法的五個重要特性是。8.下面程序段的時(shí)間復(fù)雜度是□。}1.21.線性結(jié)構(gòu)、 1A.iBA.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)B.散列方式和索引方式C.鏈表存儲結(jié)構(gòu)和數(shù)組A.QU—>rear—QU—>frontB.QU—>rear—QU—>front-1==m0C.QU—>front==QU—>rearD.QU—>front==QU—A.((QU—>rear-QU—>front)+Maxsize)%Maxsize==m0A.(rear-front+m)%mB.rear-fronC.rear-front-1D.r2.2填空題（將正確的答案填在2.向一個長度為n的向量的第i個元素（1≤i≤n+1）之前插入一個元素時(shí)，需向后移動____個元素。3.向一個長度為n的向量中刪除第i個元素（1≤i≤n）時(shí)，需向前移動____個元素。4.向棧中壓入元素的操作是___