數(shù)據(jù)結構實驗與習題

1數(shù)據(jù)結構實驗與習題2要的環(huán)節(jié)。目前各種“數(shù)據(jù)結構”教材較為注重理論的敘述與介紹，算法描述上的原因編寫了這本“數(shù)據(jù)結構實驗與習題”。本參考書包括C語言基礎知識、上機實驗習題和書面作業(yè)練習題三部分。在C語言基礎知識部分，主要介紹了輸入/輸出、函數(shù)及參數(shù)傳遞和結構體的概念應用。這部分內容非常重要，掌握的是否熟練會直接影響“數(shù)據(jù)結構“的學習。在實驗部分，包括有完整的C語言源程序例題，介紹了一些設計數(shù)據(jù)結構題目所需程序，或者擴充已經給出的源程序，也有需獨立思考設計的綜合實驗題。答分析題。并且配有部分練習題的答案供學生自學、練習、參考。由于時間倉足、水平有限，書中難免存在錯誤和不妥之處，敬請讀者指正。3 1 3 5 8 10 12 20 28 30 32 34 40 42第三部分書面作業(yè)練習題 48 51 54 57 58 60 69 75 784言，由于該語言語法規(guī)范、嚴謹，非常適用于數(shù)據(jù)結構課程教學。在Windows環(huán)境下涌現(xiàn)出一系列的功能強大、面向對象的程序開發(fā)工具，如：VisualC++,BorlandC++,VBasic,VisualFoxpro等。由于VisualDelphi法描述工具。近年來在計算機科學研究、系統(tǒng)開發(fā)、教學以及應用開發(fā)中，C語言的使用越來越廣泛。因此，本教材采用類C語言進行算法描述。基礎好，可以越過這一部分內容不看。算法程序，如果數(shù)據(jù)不能正確輸入，算法設計得再好也無法正常運行。C語言的輸入是由系統(tǒng)提供的scanf()等函數(shù)實現(xiàn)，在程序的首部一般要求寫入：函數(shù)scanf()的功能很豐富，輸入格式也是多種多樣，這是大家較為熟悉的知識，這里不做詳細介紹。在使用中需要注意以下幾個問題。（1）一條scanf()語句有多個變量、并且都是數(shù)值型（int,float,double）時，在輸入數(shù)據(jù)時應該在一行之內鍵入多個數(shù)據(jù)，數(shù)據(jù)之間空格分隔。例如：scanf(“%d%f”,&n,&x);就是在兩個數(shù)據(jù)之間使用空格鍵為分隔符，最后打回車鍵。5如果語句中在%d和%f之間有一個逗號：（2）在需要字符型變量或字符串輸入時，要單獨寫一條輸入語句，這樣不易出錯。如果在同一條scanf()語句中將字符型和數(shù)值型混合輸入常常會出錯。因為鍵盤輸入時在數(shù)符，而不能起到‘分隔符’的作用。所以將它們混在一起容易出錯。（3）在scanf()語句中變量寫法應該是該變量的地址，這一點常被忽視。請看下列程序：4:printf(“\n請輸入姓名：”);scanf(“%s”,n5:printf(“\n請輸入性別：”);scanf(6:printf(“\n請輸入學號和成績：”);scanf}為了方便說明問題程序中加了行號，運行時當然不允許行號。一般情況下在scanf()語句中的變量名之前要加上求地址符&，上述程序第5，6行之中就是這地址，是該數(shù)組的首地址，所以name前面不加&。在本程序中把字符串、字符、數(shù)值型變量分別寫入不同的scanf()語句，輸入數(shù)據(jù)的具體形式如下：被忽略，還會影響后面的輸入語句無法正確讀入數(shù)據(jù)。因此，應該充分重視數(shù)據(jù)的輸入技術。C語言的輸出是由系統(tǒng)提供的printf()等函數(shù)來實現(xiàn)，在程序的首部一般要求寫入：輸出函數(shù)printf()的語法一般容易掌握，這里強調的是怎樣合理巧妙的使用它。1.在連續(xù)輸出多個數(shù)據(jù)時，數(shù)據(jù)之間一定要有間隔，不能連在6行符。這樣使光標與提示信息出現(xiàn)在同一行上，光標停在問號后邊：X=?。。幾個數(shù)據(jù)在同一行輸出，不能換行掉這些輔助輸出語句。者之之所以感到編程難，就是忽視了這個基倡模塊化結構化程序設計，不論BASIC、FONFTRAN、PASCAL還是其他高級語言，最終要涉及到子函數(shù)的設計和使用。C語言的源程序是由一個主函數(shù)和若干（或零個）子函數(shù)構成函數(shù)直接或間接的調用自身時，這樣的函數(shù)稱為遞歸函數(shù)。是否能夠熟練的設計和使用函數(shù)，是體現(xiàn)一個有必要回顧和復習C語言函數(shù)的基本概念。函數(shù)設計的一般格式是：而函數(shù)體內所需處理的數(shù)據(jù)往往通過形參表傳送，函數(shù)也可以不設形參表，此時寫為：例1.2設計一個函數(shù)計算三個整數(shù)之和，再設計一個函數(shù)7調用兩個函數(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);運行結果：/*在賦值語句中調用函數(shù)sumx()函數(shù)在被調用時，由主調程序提供實參，將信息傳遞給形參。在調法通常分為傳值和傳址兩大類。相同。傳值調用的主要特點是數(shù)據(jù)的單向傳遞，由實參通過形參將數(shù)據(jù)代入被調用函數(shù)，不論在調用期間形參值是否改變，調用結束返回主調函數(shù)之后，實參值都不會改變。8在不同的算法語言中，傳址調用的語法有所不同。在PASCAL語言中用變參實現(xiàn)傳址。不變，但是該地址中的數(shù)據(jù)發(fā)生相應改變。這就是數(shù)據(jù)的雙向傳遞?，F(xiàn)看一例題：例1.3設計一個函數(shù)實現(xiàn)兩個數(shù)據(jù)的交換，在主程序中調用。voidmain()printf(“\n%6d%6d”,x,y);}運行結果：參地址中的內容，而作為主函數(shù)變量x,y的地址仍然沒有改變。從整數(shù)交換的角度看，本例題實現(xiàn)了雙向數(shù)據(jù)傳遞。若從指針地址角度看，調用前后指針地址不變。如果需要在函數(shù)體中改變指針的地址，這就需要在原指針基礎之上再加一級指針：雜。不如PASCAL的變量參數(shù)簡便，也不如C++是數(shù)據(jù)結構程序設計的重要語法基礎。定義結構體的一般格式：9{變量名2；??結構體類型的變量，聲明創(chuàng)建一個結構體變量的方法是：例如：structElemTypestructElemType使得書寫更加簡便。例如：typedefstructElemType就是一個新的類型名，并且是結構體類型名。聲明變量x的語一個結構體中可以包含多個數(shù)據(jù)子域。數(shù)據(jù)子域的類型名一般指基本數(shù)據(jù)類型（intchar等也可是已經定義的另一結構體名。數(shù)據(jù)子域變量名可以是簡單變量，也可以是數(shù)組。它們也可以稱為結構體的數(shù)據(jù)成員。通過“結構體變量名.數(shù)據(jù)子域”可以訪問數(shù)據(jù)子域。例1.6設計Student結構體，在主程序中運用。typedefstruct/*定義結構體Student*/voidmain()s1.num=1001;printf(“\n姓名：%s”,s1.nprintf(“\n學號：%d”,s1.}}構體的指針，通過以下語句段可以說明結構體指針的一般用法。p->num=101;p->x=83;printf(“\n%10s%6d%6d”,p->name,p->num,p->x);}設計一個一維數(shù)組，每個數(shù)組元素是Student結構體類型，通過以下語句段可以說明結構體數(shù)組的一般用法?？梢酝ㄟ^“結構體數(shù)組名[下標].數(shù)據(jù)子域”訪問數(shù)據(jù)域。/inti;printf(“\nprintf(“\n姓名：%s”,a[i].name)；printf(“\n}}以上是關于結構體的基本概念和簡單運用。第二部分上機實驗習題），體實習步驟如下：充分地分析和理解問題本身，弄清要求做什么（而不是怎么做），限制條件是什么。？），），結構設計。詳細設計是對函數(shù)（模塊）的進一步求精，用偽高級語言（寫出算法框架，這時不必確定很多結構和變量。編碼，即程序設計，是對詳細設計結果的進一步求精，即用某種差錯矯正，在程序成功后再刪去它們。熟悉高級語言用法，如C語言。熟悉機器（即操作系統(tǒng)），基本的查主要有兩條路徑，一是用一組測試數(shù)據(jù)手工執(zhí)行程序（或分模塊進行二是通過閱讀言。如果程序中邏輯概念清楚，后者將比前者有效。序，表面上的麻煩工作可以大大降低調試時所面臨的復雜性，提高工作效率。在上機實開始之前要充分準備實驗數(shù)據(jù)，在上機實踐過程中要及時記錄實驗數(shù)據(jù)，在上機實踐完成之后必須及時總結分析。寫出實驗報告。一般性、較小規(guī)模的上機實驗題，必須遵循下列要求。養(yǎng)成良好的習慣。實驗者必須重視這一環(huán)節(jié)，否則等同于沒有完成實驗任務。這里可以體現(xiàn)個人特色、何解決的；經驗和體會等。二、實驗習報告的提高要求：階段性、較大規(guī)模的上機實驗題，應該遵循下列要求。養(yǎng)成科學的習慣。a.設計思想：存儲結構（題目中限定的要描述）；主要算法基本思可以通過調用關系圖表達。c.實現(xiàn)注釋：各項功能的實現(xiàn)程度、在完成基本要求的基礎上還有什么功能。（3）用戶手冊：即使用說明。時間復雜度、空間復雜度分析；改進設想；經驗和體會等。1.了解抽象數(shù)據(jù)類型（ADT）的基本概念，及描述2.通過對復數(shù)抽象數(shù)據(jù)類型ADT的實現(xiàn)，熟悉C語言語法及程序設計。學習打下基礎。復數(shù)抽象數(shù)據(jù)類型ADT的描述及實現(xiàn)。數(shù)據(jù)對象：D={c1,c2c1,c2□FloatSet}數(shù)據(jù)關系：R={<c1,c2>c1/*存儲表示，結構體類型的定義*/typedefstructfloaty;voidoutputc(compa);compadd(compk,comph);printf("輸入實部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ù)中的調用等）。提示：//求兩個復數(shù)相乘之積的函數(shù)再次調試運行程序。輸入數(shù)據(jù)，記錄結果，最后完成實驗報告。1.了解線性表的邏輯結構特性，以及這種特性在計算機內的兩種存儲2.重點是線性表的基本操作在兩種存儲結構上的實現(xiàn)；其中以鏈表的操作為側重點；并進一步學習結構化的程序設計方法。1.線性表的順序存儲表示（結構）及存儲地址中也是相鄰的,既地址連續(xù)。不同的教材有不同的表示，有的直接采用一維數(shù)組，typedefstructintlength;/}SqList;（2）本程序是一個完整的、子函數(shù)較多的源程序。目的為學生提供一個示范，提供順序存儲表示的資料，供學生參考。比如，主函數(shù)中簡單“菜技術，同學們可以在main()函數(shù)中直接寫幾個簡單的調用語句，就象前面的復中的main()一樣。但是隨著學習的深入，盡早學會使用“菜單設計”技術，會明顯提高編程和運行效率。#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.結束程序運行");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.線性表的鏈表存儲表示（結構）及實現(xiàn)。存儲地址中可以不相鄰,既地址不連續(xù)。不同的教材的表示基本是一致的。typedefstructLNode（2）本程序是一個完整的、子函數(shù)較多的源程序。目的為學生提供一個示范，提供關于鏈表操作的資料，供學生參考?？梢钥吹奖境绦虻膍ain(結構十分相似。稍加改動還可為其他題目的源程序所用。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.結束程序運行");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個人按順時針方向圍坐一圈，開始按順時針方向自1開始順序報數(shù)。方法1．報m的人出列（將其刪除從他在順時針方向上的下一個人開始重新從一報數(shù)，??,如此下去，直到所有人全部出列為止。試設計一個程序求出出列順序。要求利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序打印出各人的編號和此人密碼。方法2.報m的人出列（將其刪除將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從一報數(shù)，??,如此下去，直到所有人全部出列為止。試設計一出各人的編號和此人密碼。typedefstructnode/*結點的結構定義//*密碼子域/*指針域/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;/*結點送值*/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);麻煩同學們可以試一試，加進頭結點如何實現(xiàn)并不是任何時候有頭結點都能使程序操作簡化，要根據(jù)實際情況，決定用是否使用頭結點。感興趣的同學可以設計一個程序實現(xiàn)約瑟夫環(huán)的方在一般情況下默認使用頭結點。不論是單向鏈表還是循環(huán)鏈表，頭指針不能丟。1.用順序存儲表示（數(shù)組）實現(xiàn)約瑟夫環(huán)2.一個線性表有n個元素（n<MAXSIZE,MAXSIZE指線性表的最大長度且遞增序實現(xiàn)。要求：采用順序存儲表示實現(xiàn)；采用鏈式存儲表示方法實現(xiàn)；比劣。要求1）指定的值x由鍵盤輸入2）程序能處理空鏈表的情況。4.用鏈表建立通訊錄。通訊錄內容有：姓名、通訊地址、電話號碼。要求1）通訊錄是按姓名項的字母順序排列的；（2）能查找通訊錄中某人的信息；[提示]可用鏈表來存放這個通訊錄，一個中的‘當前結點’的數(shù)據(jù)小，就插在其前面。否則，再看后面是否還有結點，若沒有結點了就插在其后面成為末結點；若后面還有結點，再與后面的結點逐一比較處理。5.超長正整數(shù)的加法，設計一個程序實現(xiàn)放在鏈表的最后一個結點中，表頭結點值規(guī)定位-1。例如：大整數(shù)“567890987654321”可用如下的頭結點的鏈表表示：按照此數(shù)據(jù)結構，可以從兩個表頭結點開始，順序依次對應相加，求出所需要的進位后，將其代入下一個結點進行運算。1.掌握棧這種數(shù)據(jù)結構特性及其主要存儲結構，并能在現(xiàn)實生活中靈活運用。2.掌握隊列這種數(shù)據(jù)結構特性及其主要存儲結構，并能在現(xiàn)實生活中靈活運用。3.了解和掌握遞歸程序設計的基本原理和方法。詳細。為了減輕學生上機實驗的困難，在此給出幾個例題供參考。1.棧的順序存儲結構及實現(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.結束程序運行");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)隊列（即隊列的順序存儲結構）實現(xiàn)。typedefintElemType;typedefstructvoidout_Q(SqQueueQvoidEnQueue(SqQueu{intk;ElemTypee,x;charch;init_Q(&Q1);printf("\n\n2.出隊一個元素，返回其值")；printf("\n\n3.結束程序運行");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.出隊一個元素，返回其值")；printf("\n\n3.結束程序運行");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基礎上修改程序，實現(xiàn)十進制數(shù)據(jù)M向N進制（2或8或（1）采用順序存儲結構實現(xiàn)棧。（2）采用鏈表結構實現(xiàn)棧。2.阿克曼函數(shù)（Ackermann’sfunction）定義如下：人們之所以研究該函數(shù)，是因為m和n值的較小增長都會引起函數(shù)值的極快增長。（1）設計運用遞歸算法的源程序，上機運行。（2）寫一個非遞歸算法的源程序，上機運行。并進行比較。3．二項式(a+b)n展開后，其系數(shù)構成楊輝三角形，利用隊列寫出打印楊輝三角形的前n行的程序。11.熟悉串類型的實現(xiàn)方法，了解簡單文字處理的設計2.熟悉C語言的字符和把字符串處理的原理和方法。下面(1)字符：charch;ch是單個字符變量ch=’a’;’(2）字符串：S2=(char)malloc(si個串最多容10個字符；下列賦值語句是錯誤的：應該使用串拷貝函數(shù)：strcpy(S1,“abcdefghi”);strcpy(S3[0],”123456789”);strcpy(S3[1],”用雙引號括起來的是字符串常量，在處理字符串常量時，注意總是有一個字符‘\0’作是1，??,s3[0][8]里是9,s3[0][9]里是‘\0’（串尾標志）。(3)常見的字符函數(shù)：當str1<str2，函數(shù)結果<0；接后的新串。實現(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)字符串常量的提供有多種手段?？梢栽诙x串類型同時初始化串值：的方法修改、調試、運行程序。熟悉稀疏矩陣的“三元組表”和“十字鏈表”存儲結構，運用它們進行矩陣簡單運算處理。稀疏矩陣的十字鏈表存儲與輸出。#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頁）稀疏矩陣，進行矩陣處理的程序。（1）矩陣轉置（2）矩陣加2.上機調試上面給出的十字鏈表的程序，在此基礎上增加查找功能：3.實現(xiàn)迷宮求解程序。1.熟練掌握二叉樹在二叉鏈表存儲結構中的常用遍歷方法：先序遞歸遍歷、中序遞遞歸遍歷。2.用樹解決實際問題，如哈夫曼編碼等。加深對“數(shù)據(jù)結構+算法=程序”的理解和認識，提高編寫較復雜程序的能力。的序號（按滿二叉樹編號）和數(shù)據(jù)同時給出：序號數(shù)據(jù)元素。結合下圖的二叉樹數(shù)的輸要輸入。結合下圖的二叉樹數(shù)的輸入據(jù)順序應該是：點的左右子樹。下列程序中的統(tǒng)計二叉樹結點的函數(shù)，是對二叉樹遍歷方法的應用模仿練習。#include<stdio.h>/#include<stdlib.h>typedefstructBiTNode/*樹結點結構*/\/\typedefstructBiTNode/*樹結點結構*/\/\BiTNode*t;intn,n0,n1,n2,;{charch;intk;printf("\n\n1.建立二叉樹方法1");printf("\n\n2.建立二叉樹方法2");printf("\n\n3.中序遞歸遍歷二叉樹");printf("\n\n4.計算樹中結點個數(shù)");printf("\n\n5.結束程序運行");printf("\n======================================");printf("\n請輸入您的選擇(1,2,3,4,5,6)"){case1:t=creat_bt1()case2:t=creat_bt2();break;/*調用遞歸建立二叉樹算法printf("\n\n打回車鍵，繼續(xù)?！?;ch=getch();printf(“\n二叉樹結點總數(shù)n=%d”,nprintf(“\n二叉樹葉子結點數(shù)n0=%d”,n0printf(“\n度為2的結點printf("\n\n打回車鍵，繼續(xù)。“);ch=getch();printf("\n----------------");printf("\n再見！");printf(“\n打回車鍵，返回。“);ch=getch();/*利用二叉樹性質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);}/*讀者可以試著運用先序或后序遞歸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.哈夫曼樹問題。利用哈夫曼編碼進行通訊可以大大提高信道利用率，縮短信息傳輸時間，的數(shù)據(jù)進行解碼（復原）對于雙工信道（即可以雙向傳輸?shù)男诺烂慷硕家幸粋€完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。文，再輸出該文的二進制碼。[測試數(shù)據(jù)]用下表中給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建ABCDEFGHIJKLMN15OPQRSTUVWXYZ1811并實現(xiàn)以下報文的譯碼和輸出：“THISPROGRAMISMYFAVORITE”。度優(yōu)先遍歷和廣度優(yōu)先遍歷。進一步掌握遞歸算法的設計方法。程設計。（邊上帶權值的圖）的鄰接矩陣表示。typedefintVexType;typedefVexTypeMgraph[MAX][MAX];/*Mgraph是二維數(shù)組類型標識符*/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ù)組類型標識符*/voidcreat_L(Lgraphvoidout_L(LgraphGvoiddfsL(LgraphG,intv);LgraphGa;for(i=0;i<MAX;i++)vis[i]=0;/*頂點訪問的標志數(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結點鏈接到第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;的更加具體詳細）供參考。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.閱讀理解上面第一個關于圖的鄰接矩陣的程序，做下列題目。提示：無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣是非對稱的。提示：城市名暫時用代號（1，2，??)表示，在程序中以數(shù)組的下標表示城市名。它的鄰接矩陣如下：12345670∞∞∞0∞615∞∞∞∞∞02.調試運行上面第二個程序，即圖的鄰接鏈表存儲的程序。解決下列問題。提示：有向圖的鄰接鏈表分為正鄰接鏈表和逆鄰接鏈表。運行調試程序。法的特點、使用范圍和效率有進一步的了解。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);/*調用查找算法，f是待找結點的父結點指elsef->rch=s;}printf(“\nKey=?”);scanf(“%d”,&k);}/*查找算法，返回的是待找結點（e）的父結點指針，為插入提供條件*/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!”);/*中根遍歷二叉排序樹，結果應該是有printf(“name:%s\ttel:%s\n”,t□name,t□tel);display(t□rc);2.設有一組關鍵字(19,14,23,1,68,20,84,27,56,11,10,79)建,立一個哈希查找表。法解決沖突。熟悉幾種典型的排序方法，并對各種算法的特點、使用范圍了解。有廣泛的應用。下面給出的是冒泡排序、快速排序的實現(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打回車鍵，結束顯示。“);ch=getch();#defineMAX1000typedefintElemType;/*關鍵字的類型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)/*進棧一個元素*/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.結束程序運行");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ù)即右區(qū)首、尾指針組成的結構體變量入棧?？焖倥判虻淖顗那闆r亦即各元素已有序時，再進行快速排序，這種情況下錄關鍵字無序的情況。排序因其應用廣泛，所以人們在排序找方面的研究經久不衰。1.編寫程序實現(xiàn)簡單選擇排序、堆排序（或歸并排序），進行比較分析。2.編寫程序實現(xiàn)簡單插入排序、希爾排序（或基數(shù)排序），進行比較分析，第三部分書面作業(yè)練習題1.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的□以及它們之間的□和運算等的學科。2.數(shù)據(jù)結構被形式地定義為（K，R其中K是□的有限集合，R是K上的□有限集合。3.在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成□。4.線性表的順序存儲結構是一種□的存儲結構，線性表的鏈式存儲結構是一種□的存儲結構。5.算法分析的目的是□,算法分析的兩個主要方面是□。A.找出數(shù)據(jù)結構的合理性B.研究算法中的輸入和輸出的關系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性A.空間復雜性和時間復雜性B.正確性和簡明性C.可讀性和文檔性6.計算機算法指的是□,它必具備輸入、輸出和□等五個特性?！魽.計算方法B.排序C.解決問題的有限運算序列D.調度方法□A.可行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性7.線性表的邏輯順序與存儲順序總是一致的，這種說法□。8.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址□。C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以9.在以下的敘述中，正確的是□。B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進先出10.每種數(shù)據(jù)結構都具備三個基本運算：插入、刪除和查找，這種說法□。1.數(shù)據(jù)邏輯結構包括□、□和□三種類型，樹形結構和圖形結構合稱為□。2.在線性結構中，第一個結點□前驅結點，其余每個結點有且只有□個前驅結點；最后一個結點□后續(xù)結點，其余每個結點有且只有□個后續(xù)結點。3.在樹形結構中，樹根結點沒有□結點，其余每個結點有且只有□個前驅結點，葉子結點沒有□結點，其余每個結點的后續(xù)結點可以□。4.在圖形結構中，每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以□。5.線性結構中元素之間存在□關系，樹形結構中元素之間存在□關系，圖形結構中元素之間存在□關系。6.算法的五個重要特性是。8.下面程序段的時間復雜度是□。}1.21.線性結構、 1A.iBA.順序存儲結構和鏈式存儲結構B.散列方式和索引方式C.鏈表存儲結構和數(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）之前插入一個元素時，需向后移動____個元素。3.向一個長度為n的向量中刪除第i個元素（1≤i≤n）時，需向前移動____個元素。4.向棧中壓入元素的操作是___