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

2、示表中所有的數(shù)據(jù)。程序代碼:#in clude<stdio.h> #in clude<malloc.h>#defi ne OK 1#defi ne ERROR 0 #defi ne OVERFLOW -2#defi ne LIST_INIT_SIZE 100#defi ne LISTINCREMENT 10typ edef structint* elem;int len gth;int listsize;Sqlist;int In itList_Sq(Sqlist & L)L.elem=(i nt*)malloc(LIST_INIT_SIZE*sizeof(i

3、nt); if(!L.elem) return -1;L.le ngth=0;L.listsize=LIST_INIT_SIZE;return OK;int ListI nsert_Sq(Sqlist&L,i nt i,i nt e)if(i<1|i>L.le ngth+1) return ERROR;if(L.le ngth=L.listsize)int *n ewbase;newbase=(i nt*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(i nt); if(!n ewbase) retur n -1;L.el

4、em=n ewbase;L.listsize+=LISTINCREMENT;int *p ,*q;q=&(L.elemi-1);for(p=&(L.elemL.le ngth-1) ;p>=q;-p)*( p+1)=* p；*q=e;+L.le ngth;return OK;int ListDelete_Sq(Sqlist & L,i nt i,i nt e)int *p ,*q;if(i<1|i>L.le ngth)return ERROR;p=&(L.elemi-1);e=* p;q=L.elem+L .len gth-1;for(+p;p

5、 <=q;+p)*(p-1)=* p;-L .len gth;return OK;int mai n()Sqlist L;InitList_Sq(L);/ 初始化int i,a=3,-5,6,8,2,-5,4,7,-9;for(i=1;i<10;i+)ListI nsert_Sq(L,i,ai-1);for(i=0;i<9;i+)prin tf(" %d",L.elemi);printf("n");/ 插入 9個數(shù)ListI nsert_Sq(L,3,24);for(i=0;i<10;i+)prin tf(" %d&qu

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

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

8、相應(yīng)的結(jié)點(diǎn)并刪除。5、修改程序：（1）增加插入結(jié)點(diǎn)的功能。（2）建立鏈表的方法有 前插” 后插”法。程序代碼：#in clude<stdio.h>#in clude<malloc.h>#defi ne NULL 0#defi ne OK 1#defi ne ERROR 0typ edef struct LNodeint data;struct LNode *n ext;LNode,*L in kList;int In itList_L(Li nkList & L)L=(Li nkList)malloc(sizeof(LNode);L-> next=NULL

9、;return OK;int ListI nsert_L(Li nkList & L,i nt i,i nt e)Lin kList p,s;int j;p=L；j=O;while( p&&j<i-1) p=p->n ext;+j;if(! p|j>i-1)return ERROR;s=(L in kList)malloc(sizeof(LNode); s->data=e;s->n ext =p->n ext;p->n ext=s;return OK;int ListDelete_L(Li nkList&L,int i,

10、i nt & e)Lin kList p,q;int j;p=L;j=0;while( p-> next&&j<i-1) p=p->n ext;+j;if(!( p-> next)|j<i-1) return ERROR;q=p->n ext ;p->n ext=q->n ext; e=q->data;free(q);return OK;int mai n()Lin kList L,p;char a8='A',C,'E','F','H','J&#

11、39;,Q,'U' int i,j;In itList_L(L); for(i=1,j=0;i<=8,j<8;i+,j+) ListI nsert_L(L,i,aj);p=L->n ext;while( p!=NULL)prin tf("%ct", p->data); p=p->n ext;/插入八個字符prin tf("n");i=2;int e;ListI nsert_L(L,i,'B'); p=L->n ext;while( p!=NULL)prin tf("%ct&qu

12、ot;, p->data); p=p->n ext;/插入一個字符prin tf("n");i=3;ListDelete_L(L,i,e); p=L->n ext;while( p!=NULL)prin tf("%ct", p->data); p=p->n ext;prin tf("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心得體會：單鏈表是通過掃描指針 P進(jìn)行單鏈表的操作；頭指針唯一標(biāo)識點(diǎn)鏈表的存在; 插入和刪除元

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

14、lude<stdlib.h>#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -2#defi ne N 100#defi ne STACK_INIT_SIZE #defi ne STACKINCREMENT typ edef structintint10010*base;*top;stacksize;/在棧構(gòu)造之前和銷毀之后，base的值為NULL棧頂指針/當(dāng)前已分配的存儲空間，以元素為單位int SqStack;int In itStack(SqStack &S) /

15、構(gòu)造一個空棧Sif(!(S.base=(i nt *)malloc(STACK_INIT_SIZE*sizeof(i nt) exit(OVERFLOW);/存儲分配失敗S.t op=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int StackE mp ty(SqStack S) /若棧S為空棧，則返回TRUE，否則返回FALSEif(S.to p=S.base)return TRUE;elsereturn FALSE;int P ush(SqStack & S, i nt e) /插入元素e為新的棧頂元素if(S.to p-S.base

16、>=S.stacksize)/ 棧滿，追加存儲空間S.base=(i nt *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(i nt);if(!S.base)exit(OVERFLOW); /存儲分配失敗S.t op=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.to p)+=e;return OK;int Pop (SqStack & S,i nt &e) II若棧不空，則刪除S的棧頂元素，用e返回其值，并返回 OK ;否則返回ERRORif(S.to p=

17、S.base)return ERROR;e=*-S.t op;return OK;int mai n()SqStack s;int i,e,j,k=1;char chN = 0,* p,bN = 0;if(I nitStack(s) /初始化棧成功printf("請輸入表達(dá)式:n");gets(ch);p=ch;while(* p) 沒到串尾Push(s,* P+);for(i=0;i<N;i+)if(!StackE mp ty(s) /棧不空Pop(s,e); /彈出棧頂元素bi=e;for(i=0;i<N;i+)if(chi!=bi)k=0;if(k=0)p

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

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

20、優(yōu)先遍歷）的操作。1 鄰接矩陣作為存儲結(jié)構(gòu)#i nclude"stdio.h"#i nclude"stdlib.h"/定義最大頂點(diǎn)數(shù)#defi ne MaxVertexNum 100typ edef structchar vexsMaxVertexNum;/ 頂點(diǎn)表int edgesMaxVertexNumMaxVertexNum;/ 鄰接矩陣，可看作邊表int n,e;圖中的頂點(diǎn)數(shù)n和邊數(shù)eMGra ph;/用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void CreatMGra ph(MGra ph *G)int i,j,k;char a;prin t

21、f("I np ut VertexNum( n) and EdgesNum(e):");sca nf("%d,%d",&G-> n,& G->e);/ 輸入頂點(diǎn)數(shù)和邊數(shù)sca nf("%c", &a);/讀入頂點(diǎn)信息，建立頂點(diǎn)表prin tf("I nput Vertex stri ng:"); for(i=0;i<G-> n;i+) sca nf("%c", &a); G->vexsi=a;for(i=0;i<G-> n

22、;i+)for(j=0;j<G-> n;j+)G->edgesij=0;/初始化鄰接矩陣prin tf("I nput edges,Creat Adjace ncy Matrix n");for(k=0;k<G->e;k+) /讀入e條邊，建立鄰接矩陣scanf("%d%d",&i,&j);/輸入邊(Vi , Vj)的頂點(diǎn)序號G->edgesij=1;G->edgesji=1; /若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句 /= 定義標(biāo)志向量，為全局變量 =typ edef enu m

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

24、(G); printf("Print Graph DFS:"); DFS(G); prin tf("n");printf("Print Graph BFS:");BFS(G,3);prin tf("n");/為圖G申請內(nèi)存空間/健立鄰接矩陣/深度優(yōu)先遍歷以序號為3的頂點(diǎn)開始廣度優(yōu)先遍歷定義最大頂點(diǎn)數(shù)邊表結(jié)點(diǎn)/鄰接點(diǎn)域鏈域2.鄰接鏈表作為存儲結(jié)構(gòu)#i nclude"stdio.h"#i nclude"stdlib.h"#defi ne MaxVertexNum 50 typ e

25、def struct no deint adjvex;struct node *n ext;EdgeNode;typ edef struct vno de char vertex; EdgeNode *firstedge;VertexNode;typ edef VertexNode AdjListMaxVertexNum; typ edef struct AdjList adjlist; int n,e; ALGra ph;頂點(diǎn)表結(jié)點(diǎn)/頂點(diǎn)域/邊表頭指針/AdjList是鄰接表類型/鄰接表/圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)/圖類型/=建立圖的鄰接表= void CreatALGra ph(ALGra ph

26、 *G) int i,j,k;char a;EdgeNode *s;/定義邊表結(jié)點(diǎn)prin tf("I np ut VertexNum( n) and EdgesNum(e):");sca nf("%d,%d",&G-> n,& G->e);/ 讀入頂點(diǎn)數(shù)和邊數(shù)sca nf("%c", &a);II建立邊表prin tf("I nput Vertex stri ng:");for(i=0;i<G-> n;i+)/讀入頂點(diǎn)信息/邊表置為空表scan f("%c

27、",&a);G->adjlisti.vertex=a;G->adjlisti.firstedge=NULL;prin tf("I nput edges,Creat Adjace ncy List n");for(k=0;k<G->e;k+) 建立邊表scanf("%d%d",&i,&j);讀入邊(Vi，Vj)的頂點(diǎn)對序號s=(EdgeNode *)malloc(sizeof(EdgeNode);/ 生成邊表結(jié)點(diǎn)s->adjvex=j;/鄰接點(diǎn)序號為js->n ext=G->adjlisti.firstedge;G->adjlisti.firstedge=s;將新結(jié)點(diǎn)*S插入頂點(diǎn) Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode);s->adjvex=i;/鄰接點(diǎn)序號為is->n ext=G->adjlistj.firstedge;G->adjlistj.firstedge=s;將新結(jié)點(diǎn)*S插入頂點(diǎn) Vj的邊表頭部 /= 定義標(biāo)志向量，為全局變量 =t