c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告

1、c 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告數(shù)據(jù)結(jié)構(gòu) (C 語言版 ) 實(shí)驗(yàn)報告 ; 專業(yè)：計算機(jī)科學(xué)與技術(shù)、軟件工程; 學(xué)號 :_XX40703061_; 班級 :_ 軟件二班 _; 姓名 :_ 朱海霞 _; 指導(dǎo)教師:_ 劉遵仁 _; 青島大學(xué)信息工程學(xué)院;XX 年10 月 ; 實(shí)驗(yàn) 1; 實(shí)驗(yàn)題目：順序存儲結(jié)構(gòu)線性表的插入和刪除;實(shí)驗(yàn)?zāi)繑?shù)據(jù)結(jié)構(gòu) (C 語言版 )實(shí)驗(yàn)報告專業(yè)：計算機(jī)科學(xué)與技術(shù)、軟件工程學(xué)號 :_XX40703061_班級 :_ 軟件二班 _姓名 :_ 朱海霞 _指導(dǎo)教師 :_ 劉遵仁 _青島大學(xué)信息工程學(xué)院XX 年10月實(shí)驗(yàn) 1實(shí)驗(yàn)題目：順序存儲結(jié)構(gòu)線性表的插入和刪除實(shí)驗(yàn)?zāi)康模毫私夂驼莆站€性表的

2、邏輯結(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è)計輸入一組數(shù)據(jù)(3 ，-5 ，6，8，2，-5 ， 4， 7， -9) ，測試程序的如下功能：根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲單元并刪除，顯示表中所有的數(shù)據(jù)。程序代碼 :#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#de

