數(shù)據(jù)結(jié)構(gòu)(C語言版)實驗報告(二)

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

2、有的數(shù)據(jù)。程序代碼：#include<stdio.h>#include<malloc.h>#defineOK1#defineERROR0#defineOVERFLOW-2#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructint*elem;intlength;intlistsize;Sqlist;intInitList_Sq(Sqlist&L)L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem)return-1;L.length=0;

3、L.listsize=LIST_INIT_SIZE;returnOK;intListInsert_Sq(Sqlist&L,inti,inte)if(i<1|i>L.length+1)returnERROR;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;returnOK;intListDelete_Sq(Sqlist&L,inti,inte)int*p,*q;if(i<1|i>L.length)returnERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p<=q;+p)*(p-1)=*p;-L.length;returnOK;intmain()SqlistL;InitList_Sq(L);/初始化inti,a尸

5、3,-5,6,82-5,47-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",L.elemi);printf("n");插入一個數(shù)inte;ListDelete_Sq(L,2,e);for(i=0;i<9;i+)printf("%d"

6、,L.elemi);刪除一個數(shù)printf("n");return0;實驗結(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)是一種隨機存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快；結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也相鄰；不使用指針，節(jié)省存儲空間；但是插入和刪除元素需要移動大量元素，消耗大量時間；需要一個連續(xù)的存儲空間；插入元素可能發(fā)生溢出；自由區(qū)中的存儲空間不能被其他數(shù)據(jù)共享實驗2實驗題目：單鏈表的插入和刪除實驗目的：了解和掌握線性表的邏輯結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，掌握單鏈

7、表的基本算法及相關的時間性能分析。實驗要求：建立一個數(shù)據(jù)域定義為字符類型的單鏈表，在鏈表中不允許有重復的字符；根據(jù)輸入的字符，先找到相應的結(jié)點，后刪除之。實驗主要步驟：3、分析、理解給出的示例程序。4、調(diào)試程序，并設計輸入數(shù)據(jù)(如：A,C,E,F,H,J,Q,M),測試程序的如下功能：不允許重復字符的插入；根據(jù)輸入的字符，找到相應的結(jié)點并刪除。5、修改程序：(1) 增加插入結(jié)點的功能。(2) 建立鏈表的方法有前插“、后插”法。程序代碼：#include<stdio.h>#include<malloc.h># defineNULL0# defineOK1# defineE

8、RROR0typedefstructLNodeintdata;structLNode*next;LNode,*LinkList;intInitList_L(LinkList&L)L=(LinkList)malloc(sizeof(LNode);L->next=NULL;returnOK;intListInsert_L(LinkList&L,inti,inte)LinkListp,s;intj;p=L;j=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)returnERROR;s=(LinkList)ma

