數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）實(shí)驗(yàn)報(bào)告專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程學(xué)號(hào):班級(jí):軟件二班姓名:朱海霞指導(dǎo)教師:—?jiǎng)⒆袢是鄭u大學(xué)信息工程學(xué)院2023年10月bba”是回文,而“abab”不是回文。實(shí)驗(yàn)重要環(huán)節(jié)(1)數(shù)據(jù)從鍵盤(pán)讀入；(2)輸出要判斷的字符串；⑶運(yùn)用棧的基本操作對(duì)給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“N0”。程序代碼：include<stdio.h>include<stdlib.h>defineTRUE1#defineFALSE0#defineOKIdefineERROR0deHneOVERFLOW-2deflneN100#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT。10typedefstruct{int*base;g"/在棧構(gòu)造之前和銷(xiāo)毀之后,base的值為NULLint*top；go〃棧頂指針intg，stacksize;。//當(dāng)前已分派的存儲(chǔ)空間，以元素為單位}SqStack;intInitStack(SqStack&S){//構(gòu)造一個(gè)空棧Sif(!(S.basc=(int*)ma1loc(STACK_INIT_SIZE*sizeof(int))))exit(OVERFLOW);//存儲(chǔ)分派失敗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){//插入元素c為新的棧頂元素if(S.top-S.base>=S.stacksize)//棧滿(mǎn),追加存儲(chǔ)空間(S.base=(int*)rea1loc(S.base,(S.stacksize+STACKINCREMENT)*sieof(int));if(!S.base)exit(OVERFLOW)；//存儲(chǔ)分派失敗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=*--S.top;returnOK；}intmain(){SqStacks;inti,ej,k=l；charch[N]={0},?p,b[N]={0};if(InitStack(s))//初始化棧成功(printf("請(qǐng)輸入表達(dá)式八n”)；gets(ch);P=ch;while(*p)//沒(méi)到串尾Push(s,*p++);dfor(i=0;i<N;i++){?if(!StackEmpty(s)){〃棧不空Pop(s,e)；//彈出棧頂元素b[i]=e;for(i=0;i<N；i++){3if(ch[i]!=b[i])ak=0;}?if(k==0)。printf("NO!");elsePrintf(“輸出:“)printf(MYES!0);}return0；}實(shí)驗(yàn)結(jié)果：請(qǐng)輸入表達(dá)式：abcba輸出:YES!心得體會(huì):棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進(jìn)后出的性質(zhì),這個(gè)固有性質(zhì)使棧成為程序設(shè)計(jì)中的有用工具。實(shí)驗(yàn)4實(shí)驗(yàn)題目:二叉樹(shù)操作設(shè)計(jì)和實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康模赫莆斩x樹(shù)的定義、性質(zhì)及存儲(chǔ)方式，各種遍歷算法。實(shí)驗(yàn)規(guī)定:采用二叉樹(shù)鏈表作為存儲(chǔ)結(jié)構(gòu)，完畢二叉樹(shù)的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。實(shí)驗(yàn)重要環(huán)節(jié)：1、分析-、理解程序。2、調(diào)試程序，設(shè)計(jì)一棵二叉樹(shù)，輸入完全二叉樹(shù)的先序序列，用#代表虛結(jié)點(diǎn)（空指針）,如ABD###CE##F##,建立二叉樹(shù)，求M光序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。程序代碼：實(shí)驗(yàn)結(jié)果：心得體會(huì)：'實(shí)驗(yàn)5實(shí)驗(yàn)題目：圖的遍歷操作實(shí)驗(yàn)?zāi)康模赫莆沼邢驁D和無(wú)向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu);掌握DFS及BFS對(duì)圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。實(shí)驗(yàn)規(guī)定：采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu)，完畢有向圖和無(wú)向圖的DFS和BFS操作。

