c數(shù)據(jù)結(jié)構(gòu)實驗報告[范本]

c數(shù)據(jù)結(jié)構(gòu)實驗報告數(shù)據(jù)結(jié)構(gòu)(C語言版)實驗報告;專業(yè)：計算機科學(xué)與技術(shù)、軟件工程;學(xué)號:_XX40703061_;班級:_軟件二班_;姓名:_朱海霞_;指導(dǎo)教師:_劉遵仁_;青島大學(xué)信息工程學(xué)院;XX年10月;實驗1;實驗題目：順序存儲結(jié)構(gòu)線性表的插入和刪除;實驗?zāi)?數(shù)據(jù)結(jié)構(gòu)(C語言版) 實驗報告 專業(yè)：計算機科學(xué)與技術(shù)、軟件工程 學(xué)號:_XX40703061_ 班級:_軟件二班_ 姓名:_朱海霞_ 指導(dǎo)教師:_劉遵仁_ 青島大學(xué)信息工程學(xué)院 XX年10月 實驗1 實驗題目：順序存儲結(jié)構(gòu)線性表的插入和刪除 實驗?zāi)康模?了解和掌握線性表的邏輯結(jié)構(gòu)和順序存儲結(jié)構(gòu)，掌握線性表的基本算法及相關(guān)的時間性能分析。 實驗要求： 建立一個數(shù)據(jù)域定義為整數(shù)類型的線性表，在表中允許有重復(fù)的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù)，先找到相應(yīng)的存儲單元，后刪除之。 實驗主要步驟： 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 #define LISTINCREMENT 10 typedef struct int* 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(,(+LISTINCREMENT)*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,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; 實驗結(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)簡單，邏輯上相鄰的元素在物理上也相鄰;不使用指針，節(jié)省存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續(xù)的存儲空間;插入元素可能發(fā)生溢出;自由區(qū)中的存儲空間不能被其他數(shù)據(jù)共享 實驗2 實驗題目：單鏈表的插入和刪除 實驗?zāi)康模?了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。 實驗要求： 建立一個數(shù)據(jù)域定義為字符類型的單鏈表，在鏈表中不允許有重復(fù)的字符;根據(jù)輸入的字符，先找到相應(yīng)的結(jié)點，后刪除之。 實驗主要步驟： 3、分析、理解給出的示例程序。 4、調(diào)試程序，并設(shè)計輸入數(shù)據(jù)(如：A，C，E，F(xiàn)，H，J，Q，M)，測試程序的如下功能：不允許重復(fù)字符的插入;根據(jù)輸入的字符，找到相應(yīng)的結(jié)點并刪除。 5、修改程序： (1) 增加插入結(jié)點的功能。 (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(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&j p=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; int ListDelete_L(LinkList&L,int i,int &e) LinkList p,q; int j; p=L;j=0; while(p-next&j p=p-next;+j; if(!(p-next)|j return ERROR; q=p-next;p-next=q-next; e=q-data;free(q); return OK; int main() LinkList L,p; char a=A,C,E,F,H,J,Q,U; int i,j; InitList_L(L); for(i=1,j=0;ip=L-next; while(p!=NULL) printf(%c ,p-data); p=p-next; /插入八個字符printf( ;實驗結(jié)果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會：;單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯;實驗3;實驗題目：棧操作設(shè)計和實現(xiàn);實驗?zāi)康模?1、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實;2、掌握棧的特點，即后進先出和先進先出的原則;3、掌握棧的基本運算，如：入棧與出棧 /插入八個字符 printf( ); i=2; int e; ListInsert_L(L,i,B); p=L-next; while(p!=NULL) printf(%c ,p-data); p=p-next; /插入一個字符 printf( ); i=3; ListDelete_L(L,i,e); p=L-next; while(p!=NULL) printf(%c ,p-data); p=p-next; printf( ); return 0; 實驗結(jié)果： A C E F H J Q U A B C E F H J Q U A B E F H J Q U 心得體會： 單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯一標(biāo)識點鏈表的存在;插入和刪除元素快捷，方便。 實驗3 實驗題目：棧操作設(shè)計和實現(xiàn) 實驗?zāi)康模?1、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實際中靈活應(yīng)用。 2、掌握棧的特點，即后進先出和先進先出的原則。 3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。 實驗要求： 回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如 “abba”是回文，而“abab”不是回文。 實驗主要步驟 (1)數(shù)據(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 struct int *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULL int *top; / 棧頂指針 int stacksize; / 當(dāng)前已分配的存儲空間，以元素為單位 SqStack; int InitStack(SqStack &S) / 構(gòu)造一個空棧S if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int) exit(OVERFLOW); / 存儲分配失敗 =; =STACK_INIT_SIZE; return OK; int StackEmpty(SqStack S) / 若棧S為空棧，則返回TRUE，否則返回FALSE if(=) return TRUE; else return FALSE; int Push(SqStack &S, 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 ch = 0,*p,b = 0; if(InitStack(s) / 初始化棧成功 printf(請輸入表達式: ); gets(ch); p=ch; while(*p) / 沒到串尾 Push(s,*p+); for(i=0;i if(!StackEmpty(s) / 棧不空 Pop(s,e); / 彈出棧頂元素 b=e; for(i=0;i if(ch!=b) k=0; if(k=0) printf(NO!); else printf(輸出:) printf(YES!); return 0; 實驗結(jié)果： 請輸入表達式： abcba 輸出：YES! 心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性質(zhì)，這個固有性質(zhì)使棧成為程序設(shè)計中的有用工具。 實驗4 實驗題目：二叉樹操作設(shè)計和實現(xiàn) 實驗?zāi)康模?掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。 實驗要求： 采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。 實驗主要步驟： 1、分析、理解程序。 2、調(diào)試程序，設(shè)計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(空指針)，如ABD#CE#F#，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點總數(shù)。 程序代碼: 實驗結(jié)果： 心得體會： 實驗5 實驗題目：圖的遍歷操作 實驗?zāi)康模?掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu);掌握DFS及BFS對圖的遍歷操作;了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。 實驗要求： 采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。 實驗主要步驟： 設(shè)計一個有向圖和一個無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)的操作。 1. 鄰接矩陣作為存儲結(jié)構(gòu) #include #include #define MaxVertexNum 100 /定義最大頂點數(shù) typedef struct char vexs; /頂點表 int edges; /鄰接矩陣，可看作邊表 int n,e; /圖中的頂點數(shù)n和邊數(shù)e MGraph; /用鄰接矩陣表示的圖的類型 /=建立鄰接矩陣= void CreatMGraph(MGraph *G) int 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;in;i+) scanf(%c,&a); G-vexs=a; /讀入頂點信息，建立頂點表 for(i=0;in;i+) for(j=0;jn;j+) G-edges=0; /初始化鄰接矩陣 printf(Input edges,Creat Adjacency Matrix ); for(k=0;ke;k+) /讀入e條邊，建立鄰接矩陣 scanf(%d%d,&i,&j); /輸入邊(Vi，Vj)的頂點序號 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)先遍歷的遞歸算法= 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); /為圖G申請內(nèi)存空間 CreatMGraph(G); /建立鄰接矩陣 printf(Print Graph DFS: ); DFS(G); /深度優(yōu)先遍歷 printf( ); printf(Print Graph BFS: ); BFS(G,3); /以序號為3的頂點開始廣度優(yōu)先遍歷 printf( ); 2. 鄰接鏈表作為存儲結(jié)構(gòu) #include #include #define MaxVertexNum 50 /定義最大頂點數(shù) typedef struct node /邊表結(jié)點 int adjvex; /鄰接點域 struct node *next; /鏈域 EdgeNode; typedef struct vnode /頂點表結(jié)點 char vertex; /頂點域 EdgeNode *firstedge; /邊表頭指針 VertexNode; typedef VertexNode AdjList; /AdjList是鄰接表類型 typedef struct AdjList adjlist; /鄰接表 int n,e; /圖中當(dāng)前頂點數(shù)和邊數(shù) ALGraph; /圖類型 /=建立圖的鄰接表= void 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;in;i+) /建立邊表 scanf(%c,&a); G-adjlist.vertex=a; /讀入頂點信息 G-adjlist.firstedge=NULL; /邊表置為空表 printf(Input edges,Creat Adjacency List ); for(k=0;ke;k+) /建立邊表 scanf(%d%d,&i,&j); /讀入邊(Vi，Vj)的頂點對序號 s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成邊表結(jié)點 s-adjvex=j; /鄰接點序號為j s-next=G-adjlist.firstedge; G-adjlist.firstedge=s; /將新結(jié)點*S插入頂點Vi的邊表頭部 s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /鄰接點序號為i s-next=G-adjlist.firstedge; G-adjlist.firstedge=s; /將新結(jié)點*S插入頂點Vj的邊表頭部 /=定義標(biāo)志向量，為全局變量= typedef enumFALSE,TRUE Boolean; Boolean visited; /=DFS：深度優(yōu)先遍歷的遞歸算法= void DFSM(ALGraph *G,int i) /以Vi為出發(fā)點對鄰接鏈表表示的圖