數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書-資料下載頁
2024-09-22 19:45本頁面
【正文】 樹的鏈?zhǔn)酱鎯Ρ硎? typedef char DataType。//應(yīng)由用戶定義 DataType的實(shí)際類型 typedef struct node { DataType data。struct node *lchild, *rchild。//左右孩子指針 } BinTNode。 //結(jié)點(diǎn)類型 typedef BinTNode *BinTree。 ，然后分別創(chuàng)建左右子樹。在創(chuàng)建二叉樹的過程中，要注意結(jié)點(diǎn)數(shù)是根據(jù)輸入的字符確定的。如： void CreateBinTree(BinTree T){ 實(shí)驗(yàn)三 內(nèi)部排序的基本操作 【實(shí)驗(yàn)?zāi)康摹? 。 、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序、基數(shù)排序等算法的基本思想。 ，對于不同的排序方法有不同的影響，通過該實(shí)驗(yàn)進(jìn)一步加深理解。 。 【實(shí)驗(yàn)內(nèi)容】 8個整數(shù)，存放在數(shù)組 quick[8]中，并輸出值。 結(jié)果，觀察關(guān)鍵字次序的變化。 8個整數(shù) 按照升序輸入，即 k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。 8個整數(shù)按照降序輸入，即 k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。 排序算法的執(zhí)行時間，比較執(zhí)行效率。 3萬個數(shù)，對其進(jìn)行排序，觀察其結(jié)果。 【實(shí)驗(yàn)安排】 建議課時安排如下： 課外 2學(xué)時，課內(nèi) 2學(xué)時 【實(shí)驗(yàn)提示】 C語言的定義記錄類型的存儲結(jié)構(gòu)： typedef int InfoType。define n 10 typedef int KeyType。typedef struct { //假設(shè)的文件長度，即待排序的記錄數(shù)目 //假設(shè)的關(guān)鍵字類型 //記錄類型 //關(guān)鍵字項(xiàng) //其它數(shù)據(jù)項(xiàng)，類型 InfoType依賴于具體應(yīng)用而 KeyType key。 InfoType otherinfo。定義 } RecType。typedef RecType SeqList[n+1]。作哨兵 。 //SeqList為順序表類型，表中第 0個單元一般用 第五篇：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書 數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 指 導(dǎo) 書 南京工程學(xué)院 信息管理與信息系統(tǒng)教研室 2024年 3月 實(shí)驗(yàn)一 線性表操作 一、實(shí)驗(yàn)?zāi)康? C語言的上機(jī)環(huán)境，進(jìn)一步掌握 C語言的結(jié)構(gòu)特點(diǎn)。 C語言實(shí)現(xiàn)。 —— 單鏈表的定義及 C 語言實(shí)現(xiàn)。 表中的各種基本操作。 —— 單鏈表中的各種基本操作。 二、實(shí)驗(yàn)內(nèi)容 、插入及刪除。 、插入及刪除。 三、實(shí)驗(yàn)步驟 n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。 一個順序表 L={21， 23， 14， 5， 56， 17， 31}，然后在第 i個位置插入元素 68。 ，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。 四、實(shí)現(xiàn)提示 C語言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用 C語言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲。 在 此，我們利用 C語言的結(jié)構(gòu)體類型定義順序表： define MAXSIZE 1024 typedef int elemtype。/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE]。int len。/* 順序表的長度 */ }sequenlist。將此結(jié)構(gòu)定義放在一個頭文件 ，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。 i個元素，在插入過程中注意溢出情況以及數(shù)組的下標(biāo)與位序（ 順序表中元素的次序）的區(qū)別。 ，還含有一個指針域。用 C語言描述結(jié)點(diǎn)結(jié)構(gòu)如下： typedef int elemtype。typedef struct node { elemtype data。//數(shù)據(jù)域 struct node *next。//指針域 }linklist。注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時指針的變化。構(gòu)造一個結(jié)點(diǎn)需用到 C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量 p分配一個結(jié)點(diǎn)的地址： p=(linklist *)malloc(sizeof(linklist))。該語句的功能是申請分配一個類型為 linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量 p 中。當(dāng)結(jié)點(diǎn)不需要時可以用標(biāo)準(zhǔn)函數(shù) free(p)釋放結(jié)點(diǎn)存儲空間，這時 p為空值（ NULL）。 五、思考與提高 ，應(yīng)如何建立順序表。 main函數(shù)里如果去掉 L=a語句，會出現(xiàn)什么結(jié)果？ 實(shí)驗(yàn)二 棧和隊(duì)列的應(yīng)用 一、實(shí)驗(yàn)?zāi)康? 二、實(shí)驗(yàn)內(nèi)容 各種基本運(yùn)算。 。 三、實(shí)驗(yàn)步驟 (1)初始化順序棧 。(2)插入元素 (3)刪除棧頂元素 (4)取棧頂元素 (5)遍歷順序棧 (6)置空順序棧 (1)初始化并建立鏈隊(duì)列 (2.)入鏈隊(duì)列 (3)出鏈隊(duì)列 (4)遍歷鏈隊(duì)列 四、實(shí)現(xiàn)提示 1./*定義順序棧的存儲結(jié)構(gòu) */ typedef struct { ElemType stack[MAXNUM]。int top。}SqStack。 /*初始化順序棧函數(shù) */ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack))。/*申請空間 */} /*入棧函數(shù) */ void Push(SqStack *p,ElemType x){if(ptoptop=ptop+1。/*棧頂 +1*/ pstack[ptop]=x。} /*數(shù)據(jù)入棧 */ } /*出棧函數(shù) */ ElemType Pop(SqStack *p){x=pstack[ptop]。/*將棧頂元素賦給 x*/ ptop=ptop1。} /*棧頂1*/ /*獲取棧頂元素函數(shù) */ ElemType GetTop(SqStack *p){ x=pstack[ptop]。} /*遍歷順序棧函數(shù)*/ void OutStack(SqStack *p){ for(i=ptop。i=0。i)printf(“ 第 %d 個數(shù)據(jù)元素是： %6dn”,i,p stack[i])。} /*置空順序棧函數(shù) */ void setEmpty(SqStack *p){ ptop=1。} 可參考代碼： include “” define StackSize 100 typedef i nt ElemType。main(){ SqStack S。 ElemType e。 int N。 /*初始化順序棧 */ /*入棧 */ /*出棧 */ /*遍歷順序棧 */ getch()。} 2./*定義鏈隊(duì)列 */ typedef struct Qnode { ElemType data。struct Qnode *next。}Qnodetype。typedef struct { Qnodetype *front。Qnodetype *rear。}Lqueue。 /*初始化并建立鏈隊(duì)列函數(shù) */ void creat(Lqueue *q) { h=(Qnodetype*)malloc(sizeof(Qnodetype))。/*初始化申請空間 */ hnext=NULL。qfront=h。qrear=h。for(i=1。idata=x。snext=NULL。qrearnext=s。qrear=s。} /*出鏈隊(duì)列函數(shù) */ ElemType Ldelete(Lqueue *q){ p=qfrontnext。qfrontnext=pnext。if(pnext==NULL)qrear=qfront。x=pdata。free(p)。} /*釋放空間 */ /*遍歷鏈隊(duì)列函數(shù) */ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊(duì)尾 */ { printf(“%d ”,p data)。p=pnext。} } 可參考如下代碼： include “” define MaxSize 100 typedef int ElemType。main(){ LinkQueue Q。 ElemType e。 /*初始化并建立鏈隊(duì)列 */ /*入鏈隊(duì)列 */ /*出鏈隊(duì)列 */ *遍歷鏈隊(duì)列 */ } DestoryQueue(Q)。 getch()。} 五、思考與提高 ？ 試寫一個算法，判別讀入的一個以 ‘’ 為結(jié)束符的字符序列是否是 ?回文 ?。實(shí)驗(yàn)三 樹操作 一、實(shí)驗(yàn)?zāi)康? ，掌握二叉樹的建立與存儲 ，掌握二叉樹的遍歷方法 二、實(shí)驗(yàn)內(nèi)容 三、實(shí)驗(yàn)步驟 、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 ,并通過調(diào)用函數(shù) , 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。 四、實(shí)現(xiàn)提示 ： 首先建立二叉樹的根 結(jié)點(diǎn)，然后建立其左右子樹，直到空子樹為止。 、中序遍歷與后序遍歷二叉樹。 include include typedef int Status。typedef char ElemType。typedef struct BiTNode { ElemType data。struct BiTNode *lchild,*rchild。}BiTNode,*BiTree。/*建立二叉樹 */ BiTree CreateBiTree(BiTree T){ } /*先序遍歷 */ Status PreOrderTraverse(BiTree T){ } /*中序遍歷 */ Status InOrderTraverse(BiTree T){ } /*后序遍歷 */ Status PostOrderTraverse(BiTree T){ } int main(){ BiTree T。CreateBiTree(T)。PreOrderTraverse(T)。printf(“n”)。/* 先序遍歷 */ InOrderTraverse(T)。printf(“n”)。/* 中序遍歷 */ PostOrderTraverse(T)。printf(“n”)。/* 后序遍歷 */ return 0。} 五、思考與提高 編寫遞歸算法，計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。
法律信息相關(guān)推薦
鄂ICP備17016276號-1