數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 實(shí)驗(yàn)報(bào)告專(zhuān)業(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)線(xiàn)性表的插入和刪除實(shí)驗(yàn)?zāi)康模毫私夂驼莆站€(xiàn)性表的邏輯結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)，掌握線(xiàn)性表的基本算法及相關(guān)的時(shí)間性能分析。實(shí)驗(yàn)要求：建立一個(gè)數(shù)據(jù)域定義為整數(shù)類(lèi)型的線(xiàn)性表，在表中允許有重復(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），測(cè)試程序的如下功能：

2、根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲(chǔ)單元并刪除，顯示表中所有的數(shù)據(jù)。程序代碼:#include#include#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(LIST_INIT_SIZE*sizeof(int);if(!L.elem) return -1;L.

3、length=0;L.listsize=LIST_INIT_SIZE;return OK;int ListInsert_Sq(Sqlist&L,int i,int e)if(iL.length+1) return ERROR;if(L.length=L.listsize)int *newbase;newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int);if(!newbase) return -1;L.elem=newbase;L.listsize+=LISTINCREMENT;int *p,*q;q=&(L.ele

4、mi-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(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;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

5、;for(i=1;i10;i+) ListInsert_Sq(L,i,ai-1);for(i=0;i9;i+)printf( %d,L.elemi);printf(n);/插入9個(gè)數(shù)ListInsert_Sq(L,3,24);for(i=0;i10;i+)printf( %d,L.elemi);printf(n);/插入一個(gè)數(shù)int e;ListDelete_Sq(L,2, e);for(i=0;i9;i+)printf( %d,L.elemi);/刪除一個(gè)數(shù) printf(n);return 0;實(shí)驗(yàn)結(jié)果：3，-5,6,8,2，-5,4,7，-93，-5,24,6,8,2，-5,4,7，-9

6、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)單，邏輯上相鄰的元素在物理上也相鄰；不使用指針，節(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)康模毫私夂驼莆站€(xiàn)性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時(shí)間性能分析。實(shí)驗(yàn)要求：建立一個(gè)數(shù)據(jù)域定義為字符類(lèi)型的單鏈表，在鏈表中不允許有重復(fù)的字符；根據(jù)輸入的字符，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。實(shí)驗(yàn)主要步驟：3、 分析、理解給

7、出的示例程序。4、 調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)（如：A，C，E，F(xiàn)，H，J，Q，M），測(cè)試程序的如下功能：不允許重復(fù)字符的插入；根據(jù)輸入的字符，找到相應(yīng)的結(jié)點(diǎn)并刪除。5、 修改程序：（1） 增加插入結(jié)點(diǎn)的功能。（2） 建立鏈表的方法有“前插”、“后插”法。程序代碼:#include#include#define NULL 0#define OK 1#define ERROR 0typedef struct LNode int data; struct LNode *next;LNode,*LinkList;int InitList_L(LinkList &L)L=(LinkList)malloc

8、(sizeof(LNode);L-next=NULL;return OK;int ListInsert_L(LinkList &L,int i,int e)LinkList p,s;int j;p=L;j=0;while(p&jnext;+j;if(!p|ji-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)LinkList p,q;int j;p=L;j=0;while(p-nex

9、t&jnext;+j;if(!(p-next)|jnext;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,U;int i,j;InitList_L(L);for(i=1,j=0;i=8,jnext;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=p-nex

10、t;/插入一個(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)實(shí)驗(yàn)?zāi)康模?、掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。3、掌握棧的基本

11、運(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 #include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define N 100 #define STACK_I

12、NIT_SIZE100 #define STACKINCREMENT10 typedef struct int *base; / 在棧構(gòu)造之前和銷(xiāo)毀之后，base的值為NULL int*top; / 棧頂指針 int stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 SqStack; int InitStack(SqStack &S) / 構(gòu)造一個(gè)空棧S if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int) exit(OVERFLOW); / 存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT

13、_SIZE; return OK; int StackEmpty(SqStack S) / 若棧S為空棧，則返回TRUE，否則返回FALSE if(S.top=S.base) return TRUE; else return FALSE; int Push(SqStack &S, int e) / 插入元素e為新的棧頂元素 if(S.top-S.base=S.stacksize) / 棧滿(mǎn)，追加存儲(chǔ)空間 S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) exit(OVERFLOW

14、); / 存儲(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) return 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) / 初始化棧成功 pri

15、ntf(請(qǐng)輸入表達(dá)式:n); gets(ch); p=ch; while(*p) / 沒(méi)到串尾 Push(s,*p+); for(i=0;iN;i+) if(!StackEmpty(s) / 棧不空 Pop(s,e); / 彈出棧頂元素bi=e; for(i=0;in,&G-e); /輸入頂點(diǎn)數(shù)和邊數(shù) scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) scanf(%c,&a); G-vexsi=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表 for(i=0;in;i+)for(j=0;jn;j+) G-edgesij=0; /初始化鄰接矩陣

16、 printf(Input edges,Creat Adjacency Matrixn); for(k=0;ke;k+) /讀入e條邊，建立鄰接矩陣 scanf(%d%d,&i,&j); /輸入邊（Vi，Vj）的頂點(diǎn)序號(hào) G-edgesij=1; G-edgesji=1; /若為無(wú)向圖，矩陣為對(duì)稱(chēng)矩陣；若建立有向圖，去掉該條語(yǔ)句 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(MGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示

17、的圖G進(jìn)行DFS搜索，鄰接矩陣是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); /為圖G申請(qǐng)內(nèi)存空間 CreatMGraph(G); /建立鄰接矩陣 printf(Print Graph DFS: ); DFS(G); /深度優(yōu)先遍歷 printf(n); printf(Print Graph BFS: ); BFS(G,3);

18、/以序號(hào)為3的頂點(diǎn)開(kāi)始廣度優(yōu)先遍歷 printf(n);2 鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)#includestdio.h#includestdlib.h#define MaxVertexNum 50 /定義最大頂點(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

19、; /AdjList是鄰接表類(lèi)型typedef struct AdjList adjlist; /鄰接表 int n,e; /圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph; /圖類(lèi)型/=建立圖的鄰接表=void 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

20、n;i+) /建立邊表 scanf(%c,&a);G-adjlisti.vertex=a; /讀入頂點(diǎn)信息G-adjlisti.firstedge=NULL; /邊表置為空表 printf(Input edges,Creat Adjacency Listn); for(k=0;ke;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)為js-next=G-adjlisti.firstedge;G-adjlisti.firsted

21、ge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /鄰接點(diǎn)序號(hào)為is-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(ALGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索給出你的編碼 /=BFS：廣度優(yōu)先遍歷=void BF