數(shù)據(jù)結(jié)構(gòu)實驗報告

1、實驗一：線性表一，實驗?zāi)康模?）理解和掌握線性順序表元素建立，查找，插入、刪除等算法。（2)熟悉C語言的上機環(huán)境，掌握C語言的基本結(jié)構(gòu)。（3) 熟悉對單鏈表的一些基本操作和具體的函數(shù)定義。（4) 通過單鏈表的定義掌握線性表的鏈式存儲結(jié)構(gòu)的特點。（5) 熟悉對單鏈表的一些其它操作。二，實驗內(nèi)容實現(xiàn)單鏈表的定義和操作是最為基礎(chǔ)的內(nèi)容，共有如下幾個環(huán)節(jié)：（1）建立結(jié)點類型。（2）初始化單鏈表。（3）求單鏈表的長度。（4）用前插法建立單鏈表。（5）從單鏈表表中查找元素。（6）向單鏈表中插入元素。（7）從單鏈表中刪除元素。三，問題描述（1）建立一個線性順序表，要求從鍵盤輸入幾個數(shù)，并將該線性順序表的 元

2、素從屏幕顯示出來；（2) 編寫插入和刪除函數(shù)，由用戶輸入待插入元素及插入位置，將完成插 入后的線性順序表輸出；由用戶輸入刪除第幾個元素，將完成刪除 的線性順序表輸出。（3) 編寫查找函數(shù)，在上面的線性順序表中查找其中一個元素，如果找到， 返回該元素在線性順序表中該元素的值。（4）編寫求單鏈表長度的函數(shù)，結(jié)果為輸出元素的個數(shù)。四，實驗代碼/*本實驗程序要求單鏈表的數(shù)據(jù)域是字符串,完成單鏈表的初始化、插入、刪除操作插入時不允許重復(fù)的串插入表中。*/#include #include #include using namespace std;typedef char DataType;/定義Data

3、Type為字符類型，后面用字符數(shù)組表示字符串typedef struct LNodeDataType string10; LNode *next;LNode,*Listpointer;/定義單鏈表的結(jié)點類型Listpointer Creatnullnode()/創(chuàng)建一個空結(jié)點 Listpointer p; /定義頭指針p=(Listpointer)malloc(sizeof(LNode);p-next=NULL;return p;int ListpointerLength(Listpointer L)int k=0;while(L-next)k+;L=L-next;return k;/求單鏈表

4、的長度void ListpointerTraverse(Listpointer L)Listpointer p=L;printf(當前鏈表為：n);while(L-next)printf(%s,L-next-string);printf(n);L=L-next;cout共ListpointerLength(p)個元素endlnext=NULL);/檢查單鏈表是否為空Listpointer ListpointerGet(Listpointer L,int i)if(iListpointerLength(L)return NULL;for(int k=0;knext;return L;/從單鏈表表

5、中查找元素int ListpointerLocate(Listpointer L,DataType* x)int k=0;while(L-next)k+;if(strcmp(L-next-string,x)=0)return k;L=L-next;return -1;/從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置void ListpointerInsert(Listpointer L,int i,DataType* x)Listpointer p=L;if(iListpointerLength(L)+1)cout位置越界，未插入！endlnext)&(strcmp(p-next-str

6、ing,x)!=0)p=p-next;if(p-next)printf(該數(shù)據(jù)之前結(jié)點已存在，未插入n);return;elsep=L;for(int k=1;knext; Listpointer q=(Listpointer)malloc(sizeof(LNode); strcpy(q-string,x); q-next=L-next; L-next=q; ListpointerTraverse(p);/向單鏈表中插入元素void ListpointerDel(Listpointer L,DataType* x)Listpointer s=L;while(L-next&strcmp(L-ne

7、xt-string,x)!=0)L=L-next;if(L-next=NULL)cout沒有該數(shù)據(jù)，鏈表未修改endlnext;L-next=L-next-next;free(q);ListpointerTraverse(s);/從單鏈表中刪除元素Listpointer ListpointerCreat(Listpointer L)char s10;Listpointer p,q,r=NULL;r=L;printf(請輸入各個結(jié)點的數(shù)據(jù)，每個結(jié)點不超過10個字符，依次回車確認，輸入#回車結(jié)束：n);scanf(%s,s);while(strcmp(s,#)!=0)p=L;while(p-nex

8、t)&(strcmp(p-next-string,s)!=0)p=p-next;if(p-next)printf(該數(shù)據(jù)之前結(jié)點已存在，未插入，請繼續(xù)輸入：n);scanf(%s,s);elseq=(Listpointer)malloc(sizeof(LNode);strcpy(q-string,s);q-next=NULL;r-next=q; r=q; scanf(%s,s);r-next=NULL;coutendl;ListpointerTraverse(L);return L;/用尾插法建立單鏈表int main()Listpointer first=Creatnullnode();in

9、t flag=1,i;while(flag) if(ListpointerEmpty(first)cout鏈表為空，按以下提示創(chuàng)建：endl;first=ListpointerCreat(first); int ch;/功能編號 cout歡迎您光臨 n;cout*n;cout* 1,插入 *n;cout* 2,刪除 *n;cout* 3,查找已知下標對應(yīng)的數(shù)據(jù) *n;cout* 4,查找已知數(shù)據(jù)對應(yīng)的下標 *n; cout* 5,退出本系統(tǒng) *n;cout*n;coutch; switch(ch)case 1:int k;DataType s10;coutk; couts; Listpoint

10、erInsert(first,k,s); break;case 2:DataType s10;couts;ListpointerDel(first,s);break;case 3:int k;coutk;if(ListpointerGet(first,k)coutstringendlendl;elsecout下標越界！endlendl;break;case 4:DataType s10;couts;if(ListpointerLocate(first,s)!=-1)cout下標為：ListpointerLocate(first,s)endlendl;elsecout沒有該數(shù)據(jù)！endlnext

11、) first=first-next; free(first); free(first);break;default:cout輸入不正確，請重試！endlendl;system(CLR);/主函數(shù)五，程序運行結(jié)果1，建立鏈表2，插入數(shù)據(jù)3，刪除數(shù)據(jù)4，查找已知下標對應(yīng)的數(shù)據(jù)5，查找已知數(shù)據(jù)對應(yīng)的下標實驗二：二叉樹 一實驗?zāi)康模?) 掌握二叉樹的定義、結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及使用范圍。2) 掌握用指針類型描述、訪問和處理二叉樹的運算。3) 掌握二叉樹的建立方法，熟悉二叉樹結(jié)點的結(jié)構(gòu)和對二叉樹的基本操作4) 掌握對二叉樹每一種操作的具體實現(xiàn)，掌握二叉樹遍歷的基本方法（前序、 中序、后序）

