數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)最新版本

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)鄭州輕工業(yè)學(xué)院2016.02.20目錄前言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)的一門(mén)核心基礎(chǔ)課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序開(kāi)發(fā)的重要基礎(chǔ)，也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)的特點(diǎn)和在計(jì)算機(jī)內(nèi)的存儲(chǔ)方法，并在此基礎(chǔ)上介紹一些典型算法及其時(shí)、空效率分析。這門(mén)課程的主要任務(wù)是研究數(shù)據(jù)的邏輯關(guān)系以及這種邏輯關(guān)系在計(jì)算機(jī)中的表示、存儲(chǔ)和運(yùn)算，培養(yǎng)學(xué)生能夠設(shè)計(jì)有效表達(dá)和簡(jiǎn)化算法的數(shù)據(jù)結(jié)構(gòu)，從而提高其程序設(shè)計(jì)能力。通過(guò)學(xué)習(xí)，要求學(xué)生能夠掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示和典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)

2、，能夠根據(jù)實(shí)際問(wèn)題選取合適的數(shù)據(jù)表達(dá)和存儲(chǔ)方案，設(shè)計(jì)出簡(jiǎn)潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開(kāi)發(fā)打下良好的基礎(chǔ)。另外本課程的學(xué)習(xí)過(guò)程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，通過(guò)算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，能夠培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)能力。學(xué)習(xí)這門(mén)課程，習(xí)題和實(shí)驗(yàn)是兩個(gè)關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機(jī)實(shí)驗(yàn)是最佳的途徑之一。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫(xiě)實(shí)驗(yàn)指導(dǎo)書(shū)。一、實(shí)驗(yàn)?zāi)康谋菊n程實(shí)驗(yàn)主要是為了原理和應(yīng)用的結(jié)合，通過(guò)實(shí)驗(yàn)一方面使學(xué)生更好的理解數(shù)據(jù)結(jié)構(gòu)的概念和常用的幾種數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)和實(shí)現(xiàn)的方法，加強(qiáng)學(xué)生動(dòng)手能力；另一方面培養(yǎng)學(xué)生從實(shí)際

3、問(wèn)題中抽象出對(duì)應(yīng)的抽象數(shù)據(jù)類型，進(jìn)而找到合適的計(jì)算機(jī)存儲(chǔ)方法和算法，為以后課程的學(xué)習(xí)、大型軟件的開(kāi)發(fā)、實(shí)際工程問(wèn)題打下良好的軟件開(kāi)發(fā)基礎(chǔ)。二、實(shí)驗(yàn)要求1、每次實(shí)驗(yàn)前學(xué)生必須根據(jù)實(shí)驗(yàn)內(nèi)容認(rèn)真準(zhǔn)備實(shí)驗(yàn)程序及調(diào)試時(shí)所需的輸入數(shù)據(jù)。 2、在指導(dǎo)教師的幫助下能夠完成實(shí)驗(yàn)內(nèi)容，得出正確的實(shí)驗(yàn)結(jié)果。 3、實(shí)驗(yàn)結(jié)束后總結(jié)實(shí)驗(yàn)內(nèi)容、書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告。4、遵守實(shí)驗(yàn)室規(guī)章制度、不缺席、按時(shí)上、下機(jī)。 5、實(shí)驗(yàn)學(xué)時(shí)內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機(jī)資格，平時(shí)成績(jī)扣10分。6、實(shí)驗(yàn)報(bào)告有一次不合格，扣5分，兩次以上不合格者，平時(shí)成績(jī)以零分記。三、實(shí)驗(yàn)環(huán)境 VC+6.0或其他C+

