中南大學數(shù)據結構實驗報告(共38頁)

1、精選優(yōu)質文檔-傾情為你奉上中南大學數(shù)據結構實驗報告實驗題目：（1）單鏈表的實現(xiàn)（2）棧和隊列 （3）二叉樹的遍歷（4）查找與排序 學生姓名： 代巍 學生學號： 指導老師： 余臘生 所在學院： 信息科學與工程學院 專業(yè)班級： 信息安全1201班 指導教師評定： 簽 名： 實驗一 單鏈表的實現(xiàn)一、實驗目的了解線性表的邏輯結構和各種存儲表示方法，以及定義在邏輯結構上的各種基本運算及其在某種存儲結構上如何實現(xiàn)這些基本運算。在熟悉上述內容的基礎上，能夠針對具體應用問題的要求和性質，選擇合適的存儲結構設計出相應的有效算法，解決與線性表相關的實際問題二、實驗內容用C/C+語言編寫程序，完成以下功能：（1）運

2、行時輸入數(shù)據，創(chuàng)建一個單鏈表（2）可在單鏈表的任意位置插入新結點（3）可刪除單鏈表的任意一個結點（4）在單鏈表中查找結點（5）輸出單鏈表三、程序設計的基本思想，原理和算法描述：（包括程序的結構，數(shù)據結構，輸入/輸出設計，符號名說明等）用一組地址任意的存儲單元存放線性表中的數(shù)據元素。以元素(數(shù)據元素的映象)+指針(指示后繼元素存儲位置)=結點(表示數(shù)據元素或數(shù)據元素的映象)以“結點的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是指數(shù)據接點是單向排列的。一個單鏈表結點，其結構類型分為兩部分：（1）、數(shù)據域：用來存儲本身數(shù)據。（2）、鏈域或稱為指針域：用來存儲下一個結點地址或者說指向其直接后繼的指針

3、。1、單鏈表的查找對單鏈表進行查找的思路為：對單鏈表的結點依次掃描，檢測其數(shù)據域是否是我們所要查好的值，若是返回該結點的指針，否則返回NULL。2、單鏈表的插入因為在單鏈表的鏈域中包含了后繼結點的存儲地址，所以當我們實現(xiàn)的時候，只要知道該單鏈表的頭指針，即可依次對每個結點的數(shù)據域進行檢測。假設在一個單鏈表中存在2個連續(xù)結點p、q（其中p為q的直接前驅），若我們需要在p、q之間插入一個新結點s，那么我們必須先為s分配空間并賦值，然后使p的鏈域存儲s的地址，s的鏈域存儲q的地址即可。(p-link=s;s-link=q)，這樣就完成了插入操作。3、單鏈表的刪除刪除運算思想方法刪除運算是將表的第i個

4、結點刪去。具體步驟：找到i-1的存儲位置p令p-next指向i的直接后繼結點釋放結點i的空間，將其歸還給存儲池。四、源程序及注釋#include #include #include #include #include #define ElemType int/ 鏈表類型typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;int EmptyList(LinkList &L)if(L-next=NULL)return 0;elsereturn 1; / 手動建立一個帶頭結點的線性鏈表Lvoid SCreate

