《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書(修訂版)

《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書(修訂版)《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書(修訂版)《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書(修訂版)《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書(修訂版)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書鄭州輕工業(yè)學(xué)院

目錄前言 3實驗01順序表的基本操作 7實驗02單鏈表的基本操作 19實驗03棧的基本操作 32實驗04隊列的基本操作 35實驗05二叉樹的基本操作 38實驗06哈夫曼編碼 40實驗07圖的兩種存儲和遍歷 42實驗08最小生成樹、拓?fù)渑判蚝妥疃搪窂?46實驗09二叉排序樹的基本操作 48實驗10哈希表的生成 50實驗11常用的內(nèi)部排序算法 52附：實驗報告模板 54

前言《數(shù)據(jù)結(jié)構(gòu)》是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序開發(fā)的重要基礎(chǔ)，也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)的特點和在計算機內(nèi)的存儲方法，并在此基礎(chǔ)上介紹一些典型算法及其時、空效率分析。這門課程的主要任務(wù)是研究數(shù)據(jù)的邏輯關(guān)系以及這種邏輯關(guān)系在計算機中的表示、存儲和運算，培養(yǎng)學(xué)生能夠設(shè)計有效表達和簡化算法的數(shù)據(jù)結(jié)構(gòu)，從而提高其程序設(shè)計能力。通過學(xué)習(xí)，要求學(xué)生能夠掌握各種數(shù)據(jù)結(jié)構(gòu)的特點、存儲表示和典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的數(shù)據(jù)表達和存儲方案，設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。另外本課程的學(xué)習(xí)過程也是進行復(fù)雜程序設(shè)計的訓(xùn)練過程，通過算法設(shè)計和上機實踐的訓(xùn)練，能夠培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計能力。學(xué)習(xí)這門課程，習(xí)題和實驗是兩個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機實驗是最佳的途徑之一。因此，實驗環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。為了更好地配合學(xué)生實驗，特編寫實驗指導(dǎo)書。一、實驗?zāi)康谋菊n程實驗主要是為了原理和應(yīng)用的結(jié)合，通過實驗一方面使學(xué)生更好的理解數(shù)據(jù)結(jié)構(gòu)的概念和常用的幾種數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲和實現(xiàn)的方法，加強學(xué)生動手能力；另一方面培養(yǎng)學(xué)生從實際問題中抽象出對應(yīng)的抽象數(shù)據(jù)類型，進而找到合適的計算機存儲方法和算法，為以后課程的學(xué)習(xí)、大型軟件的開發(fā)、實際工程問題打下良好的軟件開發(fā)基礎(chǔ)。二、實驗要求1、每次實驗前學(xué)生必須根據(jù)實驗內(nèi)容認(rèn)真準(zhǔn)備實驗程序及調(diào)試時所需的輸入數(shù)據(jù)。2、在指導(dǎo)教師的幫助下能夠完成實驗內(nèi)容，得出正確的實驗結(jié)果。3、實驗結(jié)束后總結(jié)實驗內(nèi)容、書寫實驗報告。4、遵守實驗室規(guī)章制度、不缺席、按時上、下機。5、實驗學(xué)時內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機資格，平時成績扣10分。6、實驗報告有一次不合格，扣5分，兩次以上不合格者，平時成績以零分記。三、實驗環(huán)境VC++或其他C++相關(guān)的編譯環(huán)境。四、說明1、本實驗的所有算法中元素類型應(yīng)根據(jù)實際需要合理選擇。2、實驗題目中帶＊者為較高要求，學(xué)生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成70%，否則實驗不合格）。3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。4、好的算法決定了好的程序，要有效地實現(xiàn)算法，就需要設(shè)計能夠有效表達和簡化算法的數(shù)據(jù)結(jié)構(gòu)，因此數(shù)據(jù)結(jié)構(gòu)是有效進行程序設(shè)計的基礎(chǔ)，是每個程序員的必修課。五、實驗報告的書寫要求1、明確實驗的目的及要求。2、記錄實驗的輸入數(shù)據(jù)和輸出結(jié)果。3、說明實驗中出現(xiàn)的問題和解決過程。4、寫出實驗的體會和實驗過程中沒能解決的問題。5、實驗程序請構(gòu)建為多文件程序，每一個算法對應(yīng)的函數(shù)原型聲明存放在頭文件*.h中，對應(yīng)的函數(shù)實現(xiàn)存放在源文件*.c中；main()函數(shù)存放在另一個源文件中，該文件包含頭文件*.h即可。六、成績考評辦法1、期末考試占70分，閉卷。2、平時考評占30分。其中實驗環(huán)節(jié)占20分（實驗準(zhǔn)備、上機、報告、驗收等）；平時占10分（出勤、作業(yè)、測驗等）。七、參考書目1、《數(shù)據(jù)結(jié)構(gòu)》（Ｃ語言版）嚴(yán)蔚敏等清華大學(xué)出版社。2、《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版）嚴(yán)蔚敏等清華大學(xué)出版社。3、《數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述》，MarkAllenWeiss著，機械工業(yè)出版社，2012。