12、5）學會利用遞歸方法編寫對二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進行處理的算法。二實驗內(nèi)容：該程序的功能是實現(xiàn)二叉樹結(jié)點的類型定義和對二叉樹的基本操作。該程序包括二叉樹結(jié)構(gòu)類型以及每一種操作的具體函數(shù)定義和主函數(shù)。共有如下幾個環(huán)節(jié)：1，建立二叉樹2，編寫先序、遞歸遍歷函數(shù)3，編寫先序、非遞歸遍歷函數(shù)4，編寫中序、遞歸遍歷函數(shù)5，編寫中序、非遞歸遍歷函數(shù)6，編寫后序、遞歸遍歷函數(shù)7，編寫后序、非遞歸遍歷函數(shù)3 問題描述實現(xiàn)二叉樹的定義和操作共有如下幾個環(huán)節(jié)：1，初始化二叉樹(即把樹根指針置空)2，按先序次序建立一個二叉樹3，檢查二叉樹是否為空4，按任一種遍歷次序（包括先序、中序、后序）輸出二叉樹中的所有結(jié)點四，

13、實驗代碼#include #include#include #include #include using namespace std; struct btnode char data; struct btnode *Lchild; struct btnode *Rchild; ; /建立二叉樹結(jié)點的結(jié)構(gòu)體類型 struct btnode *createbt(struct btnode *bt ) /先序建立二叉樹 char c; c=getchar(); if(c=.) /如果輸入為空，則子樹為空 bt=NULL; else if(!(bt=(struct btnode *)malloc(s