5、List_L(LinkList &L) LinkList l,p;int i;ElemType d;l=(LinkList) malloc(sizeof(LNode);L=(LinkList) malloc(sizeof(LNode); /生成頭結點l=L; L-next=NULL;cout請依次輸入結點值，以0為結束：d; if(d!=0)p=(LinkList) malloc(sizeof(LNode); /生成新結點p-data=d;p-next=l-next;l-next=p;l=l-next; else break;if(EmptyList(L) cout生成鏈表成功！;else c

6、outnext=NULL;srand(unsigned)time(NULL);for(int i=n;i0;-i)p=(LinkList) malloc(sizeof(LNode); /生成新結點p-data=(rand()%100+1);p-next=l-next;l-next=p;l=l-next; cout生成鏈表成功！;cin.get();cin.get(); /ZCreate_L/建立一個帶頭結點的線性鏈表LinkList CreateList_L()char c;int n;LinkList L;cout*建立線性鏈表*endl;cout1.手動建立endl;cout2.自動建立e

7、ndl;cout*c;if(c=1) SCreateList_L(L);else if(c=2) coutn;ZCreateList_L(L,n);else cout輸入錯誤，請重新輸入:next;int i=0;while (p)+i;p=p-next;return i;cin.get();cin.get(); /LengthList/ 在線性鏈表L中第i個結點之前插入新的數(shù)據元素evoid ListInsert_L(LinkList &L)int i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,s; p=L;int j=0;w

8、hile(p & jnext;+j;if(!p | ji-1) cout輸入錯誤！;cin.get();cin.get();else coute;s=(LinkList) malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;cout插入成功！;cin.get();cin.get(); /ListInsert_L/ 刪除線性鏈表L中的第i個結點void ListDelete_L(LinkList &L)int i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,q; p=L; int

9、 j=0;q=(LinkList) malloc(sizeof(LNode);while (p-next & jnext;+j; /尋找第i個結點if(!(p-next) | ji-1) coutnext;p-next=q-next;e=q-data;cout刪除成功！endl刪除的結點值為：next;cout所有數(shù)據如下所示：endl;while (p)coutdatanext;cin.get();cin.get(); /PrintListvoid SearchList(LinkList &L)/查找某一結點，顯示其位置int i=0;ElemType n;coutn;if(L=NULL)

10、coutnext;while (p-data!=n & p-next!=NULL) p=p-next; i=i+1;if(p-data=n) cout找到了對應的結點，在鏈表的第i+1位上！;else coutnext;free(p);L=NULL;cout線性鏈表L已銷毀!endl;/DestroyListint menu_select() /選擇函數(shù)char *m7= 1.建立線性鏈表,2.某一結點前插入一個結點,3.刪除一個結點,4.計算結點個數(shù)并輸出,5.查找并顯示某一結點位置,6.輸出所有節(jié)點,0.退出系統(tǒng);int i;char c1;dosystem(cls);/*清屏*/cout

11、nn=鏈表的基本操作=nn;for(i=0;i7;i+)coutmiendl;coutn=n;coutc1;while(c16);return(c1-0);void main()LinkList L=NULL;for( ; ; ) switch(menu_select()case 1:L=CreateList_L();system(pause);break;case 2:if(L!=NULL) ListInsert_L(L);else cout鏈表為空，請先建鏈表！;cin.get();cin.get();break;system(pause);break;case 3:if(L!=NULL)

12、 ListDelete_L(L);else cout鏈表為空，請先建鏈表！;cin.get();cin.get();break;system(pause);break;case 4:if(L!=NULL) int i=LengthList(L);cout結點的個數(shù)為：i;cin.get();cin.get();else cout鏈表為空，請先建鏈表！;cin.get();cin.get();break;system(pause);break;case 5:if(L!=NULL) SearchList(L);else cout鏈表為空，請先建鏈表！;cin.get();cin.get();bre

13、ak;system(pause);break;case 6:if(L!=NULL) PrintList(L);else cout鏈表為空，請先建鏈表！;cin.get();cin.get();break;system(pause);break;case 0:if(L!=NULL) DestroyList(L);exit(0);五、實驗結果實驗二 棧和隊列一、實驗目的了解棧和隊列的特性。 掌握棧的順序表示和實現(xiàn)。 掌握棧的鏈式表示和實現(xiàn)。 掌握隊列的順序表示和實現(xiàn)。 掌握隊列的鏈式表示和實現(xiàn)。 掌握棧和隊列在實際問題中的應用。二、實驗內容編寫一個程序實現(xiàn)順序棧的各種基本運算，并在此基礎上設計一個

14、主程序完成如下功能：初始化順序棧，插入元素，刪除棧頂元素，取棧頂元素，遍歷順序棧，置空順序棧。三、程序設計的基本思想，原理和算法描述棧的修改時按照先進后出的原則進行的，試驗中用到構造空棧，及入棧出棧操作。隊列是一種先進先出的線性表，只允許在表的一端插入，而在另一端刪除元素，試驗中構造隊并且入隊出隊。立順序棧SeqStack，存放測試數(shù)據；建立隊列SeqQueue存放出棧數(shù)據；建立InitStack、StackEmpty、StackFull、Pop、Push、GetTop函數(shù)用作順序棧的基本操作；建立InitQueue、QEmpty、Qfull、InQueue、OutQueue、ReadFron

15、t函數(shù)用作隊列的基本操作；建立主函數(shù)依次按序對子函數(shù)進行操作：InitStack初始化棧Push壓入數(shù)據InitQueue初始化隊列Pop彈出數(shù)據InQueue存入隊列OutQueue出隊列Push壓入棧Pop彈出數(shù)據free清空棧與隊列。在數(shù)據的輸入與數(shù)據的輸出時提供必要的提示信息。四、源程序及其注釋#include #include stack.h#include #define MAXSIZE 100/作用 ：對棧進行初始化/參數(shù)：無/返回值：SeqStackSeqStack SeqStackInit() SeqStack S ;S.top = -1 ;return S ;/作用 ：對棧

16、進行判斷是否為空/參數(shù)：傳入要判斷的棧/返回值：返回TRUE為空，返回FLASE為非空int SeqStackEmpty(SeqStack S) if(S.top top - ;printf(n清空！n) ;/作用 ：把元素x壓入棧，使其成為新的棧頂元素/參數(shù)：傳入棧和要輸入的數(shù)字/返回值：無void SeqStackPush(SeqStack *S,DataType x)S-top+ ;/要求是先挖坑，再種蘿卜S-dataS-top = x ;/作用 ：出棧/參數(shù)：要從該棧出來/返回值：從棧中出來的數(shù)DataType SeqStackPop(SeqStack *S)DataType temp

17、 ;if(SeqStackEmpty(*S)printf(sorry！為空棧！) ;/exit(1) ;elsetemp =S-dataS-top ;/出棧是當前出棧，要求先挖蘿卜再填坑S-top - ;printf(n%dn,temp) ;/作用 ：取棧頂元素/參數(shù)：要操作的棧/返回值：從棧中出來的數(shù)DataType SeqStackGetTop(SeqStack S)DataType temp ;if(SeqStackEmpty(S)printf(sorry！為空棧！) ;/exit(1) ;elsetemp =S.dataS.top ;/出棧是當前出棧，要求先挖蘿卜再填坑printf(n

18、%dn,temp) ;/作用 輸出順序棧中的元素/參數(shù)：要操作的棧/返回值：從棧中出來的數(shù)void SeqStackPrint(SeqStack S) DataType temp ;SeqStack p ;p = S ;printf(輸出棧中的所有元素:) ;while(!SeqStackEmpty(p)temp =p.datap.top ;/出棧是當前出棧，要求先挖蘿卜再填坑p.top - ;printf(n% d n,temp) ;/當這里位置數(shù)據類型怎么辦void main(void)int num ;int input ;SeqStack p ;p = SeqStackInit() ;

19、/這里調用入棧函數(shù)，把10,20,30進棧SeqStackPush(&p,10) ;SeqStackPush(&p,20) ;SeqStackPush(&p,30) ;while(1)printf(nt實驗二nn) ;printf(n1.入棧) ;printf(n2.棧頂元素彈出) ;printf(n3.取棧頂元素) ;printf(n4.輸出順序棧中的元素) ;printf(n5.清空棧n) ;printf(t請輸入要實現(xiàn)的功能n) ;scanf(%d,&num) ;switch(num)case 1 :printf(n請輸入要入棧的數(shù)：ttn) ;scanf(%d, &input) ;Se

20、qStackPush(&p,input) ;break;case 2 :SeqStackPop(&p) ;break;case 3 :SeqStackGetTop(p) ;break;case 4 :SeqStackPrint(p) ;break;case 5 :ClearStack(&p) ;break;五、實驗結果實驗三 二叉樹的建立和遍歷一、實驗目的1、學會實現(xiàn)二叉樹結點結構和對二叉樹的基本操作。2、掌握對二叉樹每種操作的具體實現(xiàn)，學會利用遞歸方法編寫對二叉樹這種遞歸數(shù)據結構進行處理的算法。二、實驗內容編寫程序任意輸入二叉樹的結點個數(shù)和結點值，構造一棵二叉樹，采用三種遞歸遍歷算法(前序、

21、中序、后序)對這棵二叉樹進行遍歷并計算出二叉樹的高度。三、程序設計的基本思想，原理和算法描述1、數(shù)據結構的定義二叉樹是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹，并且二叉樹有左右之分，其次序不能任意顛倒。二叉樹的存儲結構分為順序存儲和鏈式存儲結構，本次我們主要應用二叉樹的二叉鏈表的方式存儲方式，實驗中首先必須對二叉樹的數(shù)據結構進行定義，即定義一個二叉鏈表，其中其數(shù)據成員包括節(jié)點的數(shù)據、左子樹的指針、右子樹的指針。2、二叉樹的建立在實驗開始前我們要建立一個以先序形式的二叉樹，先序的二叉樹就是先訪問根結點，然后訪問左子樹，最后訪問右子樹的遍歷。3、二叉樹的遍歷二叉樹的遍歷分為先序、中序、后

22、序，需先取遍歷的節(jié)點的數(shù)據存入隊列中，然后輸出。4、程序中要的函數(shù)的介紹（1）二叉樹的類型定義（2）定義鏈式隊列類型（3）初始化鏈式隊列的函數(shù)（4）主函數(shù)四、源程序及注釋#include#includetypedef struct BiTNodechar data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void CreatBiTree(BiTree &T)/前序法創(chuàng)建二叉樹char ch;if(ch=getchar()=n)T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(

23、1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);void PreTravel(BiTree &T)/前序遍歷if(T) printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);void MidTravel(BiTree &T)/中序遍歷if(T) MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);void PostTravel(BiTree &T)/后序遍歷if(T) PostTravel(T-lchil

24、d);PostTravel(T-rchild);printf(%c,T-data);void main() BiTree T;printf(please input the bitree:n ); CreatBiTree(T);/*/printf(The Pretravel is:n);PreTravel(T);printf(n);/*/printf(The Midtravel is:n);MidTravel(T);printf(n);/*/printf(The PostTravel is:n);PostTravel(T);printf(n);五、實驗結果實驗四 查找和排序一、實驗目的(1)掌

25、握查找的不同方法，并能用c語言實現(xiàn)查找算法。 (2)掌握常用的排序方法，并掌握用c語言實現(xiàn)排序算法的方法。(3)熟練掌握順序表的選擇排序、冒泡排序、直接插入排序等算法的實現(xiàn)；(4)了解各種方法的排序過程及其時間復雜度的分析方法。二、實驗內容(1)完整理解有關排序和查找的相關算法和基本思想以及種種算法使用的數(shù)據存儲結構；(2)通過線性表對一組數(shù)據中的某個數(shù)據進行查找；對該組數(shù)據進行從小到大的順序進行排序；三、程序設計的基本思想，原理和算法描述：開始的時候提示輸入一組數(shù)據。并存入一維數(shù)組中，接下來調用一系列查找算法對其進行處理。順序查找只是從頭到尾進行遍歷。二分查找則是先對數(shù)據進行排序，然后利用三

26、個標志，分別指向最大，中間和最小數(shù)據，接下來根據待查找數(shù)據和中間數(shù)據的比較不斷移動標志，直至找到。二叉排序樹則是先構造，構造部分花費最多的精力，比根節(jié)點數(shù)據大的結點放入根節(jié)點的右子樹，比根節(jié)點數(shù)據小的放入根節(jié)點的左子樹，其實完全可以利用遞歸實現(xiàn)，這里使用的循環(huán)來實現(xiàn)的，感覺這里可以嘗試用遞歸。當二叉樹建好后，中序遍歷序列即為由小到大的有序序列，查找次數(shù)不會超過二叉樹的深度。這里還使用了廣義表輸出二叉樹，以使得更直觀。哈希表則是利用給定的函數(shù)式建立索引，方便查找。四、源程序及其注釋#include #define LENGTH 100#include #include #define INFMT

27、 %d#define OUTFMT %d /* #define NULL 0L */#define BOOL int#define TRUE 1#define FALSE 0#define LEN 10000typedef int ElemType;typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree;typedef BSTree BiTree;/* 插入新節(jié)點 */void Insert(BSTree *tree, ElemType item) BSTree node =

28、 (BSTree)malloc(sizeof(BSTNode); node-data = item; node-lchild = node-rchild = NULL; if (!*tree) *tree = node; else BSTree cursor = *tree; while (1) if (item data) if (NULL = cursor-lchild) cursor-lchild = node; break; cursor = cursor-lchild; else if (NULL = cursor-rchild) cursor-rchild = node; brea

29、k; cursor = cursor-rchild; return;void showbitree(BiTree T)/ 遞歸顯示二叉樹的廣義表形式if(!T)printf(空);return;printf(%d,T-data);/ 打印根節(jié)點if(T-lchild |T-rchild)putchar();showbitree(T-lchild);/ 遞歸顯示左子樹putchar(,);showbitree(T-rchild);/ 遞歸顯示右子樹putchar();/* 查找指定值 */BSTree Search(BSTree tree, ElemType item) BSTree curso

30、r = tree; while (cursor) if (item = cursor-data) return cursor; else if ( item data) cursor = cursor-lchild; else cursor = cursor-rchild; return NULL;/* 中綴遍歷 */void Inorder(BSTree tree) BSTree cursor = tree; if (cursor) Inorder(cursor-lchild); printf(OUTFMT, cursor-data); Inorder(cursor-rchild); /*

31、回收資源 */void Cleanup(BSTree tree) BSTree cursor = tree, temp = NULL; if (cursor) Cleanup(cursor-lchild); Cleanup(cursor-rchild); free(cursor); void searchtree(BSTree root) char choice; printf(中序遍歷的結果為:n); Inorder(root); printf(nn); ElemType item; BSTree ret; /* 二叉排序樹的查找測試 */ do printf(n請輸入查找數(shù)據：); sca

32、nf(%d, &item); getchar(); printf(Searching.n); ret = Search(root, item); if (NULL = ret) printf(查找失??！); else printf(查找成功！); printf(n繼續(xù)測試按y，退出按其它鍵。n); choice = getchar(); while (choice=y|choice=Y); Cleanup(root);searchhash(int *arr,int n)int a10;int b,i,j,c;j=1;for(i=0;i9;i+)ai=0;printf(以下為哈希表輸出n);fo

33、r(i=0;in;i+)c=arri%7;A:if(ac=0)ac=arri;else c=(c+1)%7;j+;ac+;goto A;printf(n%d在哈希表的第%d位,第%d次放入哈希表n,arri,c,j);j=1;void SequenceSearch(int *fp,int Length);void Search(int *fp,int length);void Sort(int *fp,int length);void SequenceSearch(int *fp,int Length) int data; printf(開始使用順序查詢.n請輸入你想要查找的數(shù)據.n); sc

34、anf(%d,&data); for(int i=0;iLength;i+) if(fpi=data) printf(經過%d次查找，查找到數(shù)據%d.n,i+1,data); return ; printf(經過%d次查找，未能查找到數(shù)據%d.n,i,data);void Search(int *fp,int length) int data; printf(開始使用順序查詢.n請輸入你想要查找的數(shù)據.n); scanf(%d,&data); printf(由于二分查找法要求數(shù)據是有序的，現(xiàn)在開始為數(shù)組排序.n); Sort(fp,length); printf(數(shù)組現(xiàn)在已經是從小到大排列,下

35、面將開始查找.n); int bottom,top,middle; bottom=0; top=length; int i=0; while (bottom=top) middle=(bottom+top)/2; i+; if(fpmiddledata) top=middle-1; else printf(經過%d次查找，查找到數(shù)據%d.n,i,data); return; printf(經過%d次查找，未能查找到數(shù)據%d.n,i,data);void Sort(int *fp,int length) printf(現(xiàn)在開始為數(shù)組排序，排列結果將是從小到大.n); int temp; for(

36、int i=0;ilength;i+) for(int j=0;jfpj+1) temp=fpj; fpj=fpj+1; fpj+1=temp; printf(排序完成!n下面輸出排序后的數(shù)組:n); for(int k=0;klength;k+) printf(%5d,fpk); printf(n); struct hash int key; int si; ;struct hash hlist11;int i,adr,sum,d;float average;void chash(int *arr,int n) for(i=0;i11;i+) hlisti.key=0; hlisti.si=0; for(i=0;in;i+) sum=0; adr=(3*arri)%11; d=adr; if(hlistadr.key=0) hlistadr.key=a