4、相關(guān)的編譯環(huán)境。四、說(shuō)明1、本實(shí)驗(yàn)的所有算法中元素類型應(yīng)根據(jù)實(shí)際需要合理選擇。2、實(shí)驗(yàn)題目中帶者為較高要求，學(xué)生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成70%，否則實(shí)驗(yàn)不合格）。3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過(guò)程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。4、好的算法決定了好的程序，要有效地實(shí)現(xiàn)算法，就需要設(shè)計(jì)能夠有效表達(dá)和簡(jiǎn)化算法的數(shù)據(jù)結(jié)構(gòu)，因此數(shù)據(jù)結(jié)構(gòu)是有效進(jìn)行程序設(shè)計(jì)的基礎(chǔ)，是每個(gè)程序員的必修課。五、實(shí)驗(yàn)報(bào)告的書(shū)寫(xiě)要求1、明確實(shí)驗(yàn)的目的及要求。2、記錄實(shí)驗(yàn)的輸入數(shù)據(jù)和輸出結(jié)果。 3、說(shuō)明實(shí)驗(yàn)中出現(xiàn)的問(wèn)題和解決過(guò)程。4、寫(xiě)出

5、實(shí)驗(yàn)的體會(huì)和實(shí)驗(yàn)過(guò)程中沒(méi)能解決的問(wèn)題。5、實(shí)驗(yàn)程序請(qǐng)構(gòu)建為多文件程序，每一個(gè)算法對(duì)應(yīng)的函數(shù)原型聲明存放在頭文件*.h中，對(duì)應(yīng)的函數(shù)實(shí)現(xiàn)存放在源文件*.c中；main()函數(shù)存放在另一個(gè)源文件中，該文件包含頭文件*.h即可。六、成績(jī)考評(píng)辦法1、期末考試占70分，閉卷。2、平時(shí)考評(píng)占30分。其中實(shí)驗(yàn)環(huán)節(jié)占20分（實(shí)驗(yàn)準(zhǔn)備、上機(jī)、報(bào)告、驗(yàn)收等）；平時(shí)占10分（出勤、作業(yè)、測(cè)驗(yàn)等）。七、參考書(shū)目1、數(shù)據(jù)結(jié)構(gòu)（語(yǔ)言版） 嚴(yán)蔚敏等 清華大學(xué)出版社 2、數(shù)據(jù)結(jié)構(gòu)題集 （C語(yǔ)言版） 嚴(yán)蔚敏等 清華大學(xué)出版社 3、數(shù)據(jù)結(jié)構(gòu)與算法分析C語(yǔ)言描述，Mark Allen Weiss著，機(jī)械工業(yè)出版社，2012實(shí)驗(yàn)01

6、 順序表的基本操作實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)實(shí)驗(yàn)類型：上機(jī)背景知識(shí)：順序表的插入、刪除及應(yīng)用。目的要求： 1掌握順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。 2掌握順序存儲(chǔ)結(jié)構(gòu)的常見(jiàn)算法。實(shí)驗(yàn)內(nèi)容：編寫(xiě)一個(gè)完整的程序，實(shí)現(xiàn)順序表的生成、插入、刪除、輸出等基本運(yùn)算。（1） 建立一個(gè)順序表，含有n個(gè)數(shù)據(jù)元素。（2） 輸出順序表。（3） 在順序表中刪除值為x的結(jié)點(diǎn)或者刪除給定位置i的結(jié)點(diǎn)。（4） 實(shí)現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前，即表的前面為奇數(shù)，后面為偶數(shù)。（5） 輸入整型元素序列，利用有序表插入算法建立一個(gè)有序表。（6） *利用算法5建立兩個(gè)非遞減有序表A和B，并把它們合并成一個(gè)非遞減有序表C。（7） 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜

7、單，分別測(cè)試上述算法。（8） *綜合訓(xùn)練： 利用順序表實(shí)現(xiàn)一個(gè)班級(jí)學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等）。實(shí)驗(yàn)說(shuō)明：1請(qǐng)構(gòu)建多文件程序，算法1至算法6對(duì)應(yīng)的函數(shù)原型聲明存放在頭文件SqList.h中，對(duì)應(yīng)的函數(shù)實(shí)現(xiàn)存放在源文件SqList.c中；main()函數(shù)存放在另一個(gè)源文件中，該文件包含頭文件SqList.h即可。2類型定義 #define MAXSIZE 100 /表中元素的最大個(gè)數(shù) typedef int ElemType; /元素類型 typedef struct ElemType *elem; /線性表 int length; /表的實(shí)際長(zhǎng)度 int listsize