實驗01順序表的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：順序表的插入、刪除及應(yīng)用。目的要求：1．掌握順序存儲結(jié)構(gòu)的特點。2．掌握順序存儲結(jié)構(gòu)的常見算法。實驗內(nèi)容：編寫一個完整的程序，實現(xiàn)順序表的生成、插入、刪除、輸出等基本運算。建立一個順序表，含有n個數(shù)據(jù)元素。輸出順序表。在順序表中刪除值為x的結(jié)點或者刪除給定位置i的結(jié)點。實現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前，即表的前面為奇數(shù)，后面為偶數(shù)。輸入整型元素序列，利用有序表插入算法建立一個有序表。*利用算法5建立兩個非遞減有序表A和B，并把它們合并成一個非遞減有序表C。在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。*綜合訓(xùn)練：利用順序表實現(xiàn)一個班級學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等）。實驗說明：1．請構(gòu)建多文件程序，算法1至算法6對應(yīng)的函數(shù)原型聲明存放在頭文件中，對應(yīng)的函數(shù)實現(xiàn)存放在源文件中；main()函數(shù)存放在另一個源文件中，該文件包含頭文件即可。2．類型定義#defineMAXSIZE100立順序表\n");printf("\t\t\t2.遍歷順序表\n");printf("\t\t\t3.刪除第i個元素\n");printf("\t\t\t4.刪除值為x的元素\n");printf("\t\t\t5.奇數(shù)排在偶數(shù)之前\n");printf("\t\t\t6.插入法生成遞增有序表\n");printf("\t\t\t7.兩個非遞減有序表La和Lb合并成非遞減有序表Lc\n");printf("\t\t\t0.退出\n\n");}/*初始化順序表*/StatusInitList_Sq(SqList&L,intn){=(ElemType*)malloc(n*sizeof(ElemType));if(!exit(OVERFLOW);=0;=n;returnOK;}/*建立順序表*/StatusCreateList_Sq(SqList&L){intn,i;printf("請輸入順序表長度：");scanf("%d",&n);if(InitList_Sq(L,n)){printf("請輸入%d個元素：",n);for(i=0;i<n;i++){scanf("%d",&[i]);++;}returnOK;}elsereturnERROR;}/*輸出順序表*/voidPrintList_Sq(SqListL){inti;printf("順序表中元素為：\n");for(i=0;i<;i++){printf("%d",[i]);}printf("\n");}/*刪除第i個元素*/StatusDeleteList_Sq(SqList&L,inti,ElemType&e){ ElemType*p,*q; if((i<1)||(i>)returnERROR; p=&[i-1]); e=*p; q=+; for(++p;p<=q;++p)*(p-1)=*p; ; returnOK;}/*刪除值為x的元素，刪除成功返回OK，刪除失敗返回ERROR*/StatusDeleteListX_Sq(SqList&L,ElemTypex){ ElemType*p,*q; }/*奇數(shù)排在偶數(shù)之前*/StatusAdjustList_Sq(SqList&L){ElemType*p,*q;inttemp;returnOK;}/*插入法生成遞增有序表，有序表生成成功返回OK，失敗返回ERROR*/StatusOrderList_sq(SqList&L,intn){inti,j,x;/*x表示每次待插入的元素*/}/*兩個非遞減有序表A和B，并把它們合并成一個非遞減有序表C*/voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=;pb=;==+;pc==(ElemType*)malloc*sizeof(ElemType));if(!exit(OVERFLOW);pa_last=+-1;pb_last=+-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}#include""intmain(){intchoice,n,i,x;SqListL,La,Lb,Lc;while(1){menu();printf("選擇你的操作：");scanf("%d",&choice);switch(choice){case1:if(CreateList_Sq(L))printf("順序表創(chuàng)建成功\n");elseprintf("順序表創(chuàng)建失敗\n");break;case2:PrintList_Sq(L);break;case3:printf("請輸入刪除元素的位置：");scanf("%d",&i);if(DeleteList_Sq(L,i,x))printf("被刪除元素值為：%d\n",x);elseprintf("刪除失敗\n");break;case4:printf("請輸入刪除元素值：");scanf("%d",&x);if(DeleteListX_Sq(L,x))printf("刪除成功\n");elseprintf("刪除失敗\n");PrintList_Sq(L);break;case5:AdjustList_Sq(L);printf("新鏈表為：\n");PrintList_Sq(L);break;case6:printf("請輸入順序表長度：");scanf("%d",&n);if(OrderList_sq(L,n)){printf("值有序順序表為：\n");PrintList_Sq(L);}elseprintf("順序表創(chuàng)建失敗\n");break;case7:printf("請輸入順序表La的長度：");scanf("%d",&n);OrderList_sq(La,n);printf("請輸入順序表Lb的長度：");scanf("%d",&n);OrderList_sq(Lb,n);MergeList_Sq(La,Lb,Lc);printf("合并后的順序表為：\n");PrintList_Sq(Lc);break;case0:return0;default:printf("輸入錯誤，請重新輸入\n");}}}