實(shí)驗(yàn)重要環(huán)節(jié)：設(shè)計(jì)一個(gè)有向圖和一個(gè)無(wú)向圖，任選一種存儲(chǔ)結(jié)構(gòu)，完畢有向圖和無(wú)向圖的DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)的操作。.鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)include"stdio.h"inc1udeHstdIib.h"defineMaxVertexNumI00〃定義最大頂點(diǎn)數(shù)typedefstruct{charvexsJMaxVertexNumJ;//頂點(diǎn)表intedges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表intn,e;〃圖中的頂點(diǎn)數(shù)n和邊數(shù)e}MGraph;〃用鄰接矩陣表達(dá)的圖的類(lèi)型//========建立鄰接矩陣=======voidCrea(MGraph(MGraph*G)(inii,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e)：");scanf("%d,%d",&G->n,&G->e);//輸入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n：i++)(scanf("%cu,&a);G->vexs[i]=a;G->vexs[i]=a;G->vexs[i]=a;//G->vexs[i]=a;//讀入頂點(diǎn)信息，建立頂點(diǎn)表for(i=0;i<G->n;i++)?for(j=0;j<G_>n；j++)。G->edges[il[j]=0；//初始化鄰接矩陣printf("Inputedges,CrcatAdjacencyMatrix\n");for(k=0；k<G->e;k++){〃讀入e條邊，建立鄰接矩陣seanf(”%d%d”,&i,&」)；//輸入邊(Vi,Vj)的頂點(diǎn)序號(hào)。G->edges[ij[j]=1；G->edges[j][i]=1;//若為無(wú)向圖，矩陣為對(duì)稱(chēng)矩陣；若建立有向圖，去掉該條語(yǔ)句))〃=========定義標(biāo)志向量，為全局變量======:lypedefenum{FALSE,TRUE}Boolean；Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(MGraph*Ginli){〃以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表達(dá)的圖G進(jìn)行DFS搜索，鄰接矩陣是0,1矩陣給出你的編碼//===========BFS：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){〃以Vk為源點(diǎn)對(duì)用鄰接矩陣表達(dá)的圖G進(jìn)行廣度優(yōu)先搜索給出你的編碼