8、; /當(dāng)前分配的存儲(chǔ)容量 SqList; /順序表的類型名3建立順序表時(shí)可利用隨機(jī)函數(shù)自動(dòng)產(chǎn)生數(shù)據(jù)。注意問(wèn)題：1、 插入、刪除時(shí)元素的移動(dòng)原因、方向及先后順序。2、 理解函數(shù)形參與實(shí)參的傳遞關(guān)系。部分源代碼：DS.h#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;SqList.h#ifndef SQLI

9、ST_H_INCLUDED#define SQLIST_H_INCLUDED#include "DS.h"typedef int ElemType;typedef struct ElemType *elem; int length; int listsize;SqList;void menu();Status InitList_Sq(SqList &L, int n);/*初始化順序表*/Status CreateList_Sq(SqList &L);/*建立順序表*/void PrintList_Sq(SqList L);/*輸出順序表*/Status D

10、eleteList_Sq(SqList &L,int i,ElemType &e);/*刪除第i個(gè)元素*/Status DeleteListX_Sq(SqList &L,ElemType x);/*刪除值為x的元素*/Status AdjustList_Sq(SqList &L);/*奇數(shù)排在偶數(shù)之前*/Status OrderList_sq(SqList &L, int n);/*插入法生成遞增有序表*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/*兩個(gè)非遞減有序表A和B，并把它們

11、合并成一個(gè)非遞減有序表C*/#endif / SQLIST_H_INCLUDEDSqList.cpp#include "SqList.h"void menu() printf("ttt 順序表基本操作nn"); printf("ttt1.建 立 順 序 表n"); printf("ttt2.遍 歷 順 序 表n"); printf("ttt3.刪 除 第 i 個(gè) 元 素n"); printf("ttt4.刪 除 值 為 x 的 元 素n"); printf("ttt

12、5.奇 數(shù) 排 在 偶 數(shù) 之 前n"); printf("ttt6.插 入 法 生 成 遞 增 有 序 表n"); printf("ttt7.兩個(gè)非遞減有序表La和Lb合并成非遞減有序表Lcn"); printf("ttt0.退 出nn");/*初始化順序表*/Status InitList_Sq(SqList &L, int n) L.elem=(ElemType*)malloc(n*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.lists