實驗02單鏈表的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：單鏈表的插入、刪除及應(yīng)用。目的要求：1．掌握單鏈表的存儲特點及其實現(xiàn)。2．掌握單鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：編寫一個完整的程序，實現(xiàn)單鏈表的生成、插入、刪除、輸出等基本操作。隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單向鏈表（無序）。計算單鏈表的長度，遍歷單鏈表。把單鏈表中的元素逆置（不允許申請新的結(jié)點空間）。在單鏈表中刪除所有值為偶數(shù)的元素結(jié)點。編寫在非遞減有序單鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單鏈表。*利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞增有序鏈表。*利用算法5建立兩個非遞減有序單鏈表，然后合并成一個非遞減有序鏈表。*利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。*采用單鏈表實現(xiàn)一元多項式的存儲并實現(xiàn)兩個多項式相加并輸出結(jié)果。在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。*綜合訓(xùn)練：1）利用鏈表實現(xiàn)一個班級學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲到文件中）2）約瑟夫環(huán)問題：設(shè)有n個人圍坐在圓桌周圍，從某個位置開始編號為1，2，3，…，n，坐在編號為1的位置上的人從1開始報數(shù)，數(shù)到m的人便出列；下一個（第m+1個）人又從1開始報數(shù)，數(shù)到m的人便是第二個出列的人；如此重復(fù)下去，直到最后一個人出列為止，得到一個出列的編號順序。例如，當(dāng)n=8，m=4時，若從第一個位置數(shù)起，則出列的次序為4，8，5，2，1，3，7，6。試編寫程序確定出列的順序。要求用不帶頭結(jié)點的單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出個人編號。實驗說明：1．類型定義typedefintElemType;立單鏈表\n");printf("\t\t\t2.遍歷單鏈表\n");printf("\t\t\t3.計算鏈表長度\n");printf("\t\t\t4.鏈表逆置\n");printf("\t\t\t5.刪除偶數(shù)節(jié)點\n");printf("\t\t\t6.生成值有序單鏈表\n");printf("\t\t\t7.合并生成降序鏈表\n");printf("\t\t\t8.合并生成升序鏈表\n");printf("\t\t\t9.分解鏈表\n");printf("\t\t\t0.退出\n\n");}/*初始化空表*/StatusInit_Linklist(LinkList&L){L=(LinkList)malloc(sizeof(Lnode));if(!L)returnERROR; L->next=NULL; returnOK;}/*尾插法建立單鏈表*/StatusCreat_Linklist(LinkList&L){intx;LinkListp,rear;Init_Linklist(L);rear=L;printf("輸入-1表示輸入結(jié)束\n");while(scanf("%d",&x),x!=-1){p=(LinkList)malloc(sizeof(Lnode));if(!p)returnERROR;p->data=x;rear->next=p;rear=p;}rear->next=NULL;returnOK;}/*單鏈表遍歷*/voidDisp_Linklist(LinkListL){LinkListp;p=L->next;while(p){printf("%d",p->data);p=p->next;}printf("\n");}/*計算單鏈表長度*/intlength_Linklist(LinkListL){intcount=0;/*count表示單鏈表長度*/LinkListp;returncount;}/*單鏈表逆置*/voidReverse_Linklist(LinkListL){LinkListp,q;}/*刪除值為偶數(shù)的結(jié)點*/voidDelEven_Linklist(LinkListL){LinkListp,q;}/*在有序單鏈表中插入元素，鏈表仍然有序，插入成功返回OK，插入失敗返回ERROR*/StatusInsert_Linklist(LinkListL,intx){;}/*創(chuàng)建非遞減有序單鏈表，創(chuàng)建成功返回OK，創(chuàng)建失敗返回ERROR*/StatusCreatOrder_Linklist(LinkList&L){}/*兩個非遞減有序單鏈表La和Lb合并成一個非遞增有序鏈表Lc*/voidMergeDescend_Linklist(LinkListLa,LinkListLb,LinkList&Lc){}/*兩個非遞減有序單鏈表La和Lb合并成一個非遞減有序鏈表Lc*/voidMergeAscend_Linklist(LinkListLa,LinkListLb,LinkList&Lc){LinkListpa,pb,pc;pa=La->next;pb=Lb->next;pc=Lc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=papa:pb;free(Lb);}/*鏈表La按值分解成兩個鏈表，La全部為奇數(shù)，Lb全部為偶數(shù)*/voidSplit_Linklist(LinkListLa,LinkList&Lb){}#include""intmain(){intchoice,length;LinkListL,La,Lb,Lc;while(1){menu();printf("選擇你的操作：");scanf("%d",&choice);switch(choice){case1:if(Creat_Linklist(L))printf("單鏈表創(chuàng)建成功\n");elseprintf("單鏈表創(chuàng)建失敗\n");break;case2:Disp_Linklist(L);break;case3:length=length_Linklist(L);printf("單鏈表長度為：%d\n",length);break;case4:Reverse_Linklist(L);printf("逆置后的鏈表為：\n");Disp_Linklist(L);break;case5:DelEven_Linklist(L);printf("新鏈表為：\n");Disp_Linklist(L);break;case6:if(CreatOrder_Linklist(L)){printf("值有序鏈表為：\n");Disp_Linklist(L);}elseprintf("單鏈表創(chuàng)建失敗\n");break;case7:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeDescend_Linklist(La,Lb,Lc);printf("合并后的新鏈表為：\n");Disp_Linklist(Lc);break;case8:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeAscend_Linklist(La,Lb,Lc);printf("合并后的新鏈表為：\n");Disp_Linklist(Lc);break;case9:Creat_Linklist(L);Split_Linklist(L,Lb);printf("分裂后的新鏈表為：\n");Disp_Linklist(L);Disp_Linklist(Lb);break;case0:return0;default:printf("輸入錯誤，請重新輸入\n");}}}實驗03棧的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：順序棧、鏈棧，入棧、出棧。目的要求：1．掌握棧的思想及其存儲實現(xiàn)。2．掌握棧的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容：采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。采用鏈?zhǔn)酱鎯崿F(xiàn)棧的初始化、入棧、出棧操作。在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。*綜合訓(xùn)練：堆棧操作合法性：假設(shè)以S和X分別表示入棧和出棧操作。如果根據(jù)一個僅由S和X構(gòu)成的序列，對一個空堆棧進行操作，相應(yīng)操作均可行（如沒有出現(xiàn)刪除時?？眨┣易詈鬆顟B(tài)也是?？?，則稱該序列是合法的堆棧操作序列。請編寫程序，輸入S和X序列，判斷該序列是否合法。括號匹配檢驗：假設(shè)表達式中允許包括兩種括號：圓括號和方括號，其嵌套的順序隨意，即([]())或[([][])]等為正確的格式，[(])或([())等均為不正確格式。輸入一個表達式，判斷其中的括號是否能正確匹配。表達式轉(zhuǎn)換：算術(shù)表達式有前綴表示法、中綴表示法和后綴表示法等形式。日常使用的算術(shù)表達式是采用中綴表示法，即二元運算符位于兩個運算數(shù)中間。請設(shè)計程序?qū)⒅芯Y表達式轉(zhuǎn)換為后綴表達式。輸入在一行中給出不含空格的中綴表達式，可包含+、-、*、\以及左右括號()，表達式不超過20個字符。在一行中輸出轉(zhuǎn)換后的后綴表達式，要求不同對象（運算數(shù)、運算符號）之間以空格分隔，但結(jié)尾不得有多余空格。實驗說明：1．類型定義順序棧示例#defineMAX100xt格式存儲，統(tǒng)計該文件中各種字符的頻率，對各字符進行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將Huffman編碼文件翻譯成源文件。實驗說明：1．參考類型定義//雙親孩子表示法typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼表注意問題：1．遞歸算法的靈活應(yīng)用。2．多級指針的使用。

