數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告(華北電力大學(xué)科技學(xué)院).

1、華北電力大學(xué)科技學(xué)院實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱(chēng) 數(shù)據(jù)結(jié)構(gòu)試驗(yàn) 課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu) 專(zhuān)業(yè)班級(jí)：軟件09k1 學(xué)生姓名：李曉東學(xué) 號(hào)：091909020111 成 績(jī)：指導(dǎo)老師：張琦 實(shí)驗(yàn)日期：2011年3月6月實(shí)驗(yàn)一 順序表及其應(yīng)用一、實(shí)驗(yàn)?zāi)康募耙?、實(shí)驗(yàn)?zāi)康?1)熟悉VC+上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。(2)掌握線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。(3)掌握線(xiàn)性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作的實(shí)現(xiàn)。(4)掌握棧和隊(duì)列的順序表示和實(shí)現(xiàn)。2、實(shí)驗(yàn)要求(1)用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧和循環(huán)隊(duì)列。(2)編寫(xiě)完整程序完成下面的實(shí)驗(yàn)內(nèi)容并上機(jī)運(yùn)行。(3)整理并上交實(shí)驗(yàn)報(bào)告。二、實(shí)驗(yàn)內(nèi)容 1.

2、 約瑟夫環(huán)的實(shí)現(xiàn)：設(shè)有n個(gè)人圍坐在圓桌周?chē)?，現(xiàn)從某個(gè)位置 i 上的人開(kāi)始報(bào)數(shù)，數(shù)到 m 的人就站出來(lái)。下一個(gè)人，即原來(lái)的第m+1個(gè)位置上的人，又從1開(kāi)始報(bào)數(shù)，再是數(shù)到m的人站出來(lái)。依次重復(fù)下去，直到全部的人都站出來(lái)，按出列的先后又可得到一個(gè)新的序列。由于該問(wèn)題是由古羅馬著名的史學(xué)家Josephus提出的問(wèn)題演變而來(lái)，所以通常稱(chēng)為Josephus 問(wèn)題。 例如：當(dāng)n=8,m=4,i=1時(shí)，得到的新序列為： 4，8，5，2，1，3，7，6 編寫(xiě)程序選擇順序存儲(chǔ)方式模擬整個(gè)過(guò)程，并依次輸出出列的各人的編號(hào)。程序：#include<stdio.h>#include<stdlib.h&

3、gt;#define MAX 100int main()Inti,k,out,all,count,start,person100;/定義變量printf("請(qǐng)輸入起始時(shí)的人數(shù):n");scanf("%d",&all);for(i=0;i<all;i+) personi=i+1; /初始化數(shù)組printf("請(qǐng)輸入數(shù)數(shù)的周期:n"); scanf("%d",&count);printf("你希望從第幾個(gè)人開(kāi)始？:n");scanf("%d",&st

4、art);i=start-1;/開(kāi)始下標(biāo)等于開(kāi)始人數(shù)減一if(start>all)/若開(kāi)始人數(shù)大于總?cè)藬?shù)提示出錯(cuò)printf("error!n");k=0;/1 2 3 的計(jì)數(shù)器out=0;/出局的人數(shù)while(out<all-1)if(personi!=0)/取出后置零k+;/計(jì)數(shù)器加一if(k=count)printf("%d ",personi);/打印輸出該出局的人數(shù)personi=0;/出局后此位置置零k=0;/計(jì)數(shù)器置零out+;/出局人數(shù)加一i+;/人數(shù)后移加一if(i=all) i=0;/當(dāng)i=最后一個(gè)時(shí)，讓i等于第一個(gè)fo

5、r(i=0;i<all;i+)/循環(huán)輸出最后一個(gè)人if(personi!=0)/判斷是否已經(jīng)輸出過(guò)printf("%d ",personi);break; printf("n");system("pause");return 0;實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)二 鏈表及其應(yīng)用一、實(shí)驗(yàn)?zāi)康募耙?、實(shí)驗(yàn)?zāi)康?1)熟悉VC+上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。(2)掌握線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)即單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。(3)掌握線(xiàn)性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)即單鏈表中的各種基本操作。(4)掌握棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示和實(shí)現(xiàn)。2、實(shí)驗(yàn)要求(1)用鏈?zhǔn)酱鎯?chǔ)結(jié)