〃==========主程序mainvoidmain()MGraph*G;G=(MGr叩h*)malloc(sizeof(MGraph));〃為圖G申請(qǐng)內(nèi)存空間CrcatMGraph(G);〃建立鄰接矩陣printf("PrintGraphDFS:");DFS(G);//深度優(yōu)先遍歷princf("\n");printf("PrintGmphBFS:")：BFS(G3);printf("\n");)2.鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)#include"stdio.h"BFS(G3);printf("\n");)2.鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)#include"stdio.h"#inelude"std1ib.h"#defineMaxVertexNum50typedefstructnode{intadjvex;structnode*next：}EdgeNode;typedefstructvnode{charvertex；//以序號(hào)為3的頂點(diǎn)開(kāi)始廣度優(yōu)先遍歷EdgeNode*firstedge;//定義最大頂點(diǎn)數(shù)〃邊表結(jié)點(diǎn)//鄰接點(diǎn)域〃鏈域//頂點(diǎn)表結(jié)點(diǎn)//頂點(diǎn)域//邊表頭指針}VertexNode；}VertexNode；typedefVertexNodeAdjList[MaxVertexNiim]；//AdjList是鄰接表類(lèi)typedefstruct{AdjListadj1ist;}VertexNode；typedefVertexNodeAdjList[MaxVertexNiim]；//AdjList是鄰接表類(lèi)typedefstruct{AdjListadj1ist;intn,e;}ALGraph；〃鄰接表〃圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)〃圖類(lèi)型voidCreatALGraph(ALGraph*G)(inti,j,k;chara;EdgeNode*s;〃定義邊表結(jié)點(diǎn)printf("InputVertexNum(n)andEdgesNum(e)：")；scanf(',%d,%d",&G->n.&G->e);//讀入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G—>n;i++)〃建立邊表{scanf("%c",&a);G->adjlist[i].veriex=a;〃讀入頂點(diǎn)信息G->adj1ist[i].firstedge=NULL;〃邊表置為空表)printf("Inputedges,CreatAdjacencyList\n")；for(k=0;k<G->e；k++){//建立邊表oscanf("％d%d”,&i,&j);oscanf("％d%d”,&i,&j);oscanf("％d%d”,&i,&j);〃讀入邊oscanf("％d%d”,&i,&j);〃讀入邊（Vi,Vj）的頂點(diǎn)對(duì)序號(hào)s=(EdgeNode*)mal1oc(sizeof(EdgeNode))；〃生成邊表結(jié)點(diǎn)?s->adjvex=j;//鄰接點(diǎn)序號(hào)為j?s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;〃將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode*)malloc(sizeof(EdgeNode));?s->adjvex=i;〃鄰接點(diǎn)序號(hào)為is->ncxt=G->adjlist|j].firstedge;G—>adjlist[j].firstedge=s;〃將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部1)//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(ALGraph*Ginti){〃以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表達(dá)的圖G進(jìn)行DFS搜索給出你的編碼//==========BFS：廣度優(yōu)先遍歷=========voidBFS(ALGraph*G,intk)j{〃以Vk為源點(diǎn)對(duì)用鄰接鏈表表達(dá)的圖G進(jìn)行廣度優(yōu)先搜索給出你的編碼//==========主函數(shù)===========voidmain()實(shí)驗(yàn)1實(shí)驗(yàn)題目:順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除實(shí)驗(yàn)?zāi)康模毫私夂驼莆站€性表的邏輯結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)，掌握線性表的基本算法及相關(guān)的時(shí)間性能分析。實(shí)驗(yàn)規(guī)定：建立一個(gè)數(shù)據(jù)域定義為整數(shù)類(lèi)型的線性表，在表中允許有反復(fù)的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù),先找到相應(yīng)的存儲(chǔ)單元，后刪除之。實(shí)驗(yàn)重要環(huán)節(jié)：1、分析、理解給出的示例程序。2、調(diào)試程序，并設(shè)計(jì)輸入一組數(shù)據(jù)(3,-5,6,8,2,—547,-9),測(cè)試程序的如下功能：根據(jù)輸入的數(shù)據(jù),找到相應(yīng)的存儲(chǔ)單元并刪除，、顯示表中所有的數(shù)據(jù)。程序代碼：#include<sIdio.h>#include<maHoc.h>#defineOK1defineERROROdcfineOVERFLOW-2defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefstruct{int*e1em;inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);printfCPrintGraphDFS:")；DFS(G)；printf("\n");printf('TrintGraphBFS：");BFS(G,3)；Primf(”\n")；)實(shí)驗(yàn)結(jié)果：.鄰接矩陣作為存儲(chǔ)結(jié)構(gòu).鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)心得體會(huì)：?實(shí)驗(yàn)6實(shí)驗(yàn)題目:二分查找算法的實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康模赫莆斩植檎曳ǖ墓ぷ髟砑皯?yīng)用過(guò)程，運(yùn)用其工作原理完畢實(shí)驗(yàn)題目中的內(nèi)容。。實(shí)驗(yàn)規(guī)定:編寫(xiě)程序構(gòu)造一個(gè)有序表L,從鍵盤(pán)接受一個(gè)關(guān)鍵字key,用二分查找法在L中查找key,若找到則提醒查找成功并輸出key所在的位置,否則提醒沒(méi)有找到信息。。實(shí)驗(yàn)重要環(huán)節(jié)：.建立的初始查找表可以是無(wú)序的，如測(cè)試的數(shù)據(jù)為⑶7,11,15,17,21,35,50｝或者｛11,21,7,3,15,50,42,35,17｝。.給出算法的遞歸和非遞歸代碼；.如何運(yùn)用二分查找算法在一個(gè)有序表中插入一個(gè)元素x,并保持表的有序性？程序代碼實(shí)驗(yàn)結(jié)果：心得體會(huì)：4實(shí)驗(yàn)7實(shí)驗(yàn)題目：排序?qū)嶒?yàn)?zāi)康模赫莆崭鞣N排序方法的基本思想、排序過(guò)程、算法實(shí)現(xiàn)，能進(jìn)行時(shí)間和空間性能的分析,根據(jù)實(shí)際問(wèn)題的特點(diǎn)和規(guī)定選擇合適的排序方法。實(shí)驗(yàn)規(guī)定：'實(shí)現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運(yùn)營(yíng)速度。實(shí)驗(yàn)重要環(huán)節(jié)：程序代碼實(shí)驗(yàn)結(jié)果:心得體會(huì):ntlength;?int1istsize;}Sqlist;intInitList_Sq(Sqlist&L){oL.elem=(int*)mal1oc(LIST」NIT_SIZE*sizeof(int));“f(!L.e1em)return-1；Liength=O;L.listsize=LIST_INIT_SIZE;orcturnOK；)intListInsert_Sq(Sqlist&L,inti,inte){if(i<1||i>L.length+1)returnERROR;aif(L.length==L.listsize){?int*newbase;newbase=(int*)real1oc(L.e1em,(L.listsize+LISTINCREMENT)*sizeof(int));oqf(Jnewbase)return-1;?L.elem=newbase；4.listsize+=LISTINCREMENT;°)int*p,*q;q=&(L.elem[i-l]);9for(p=&(L.elcm[LJength-1])；p>=q;-p)*(p+l)=*p;*q=e;?++L.Iength;returnOK：intListDelete_Sq(Sqlist&L,inti,inte){int*p,*q;if(i<l|Ii>L.Iength)returnERROR;p=&(L.elem[i—1])；oe=*p；sq=L.e1em+L.length_1;Mor(++p；p<=q;++p)?*(p-I)=*p;o--L.length;areturnOK;}intmain(){aSqlistL;InitList_Sq(L)；〃初始化inti,a[]={3,-5,6,82-547,-9};?for(i=l;i<10；i++)Listlnsert_Sq(L,i,a[i-1]);°for(i=0；i<9；i++)oPrintf("%d",L.elemii]);。printf("\nu)"/插入9個(gè)數(shù)oListinsert_Sq(L,3,24);?for(i=0;i<10；i++)叩rintf("%dn,L.elem[i]);gprintf("\n");//插入一個(gè)數(shù)inte；ListDe1ete_Sq(L,2,e)；for(i=0;i<9；i++)。printf(0%d"，L.elem[i]);//刪除一個(gè)數(shù)printf("\nH)；8return0;I實(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心得體會(huì)：順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時(shí)間是一個(gè)常數(shù)，速度快；結(jié)構(gòu)簡(jiǎn)樸，邏輯上相鄰的元素在物理上也相鄰；不使用指針，節(jié)省存儲(chǔ)空間;但是插入和刪除元素需要移動(dòng)大量元素，消耗大量時(shí)間；需要一個(gè)連續(xù)的存儲(chǔ)空間；插入元素也許發(fā)生溢出；自由區(qū)中的存儲(chǔ)空間不能被其他數(shù)據(jù)共享實(shí)驗(yàn)2實(shí)驗(yàn)題目:單鏈表的插入和刪除實(shí)驗(yàn)?zāi)康模毫私夂驼莆站€性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時(shí)間性能分析。實(shí)驗(yàn)規(guī)定:建立一個(gè)數(shù)據(jù)域定義為字符類(lèi)型的單鏈表，在鏈表中不允許有反復(fù)的字符；根據(jù)輸入的字符,先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。實(shí)驗(yàn)重要環(huán)節(jié)：3、分析、理解給出的示例程序。4、調(diào)試程序，并設(shè)計(jì)輸入數(shù)據(jù)(如：A,C,E,F,HJQ,M),測(cè)試程序的如下功能:不允許反復(fù)字符的插入;根據(jù)輸入的字符，找到相應(yīng)的結(jié)點(diǎn)并刪除。5、修改程序：(1)增長(zhǎng)插入結(jié)點(diǎn)的功能。(2)建立鏈表的方法有“前插”、“后插”法。程序代碼：#include<stdio.h>#include<malloc.h>defineNULL0defineOK1defineERROR0typedefstructLNode{ntdata;structLNode*next;}LN0de,*LinkList;intInitList_L(LinkList&L){L=(LinkList)mal1oc(sizeof(LNode));&L->ncxt=NULL;returnOK;}intListlnsert_L(LinkList&L,inti,inte){HJnkListp,s;"ntj；，p=L;j=O;dwhile(p&&j<i-1){p=p->next；++j；)if(!pIIj>i—1)葉eturnERR0R;?s=(LinkList)malloc(sizeof(LNode))；s->data=e;?s->next=p->next;p->next=s;returnOK;)intListDe1e