3、fine LISTINCREMENT 10typedef structint* elem;int length;int listsize;Sqlist;int InitList_Sq(Sqlist &L) =(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!) return -1;=0;=LIST_INIT_SIZE;return OK;int ListInsert_Sq(Sqlist&L,int i,int e)if(i+1) return ERROR;if(=)int *newbase;newbase=(int*)realloc(,(+LISTINCR

4、EMENT)*sizeof(int);if(!newbase) return -1;=newbase;+=LISTINCREMENT;int *p,*q;q=&();for(p=&();p=q;-p)*(p+1)=*p;*q=e;+;return OK;int ListDelete_Sq(Sqlist &L,int i,int e)int *p,*q;if(i)return ERROR;p=&();e=*p;q=+;for(+p;p*(p-1)=*p;-;return OK;int main()Sqlist L;InitList_Sq(L);/初始化int i,a=3,-5,6,8,2,-5,

5、4,7,-9;for(i=1;iListInsert_Sq(L,i,a);for(i=0;iprintf( %d,);printf( );/插入 9 個數(shù)ListInsert_Sq(L,3,24);for(i=0;iprintf( %d,);printf( );/插入一個數(shù)int e;ListDelete_Sq(L,2, e);for(i=0;iprintf( %d,);/刪除一個數(shù)printf( );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)是一種

6、隨機(jī)存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快 ; 結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也相鄰 ; 不使用指針，節(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è)計輸入數(shù)

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

8、LNode); L-next=NULL; return OK;intListInsert_L(LinkList&L,inti,inte) LinkList p,s;int j;p=L;j=0;while(p&jp=p-next;+j;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode); s-data=e;s-next=p-next;p-next=s;return OK;intListDelete_L(LinkList&L,inti,int&e) LinkList p,q;int j;p=L;j=0;while(p-next&jp=p

9、-next;+j;if(!(p-next)|jreturn ERROR;q=p-next;p-next=q-next; e=q-data;free(q);return OK;int main()LinkList L,p;chara=A,C,E,F,H,J,Q,U;inti,j;InitList_L(L);for(i=1,j=0;ip=L-next;while(p!=NULL)printf(%c ,p-data); p=p-next;/插入 八個 字符printf(;實(shí)驗(yàn) 結(jié)果： ;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會： ; 單鏈表是通過掃描指針P進(jìn)行單鏈表的操作;

10、頭指針唯 ; 實(shí)驗(yàn) 3; 實(shí)驗(yàn)題目：棧操作設(shè)計和實(shí)現(xiàn); 實(shí)驗(yàn)?zāi)康模?;1 、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實(shí);2 、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則;3 、掌握棧的基本運(yùn)算，如：入棧與出棧/插 入 八 個 字 符printf(ListInsert_L(L,i,B);while(p!=NULL)printf(%c,p-data););i=2;inte;p=L-next;p=p-next;/插入一個字符printf( ); i=3; ListDelete_L(L,i,e);p=L-next; while(p!=NULL) printf(%c ,p-data); p=p-next

11、; printf( ); return 0;實(shí)驗(yàn)結(jié)果：ACEFHJQUABCEFHJQUABEFHJQU心得體會：單鏈表是通過掃描指針P 進(jìn)行單鏈表的操作; 頭指針唯一標(biāo)識點(diǎn)鏈表的存在; 插入和刪除元素快捷，方便。實(shí)驗(yàn) 3實(shí)驗(yàn)題目：棧操作設(shè)計和實(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ù)

12、據(jù)從鍵盤讀入 ;(2) 輸出要判斷的字符串 ;(3) 利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“ Yes”，否則輸出“ No”。程序代碼 : #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define N 100#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef structint *base; /在棧構(gòu)造之前和銷毀之后，base 的值為NULL int

13、*top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲空間，以元素為單位 SqStack;int InitStack(SqStack &S) /構(gòu)造一個空棧Sif(!(=(int*)malloc(STACK_INIT_SIZE*sizeof(int) exit(OVERFLOW); / 存儲分配失敗=;=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack S) / 若棧 S 為空棧，則返回 TRUE，否則返回 FALSE if(=)return TRUE; elsereturn FALSE;int Push(SqStack &S,

14、int e) / 插入元素 e 為新的棧頂元素if(=) /棧滿，追加存儲空間=(int *)realloc(,(+STACKINCREMENT)*sizeof(int);if(!)exit(OVERFLOW); /存儲分配失敗=+;+=STACKINCREMENT;*()+=e;return OK;int Pop(SqStack &S,int &e) / 若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，并返回 OK;否則返回 ERROR if(=)return ERROR; e=*-;return OK;int main() SqStack s; int i,e,j,k=1;char c

15、h = 0,*p,b = 0;if(InitStack(s) /初始化棧成功printf(請輸入表達(dá)式 : );gets(ch);p=ch;while(*p) /沒到串尾Push(s,*p+);for(i=0;iif(!StackEmpty(s) /棧不空Pop(s,e); /彈出棧頂元素b=e;for(i=0;iif(ch!=b)k=0;if(k=0)printf(NO!);elseprintf(輸出 :)printf(YES!);return 0;實(shí)驗(yàn)結(jié)果：請輸入表達(dá)式：abcba輸出： YES!心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進(jìn)后出的性質(zhì)，這個固有性質(zhì)使棧成為程

16、序設(shè)計中的有用工具。實(shí)驗(yàn) 4實(shí)驗(yàn)題目：二叉樹操作設(shè)計和實(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)試程序，設(shè)計一棵二叉樹，輸入完全二叉樹的先序序列，用 #代表虛結(jié)點(diǎn) ( 空指針 ) ，如 ABD#CE#F#，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。程序代碼 :實(shí)驗(yàn)結(jié)果：心得體會：實(shí)驗(yàn) 5實(shí)驗(yàn)題目：圖的遍歷操作實(shí)驗(yàn)?zāi)康模赫莆沼邢驁D和無向圖的概念 ; 掌握鄰接矩陣和鄰接鏈表建立圖的存儲

17、結(jié)構(gòu) ; 掌握 DFS及 BFS對圖的遍歷操作 ; 了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。實(shí)驗(yàn)要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的 DFS和 BFS操作。實(shí)驗(yàn)主要步驟：設(shè)計一個有向圖和一個無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的 DFS(深度優(yōu)先遍歷 ) 和 BFS(廣度優(yōu)先遍歷 ) 的操作。1. 鄰接矩陣作為存儲結(jié)構(gòu)#include#include#define MaxVertexNum 100 /定義最大頂點(diǎn)數(shù)typedef structchar vexs; /頂點(diǎn)表int edges; /鄰接矩陣，可看作邊表int n,e; /圖中的頂點(diǎn)數(shù)n 和

18、邊數(shù) eMGraph; /用鄰接矩陣表示的圖的類型/= 建立鄰接矩陣 =void CreatMGraph(MGraph *G)int 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;in;i+)scanf(%c,&a);G-vexs=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表for(i=0;in;i+)for(j=0;jn;j+)G-edges=0; /初始化鄰接矩陣pri

19、ntf(Input edges,Creat Adjacency Matrix );for(k=0;ke;k+) /讀入e 條邊，建立鄰接矩陣scanf(%d%d,&i,&j); /輸入邊(Vi，Vj)的頂點(diǎn)序號G-edges=1;G-edges=1;/若 為;/=定 義標(biāo)志向量，為全局變量=;typedefenumFALSE,TRUEB;Booleanvisited=1;G-edges=1; /若為無向圖，矩陣為對稱矩陣; 若建立有向圖，去掉該條語句/= 定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visited;/=DFS：深度優(yōu)先

20、遍歷的遞歸算法=void DFSM(MGraph *G,int i) /以 Vi 為出發(fā)點(diǎn)對鄰接矩陣表示的圖G進(jìn)行 DFS搜索，鄰接矩陣是0，1 矩陣給出你的編碼/=BFS：廣度優(yōu)先遍歷=void BFS(MGraph *G,int k) /以 Vk 為源點(diǎn)對用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索給出你的編碼/= 主程序 main =void main()int i;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph); /為圖 G 申請內(nèi)存空間CreatMGraph(G); /建立鄰接矩陣printf(Print Graph DFS: );DFS(G); /深

21、度優(yōu)先遍歷printf( );printf(Print Graph BFS: );BFS(G,3); / 以序號為 3 的頂點(diǎn)開始廣度優(yōu)先遍歷 printf( );2. 鄰接鏈表作為存儲結(jié)構(gòu)#include#include#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;ty

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

23、+) /建立邊表scanf(%c,&a);G-adjlist.vertex=a; /讀入頂點(diǎn)信息G-adjlist.firstedge=NULL; /邊表置為空表printf(Input edges,Creat Adjacency List );for(k=0;ke;k+) /建立邊表scanf(%d%d,&i,&j); /讀入邊 (Vi ，Vj) 的頂點(diǎn)對序號s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成邊表結(jié)點(diǎn)s-adjvex=j; /鄰接點(diǎn)序號為js-next=G-adjlist.firstedge;G-adjlist.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode);s-adjvex=i; /鄰接點(diǎn)序號為is-next=G-adjlist.firstedge;G-adjlist.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部/= 定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visited;/=DFS：深度優(yōu)先遍歷的遞歸算法=v