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

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

2、測試程序的如下功 能：根據(jù)輸入的數(shù)據(jù)，找到相應的存儲單元并刪除，顯示表中所有的數(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個數(shù)ListInsert_Sq(L,3,24); for(i=0;i<10;i+)printf(" %d",

6、L.elemi); printf("n");/ 插入一個數(shù) int e;ListDelete_Sq(L,2, e); for(i=0;i<9;i+)printf(" %d",L.elemi);/ 刪除一個數(shù) printf("n");return 0;實驗結(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心得體會： 順序存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快； 結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也相鄰

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

8、的字符，找到相應的結(jié)點并刪除。5、修改程序：（ 1） 增加插入結(jié)點的功能。（ 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;/ 插入八個字符 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;/ 插入一個字符 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;實驗結(jié)果：A C E F H J Q UA B C E F H J Q UA B E F H J Q U心得體會：單鏈表是通過掃描指針 P 進行單鏈表的操作；頭指針唯一標識點鏈表的存在； 插入和刪除元素快捷，方便。實驗 3實驗題目 ：棧操作設(shè)計和實現(xiàn)

13、實驗目的 ：1、掌握棧的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，以便在實際中靈活應用。2、掌握棧的特點，即后進先出和先進先出的原則。3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。實驗要求：回文判斷： 對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤Ｈ纭?abba”是回文，而“ abab”不是回文。實驗主要步驟（ 1）數(shù)據(jù)從鍵盤讀入；（ 2）輸出要判斷的字符串；（ 3）利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“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)造一個空棧 S#define STACKINCREMENT 10/ 在棧構(gòu)造之前和銷毀之后， base的值為 NULL/ 棧頂指針/ 當前已分配的存儲空間，以元素為單位if

15、(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)exit(OVERFLOW); / 存儲分配失敗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) / 棧滿，追加存儲空間S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base)exit(OVERFLOW); / 存儲分配失敗 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(" 請輸入表達式 :n");gets(ch);p=ch;while(*p) /沒到串尾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;實驗結(jié)果：請輸入表達式：abcba輸出： YES! 心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性 質(zhì)，這個固有性質(zhì)使棧成為程序設(shè)計中的有用工具。實驗 4實驗題目 ：二叉樹操作設(shè)計和實現(xiàn)實驗目的 ： 掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。實驗要求： 采用二叉樹鏈表作為存儲結(jié)構(gòu)， 完成二叉樹的建立， 先序、 中序和后序以及按層次遍歷 的操作，求所有葉子及結(jié)點總數(shù)的操作。實驗主要步驟：1、分析、理解程序。2、

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

20、先遍歷)和 BFS(廣度優(yōu)先遍歷)的操作。1 鄰接矩陣作為存儲結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 / 定義最大頂點數(shù)typedef structchar vexsMaxVertexNum; / 頂點表int edgesMaxVertexNumMaxVertexNum; / 鄰接矩陣，可看作邊表int n,e; / 圖中的頂點數(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); / 輸入頂點數(shù)和邊數(shù)scanf("%c",&a);printf("Input Vertex string:");for(i=0;i<G->n;i+)scanf("%c",&a);G->vexsi=a; / 讀入頂點信息，建立頂點表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 )的頂點序號G->edgesij=1;G->edgesji=1; / 若為無向圖，矩陣為對稱矩陣；若建立有向圖， /= 定義標志向量，為全局變量 = typedef enum

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

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

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

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

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