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

數(shù)據(jù)結(jié)構(gòu)(C語言版)實驗報告專業(yè)：計算機科學(xué)與技術(shù)學(xué)號:_______________________班級:_______________________姓名:_______________________指導(dǎo)教師:___________________青島大學(xué)信息工程學(xué)院2014年10月1/1文檔可自由編輯實驗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、調(diào)試程序，并設(shè)計輸入一組數(shù)據(jù)（3，-5，6，8，2，-5，4，7，-9），如下功能：根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲單元并刪除，顯示表中所有的數(shù)據(jù)。2、測試程序的程序代碼:#include<stdio.h>#include<malloc.h>#include<stdlib.h>#defineOK1#defineERROR01/1文檔可自由編輯#defineOVERFLOW-2#defineLIST_INIT_SIZE100typedefintstatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}sqlist;statusinitlist_sq(sqlist&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//initList.sqstatusgetelem_sq(sqlist&L){inti=0,e,d;printf("pleaseinputhowmanynumberyouwanttoinit\n");1/1文檔可自由編輯scanf("%d",&d);printf("pleaseinputthenumberyouwanttoinit\n");while(1){scanf("%d",&e);L.elem[i]=e;L.length++;i++;if(i>=d)break;}returnOK;}statuslistdelet_sq(sqlist&L){inti=0,e;int*p;int*q;printf("pleaseinputthenumberyouwanttodelete\n");scanf("%d",&e);for(i=0;i<L.length;i++){if(L.elem[i]==e)1/1文檔可自由編輯{p=&L.elem[i];q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;break;}}returnOK;}main(){inti=0;sqlistL;initlist_sq(L);getelem_sq(L);listdelet_sq(L);while(i<L.length){printf("%4d",L.elem[i]);i++;1/1文檔可自由編輯}}實驗結(jié)果：心得體會：經(jīng)過這次了解和掌握了線性表的邏輯結(jié)構(gòu)和順序存儲結(jié)構(gòu)，明白了線性表的基本算法。1/1文檔可自由編輯實驗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）程序代碼:1/1文檔可自由編輯實驗結(jié)果：心得體會：1/1文檔可自由編輯實驗3實驗題目：棧操作設(shè)計和實現(xiàn)實驗?zāi)康模?、掌握棧的順序存儲結(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”。程序代碼:實驗結(jié)果：1/1文檔可自由編輯心得體會：1/1文檔可自由編輯實驗4實驗題目：二叉樹操作設(shè)計和實現(xiàn)實驗?zāi)康模赫莆斩鏄涞亩x、性質(zhì)及存儲方式，各種遍歷算法。實驗要求：采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。實驗主要步驟：1、分析、理解程序。調(diào)試程序，設(shè)計一棵二叉樹，輸入完全二叉樹的先序序列，用#2、代表虛結(jié)點（空指針），如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點總數(shù)。程序代碼:實驗結(jié)果：1/1文檔可自由編輯心得體會：1/1文檔可自由編輯實驗5實驗題目：圖的遍歷操作實驗?zāi)康模赫莆沼邢驁D和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(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)先遍歷）的操作。鄰接矩陣作為存儲結(jié)構(gòu)1．#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100typedefstruct{//定義最大頂點數(shù)charvexs[MaxVertexNum];//頂點表intedges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表1/1文檔可自由編輯intn,e;//圖中的頂點數(shù)n和邊數(shù)e}MGraph;//用鄰接矩陣表示的圖的類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);scanf("%c",&a);//輸入頂點數(shù)和邊數(shù)printf("InputVertexstring:");for(i=0;i<G->n;i++){scanf("%c",&a);G->vexs[i]=a;//讀入頂點信息，建立頂點表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;//初始化鄰接矩陣printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){//讀入e條邊，建立鄰接矩陣scanf("%d%d",&i,&j);//輸入邊（Vi，Vj）的頂點序號1/1文檔可自由編輯G->edges[i][j]=1;G->edges[j][i]=1;//若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(MGraph*G,inti){//以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣給出你的編碼//===========BFS：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){//以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索給出你的編碼//==========主程序main=====voidmain(){1/1文檔可自由編輯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("\n");2．鄰接鏈表作為存儲結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定義最大頂點數(shù)typedefstructnode{//邊表結(jié)點intadjvex;structnode*next;//鏈域//鄰接點域}EdgeNode;typedefstructvnode{//頂點表結(jié)點1/1文檔可自由編輯charvertex;//頂點域EdgeNode*firstedge;//邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];是鄰接表類型//AdjListtypedefstruct{AdjListadjlist;//鄰接表intn,e;}ALGraph;//圖中當(dāng)前頂點數(shù)和邊數(shù)//圖類型//=========建立圖的鄰接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s;//定義邊表結(jié)點printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);scanf("%c",&a);//讀入頂點數(shù)和邊數(shù)printf("InputVertexstring:");for(i=0;i<G->n;i++)//建立邊表{scanf("%c",&a);1/1文檔可自由編輯G->adjlist[i].vertex=a;//讀入頂點信息G->adjlist[i].firstedge=NULL;//邊表置為空表}printf("Inputedges,CreatAdjacencyList\n");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->adjlist[i].firstedge;G->adjlist[i].firstedge=s;//將新結(jié)點*S插入頂點Vi的邊表頭部s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i;//鄰接點序號為is->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;//將新結(jié)點*S插入頂點Vj的邊表頭部}}//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;1/1文檔可自由編輯Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(ALGraph*G,inti){//以Vi為出發(fā)點對鄰接鏈表表示的圖G進行DFS搜索給出你的編碼//==========BFS：廣度優(yōu)先遍歷=========voidBFS(ALGraph*G,intk){//以Vk為源點對用鄰接鏈表表示的圖G進行廣度優(yōu)先搜索給出你的編碼//==========主函數(shù)===========voidmain(){inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);printf("PrintGraphDFS:");DFS(G);