實驗07圖的兩種存儲和遍歷實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：圖的存儲、遍歷及其應(yīng)用。目的要求：1．掌握圖的存儲思想及其存儲實現(xiàn)。2．掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容：鍵盤輸入數(shù)據(jù)，分別建立一個有向圖和一個無向圖的鄰接表。輸出該鄰接表。在有向圖的鄰接表的基礎(chǔ)上計算各頂點的度，并輸出。采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先遍歷。采用鄰接表存儲實現(xiàn)無向圖的廣度優(yōu)先遍歷。在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。*綜合訓(xùn)練地下迷宮探索：假設(shè)有一個地下通道迷宮，它的通道都是直的，而通道所有交叉點（包括通道的端點）上都有一盞燈和一個開關(guān)。請問你如何從某個起點開始在迷宮中點亮所有的燈并回到起點輸入格式：輸入第一行給出三個正整數(shù)，分別表示地下迷宮的節(jié)點數(shù)N（1<N≤1000，表示通道所有交叉點和端點）、邊數(shù)M（M≤3000，表示通道數(shù)）和探索起始節(jié)點編號S（節(jié)點從1到N編號）。隨后的M行對應(yīng)M條邊（通道），每行給出一對正整數(shù)，分別是該條邊直接連通的兩個節(jié)點的編號。輸出格式：若可以點亮所有節(jié)點的燈，則輸出從S開始并以S結(jié)束的包含所有節(jié)點的序列，序列中相鄰的節(jié)點一定有邊（通道）；否則雖然不能點亮所有節(jié)點的燈，但還是輸出點亮部分燈的節(jié)點序列，最后輸出0，此時表示迷宮不是連通圖。由于深度優(yōu)先遍歷的節(jié)點序列是不唯一的，為了使得輸出具有唯一的結(jié)果，我們約定以節(jié)點小編號優(yōu)先的次序訪問（點燈）。在點亮所有可以點亮的燈后，以原路返回的方式回到起點。輸入樣例：6811223344556643615輸出樣例：12345654321實驗說明：