13、ize=n; return OK;/*建立順序表*/Status CreateList_Sq(SqList &L) int n, i; printf("請(qǐng)輸入順序表長(zhǎng)度："); scanf("%d", &n); if(InitList_Sq(L, n) printf("請(qǐng)輸入%d個(gè)元素：", n); for(i = 0; i < n; i+) scanf("%d", &L.elemi); L.length+; return OK; else return ERROR;/*輸出順序表*/

14、void PrintList_Sq(SqList L) int i; printf("順序表中元素為：n"); for(i = 0; i < L.length; i+) printf("%d ", L.elemi); printf("n");/*刪除第i個(gè)元素*/Status DeleteList_Sq(SqList &L,int i,ElemType &e)ElemType *p, *q;if( (i<1) | (i>L.length) ) return ERROR;p = &(L.elem

15、i-1);e = *p; q = L.elem+L.length-1;for(+p; p <= q; +p) *(p-1) = *p;-L.length;return OK;/*刪除值為x的元素，刪除成功返回OK，刪除失敗返回ERROR*/Status DeleteListX_Sq(SqList &L,ElemType x)ElemType *p, *q;/*奇數(shù)排在偶數(shù)之前*/Status AdjustList_Sq(SqList &L) ElemType *p, *q; int temp; return OK;/*插入法生成遞增有序表，有序表生成成功返回OK，失敗返回

16、ERROR*/Status OrderList_sq(SqList &L, int n) int i, j, x; /*x表示每次待插入的元素*/*兩個(gè)非遞減有序表A和B，并把它們合并成一個(gè)非遞減有序表C*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc ) ElemType *pa, *pb, *pc, *pa_last, *pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (

17、ElemType *)malloc(Lc.listsize * sizeof(ElemType); if (!Lc.elem) exit (OVERFLOW); pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while (pa <= pa_last && pb <= pb_last) if (*pa <= *pb) *pc+ = *pa+; else *pc+ = *pb+; while(pa <= pa_last) *pc+ = *pa+; while(pb

18、<= pb_last) *pc+ = *pb+;main.cpp#include "SqList.h"int main() int choice, n, i, x; SqList L, La, Lb, Lc; while(1) menu(); printf("選擇你的操作："); scanf("%d",&choice); switch(choice) case 1: if(CreateList_Sq(L) printf("順序表創(chuàng)建成功n"); else printf("順序表創(chuàng)建失敗n&q

19、uot;); break; case 2: PrintList_Sq(L); break; case 3: printf("請(qǐng)輸入刪除元素的位置："); scanf("%d", &i); if(DeleteList_Sq(L, i, x) printf("被刪除元素值為：%dn",x); else printf("刪除失敗n"); break; case 4: printf("請(qǐng)輸入刪除元素值："); scanf("%d", &x); if(DeleteLis

20、tX_Sq(L, x) printf("刪除成功n"); else printf("刪除失敗n"); PrintList_Sq(L); break; case 5: AdjustList_Sq(L); printf("新鏈表為：n"); PrintList_Sq(L); break; case 6: printf("請(qǐng)輸入順序表長(zhǎng)度："); scanf("%d", &n); if(OrderList_sq(L, n) printf("值有序順序表為：n"); Prin

21、tList_Sq(L); else printf("順序表創(chuàng)建失敗n"); break; case 7: printf("請(qǐng)輸入順序表La的長(zhǎng)度："); scanf("%d", &n); OrderList_sq(La, n); printf("請(qǐng)輸入順序表Lb的長(zhǎng)度："); scanf("%d", &n); OrderList_sq(Lb, n); MergeList_Sq(La, Lb, Lc); printf("合并后的順序表為：n"); PrintLi

22、st_Sq(Lc); break; case 0: return 0; default: printf("輸入錯(cuò)誤，請(qǐng)重新輸入n"); 實(shí)驗(yàn)02 單鏈表的基本操作實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)實(shí)驗(yàn)類型：上機(jī)背景知識(shí)：?jiǎn)捂湵淼牟迦?、刪除及應(yīng)用。目的要求： 1掌握單鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。 2掌握單鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容： 編寫(xiě)一個(gè)完整的程序，實(shí)現(xiàn)單鏈表的生成、插入、刪除、輸出等基本操作。（1） 隨機(jī)產(chǎn)生或鍵盤(pán)輸入一組元素，建立一個(gè)帶頭結(jié)點(diǎn)的單向鏈表（無(wú)序）。（2） 計(jì)算單鏈表的長(zhǎng)度，遍歷單鏈表。（3） 把單鏈表中的元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。（4） 在

23、單鏈表中刪除所有值為偶數(shù)的元素結(jié)點(diǎn)。（5） 編寫(xiě)在非遞減有序單鏈表中插入一個(gè)元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個(gè)非遞減有序單鏈表。（6） * 利用算法5建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞增有序鏈表。（7） * 利用算法5建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞減有序鏈表。（8） * 利用算法1建立的鏈表，實(shí)現(xiàn)將其分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量利用已知的存儲(chǔ)空間）。（9） * 采用單鏈表實(shí)現(xiàn)一元多項(xiàng)式的存儲(chǔ)并實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加并輸出結(jié)果。（10） 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。（11） * 綜合訓(xùn)練：1）利用鏈表實(shí)現(xiàn)一個(gè)班級(jí)

24、學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲(chǔ)到文件中）2）約瑟夫環(huán)問(wèn)題：設(shè)有n個(gè)人圍坐在圓桌周圍，從某個(gè)位置開(kāi)始編號(hào)為1，2，3，n，坐在編號(hào)為1的位置上的人從1開(kāi)始報(bào)數(shù)，數(shù)到m的人便出列；下一個(gè)（第m+1個(gè)）人又從1開(kāi)始報(bào)數(shù)，數(shù)到m的人便是第二個(gè)出列的人；如此重復(fù)下去，直到最后一個(gè)人出列為止，得到一個(gè)出列的編號(hào)順序。例如，當(dāng)n=8，m=4時(shí)，若從第一個(gè)位置數(shù)起，則出列的次序?yàn)?，8，5，2，1，3，7，6。試編寫(xiě)程序確定出列的順序。要求用不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列順序打印出個(gè)人編號(hào)。實(shí)驗(yàn)說(shuō)明： 1類型定義 typedef int Ele

