大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告材料

1、數(shù)據(jù)結(jié)構(gòu) （C 語(yǔ)言版） 實(shí)驗(yàn)報(bào)告專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程學(xué)號(hào): 201240703061班級(jí): 軟件二班 姓名: 朱海霞 指導(dǎo)教師 : _劉遵仁青島大學(xué)信息工程學(xué)院2013年 10月實(shí)驗(yàn) 1實(shí)驗(yàn)題目 ：順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除實(shí)驗(yàn)?zāi)康?：了解和掌握線性表的邏輯結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)， 掌握線性表的基本算法及相關(guān)的時(shí)間性 能分析。實(shí)驗(yàn)要求： 建立一個(gè)數(shù)據(jù)域定義為整數(shù)類型的線性表， 在表中允許有重復(fù)的數(shù)據(jù)； 根據(jù)輸入的數(shù)據(jù)， 先找到相應(yīng)的存儲(chǔ)單元，后刪除之。實(shí)驗(yàn)主要步驟：1、分析、理解給出的示例程序。2、調(diào)試程序，并設(shè)計(jì)輸入一組數(shù)據(jù)( 3，-5 ，6，8，2，-5 ，4，7，-9 )，

2、測(cè)試程序的如下功 能：根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲(chǔ)單元并刪除，顯示表中所有的數(shù)據(jù)。程序代碼 :#include<stdio.h>#include<malloc.h>#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structint* elem;int length;int listsize;Sqlist;int InitList_Sq(Sqlist &L) L.elem=(int*)malloc(LIS

3、T_INIT_SIZE*sizeof(int); if(!L.elem) return -1;L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int ListInsert_Sq(Sqlist&L,int i,int e) if(i<1|i>L.length+1) return ERROR; if(L.length=L.listsize)int *newbase; newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int); if(!newbase) re

4、turn -1;L.elem=newbase; L.listsize+=LISTINCREMENT;int *p,*q; q=&(L.elemi-1);for(p=&(L.elemL.length-1);p>=q;-p)*(p+1)=*p;*q=e;+L.length; return OK;int ListDelete_Sq(Sqlist &L,int i,int e)int *p,*q;if(i<1|i>L.length)return ERROR; p=&(L.elemi-1);e=*p; q=L.elem+L.length-1;for(+p

5、;p<=q;+p)*(p-1)=*p;-L.length;return OK;int main()Sqlist L;InitList_Sq(L);/ 初始化int i,a=3,-5,6,8,2,-5,4,7,-9; for(i=1;i<10;i+)ListInsert_Sq(L,i,ai-1); for(i=0;i<9;i+)printf(" %d",L.elemi); printf("n");/插入 9個(gè)數(shù)ListInsert_Sq(L,3,24); for(i=0;i<10;i+)printf(" %d",

6、L.elemi); printf("n");/ 插入一個(gè)數(shù) int e;ListDelete_Sq(L,2, e); for(i=0;i<9;i+)printf(" %d",L.elemi);/ 刪除一個(gè)數(shù) printf("n");return 0;實(shí)驗(yàn)結(jié)果：3， -5,6,8,2 ， -5,4,7 ， -9 3，-5,24,6,8,2 ，-5,4,7 ，-9 3,24,6,8,2 ，-5,4,7 ， -9心得體會(huì)： 順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時(shí)間是一個(gè)常數(shù)，速度快； 結(jié)構(gòu)簡(jiǎn)單，邏輯上相鄰的元素在物理上也相鄰

7、；不使用指針，節(jié)省存儲(chǔ)空間； 但是插入和刪除元素需要移動(dòng)大量元素，消耗大量時(shí)間；需要一個(gè)連續(xù)的存儲(chǔ) 空間；插入元素可能發(fā)生溢出；自由區(qū)中的存儲(chǔ)空間不能被其他數(shù)據(jù)共享 實(shí)驗(yàn) 2實(shí)驗(yàn)題目 ：?jiǎn)捂湵淼牟迦牒蛣h除實(shí)驗(yàn)?zāi)康?：了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)， 掌握單鏈表的基本算法及相關(guān)的時(shí)間性 能分析。實(shí)驗(yàn)要求：建立一個(gè)數(shù)據(jù)域定義為字符類型的單鏈表， 在鏈表中不允許有重復(fù)的字符； 根據(jù)輸入的 字符，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。實(shí)驗(yàn)主要步驟：3、分析、理解給出的示例程序。4、調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)（如： A， C， E，F(xiàn)，H，J，Q，M），測(cè)試程序的如下功能：不 允許重復(fù)字符的插入；根據(jù)輸入

8、的字符，找到相應(yīng)的結(jié)點(diǎn)并刪除。5、修改程序：（ 1） 增加插入結(jié)點(diǎn)的功能。（ 2） 建立鏈表的方法有“前插” 、“后插”法。程序代碼 : #include<stdio.h> #include<malloc.h> #define NULL 0 #define OK 1 #define ERROR 0 typedef struct LNodeint data; struct LNode *next;LNode,*LinkList;int InitList_L(LinkList &L)L=(LinkList)malloc(sizeof(LNode);L->nex