9、lloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;returnOK;intListDelete_L(LinkList&L,inti,int&e)LinkListp,q;intj;p=L;j=0;while(p->next&&j<i-1)p=p->next;+j;if(!(p->next)|j<i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK

10、;intmain()LinkListL,p;chara8='A','C',E,'F','H','J','Q','U'inti,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;inte

11、;ListInsert_L(L,i,'B');p=L->next;while(p!=NULL)printf("%ct",p->data);p=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");return0;實驗結(jié)果：ACEFHJQUABCEFHJQUABEFHJQU心得體會：單鏈

12、表是通過掃描指針P進行單鏈表的操作；頭指針唯一標識點鏈表的存在;插入和刪除元素快捷，方便。實驗3實驗題目：棧操作設計和實現(xiàn)實驗目的：1、掌握棧的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，以便在實際中靈活應用。2、掌握棧的特點，即后進先出和先進先出的原則。3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。實驗要求：回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如“abbOI回文，而"abab是回文。實驗主要步驟(1)數(shù)據(jù)從鍵盤讀入；(2)輸出要判斷的字符串；(3)利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“Yes'；否

13、則輸出“No：程序代碼：#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#define OVERFLOW -2#define N 100#define STACK_INIT_SIZE#define STACKINCREMENTtypedef structint *base;int *top;intstacksize; SqStack;int InitStack(SqStack &S) /構(gòu)造一個空棧S#defineERROR010010/在棧構(gòu)造之前和銷毀之后，base的

14、值為NULL/棧頂指針/當前已分配的存儲空間，以元素為單位if(!(S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)exit(OVERFLOW);/存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;intStackEmpty(SqStackS)/若棧S為空棧，則返回TRUE,否則返回FALSEif(S.top=S.base)returnTRUE;elsereturnFALSE;intPush(SqStack&S,inte)/插入元素e為新的棧頂元素if(S.top-S.base&

15、gt;=S.stacksize)/棧滿，追加存儲空間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;returnOK;intPop(SqStack&S,int&e)/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERRORif(S.top=S.base)returnERROR;e

16、=*-S.top;returnOK;intmain()SqStacks;inti,e,j,k=1;charchN=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("NO!");elseprintf("輸出

17、：")printf("YES!");return0;實驗結(jié)果：請輸入表達式：abcba輸出：YES!心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性質(zhì)，這個固有性質(zhì)使棧成為程序設計中的有用工具。實驗4實驗題目：二叉樹操作設計和實現(xiàn)實驗目的：掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。實驗要求：采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。實驗主要步驟：1、分析、理解程序。2、調(diào)試程序，設計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(空指針)，如ABD#CE#F#,建

18、立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點總數(shù)。程序代碼：實驗結(jié)果:心得體會:實驗5實驗題目：圖的遍歷操作實驗目的：掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS及BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領域的廣泛應用。實驗要求：采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。實驗主要步驟：設計一個有向圖和一個無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)的操作。1 .鄰接矩陣作為存儲結(jié)構(gòu)#include"stdio.h"#inclu

19、de"stdlib.h"#defineMaxVertexNum100定義最大頂點數(shù)typedefstructcharvexsMaxVertexNum;頂點表intedgesMaxVertexNumMaxVertexNum;鄰接矩陣，可看作邊表intn,e;圖中的頂點數(shù)n和邊數(shù)eMGraph;用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=voidCreatMGraph(MGraph*G)inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d”,&G->

20、n,&G->e);輸入頂點數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i+)scanf("%c",&a);G->vexsi=a;讀入頂點信息，建立頂點表for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0;初始化鄰接矩陣printf("Inputedges,CreatAdjacencyMatrixn");for(k

21、=0;k<G->e;k+)讀入e條邊，建立鄰接矩陣scanf("%d%d",&i,&j);輸入邊(Vi,Vj)的頂點序號G->edgesij=1;G->edgesji=1;/若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句/=定義標志向量，為全局變量=typedefenumFALSE,TRUEBoolean;BooleanvisitedMaxVertexNum;/=DFS:深度優(yōu)先遍歷的遞歸算法=voidDFSM(MGraph*G,inti)以Vi為出發(fā)點對鄰接矩陣表示的圖G進彳TDFS搜索，鄰接矩陣是0,1矩陣給出你的編碼/=

22、BFS:廣度優(yōu)先遍歷=voidBFS(MGraph*G,intk)以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索給出你的編碼/=主程序main=voidmain()inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph);為圖G申請內(nèi)存空間CreatMGraph(G);/犍立鄰接矩陣printf("PrintGraphDFS:");DFS(G);深度優(yōu)先遍歷printf("n");printf("PrintGraphBFS:");BFS(G,3);以序號為3的頂點開始廣度優(yōu)先遍歷printf(&

23、quot;n");2 .鄰接鏈表作為存儲結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50定義最大頂點數(shù)typedefstructnode邊表結(jié)點intadjvex;鄰接點域structnode*next;鏈域EdgeNode;typedefstructvnode頂點表結(jié)點charvertex;頂點域EdgeNode*firstedge;邊表頭指針VertexNode;typedefVertexNodeAdjListMaxVertexNum;/AdjList是鄰接表類型typed

24、efstructAdjListadjlist;鄰接表intn,e;圖中當前頂點數(shù)和邊數(shù)ALGraph;圖類型/=建立圖的鄰接表=voidCreatALGraph(ALGraph*G)inti,j,k;chara;EdgeNode*s;定義邊表結(jié)點printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d”,&G->n,&G->e);讀入頂點數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");fo

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