25、mType; /元素類型 typedef struct node ElemType data; struct node *next; LinkNode, *LinkList; 2為了算法實(shí)現(xiàn)簡(jiǎn)單，建議采用帶頭結(jié)點(diǎn)的單鏈表。注意問(wèn)題：1重點(diǎn)理解鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)及指針的含義。 2注意比較順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的各自特點(diǎn)。 3注意比較帶頭結(jié)點(diǎn)、無(wú)頭結(jié)點(diǎn)鏈表實(shí)現(xiàn)插入、刪除算法時(shí)的區(qū)別。 4單鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對(duì)這部分常見(jiàn)算法的理解。部分源代碼：DS.h#include <stdio.h>#include <stdlib.h>#include <string.

26、h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;LinkList.h#include "DS.h"typedef int Elemtype;typedef struct Node Elemtype data;struct Node *next;Lnode,*LinkList;void menu(); /*菜單*/Status Init_Linklist(LinkList &L); /*初始化空表*/Status

27、 Creat_Linklist(LinkList &L); /*尾插法建立單鏈表*/void Disp_Linklist(LinkList L); /*單鏈表遍歷*/int length_Linklist(LinkList L); /*計(jì)算單鏈表長(zhǎng)度*/void Reverse_Linklist(LinkList L); /*單鏈表逆置*/void DelEven_Linklist(LinkList L); /*刪除值為偶數(shù)的結(jié)點(diǎn)*/Status Insert_Linklist(LinkList L, int x); /*在有序單鏈表L中插入元素x，鏈表仍然有序*/Status Cre

28、atOrder_Linklist(LinkList &L); /*創(chuàng)建非遞減有序單鏈表*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*兩個(gè)非遞減有序單鏈表La和Lb合并成一個(gè)非遞增有序鏈表Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*兩個(gè)非遞減有序單鏈表La和Lb合并成一個(gè)非遞減有序鏈表Lc*/void Split_Linklist(LinkList La, LinkList

29、&Lb); /*鏈表La按值分解成兩個(gè)鏈表，La全部為奇數(shù)，Lb全部為偶數(shù)*/LinkList.cpp#include "LinkList.h"void menu() printf("ttt 單鏈表基本操作nn"); printf("ttt1.建 立 單 鏈 表n"); printf("ttt2.遍 歷 單 鏈 表n"); printf("ttt3.計(jì) 算 鏈 表 長(zhǎng) 度n"); printf("ttt4.鏈 表 逆 置n"); printf("ttt5.刪

30、 除 偶 數(shù) 節(jié) 點(diǎn)n"); printf("ttt6.生 成 值 有 序 單 鏈 表n"); printf("ttt7.合 并 生 成 降 序 鏈 表n"); printf("ttt8.合 并 生 成 升 序 鏈 表n"); printf("ttt9.分 解 鏈 表n"); printf("ttt0.退 出nn");/*初始化空表*/Status Init_Linklist(LinkList &L) L=(LinkList)malloc(sizeof(Lnode); if(!

