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

1、湖南師范大學(xué)工程與設(shè)計學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗報告姓 名：熊富豪 年 級：2015級專 業(yè)：計算機科學(xué)與技術(shù)學(xué) 號：6任課教師：肖柳明開課時間：20162017學(xué)年第一學(xué)期實驗（一）實驗時間2016年12月8日星期四實驗地點前棟403實驗題目線性表的存儲及操作實驗?zāi)康?) 掌握順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的特點；2) 掌握常見算法。實驗內(nèi)容一內(nèi)容：已知兩個按元素值有序的線性表A和B，編程實現(xiàn)：將A和B有序歸并成一個按元素值有序的線性表，然后刪除值相同的元素。二步驟：1) 從鍵盤輸入兩個按元素值有序的線性表A和B的值；2) 根據(jù)輸入把數(shù)據(jù)元素分別以順序存儲結(jié)構(gòu)和線性鏈表存儲；3) 有序歸并成一個新的按元素

2、值有序的線性表C；4) 輸出顯示合并后的線性表C；5) 分別在順序存儲結(jié)構(gòu)和線性鏈表存儲結(jié)構(gòu)上刪除值相同的元素，并顯示刪除后的線性表。 一結(jié)構(gòu)定義（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)）:struct Node int *elem; int length; int listsize; A,B,C;struct node int data; struct node *next; *HA,*HB,*HC;二.算法描述（類C語言+流程圖）：先將兩個表的元素從鍵盤輸入，然后再將兩個表相加，得到第三個表。在合并后的表中找到值相同的元素，將后面的元素前移以刪除值相同的元素，最后將表的長度減1得到最終的結(jié)果。/順序表LA，L