9、t=NULL;return OK;int ListInsert_L(LinkList &L,int i,int e)LinkList p,s;int j;p=L;j=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;return OK;int ListDelete_L(LinkList&L,int i,int &e)L

10、inkList p,q;int j;p=L;j=0;while(p->next&&j<i-1)p=p->next;+j;if(!(p->next)|j<i-1)return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;int main()LinkList L,p;char a8='A','C','E','F','H','J','Q',

11、9;U'int i,j;InitList_L(L);for(i=1,j=0;i<=8,j<8;i+,j+)ListInsert_L(L,i,aj);p=L->next;while(p!=NULL) printf("%ct",p->data); p=p->next;/ 插入八個(gè)字符 printf("n");i=2;int e; ListInsert_L(L,i,'B'); p=L->next;while(p!=NULL) printf("%ct",p->data); p=

12、p->next;/ 插入一個(gè)字符 printf("n");i=3;ListDelete_L(L,i,e); p=L->next;while(p!=NULL) printf("%ct",p->data); p=p->next;printf("n");return 0;實(shí)驗(yàn)結(jié)果：A C E F H J Q UA B C E F H J Q UA B E F H J Q U心得體會(huì)：?jiǎn)捂湵硎峭ㄟ^(guò)掃描指針 P 進(jìn)行單鏈表的操作；頭指針唯一標(biāo)識(shí)點(diǎn)鏈表的存在； 插入和刪除元素快捷，方便。實(shí)驗(yàn) 3實(shí)驗(yàn)題目 ：棧操作設(shè)計(jì)和實(shí)現(xiàn)

13、實(shí)驗(yàn)?zāi)康?：1、掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。3、掌握棧的基本運(yùn)算，如：入棧與出棧等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。實(shí)驗(yàn)要求：回文判斷： 對(duì)于一個(gè)從鍵盤(pán)輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如“ abba”是回文，而“ abab”不是回文。實(shí)驗(yàn)主要步驟（ 1）數(shù)據(jù)從鍵盤(pán)讀入；（ 2）輸出要判斷的字符串；（ 3）利用棧的基本操作對(duì)給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“ No”。程序代碼 : #include<stdio.h> #include<stdlib.h

14、> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2#define N 100 #define STACK_INIT_SIZE 100typedef structint *base;int *top;int stacksize; SqStack;int InitStack(SqStack &S) / 構(gòu)造一個(gè)空棧 S#define STACKINCREMENT 10/ 在棧構(gòu)造之前和銷毀之后， base的值為 NULL/ 棧頂指針/ 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位if

15、(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)exit(OVERFLOW); / 存儲(chǔ)分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack S) /若棧 S為空棧，則返回 TRUE，否則返回 FALSEif(S.top=S.base)return TRUE;elsereturn FALSE;int Push(SqStack &S, int e) / 插入元素 e 為新的棧頂元素if(S.top-S.base>=S.stack

16、size) / 棧滿，追加存儲(chǔ)空間S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base)exit(OVERFLOW); / 存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*(S.top)+=e;return OK;int Pop(SqStack &S,int &e) / 若棧不空，則刪除 S的棧頂元素，用 e返回其值，并返回 OK；否則返回 ERROR if(S.top=S.base)retur