31、L) return ERROR;L->next=NULL;return OK;/*尾插法建立單鏈表*/Status Creat_Linklist(LinkList &L) int x; LinkList p,rear; Init_Linklist(L); rear = L; printf("輸入-1表示輸入結(jié)束n"); while(scanf("%d",&x),x != -1) p = (LinkList)malloc(sizeof(Lnode); if(!p) return ERROR; p->data = x; rear-

32、>next = p; rear = p; rear->next = NULL; return OK;/*單鏈表遍歷*/void Disp_Linklist(LinkList L) LinkList p; p = L->next; while(p) printf("%d ", p->data); p = p->next; printf("n");/*計(jì)算單鏈表長(zhǎng)度*/int length_Linklist(LinkList L) int count = 0; /*count表示單鏈表長(zhǎng)度*/ LinkList p; retur

33、n count;/*單鏈表逆置*/void Reverse_Linklist(LinkList L) LinkList p, q ; /*刪除值為偶數(shù)的結(jié)點(diǎn)*/void DelEven_Linklist(LinkList L) LinkList p, q; /*在有序單鏈表中插入元素，鏈表仍然有序，插入成功返回OK，插入失敗返回ERROR*/Status Insert_Linklist(LinkList L, int x) ;/*創(chuàng)建非遞減有序單鏈表，創(chuàng)建成功返回OK，創(chuàng)建失敗返回ERROR*/Status CreatOrder_Linklist(LinkList &L) /*兩個(gè)非遞

34、減有序單鏈表La和Lb合并成一個(gè)非遞增有序鏈表Lc*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) /*兩個(gè)非遞減有序單鏈表La和Lb合并成一個(gè)非遞減有序鏈表Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) LinkList pa, pb, pc; pa = La->next; pb = Lb->next; pc = Lc = La; while(pa && pb) if(p

35、a->data <= pb->data) pc->next = pa; pc = pa; pa = pa->next; else pc->next = pb; pc = pb; pb = pb->next; pc->next = pa ? pa : pb; free(Lb);/*鏈表La按值分解成兩個(gè)鏈表，La全部為奇數(shù)，Lb全部為偶數(shù)*/void Split_Linklist(LinkList La, LinkList &Lb) main.cpp#include "LinkList.h"int main() int

36、choice, length; LinkList L, La, Lb, Lc; while(1) menu(); printf("選擇你的操作："); scanf("%d",&choice); switch(choice) case 1: if(Creat_Linklist(L) printf("單鏈表創(chuàng)建成功n"); else printf("單鏈表創(chuàng)建失敗n"); break; case 2: Disp_Linklist(L); break; case 3: length = length_Linkli

37、st(L); printf("單鏈表長(zhǎng)度為：%dn",length); break; case 4: Reverse_Linklist(L); printf("逆置后的鏈表為：n"); Disp_Linklist(L); break; case 5: DelEven_Linklist(L); printf("新鏈表為：n"); Disp_Linklist(L); break; case 6: if(CreatOrder_Linklist(L) printf("值有序鏈表為：n"); Disp_Linklist(L)

38、; else printf("單鏈表創(chuàng)建失敗n"); break; case 7: CreatOrder_Linklist(La); CreatOrder_Linklist(Lb); MergeDescend_Linklist(La, Lb, Lc); printf("合并后的新鏈表為：n");Disp_Linklist(Lc); break; case 8: CreatOrder_Linklist(La); CreatOrder_Linklist(Lb); MergeAscend_Linklist(La, Lb, Lc); printf("合

39、并后的新鏈表為：n");Disp_Linklist(Lc); break; case 9: Creat_Linklist(L); Split_Linklist(L, Lb); printf("分裂后的新鏈表為：n"); Disp_Linklist(L); Disp_Linklist(Lb); break; case 0: return 0; default: printf("輸入錯(cuò)誤，請(qǐng)重新輸入n"); 實(shí)驗(yàn)03 棧的基本操作實(shí)驗(yàn)學(xué)時(shí)：學(xué)時(shí)實(shí)驗(yàn)類型：上機(jī)背景知識(shí)：順序棧、鏈棧，入棧、出棧。目的要求： 1掌握棧的思想及其存儲(chǔ)實(shí)現(xiàn)。 2掌握棧的常見(jiàn)

40、算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：（1） 采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。（2） 采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。（3） 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別測(cè)試上述算法。（4） * 綜合訓(xùn)練：1） 堆棧操作合法性：假設(shè)以S和X分別表示入棧和出棧操作。如果根據(jù)一個(gè)僅由S和X構(gòu)成的序列，對(duì)一個(gè)空堆棧進(jìn)行操作，相應(yīng)操作均可行（如沒(méi)有出現(xiàn)刪除時(shí)棧空）且最后狀態(tài)也是?？?，則稱該序列是合法的堆棧操作序列。請(qǐng)編寫(xiě)程序，輸入S和X序列，判斷該序列是否合法。2） 括號(hào)匹配檢驗(yàn)：假設(shè)表達(dá)式中允許包括兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即()或()等為正確的格式，()或()等均為不正確格式。

41、輸入一個(gè)表達(dá)式，判斷其中的括號(hào)是否能正確匹配。3） 表達(dá)式轉(zhuǎn)換：算術(shù)表達(dá)式有前綴表示法、中綴表示法和后綴表示法等形式。日常使用的算術(shù)表達(dá)式是采用中綴表示法，即二元運(yùn)算符位于兩個(gè)運(yùn)算數(shù)中間。請(qǐng)?jiān)O(shè)計(jì)程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。輸入在一行中給出不含空格的中綴表達(dá)式，可包含+、-、*、以及左右括號(hào)()，表達(dá)式不超過(guò)20個(gè)字符。在一行中輸出轉(zhuǎn)換后的后綴表達(dá)式，要求不同對(duì)象（運(yùn)算數(shù)、運(yùn)算符號(hào)）之間以空格分隔，但結(jié)尾不得有多余空格。實(shí)驗(yàn)說(shuō)明：1類型定義 順序棧示例#define MAX 100 /棧的最大值typedefstruct SElemType *base； SElemType *top；in

42、t stacksize；SqStack； 鏈棧示例 typedef int ElemType; /元素類型 typedef struct snode SElemType data; struct snode *next; StackNode, *LinkStack;2算法4的每個(gè)子功能盡可能寫(xiě)成函數(shù)形式。注意問(wèn)題： 1重點(diǎn)理解棧的算法思想，能夠根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。 2注意算法4的各個(gè)函數(shù)之間值的傳遞情況。 3棧的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)（樹(shù)、圖、查找、排序等）。實(shí)驗(yàn)04 隊(duì)列的基本操作實(shí)驗(yàn)學(xué)時(shí)：學(xué)時(shí)實(shí)驗(yàn)類型：上機(jī)背景知識(shí)：循環(huán)隊(duì)列、鏈隊(duì)列，入隊(duì)、出隊(duì)。目的要求： 1掌握隊(duì)列的思想及其存

43、儲(chǔ)實(shí)現(xiàn)。 2掌握隊(duì)列的常見(jiàn)算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：（1） 采用順序存儲(chǔ)實(shí)現(xiàn)循環(huán)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。（2） 采用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列的初始化、入隊(duì)、出隊(duì)操作。（3） 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別測(cè)試上述算法。（4） *綜合訓(xùn)練：銀行排隊(duì)系統(tǒng)模擬:請(qǐng)用一個(gè)隊(duì)列來(lái)模擬銀行排隊(duì)系統(tǒng)，隊(duì)列中存儲(chǔ)序號(hào)。請(qǐng)?jiān)O(shè)置一個(gè)菜單，包括叫號(hào)和排號(hào)兩個(gè)選項(xiàng)。若選擇叫號(hào)，則輸出并刪除隊(duì)首元素；若選擇排號(hào)，則順序生成一個(gè)序號(hào)，加入隊(duì)列，并輸出該序號(hào)和前面有多少人等候。實(shí)驗(yàn)說(shuō)明： 1類型定義 循環(huán)隊(duì)列示例#define MAXQSIZE 100 /隊(duì)列的最大長(zhǎng)度typedefstruct QElemType *b

44、ase；int front；int rear；SqQueue；鏈隊(duì)列示例typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;注意問(wèn)題： 1重點(diǎn)理解隊(duì)列的算法思想，能夠根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。 2隊(duì)列的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)（樹(shù)、圖、查找、排序等）。實(shí)驗(yàn)05 二叉樹(shù)的基本操作實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)實(shí)驗(yàn)類型：上機(jī)背景知識(shí)：二叉樹(shù)的存儲(chǔ)、建立、遍歷及其應(yīng)用。目的要求： 1掌握二叉樹(shù)的存儲(chǔ)實(shí)現(xiàn)。