1．類型定義（鄰接表存儲）#defineMAX_VERTEX_NUM20//頂點最大個數(shù)typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;//邊的權(quán)值}ArcNode;//表結(jié)點

#defineVertexTypeint//頂點元素類型typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//typedefstruct{AdjListvertices;intvexnum,arcnum;//頂點的實際數(shù)，邊的實際數(shù)intkind;}ALGraph;2．上述類型定義可以根據(jù)實際情況適當(dāng)調(diào)整。3．算法4、5分別利用棧、隊列實現(xiàn)非遞歸算法。注意問題：1．注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。2．注意區(qū)別正、逆鄰接。

實驗08最小生成樹、拓?fù)渑判蚝妥疃搪窂綄嶒瀸W(xué)時：2學(xué)時實驗類型：上機背景知識：圖的存儲、遍歷及其應(yīng)用。目的要求：掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容：（1）鍵盤輸入數(shù)據(jù)，分別建立一個有向圖的鄰接表和一個無向圖的鄰接矩陣。（2）輸出該鄰接表和鄰接矩陣。（3）以有向圖的鄰接表為基礎(chǔ)輸出它的拓?fù)渑判蛐蛄?。?）以無向圖的鄰接矩陣為基礎(chǔ)實現(xiàn)最小生成樹的PRIM算法。（5）以有向圖的鄰接矩陣為基礎(chǔ)實現(xiàn)Dijkstra算法輸出單源點到其它頂點的最短路徑。（6）在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。（7）*綜合訓(xùn)練：校園導(dǎo)航1）問題描述：在給出校園各主要建筑的名稱信息及有路線連通的建筑之間的距離（或行進時間）的基礎(chǔ)上，利用校園導(dǎo)航系統(tǒng)計算出給定的起點到終點之間距離最近（或行進時間最短）的行進路線。2）設(shè)計要求：文件讀入或鍵盤方式讀入校園主要建筑信息及建筑間的距離（或行進時間）信息。創(chuàng)建完地圖后，以文件形式保存，以免重復(fù)創(chuàng)建。計算出給定的起點到終點之間距離最近（或行進時間最短）的行進路線，并輸出該路線（包括經(jīng)過哪些建筑）及其總距離（或總行進時間）。實驗說明：