6、構(gòu)實(shí)現(xiàn)單鏈表（和單向循環(huán)鏈表）的建立、查找和刪除等運(yùn)算。(2)編寫(xiě)完整程序完成下面的實(shí)驗(yàn)內(nèi)容并上機(jī)運(yùn)行。(3)整理并上交實(shí)驗(yàn)報(bào)告。二、實(shí)驗(yàn)內(nèi)容 1.約瑟夫環(huán)的問(wèn)題：設(shè)有n個(gè)人圍坐在圓桌周?chē)?，現(xiàn)從某個(gè)位置 i 上的人開(kāi)始報(bào)數(shù)，數(shù)到 m 的人就站出來(lái)。下一個(gè)人，即原來(lái)的第m+1個(gè)位置上的人，又從1開(kāi)始報(bào)數(shù)，再是數(shù)到m的人站出來(lái)。依次重復(fù)下去，直到全部的人都站出來(lái)，按出列的先后又可得到一個(gè)新的序列。由于該問(wèn)題是由古羅馬著名的史學(xué)家Josephus提出的問(wèn)題演變而來(lái)，所以通常稱(chēng)為Josephus 問(wèn)題。 例如：當(dāng)n=8,m=4,i=1時(shí)，得到的新序列為： 4，8，5，2，1，3，7，6用單向循環(huán)鏈表存

7、儲(chǔ)結(jié)構(gòu)模擬此過(guò)程。實(shí)現(xiàn)提示：typedef struct Node   int data;     struct Node *next; *nodetype;/定義指向鏈節(jié)點(diǎn)類(lèi)型的指針1） 先建立單向循環(huán)鏈表。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：p=(nodetype)malloc(sizeof(struct Node);該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類(lèi)型為結(jié)構(gòu)體類(lèi)型為Node的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p

8、為空值（NULL）。2） 注意在刪除第m個(gè)節(jié)點(diǎn)時(shí)，需要一個(gè)輔助指針指向刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，刪除節(jié)點(diǎn)只需要修改指針即可。2. 若已知非空線(xiàn)性鏈表第一個(gè)結(jié)點(diǎn)的指針為list（即非空不帶頭節(jié)點(diǎn)的單鏈表頭指針為list），請(qǐng)寫(xiě)一個(gè)算法并實(shí)現(xiàn),將該鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前端。實(shí)現(xiàn)提示：此算法需要四個(gè)輔助指針，掃描鏈表節(jié)點(diǎn)指針p 以及其前驅(qū)節(jié)點(diǎn)指針r ,數(shù)據(jù)域小的節(jié)點(diǎn)指針q以及其前驅(qū)節(jié)點(diǎn)指針s .設(shè)計(jì)程序：#include<stdio.h> #include <malloc.h>#include <stdlib.h>typedef struct Nod

9、eint data;struct Node *next; *nodetype ;/聲明鏈表結(jié)構(gòu)nodetype creatList(nodetype head,int x)/創(chuàng)建鏈表int i;nodetype p,q;head=(nodetype)malloc(sizeof(struct Node);/申請(qǐng)空間head->data=x;/修正讓第一個(gè)節(jié)點(diǎn)的data值為最大p=head;/p為輔助指針指尾節(jié)點(diǎn)for(i=1;i<x;i+)/循環(huán)建立鏈表q=(nodetype)malloc(sizeof(struct Node);/申請(qǐng)空間if(!q) exit(1);/判斷是否申請(qǐng)

10、成功q->data=i;/賦值data等于ip->next=q;p=q;/p指向尾節(jié)點(diǎn)p->next=head;/讓尾節(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)return (head);/返回頭結(jié)點(diǎn)void del (nodetype Previous,nodetype Point)/刪除節(jié)點(diǎn)Previous->next=Point->next;/讓要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)的next域指向要?jiǎng)h除節(jié)點(diǎn)的next域free(Point);/釋放節(jié)點(diǎn)空間int main()int all,count,start,i,j,out;nodetype Node,point,previous,p

11、ointer;Node=NULL;/初始化節(jié)點(diǎn)printf("請(qǐng)輸入總?cè)藬?shù)n");scanf("%d",&all);Node=creatList(Node,all);/創(chuàng)建鏈表printf("請(qǐng)輸入周期n");scanf("%d",&count);printf("請(qǐng)輸入起始位置n");scanf("%d",&start);if (start>all) /溢出出錯(cuò)提示printf(“errorn”);elseprintf(" 總?cè)藬?shù)為：%

12、d 周期：%d 起始位置：%dn",all,count,start);printf("n");printf(" 出局的順序?yàn)椋?quot;);point=Node;/point為輔助變量j=1;/初始化計(jì)數(shù)器while(j<=start)previous=point;/前一個(gè)指針指向此節(jié)點(diǎn)point=point->next;/此節(jié)點(diǎn)指向下一個(gè)j+;/計(jì)數(shù)器加一out=0;/出局的人數(shù)while(out<all-1)for(j=1;j<count;j+)point=point->next;/此節(jié)點(diǎn)后移previous=prev