45、2掌握二叉樹(shù)的遍歷思想。 3掌握二叉樹(shù)的常見(jiàn)算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：（1） 從鍵盤(pán)上輸入數(shù)據(jù)，建立二叉鏈表。 （2） 前序遍歷、中序遍歷、后序遍歷二叉樹(shù)：遞歸算法。（3） 前序遍歷、中序遍歷、后序遍歷二叉樹(shù)：非遞歸算法。（4） 借助隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層次遍歷。（5） 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。（6） *綜合訓(xùn)練：家族關(guān)系查詢系統(tǒng)：建立家族關(guān)系數(shù)據(jù)庫(kù)，可以實(shí)現(xiàn)家族成員的添加，可以查詢家族成員的雙親、祖先、兄弟、孩子和后代等信息。實(shí)驗(yàn)說(shuō)明： 1類型定義 /二叉鏈表存儲(chǔ) #define TElemType char /元素類型 typedef struct BiTNode TE

46、lemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;注意問(wèn)題： 1注意理解遞歸算法的執(zhí)行步驟。2注意字符類型數(shù)據(jù)在輸入時(shí)的處理。3重點(diǎn)理解如何利用棧結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法。實(shí)驗(yàn)06 哈夫曼編碼實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)實(shí)驗(yàn)類型：綜合型實(shí)驗(yàn)背景知識(shí)：二叉樹(shù)的應(yīng)用、哈夫曼樹(shù)。目的要求： 掌握哈夫曼樹(shù)和哈夫曼編碼的基本思想和算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容：（1）修理牧場(chǎng)：農(nóng)夫要修理牧場(chǎng)的一段柵欄，他測(cè)量了柵欄，發(fā)現(xiàn)需要N塊木頭，每塊木頭長(zhǎng)度為整數(shù)Li個(gè)長(zhǎng)度單位，于是他購(gòu)買了一條很長(zhǎng)的、能鋸成N塊的木頭，即該木頭的長(zhǎng)度是Li的總和。但是農(nóng)夫自己沒(méi)

