大數(shù)據(jù)結構實驗報告材料

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

2、單元并刪除，顯示表中所有的數(shù)據(jù)。程序代碼:#include#include#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;L.listsize=LIST_INIT_SIZ

3、E;returnOK;intListInsert_Sq(Sqlist&L,inti,inte)if(iL.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.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+

4、1)=*p;*q=e;+L.length;returnOK;intListDelete_Sq(Sqlist&L,inti,inte)int*p,*q;if(iL.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=3,-5,6,8,2,-5,4,7,-9;for(i=1;i10;i+)ListInsert_Sq(L,i,ai-1);for(i=0;i9;i+)

5、printf(%d”,L.elemi);printf(n);/插入9個數(shù)ListInsert_Sq(L,3,24);for(i=0;i10;i+)printf(%d,L.elemi);printf(n);/插入一個數(shù)inte;ListDelete_Sq(L,2,e);for(i=0;i9;i+)printf(%d,L.elemi);/刪除一個數(shù)printf(n);return0;實驗結果：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心得體會：順序存儲結構是一種隨機存取結構，存取任何元素的時間是一個常數(shù)，速度快；結

6、構簡單，邏輯上相鄰的元素在物理上也相鄰；不使用指針，節(jié)省存儲空間；但是插入和刪除元素需要移動大量元素，消耗大量時間；需要一個連續(xù)的存儲空間；插入元素可能發(fā)生溢出；自由區(qū)中的存儲空間不能被其他數(shù)據(jù)共享實驗2實驗題目:單鏈表的插入和刪除實驗目的：了解和掌握線性表的邏輯結構和鏈式存儲結構，掌握單鏈表的基本算法及相關的時間性能分析。實驗要求：建立一個數(shù)據(jù)域定義為字符類型的單鏈表，在鏈表中不允許有重復的字符；根據(jù)輸入的字符，先找到相應的結點，后刪除之。實驗主要步驟：3、分析、理解給出的示例程序。4、調試程序，并設計輸入數(shù)據(jù)(如：A,C,E,F,H,J,Q,M,測試程序的如下功能：不允許重復字符的插入；根

7、據(jù)輸入的字符，找到相應的結點并刪除。5、修改程序：(1) 增加插入結點的功能。(2) 建立鏈表的方法有“前插”、“后插”法。程序代碼:#include#include#defineNULL0#defineOK1#defineERROR0typedefstructLNodeintdata;structLNode*next;LNode,*LinkList;intInitList_L(LinkList&L)(L=(LinkList)malloc(sizeof(LNode);L-next=NULL;returnOK;intListInsert_L(LinkList&L,inti,inte)(LinkL

8、istp,s;intj;p=L;j=0;while(p&jnext;+j;if(!p|ji-1)returnERROR;s=(LinkList)malloc(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&jnext;+j;if(!(p-next)|jnext;p-next=q-next;e=q-data;free(q);returnOK;intmain()LinkListL,p;c

9、hara8=A,C,E,F,H,J,Q,U;inti,j;InitList_L(L);for(i=1,j=0;i=8,jnext;while(p!=NULL)printf(%ct”,p-data);p=p-next;/插入八個字符printf(n);i=2;inte;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

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

11、 輸出要判斷的字符串；(3) 利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。程序代碼:#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2#defineN100#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstructint*base;/在棧構造之前和銷毀之后，base的值為NULLint*top;/棧頂指針intstacksize;/當前已分配的存儲空間，以兀素為單位SqStac

12、k;intInitStack(SqStack&S)/構造一個空棧Sif(!(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=S

13、.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)(/若棧不空，貝U刪除S的棧頂元素，用e返回其值，并返回OK否則返回ERRORif(S.top=S.base)returnERROR;e=*-S.top;re

14、turnOK;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;iN;i+)if(!StackEmpty(s)/棧不空Pop(s,e);/彈出棧頂元素bi=e;for(i=0;in,&G-e);/輸入頂點數(shù)和邊數(shù)scanf(%c”,&a);printf(InputVertexstring:);for(i=0;in;i+)scanf(%c,&a);G-vexsi=a;/讀入頂

15、點信息，建立頂點表for(i=0;in;i+)for(j=0;jn;j+)G-edgesi田=0;/初始化鄰接矩陣printf(Inputedges,CreatAdjacencyMatrixn);for(k=0;ke;k+)/讀入e條邊，建立鄰接矩陣scanf(%d%d”,&i,&j);/輸入邊(Vi,Vj)的頂點序號G-edgesij=1;去掉該條語句0,1矩陣G-edgesji=1;/若為無向圖，矩陣為對稱矩陣；若建立有向圖,/=定義標志向量，為全局變量=typedefenumFALSE,TRUEBoolean;BooleanvisitedMaxVertexNum;/=DFS:深度優(yōu)先遍歷

16、的遞歸算法=voidDFSM(MGraph*G,inti)/以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是給出你的編碼/=BFS:廣度優(yōu)先遍歷=voidBFS(MGraph*G,intk)/以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索給出你的編碼/=主程序main=voidmain()inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph);/為圖G申請內存空間CreatMGraph(G);/建立鄰接矩陣printf(PrintGraphDFS:);DFS(G);/深度優(yōu)先遍歷printf(n);printf(PrintGraphBFS:

17、);BFS(G,3);/以序號為3的頂點開始廣度優(yōu)先遍歷printf(n);鄰接鏈表作為存儲結構#includestdio.h#includestdlib.h#defineMaxVertexNum50typedefstructnode/intadjvex;/structnode*next;/EdgeNode;/定義最大頂點數(shù)邊表結點鄰接點域鏈域typedefstructvnode(/頂點表結點charvertex;/頂點域EdgeNode*firstedge;/邊表頭指針VertexNode;是鄰接表類型typedefVertexNodeAdjListMaxVertexNum;/AdjList

18、鄰接表圖中當前頂點數(shù)和邊數(shù)圖類型typedefstruct(AdjListadjlist;/intn,e;/ALGraph;/=建立圖的鄰接表voidCreatALGraph(ALGraph*G)(inti,j,k;chara;EdgeNode*s;/定義邊表結點printf(InputVertexNum(n)andEdgesNum(e):);scanf(%d,%d”,&G-n,&G-e);/讀入頂點數(shù)和邊數(shù)scanf(%c”,&a);printf(InputVertexstring:);for(i=0;in;i+)/建立邊表(scanf(%c,&a);G-adjlisti.vertex=a;

19、/讀入頂點信息G-adjlisti.firstedge=NULL;/邊表置為空表printf(Inputedges,CreatAdjacencyListn);for(k=0;ke;k+)/建立邊表scanf(%d%d,&i,&j);/讀入邊(Vi,Vj)的頂點對序號s=(EdgeNode*)malloc(sizeof(EdgeNode);/生成邊表結點s-adjvex=j;/鄰接點序號為js-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;/將新結點*S插入頂點Vi的邊表頭部s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;/鄰接點序號為is-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s;/將新結點*S插入頂點Vj的邊表頭部/=定義標志向量，為全局變量=typedefenumFALSE,TRUEBoolean;BooleanvisitedMaxVertexNum;/=DFS:深度優(yōu)先遍歷的遞歸算法=voidDFSM(ALGraph*G,inti)/以Vi為出發(fā)點對鄰接鏈表表示的圖G進行DFS搜索給出你的編碼/=BFS:廣度優(yōu)先遍歷=voidBFS(ALGrap