1．類型定義鄰接表存儲見實驗07鄰接矩陣存儲示例#defineMAX_VERTEX_NUM20//頂點最大個數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{VRTypeadj;intweight;//邊的權(quán)值}ArcCell;AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;//頂點的實際數(shù)，邊的實際數(shù)GraphKindkind;}MGraph;注意問題：注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。

實驗09二叉排序樹的基本操作實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：樹表查找。目的要求：掌握二叉排序樹、AVL樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)。實驗內(nèi)容：隨機產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹，然后刪除某一指定關(guān)鍵字元素。*建立AVL樹并實現(xiàn)刪除某一指定關(guān)鍵字元素。*綜合訓(xùn)練：樹種統(tǒng)計隨著衛(wèi)星成像技術(shù)的應(yīng)用，自然資源研究機構(gòu)可以識別每一棵樹的種類。請編寫程序幫助研究人員統(tǒng)計每種樹的數(shù)量，計算每種樹占總數(shù)的百分比。首先輸入正整數(shù)N（≤105），隨后N行，每行給出衛(wèi)星觀測到的一棵樹的種類名稱。種類名稱由不超過30個英文字母和空格組成（不區(qū)分大小寫）。按字典序遞增輸出各種樹的種類名稱及其所占總數(shù)的百分比，其間以空格分隔，每種樹的信息占一行。實驗說明：1．存儲定義參見實驗05二叉鏈表的存儲。2．各種關(guān)鍵字?jǐn)?shù)據(jù)輸入可利用隨機函數(shù)自動產(chǎn)生，以便節(jié)省上機時間。注意問題：1．注意建立二叉排序樹時相同元素的處理。2．注意理解動態(tài)查找概念。

實驗10哈希表的生成實驗學(xué)時：2學(xué)時實驗類型：上機背景知識：哈希查找。目的要求：掌握哈希存儲結(jié)構(gòu)的思想，能選擇合適的哈希函數(shù)，實現(xiàn)不同沖突處理方法的哈希表的查找、建立。實驗內(nèi)容：（1）設(shè)計哈希函數(shù)及處理沖突的方法；（2）鍵盤輸入數(shù)據(jù)，利用設(shè)計的哈希函數(shù)及線性探測法生成哈希表；（3）用同樣的輸入數(shù)據(jù)和哈希函數(shù)，用鏈地址法處理沖突生成哈希表；（4）在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法；（5）分析兩種方法的平均查找長度。（6）*綜合訓(xùn)練：QQ帳戶的申請與登陸首先輸入一個正整數(shù)N（≤105），隨后給出N行指令。每行指令的格式為：“命令符（空格）QQ號碼（空格）密碼”。其中命令符為“N”（代表New）時表示要新申請一個QQ號，后面是新帳戶的號碼和密碼；命令符為“L”（代表Login）時表示是老帳戶登陸，后面是登陸信息。QQ號碼為一個不超