13、ious->next;/前節(jié)點(diǎn)后移printf(" %d",point->data);/打印輸出要出局的人pointer=point->next;/保留point的接口del(previous,point);/刪除此節(jié)點(diǎn)point=pointer;/重新賦值out+;/出局的人數(shù)加一printf(" %dn",point->data);/輸出最后一個(gè)人free(point);/釋放此節(jié)點(diǎn)return 0;運(yùn)行結(jié)果：實(shí)驗(yàn)三 二叉樹(shù)一、實(shí)驗(yàn)?zāi)康募耙?、實(shí)驗(yàn)?zāi)康?1)通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的建立與存儲(chǔ)(2)通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的遍歷方法

14、2、實(shí)驗(yàn)要求 (1)二叉樹(shù)需要用二叉鏈表作為節(jié)點(diǎn)類(lèi)型描述。(2)二叉樹(shù)的遍歷遞歸算法能夠轉(zhuǎn)換為非遞歸算法。(3)編寫(xiě)完整程序完成下面的實(shí)驗(yàn)內(nèi)容并上機(jī)運(yùn)行。(4)整理并上交實(shí)驗(yàn)報(bào)告。二、實(shí)驗(yàn)內(nèi)容 1、問(wèn)題描述利用先序遍歷建立一棵二叉樹(shù)，并分別用前序、中序、后序遍歷該二叉樹(shù) 2、節(jié)點(diǎn)形式 LchilddataRchild 3、說(shuō)明 (1)輸入數(shù)據(jù)：1，2，3，0，0，4，0，0，5，0，0其中“0”表示空子樹(shù)。 (2)輸出數(shù)據(jù)： 先序：1，2，3，4，5 中序：3，2，4，1，5 后序：3，4，2，5，1三、實(shí)驗(yàn)步驟1. 建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的

15、先序、中序與后序遍歷算法。2. 建立二叉樹(shù),并通過(guò)調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。實(shí)現(xiàn)提示：二叉鏈表的類(lèi)型定義如下： typedef struct btnode int data; struct btnode *Lchild,*Rchild; *bitreptr程序 BT.H typedef struct btnodeint data;struct btnode *Lchild,*Rchild; *bitreptr;/聲明變量bitreptr MdPreorder()/先序建立二叉樹(shù)int x;bitreptr head;printf("請(qǐng)輸入:");s

16、canf("%d",&x);if (x=0) head=NULL;elsehead=(bitreptr)malloc(sizeof(struct btnode);/為節(jié)點(diǎn)申請(qǐng)空間if(!head) printf("Error!"); /判斷是否申請(qǐng)成功head->data=x;/賦值給節(jié)點(diǎn)的datahead->Lchild=MdPreorder(); /左孩子遞歸調(diào)用head->Rchild=MdPreorder();/右孩子遞歸調(diào)用return head;/返回頭結(jié)點(diǎn)int PreOrder(bitreptr head) /*

17、先序遍歷*/ if(head!=NULL) /判斷頭結(jié)點(diǎn)是否為空printf("%d ",head->data);/輸出數(shù)據(jù)域PreOrder(head->Lchild);/遞歸調(diào)用左孩子PreOrder(head->Rchild);/遞歸調(diào)用右孩子return 0;int InOrder(bitreptr head) /*中序遍歷*/ if(head) InOrder(head->Lchild);printf("%d ",head->data);InOrder(head->Rchild);return 0;int P

18、ostOrder(bitreptr head) /*后序遍歷*/ if(head) PostOrder(head->Lchild);PostOrder(head->Rchild);printf("%d ",head->data);return 0;源程序： #include<stdio.h>#include<stdlib.h>#include"BT.h"/預(yù)編譯包文件int main()bitreptr Head;/申請(qǐng)變量Head=NULL;/初始化節(jié)點(diǎn)printf(" 友情提示：nn");printf(" 先序輸入一個(gè)節(jié)點(diǎn)按回車(chē)?yán)^續(xù)下個(gè)輸入n&q