3、B合為LCSqlist MergeList_sq(Sqlist La,Sqlist Lb, Sqlist Lc) pa=La.elem,pb=Lb.elem,*pc;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(int *) malloc(Lc.listsize*sizeof(int);if(!Lc.elem) /分配失敗exit(0);while(pa=pa_last&pb=pb_last) /判斷La，Lb是否結(jié)尾if

4、(*pa=*pb) /比較大小，影響插入的順序*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last) /可能存在沒有插完的情況*pc+=*pa+;while(pbnext; pb=Lb-next;Lc=pc=La;while(pa&pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb; pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);return Lc; 三.程序清單（關(guān)鍵模塊和語句加以注釋說明）:#include #include struct Node

5、 int *elem; int length; int listsize; A,B,C;struct node int data; struct node *next; *HA,*HB,*HC;void del_order() int i,j; for(i=0;iC.listsize-1;i+) if(C.elemi=C.elemi+1) for(j=i+2;j=C.listsize-1;j+) C.elemj-1=C.elemj; C.listsize-; printf(n刪除后線性表C的值：n); for(i=0;iC.listsize;i+) printf(%d ,C.elemi); i

6、nt merge_order() int i=0,j=0,k=0; C.listsize=A.listsize+B.listsize; C.elem=(int *)malloc(C.listsize*sizeof(int); if(C.elem=NULL) return 0; while(iA.listsize&jB.listsize) if(A.elemiB.elemj) C.elemk+=A.elemi+; else C.elemk+=B.elemj+; while(iA.listsize) C.elemk+=A.elemi+; while(jB.listsize) C.elemk+=B.

7、elemj+; printf(線性表C的值為：n); for(k=0;kC.listsize;k+) printf(%d , C.elemk); del_order();int creat_order() int i; printf(請輸入線性表A和表B的長度:n); scanf(%d%d,&A.listsize,&B.listsize); A.length=A.listsize; B.length=B.listsize; A.elem=(int *)malloc(A.listsize*sizeof(int); B.elem=(int *)malloc(B.listsize*sizeof(in

8、t); if(A.elem=NULL|B.elem=NULL) return 0; printf(請有序輸入線性表A的值n); for(i=0;iA.listsize;i+) scanf(%d,&(A.elemi); printf(請有序輸入線性表B的值n); for(i=0;inext;while(q!=NULL)if(q-data!=p-data) printf(%d ,q-data);p=q;q=q-next;void merge_list() struct node *pa,*pb,*q; HC=q=(struct node *)malloc(sizeof(struct node);

9、while(HA!=NULL&HB!=NULL) if(HA-datadata) q-next=HA; HA=HA-next; else q-next=HB; HB=HB-next; q=q-next; while(HA!=NULL) q-next=HA; HA=HA-next; q=q-next; while(HB!=NULL) q-next=HB; HB=HB-next; q=q-next; q=NULL; printf(線性表C的值為：n); for(q=HC-next;q!=NULL;q=q-next) printf(%d ,q-data); del_list();void creat

10、_list() struct node *p,*q; int la,lb; printf(n請輸入線性表A和B的長度:n); scanf(%d%d,&la,&lb); HA=p=(struct node *)malloc(sizeof(struct node); printf(請輸入線性表A的值:n); while(la-0) scanf(%d,&p-data); q=p; p=(struct node *)malloc(sizeof(struct node); q-next=p; q-next=NULL; HB=p; printf(請輸入線性表B的值：n); while(lb-0) scan

11、f(%d,&p-data); q=p; p=(struct node *)malloc(sizeof(struct node); q-next=p; q-next=NULL; merge_list(); main() char ch;GO:printf(a:順序存儲nb:線性鏈表n); ch=getchar(); if(ch=a) creat_order(); else if(ch=b) creat_list(); else goto GO;四.運行結(jié)果（運行界面圖及說明）:測試數(shù)據(jù)：A=（3,5,8,11），B=（2,6,8,9,11,15,20）1.線性表為順序存儲類型時:2.線性表為鏈式

12、存儲類型時:3.在選擇線性表數(shù)據(jù)存儲類型時輸入數(shù)據(jù)不合法:五.分析與總結(jié)（算法的時間、空間分析，以及改進）:時間復(fù)雜度：O(n)空間復(fù)雜度：O(1)這是第一次上數(shù)據(jù)結(jié)構(gòu)實驗課，雖然之前學(xué)過C語言，可是真到了自己編寫程序的時候，還是不知道該從何下手，編寫的過程中更是錯誤連連，根本就無法運行，后來出來了一個簡單的結(jié)果，成就感還是有的。然后繼續(xù)在現(xiàn)有程序上進行改進，最后出來了這個結(jié)果。編寫程序還是需要耐心，注意大小寫，中文括號之類的小問題，再多看書，基本就能編出簡單的程序，最后在現(xiàn)有程序上進行改進，就能一步步做好。實驗（二）實驗時間2016年12月15日星期四實驗地點前棟403實驗題目棧、隊列實驗?zāi)?/p>

13、的 1、掌握棧、隊列的思想及其存儲實現(xiàn) 2、掌握棧、隊列的常見算法的程序?qū)崿F(xiàn)及應(yīng)用實驗內(nèi)容 實驗內(nèi)容：1) 利用棧和算符優(yōu)先算法，實現(xiàn)表達式求值。 2) 采用順序存儲實現(xiàn)循環(huán)隊列的初始化、入隊、出隊和求隊列長度的操作。實驗步驟：1) 從鍵盤輸入表達式，求值，并顯示求值結(jié)果；2) 每次入隊或出隊操作后，顯示隊列情況和隊列長度。一、 結(jié)構(gòu)定義：（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)）棧： #define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct int *base; int *top; int stacksize; SqStack;隊列：t

14、ypedef struct QNode int data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue;二、 算法描述：（類C語言+流程圖）（一）、算術(shù)表達式算法基本思想：1、 首先置操作數(shù)棧為空棧，表達式起始符#為運算符棧的棧底元素。2、 依次讀入表達式中每個字符，若是操作數(shù)則進OPND棧，若是運算符則和OPTR棧頂運算符比較優(yōu)先權(quán)后進行相應(yīng)的操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素和當前讀入的字符均為#。operandType evalu

15、ateExpression()/算術(shù)表達式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧/OP為運算符號的集合InitState(OPTR); Push(OPTR,#);InitState(OPND); c = getchar();While( c != # | getop(OPTR) != # )If ( !In(c,OP) /當前輸入若為運算數(shù)則壓入OPND棧Push (OPND,c);c = getchar();Else Switch (Precede (getop(OPND),c) /比較輸入運算符和運算符棧頂元素的優(yōu)先級大小 Case :/彈出OPTR棧頂元素和OP

16、ND的兩個棧頂元素進行運算并將結(jié)果入OPND棧 Pop(OPTR,theta); /彈出OPTR棧頂元素Pop(OPND,b);Pop(OPND,a); / 彈出OPND的兩個棧頂元素 Push (OPND,Operate(a,theta,b);/ 進行運算并將結(jié)果入OPND棧 Break; Return GeTop(OPND); /返回運算結(jié)果，此時OPND的棧頂元素即為最終運算結(jié)果。二）、隊列/ 構(gòu)造一個空隊列Qint InitQueue(SqQueue *Q)Q-base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);if(!Q-base)

17、 / 存儲分配失敗exit(0);Q-front=Q-rear=0;/下標初始化為0return 1;/ 返回Q的元素個數(shù),即隊列的長度int QueueLength(SqQueue Q)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;/ 插入元素e為Q的新的隊尾元素int EnQueue(SqQueue *Q,QElemType e)if(Q-rear+1)%MAXQSIZE=Q-front) / 隊列滿return 0;Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MAXQSIZE;return 1; / 若隊列不空,則刪除Q的隊頭元素

18、,用e返回其值,并返回1;否則返回0int DeQueue(SqQueue *Q,QElemType *e)if(Q-front=Q-rear) / 隊列空return 0;*e=Q-baseQ-front;Q-front=(Q-front+1)%MAXQSIZE;return 1;三、 程序清單：（關(guān)鍵模塊和語句加以注釋說明）棧：#include #include #include /OPND棧struct ND int *base; int *top; int size;OPND;/OPTR棧 struct TR char *base; char *top; int size;OPTR;/

19、構(gòu)建OPND空棧 struct ND InitStack_ND(struct ND *S) S-base=(int *)malloc(10*sizeof(int); S-top=S-base; S-size=1;/構(gòu)建OPTR空棧 struct TR InitStack_TR(struct TR *S) S-base=(char *)malloc(10*sizeof(char); S-top=S-base; S-size=1;/用e返回OPND棧的頂元素struct ND TOP_ND(struct ND *S,int *e)/if(S-base=S-top) /return 0; *e=*(

20、S-top-1); /用e返回OPTR棧的頂元素struct TR TOP_TR(struct TR *S,char *e)/if(S-base=S-top) /return 0; *e=*(S-top-1);/在OPND棧中插入estruct ND PUSH_ND(struct ND *S,int e)*(S-top)=e;+(S-top); /在OPTR棧中插入estruct TR PUSH_TR(struct TR *S,char e) *(S-top)=e;+(S-top); /刪除OPND頂棧struct ND POP_ND(struct ND *S,int *e)/if(S-bas

21、e=S-top) /return 0; -(S-top); *e=*(S-top);/刪除OPTR頂棧struct TR POP_TR(struct TR *S,char *e)/if(S-base=S-top) /return 0; -(S-top); *e=*(S-top); /運算符優(yōu)先級char Precede(char a,char b) int i,j; char c77= , , , , , , ,=0&c=9); zi=0; d=C(z); PUSH_ND(&OPND,d); else switch(Precede(x,c) case : / 退棧并將運算結(jié)果入棧 POP_TR

22、(&OPTR,&theta); POP_ND(&OPND,&b); POP_ND(&OPND,&a); /delete PUSH_ND(&OPND,Operate(a,theta,b); break; TOP_TR(&OPTR,&x); TOP_ND(&OPND,&d); return d; main() int c; printf(請輸入要計算的表達式，以字符#結(jié)束:n); c=Expression(); printf(Result=%dn,c); 隊列：#include #include struct Node char *elem; int lenght; int front; int

23、rear;Q;/創(chuàng)建隊列 void InitQueue() printf(請輸入隊列Q的長度:n); scanf(%d,&Q.lenght); Q.elem=(char *)malloc(Q.lenght*sizeof(char); Q.front=Q.rear=1; /隊列情況 void input_Queue() int i=Q.front; printf(n此時隊列長為%dn,(Q.rear-Q.front+Q.lenght)%Q.lenght); printf(n此時隊列Q中的情況為:n); while(i!=Q.rear) printf(%c ,Q.elemi); i=(i+1)%Q

24、.lenght; /入隊 void enqueue(char *s) while(*s!=0) if(Q.rear+1)%Q.lenght=Q.front) printf(隊列已滿，不能入隊n); return ; Q.elemQ.rear=*s; Q.rear=(Q.rear+1)%Q.lenght; s+; /出隊void DeQueue(int num) if(Q.front=Q.rear) printf(n隊列為空n); return ; printf(n出隊的數(shù)據(jù)為:n); while(num!=0) if(Q.front=Q.rear) printf(隊列為空n); return

25、; printf(%c ,Q.elemQ.front); Q.front=(Q.front+1)%Q.lenght; num-; int C() char s20; int b; int a; InitQueue(); while(b) printf(請選擇1.入隊 2.出隊 0.結(jié)束n); scanf(%d,&b); if(b=1) printf(n請輸入要入隊的數(shù)據(jù):n); scanf(%s,&s); enqueue(s); input_Queue(); printf(n); else if(b=2) printf(請輸入出隊數(shù)據(jù)個數(shù)：n); scanf(%d,&a); DeQueue(a

26、); input_Queue(); printf(n); else if(b=0) return 0; else printf(請重新輸入n); main() C();四、 運行結(jié)果：（運行界面圖及說明）測試數(shù)據(jù)：（1）3695（83）（2） 循環(huán)隊列大小為11；d，e，b，g，h入隊；d，e出隊；i，j，k，l，m入隊；b出隊；n，o，p，q，r入隊表達式求值：循環(huán)隊列：五、 分析與總結(jié)：（算法的時間、空間分析，以及改進）時間復(fù)雜度：O(n)空間復(fù)雜度：O(1)用棧來做算式的運算最重要的就是排好不同運算符之間的優(yōu)先級關(guān)系，如果OPND棧和OPTR棧做好了的話基本就很簡單了，只需要注意進棧和出

27、棧不要出錯即可。實驗（三）實驗時間2016年12月15日星期四實驗地點前棟403實驗題目二叉樹的常見操作實驗?zāi)康?1、掌握二叉樹的存儲實現(xiàn)。 2、掌握二叉樹的遍歷思想。 3、掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容1、 輸入字符序列，建立二叉鏈表。 2、 求先序、中序和后序遍歷序列，并顯示輸出。 3、 求二叉樹的深度，并顯示輸出 。 4、 求二叉樹的結(jié)點總數(shù)，并顯示輸出。 一、 結(jié)構(gòu)定義：（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)）#include #include #include #define charchartypedef struct BiTNode char data; BiTNode *lchild,

28、*rchild;*BiTree;二、 算法描述：（類C語言+流程圖）void CreateBiTree(BiTree *T) / 創(chuàng)建樹TElemType ch;scanf(%c,&ch);if(ch=Nil) / 空*T=NULL;else*T=(BiTree)malloc(sizeof(BiTNode);if(!*T)exit(0);(*T)-data=ch; / 生成根結(jié)點CreateBiTree(&(*T)-lchild); / 構(gòu)造左子樹CreateBiTree(&(*T)-rchild); / 構(gòu)造右子樹/ 返回T的深度int BiTreeDepth(BiTree T)int i,

29、j;if(!T)return 0;if(T-lchild)i=BiTreeDepth(T-lchild);/遞歸求深度elsei=0;if(T-rchild)j=BiTreeDepth(T-rchild);elsej=0;return ij ? i+1 : j+1;/ 先序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void PreOrderTraverse(BiTree T,int(*Visit)(TElemType)if(T) / T不空Visit(T-data); / 先訪問根結(jié)點PreOrderTraverse(T-lchild,Visit); / 再先序遍歷左子樹PreOrd

30、erTraverse(T-rchild,Visit); / 最后先序遍歷右子樹/ 中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void InOrderTraverse(BiTree T,int(*Visit)(TElemType)if(T)InOrderTraverse(T-lchild,Visit); / 先中序遍歷左子樹Visit(T-data); / 再訪問根結(jié)點InOrderTraverse(T-rchild,Visit); / 最后中序遍歷右子樹 / 后序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次int PostOrderTraverse(BiTree T,in

31、t(*Visit)(TElemType) / 返回結(jié)點個數(shù)if(T) / T不空PostOrderTraverse(T-lchild,Visit); / 先后序遍歷左子樹PostOrderTraverse(T-rchild,Visit); / 再后序遍歷右子樹; / 最后訪問根結(jié)點int m;m=Visit(T-data);return m;三、 程序清單：（關(guān)鍵模塊和語句加以注釋說明）#include #include static int k=0;struct BiTNode char data; struct BiTNode *lchild,*rchild;*head;/先序遍歷 voi

32、d PreOrderTraverse(struct BiTNode *T) if(T) printf(%c ,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /中序遍歷 void InOrderTraverse(struct BiTNode *T) if(T) InOrderTraverse(T-lchild); printf(%c ,T-data); InOrderTraverse(T-rchild); /后序遍歷 void PostOrderTraverse(struct BiTNode *T)if(T) P

33、ostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c ,T-data); struct BiTNode* creat_Bi() struct BiTNode *p; char ch; ch=getchar(); if(ch= ) p=NULL; else if(!(p=(struct BiTNode *)malloc(sizeof(struct BiTNode) return 0; p-data=ch; p-lchild=creat_Bi(); p-rchild=creat_Bi(); return p;int d

34、epth(struct BiTNode *T) int dl,dr; if(T=NULL) return 0; else dl=depth(T-lchild); dr=depth(T-rchild); if(dl=dr) return dl+1; else return dr+1; /計算二叉樹的節(jié)點個數(shù) int statistics(struct BiTNode *T) if(T=NULL) return 0; else if(T-lchild =NULL&T-rchild=NULL) k+; return statistics(T-lchild)+statistics(T-rchild)+

35、1; void ergodic_statistics() printf(n二叉樹head的先序遍歷為：n); PreOrderTraverse(head); printf(n二叉樹head的中序遍歷為:n); InOrderTraverse(head); printf(n二叉樹head的后序遍歷為:n); PostOrderTraverse(head); printf(n二叉樹head的深度為:%dn,depth(head); printf(二叉樹head的節(jié)點總數(shù)為:%dn,statistics(head); main() head=creat_Bi(); ergodic_statistic

36、s(); printf(%d,k);四、 運行結(jié)果：（運行界面圖及說明）測試數(shù)據(jù)：輸入字符序列ABCDEGF五、 分析與總結(jié)：（算法的時間、空間分析，以及改進）時間復(fù)雜度O(n)空間復(fù)雜度O(n)做二叉樹最重要的思想就時遞歸，在一個函數(shù)中可以反復(fù)遞歸，最后求出二叉樹的深度、節(jié)點數(shù)以及它的各種遍歷。實驗（四）實驗時間2016年12月22日星期四實驗地點前棟403實驗題目查找的有關(guān)操作實驗?zāi)康?、掌握順序查找算法的思想及程序?qū)崿F(xiàn)。 2、掌握折半查找算法的思想及程序?qū)崿F(xiàn)。實驗內(nèi)容1、根據(jù)輸入數(shù)據(jù)，采用順序查找實現(xiàn)某一已知的關(guān)鍵字的查找，并顯示查找結(jié)果。 2、利用實驗一建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找，并顯示查找結(jié)果。一、 結(jié)構(gòu)定義：（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)）#include #include #include using namespace std;#define intint#define SSNUM 11#define BSTNUM 6struct SSTable int*elem; int length;typedef struct BiTNode int data; BiTNode *lchild,*rchild;*BiTree;二、 算法描述：（類C語言+流程圖）Status Search_Seq(SSTable ST, int k