14、izeof(struct btnode) printf(error!); /檢驗bt空間分配是否成功 bt-data=c; bt-Lchild=createbt(bt-Lchild); /遞歸建立左子樹 bt-Rchild=createbt(bt-Rchild); /遞歸建立右子樹 return(bt); void preOrder(struct btnode *bt) /遞歸先序遍歷 if(bt!=NULL) printf(%c,bt-data); preOrder(bt-Lchild); preOrder(bt-Rchild); void preOrder1(struct btnode *

15、bt) /非遞歸先序遍歷 int i=0; struct btnode *p; stack s; /定義棧 p=bt; while(p!=NULL|!s.empty() while(p!=NULL) printf(%c,p-data); s.push(p); /將根結(jié)點壓棧 p=p-Lchild; /遍歷左子樹 if(!s.empty() p=s.top(); /提取棧頂元素值 s.pop(); /棧頂元素出棧 p=p-Rchild; /訪問右子樹 void midOrder(struct btnode *bt) /遞歸中序遍歷 if(bt!=NULL)midOrder(bt-Lchild);

16、 printf(%c,bt-data); midOrder(bt-Rchild); void midOrder1(struct btnode *bt) /非遞歸中序遍歷 int i=0; struct btnode *p; stack s; p=bt; while(p!=NULL|!s.empty() while(p!=NULL) s.push(p); p=p-Lchild; if(!s.empty() p=s.top(); printf(%c,p-data); s.pop(); p=p-Rchild; void postOrder(struct btnode *bt) /遞歸后序遍歷 if(

17、bt!=NULL) postOrder(bt-Lchild); postOrder(bt-Rchild); printf(%c,bt-data); void postOrder1 (struct btnode *bt) /非遞歸后序遍歷 struct btnode *p,*pre=NULL; stack s; s.push(bt); while(!s.empty() p=s.top(); if(p-Lchild=NULL&p-Rchild=NULL)|(pre!=NULL&(pre=p-Lchild|pre=p-Rchild) /判斷p是否為空或是pre的根結(jié)點 printf(%c,p-dat

18、a); s.pop(); pre=p; else if(p-Rchild!=NULL) s.push(p-Rchild); /先將右結(jié)點壓棧 if(p-Lchild!=NULL) s.push(p-Lchild); /后將左結(jié)點壓棧，因為先入后出 void main() /主函數(shù) printf(注意空格符用“.”來表示：nn); printf(請按照前序遍歷的順序輸入：n); struct btnode *root=NULL; root=createbt(root); printf(n先序遞歸遍歷結(jié)果：); preOrder(root); printf(n中序遞歸遍歷結(jié)果：); midOrde

19、r(root); printf(n后序遞歸遍歷結(jié)果：); postOrder(root); printf(nn先序非遞歸遍歷結(jié)果：); preOrder1(root); printf(n中序非遞歸遍歷結(jié)果：); midOrder1(root); printf(n后序非遞歸遍歷結(jié)果：); postOrder1(root); printf(nn); system(pause);五，運行結(jié)果實驗三：圖一實驗?zāi)康?（1）掌握圖的各種存儲結(jié)構(gòu)，特別要熟練掌握鄰接矩陣和鄰接表存儲結(jié)構(gòu)。（2）遍歷是圖各種應(yīng)用的算法的基礎(chǔ)，要熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法，復(fù)習棧和隊列的應(yīng)用。二實驗內(nèi)容（1) 采

20、用鄰接矩陣作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作；（2) 采用鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。三問題具體描述（1）在圖的鄰接矩陣表示法中： 用鄰接矩陣表示頂點間的相鄰關(guān)系建立它的鄰接矩陣，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、 取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。具體過程：設(shè)x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。若發(fā)現(xiàn)頂點y已訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)

21、的所有路徑，即訪問完所有從y出發(fā)可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發(fā)的未檢測過的邊。（2）圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復(fù)訪問，可設(shè)置一個標志頂點是否被訪問過的輔助數(shù)組 visited 。廣度優(yōu)先搜索是一種分層的搜索過程, 每向前走一步可能訪問一批頂點, 不像深度優(yōu)先搜索那樣有往回退的情況。因此, 廣度優(yōu)先搜索不是一個遞歸的過程。四，實驗代碼#includestdio.h #includestdlib.h #define MaxVertexNum 100 /定義最大頂點數(shù)/ typ

22、edef struct char vexsMaxVertexNum; /頂點表/ int edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表/ int n,e; /圖中的頂點數(shù)n和邊數(shù)e/ MGraph; /用鄰接矩陣表示的圖的類型/ /=建立鄰接矩陣=/ void CreatMGraph(MGraph *G) int i,j,k; char a; printf(請輸入頂點的數(shù)目 和 邊的數(shù)目： ); scanf(%d,%d,&G-n,&G-e); /輸入頂點數(shù)和邊數(shù)/ scanf(%c,&a); printf(請輸入圖的每個頂點：); for(i=0;in;

23、i+) scanf(%c,&a); G-vexsi=a; /讀入頂點信息，建立頂點表/ for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; /初始化鄰接矩陣/ printf(請輸入每條邊對應(yīng)的起始點 和 終點：n); for(k=0;ke;k+) /讀入e條邊，建立鄰接矩陣 / scanf(%d%d,&i,&j); /輸入邊（Vi，Vj）的頂點序號/ G-edgesij=1; G-edgesji=1; /若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句/ /=定義標志向量，為全局變量=/ typedef enumFALSE,TRUE Boolean; B

24、oolean visitedMaxVertexNum; /=DFS：深度優(yōu)先遍歷的遞歸算法=/ void DFSM(MGraph *G,int i) /以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣 int j; printf(%c,G-vexsi); /訪問頂點Vi/ visitedi=TRUE; /置已訪問標志/ for(j=0;jn;j+) /依次搜索Vi的鄰接點/ if(G-edgesij=1 & ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未訪問過，故Vj為新出發(fā)點/ void DFS(MGraph *G) int i; for(i

25、=0;in;i+) visitedi=FALSE; /標志向量初始化/ for(i=0;in;i+) if(!visitedi) /Vi未訪問過/ DFSM(G,i); /以Vi為源點開始DFS搜索/ /=BFS：廣度優(yōu)先遍歷= void BFS(MGraph *G,int k) /以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索/ int i,j,f=0,r=0; int cqMaxVertexNum; /定義隊列 / for(i=0;in;i+) visitedi=FALSE; /標志向量初始化/ for(i=0;in;i+) cqi=-1; /隊列初始化/ printf(%c,G-ve

26、xsk); /訪問源點Vk/ visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊。注意，實際上是將其序號入隊/ while(cqf!=-1) /隊非空則執(zhí)行/ i=cqf; f=f+1; /Vf出隊/ for(j=0;jn;j+) /依次Vi的鄰接點Vj/ if(G-edgesij=1 & !visitedj) /Vj未訪問/ printf(%c,G-vexsj); /訪問Vj/ visitedj=TRUE; r=r+1; cqr=j; /訪問過Vj入隊/ /=main=/ void main() int i; MGraph *G; G=(MGraph *)malloc(siz

27、eof(MGraph); /為圖G/ CreatMGraph(G); /建立鄰接矩陣/ printf(圖的深度遍歷為： ); DFS(G); /深度優(yōu)先遍歷/ printf(n); printf(圖的廣度遍歷為： ); BFS(G,0); /以序號為0的頂點開始廣度優(yōu)先遍歷/ printf(n); 五，程序運行結(jié)果實驗四：快速排序及折半排序一實驗?zāi)康模?) 掌握線性結(jié)構(gòu)上排序的基本思想和算法實現(xiàn)，了解怎樣對各種查找方法進行時間性能（平均查找長度）分析。（2) 掌握樹形結(jié)構(gòu)（二叉排序樹）實現(xiàn)查找的基本思想和算法實現(xiàn)，了解怎樣對各種查找方法進行時間性能（平均查找長度）分析。二實驗內(nèi)容（1) 有序表