47、有鋸子，請(qǐng)人鋸木頭的酬金跟這段木頭的長(zhǎng)度成正比。為簡(jiǎn)單起見(jiàn)，不妨就設(shè)酬金等于所鋸木頭的長(zhǎng)度。例如，要將長(zhǎng)度為20的木頭鋸成長(zhǎng)度為8、7和5的三段，第一次鋸木頭花費(fèi)20，將木頭鋸成12和8；第二次鋸木頭花費(fèi)12，將長(zhǎng)度為12的木頭鋸成7和5，總花費(fèi)為32。如果第一次將木頭鋸成15和5，則第二次鋸木頭花費(fèi)15，總花費(fèi)為35（大于32）。請(qǐng)編寫(xiě)程序幫助農(nóng)夫計(jì)算將木頭鋸成N塊的最少花費(fèi)。首先輸入一個(gè)正整數(shù)N（N104），表示要將木頭鋸成N塊。接著給出N個(gè)正整數(shù)Li（Li50），表示每段木塊的長(zhǎng)度。輸出一個(gè)整數(shù)，即將木頭鋸成N塊的最少花費(fèi)。例如：輸入：84 5 1 2 1 3 1 1輸出：49*（2）壓縮軟件：給定一篇文章，只含有英文大小寫(xiě)字母和空格，以.txt格式存儲(chǔ)，統(tǒng)計(jì)該文件中各種字符的頻率，對(duì)各字符進(jìn)行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將Huffman編碼文件翻譯成源文件。實(shí)驗(yàn)說(shuō)明：1參考類型定義 /雙親孩子表示法 typedef struct unsigned int weight; unsi