17、n ERROR;e=*-S.top;return OK;int main()SqStack s;int i,e,j,k=1;char chN = 0,*p,bN = 0;if(InitStack(s) / 初始化棧成功printf(" 請(qǐng)輸入表達(dá)式 :n");gets(ch);p=ch;while(*p) /沒(méi)到串尾Push(s,*p+); for(i=0;i<N;i+) if(!StackEmpty(s) / 棧不空 Pop(s,e); / 彈出棧頂元素 bi=e; for(i=0;i<N;i+) if(chi!=bi) k=0;if(k=0) printf(

18、"NO!");elseprintf("輸出 :")printf("YES!"); return 0;實(shí)驗(yàn)結(jié)果：請(qǐng)輸入表達(dá)式：abcba輸出： YES! 心得體會(huì)：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進(jìn)后出的性 質(zhì)，這個(gè)固有性質(zhì)使棧成為程序設(shè)計(jì)中的有用工具。實(shí)驗(yàn) 4實(shí)驗(yàn)題目 ：二叉樹(shù)操作設(shè)計(jì)和實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康?： 掌握二叉樹(shù)的定義、性質(zhì)及存儲(chǔ)方式，各種遍歷算法。實(shí)驗(yàn)要求： 采用二叉樹(shù)鏈表作為存儲(chǔ)結(jié)構(gòu)， 完成二叉樹(shù)的建立， 先序、 中序和后序以及按層次遍歷 的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。實(shí)驗(yàn)主要步驟：1、分析、理解程序。2、

19、調(diào)試程序， 設(shè)計(jì)一棵二叉樹(shù)， 輸入完全二叉樹(shù)的先序序列， 用#代表虛結(jié)點(diǎn) (空指針)， 如 ABD#CE#F#，建立二叉樹(shù)，求出先序、中序和后序以及按層次遍歷序列，求 所有葉子及結(jié)點(diǎn)總數(shù)。程序代碼 :實(shí)驗(yàn)結(jié)果：心得體會(huì)：實(shí)驗(yàn) 5實(shí)驗(yàn)題目 ：圖的遍歷操作實(shí)驗(yàn)?zāi)康?：掌握有向圖和無(wú)向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu)；掌握 DFS 及 BFS對(duì)圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。實(shí)驗(yàn)要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu)，完成有向圖和無(wú)向圖的DFS和 BFS操作。實(shí)驗(yàn)主要步驟：設(shè)計(jì)一個(gè)有向圖和一個(gè)無(wú)向圖，任選一種存儲(chǔ)結(jié)構(gòu)，完成有向圖和無(wú)向圖的DFS(深度優(yōu)

20、先遍歷)和 BFS(廣度優(yōu)先遍歷)的操作。1 鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 / 定義最大頂點(diǎn)數(shù)typedef structchar vexsMaxVertexNum; / 頂點(diǎn)表int edgesMaxVertexNumMaxVertexNum; / 鄰接矩陣，可看作邊表int n,e; / 圖中的頂點(diǎn)數(shù) n 和邊數(shù) eMGraph; / 用鄰接矩陣表示的圖的類型/= 建立鄰接矩陣 =void CreatMGraph(MGraph *G)int

21、i,j,k;char a;printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); / 輸入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("Input Vertex string:");for(i=0;i<G->n;i+)scanf("%c",&a);G->vexsi=a; / 讀入頂點(diǎn)信息，建立頂點(diǎn)表for(i=0;i<G-&

22、gt;n;i+)for(j=0;j<G->n;j+)G->edgesij=0; / 初始化鄰接矩陣printf("Input edges,Creat Adjacency Matrixn");for(k=0;k<G->e;k+) /讀入 e 條邊，建立鄰接矩陣scanf("%d%d",&i,&j); / 輸入邊( Vi ，Vj )的頂點(diǎn)序號(hào)G->edgesij=1;G->edgesji=1; / 若為無(wú)向圖，矩陣為對(duì)稱矩陣；若建立有向圖， /= 定義標(biāo)志向量，為全局變量 = typedef enum

23、FALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS ：深度優(yōu)先遍歷的遞歸算法 = void DFSM(MGraph *G,int i) / 以 Vi 為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖 G 進(jìn)行 DFS搜索，鄰接矩陣是給出你的編碼去掉該條語(yǔ)句0，1 矩陣/=BFS ：廣度優(yōu)先遍歷 =void BFS(MGraph *G,int k) / 以 Vk 為源點(diǎn)對(duì)用鄰接矩陣表示的圖 G進(jìn)行廣度優(yōu)先搜索給出你的編碼/= 主程序 main =void main()int i;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph)

24、; /為圖 G申請(qǐng)內(nèi)存空間CreatMGraph(G); / printf("Print Graph DFS: "); DFS(G); / printf("n");printf("Print Graph BFS: "); BFS(G,3); /建立鄰接矩陣深度優(yōu)先遍歷以序號(hào)為 3 的頂點(diǎn)開(kāi)始廣度優(yōu)先遍歷printf("n");2 鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50/定義最大頂

25、點(diǎn)數(shù)typedef struct node /邊表結(jié)點(diǎn)int adjvex; /鄰接點(diǎn)域struct node *next; /鏈域EdgeNode;typedef struct vnode /頂點(diǎn)表結(jié)點(diǎn)char vertex; / 頂點(diǎn)域EdgeNode *firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList 是鄰接表類型typedef struct AdjList adjlist; /鄰接表int n,e; /圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph; /圖類型/= 建立圖的鄰接表 =void

26、CreatALGraph(ALGraph *G)int i,j,k;char a;EdgeNode *s;/ 定義邊表結(jié)點(diǎn)printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); /讀入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("Input Vertex string:");for(i=0;i<G->n;i+) /建立邊表scanf("%c",

27、&a);G->adjlisti.vertex=a; /讀入頂點(diǎn)信息G->adjlisti.firstedge=NULL; /邊表置為空表printf("Input edges,Creat Adjacency Listn");for(k=0;k<G->e;k+) / 建立邊表 scanf("%d%d",&i,&j); / 讀入邊( Vi ， Vj )的頂點(diǎn)對(duì)序號(hào) s=(EdgeNode *)malloc(sizeof(EdgeNode); / 生成邊表結(jié)點(diǎn) s->adjvex=j; / 鄰接點(diǎn)序號(hào)為 j s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; / 將新結(jié)點(diǎn) *S 插入頂點(diǎn) Vi 的邊表頭部 s=(EdgeNode *)malloc(sizeof(EdgeNode);s->adjvex=i; / 鄰接點(diǎn)序號(hào)為 i s->next=G->adjlistj.firstedge;G->adjlistj.firstedge=s; / 將新結(jié)點(diǎn) *S 插入頂點(diǎn) Vj 的邊表頭部 /= 定義標(biāo)志向量，為全局變量 =typedef enum