28、的二分查找,建立有序表，然后進行二分查找（2) 二叉排序樹的查找,建立二叉排序樹，然后查找三，實驗代碼1，快速排序#include #include #include #include malloc.husing namespace std; struct sqlist int key11; int length; ; /鏈表的結(jié)構(gòu)型定義 int partition(struct sqlist *l,int low,int high) int pivotkey; l-key0=l-keylow;pivotkey=l-keylow;while(lowhigh) while(lowkeyhigh=

29、pivotkey) high-;l-keylow=l-keyhigh; while(lowkeylowkeyhigh=l-keylow; l-keylow=l-key0;return low; /找到序列的樞軸 void qsort(struct sqlist *l,int low,int high) int pivotloc; if(lowlength); /“快速調(diào)用”的函數(shù)定義void main() /主函數(shù) int n; int i; struct sqlist num; printf(請輸入排序的個數(shù):n); scanf(%d,&n); printf(請輸入數(shù)值:n); num.le

30、ngth=n; for(i=1; i=num.length; i+) scanf(%d,&(num.keyi); quicksort(&num); printf(n快速排序后的結(jié)果為n); for(i=1;i=num.length;i+) printf(%d ,num.keyi); printf(nn); system(pause);2，折半排序#include #include#include #include malloc.husing namespace std; #define maxlen 50typedef struct int datamaxlen+1; int last;Seq

31、uenlist; /結(jié)構(gòu)體類型定義 Sequenlist *Sqlset() Sequenlist *L; int i; L= (Sequenlist*) malloc(sizeof(Sequenlist); L-last=0; printf(請輸入表長:n); scanf(%d,&i); printf(請輸入數(shù)值:n); if(i0) for(L-last=1; L-lastlast+) scanf(%d, & L- dataL-last); L-last-; return (L); /單鏈表的建立void zhe_ban(Sequenlist *L) /折半插入 int i,j,low,high,mid; for(i=1; ilast; i+)L