2023年數(shù)據(jù)結(jié)構(gòu)C語言版實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)（C語言版)實(shí)驗(yàn)報(bào)告專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程學(xué)號(hào):___＿_(dá)____＿_(dá)＿＿＿_(dá)________班級(jí):_＿_(dá)_＿_(dá)___軟件二班___＿_(dá)＿_(dá)_＿_(dá)___＿姓名:__＿_(dá)__＿_(dá)朱海霞_______＿_(dá)____＿指導(dǎo)教師:_＿_(dá)劉遵仁___＿_(dá)____＿_(dá)_____青島大學(xué)信息工程學(xué)院2０2３年10月?實(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ù)類型的線性表，在表中允許有反復(fù)的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù)，先找到相應(yīng)的存儲(chǔ)單元，后刪除之。實(shí)驗(yàn)重要環(huán)節(jié):分析、理解給出的示例程序。調(diào)試程序，并設(shè)計(jì)輸入一組數(shù)據(jù)（3,-5，6,８，2,－5,4,7，-9),測試程序的如下功能：根據(jù)輸入的數(shù)據(jù),找到相應(yīng)的存儲(chǔ)單元并刪除,顯示表中所有的數(shù)據(jù)。程序代碼:#inclｕdｅ＜sｔdio.h>＃include＜ｍａlloc．ｈ＞＃dｅfｉｎeOＫ1#deｆineＥＲRＯR0#defineOVERFLOW－2#defineLIST＿IＮIT_SIZE100#ｄefinｅLISＴＩNCＲEＭEＮＴ1０typedefstrucｔ{ iｎｔ*ｅｌem;?iｎtleｎgｔh;?intlｉstsｉze;}Ｓqlｉst;iｎtInitList_Ｓq(Sqlist&L){?L.elem=(ｉnt*）malｌoc（LIST_INIT_SIZE*sizeｏf(iｎｔ));?if(！L.eｌem)return-１；?L.leｎgth=0; L.listsｉze=LＩST_IＮIT＿SＩZE;?returnOＫ;}intＬiｓtInsert_Sq(Ｓqlisｔ&L,iｎti,intｅ){ if(i<１||ｉ>L.length+１)returｎＥRRＯR;?if(Ｌ．length＝=L.lisｔsｉze){??int*nｅｗbase; neｗbａse=(int*）realｌoc（L.ｅｌeｍ，(L.listｓize+ＬISＴINCRＥMEＮT)*sｉｚｅof（int）);??iｆ(!ｎeｗbａｓe)ｒeturn-1; ?L.elem=newｂase；??L.listsｉzｅ+=LIＳＴＩNCREＭENT;?｝ ｉｎt＊p，*q; q＝&(L.elem[i-1]）;?foｒ(p＝＆(L.ｅlem[Ｌ.lenｇth-１])；p>＝ｑ;--p) ＊(p＋1)=＊ｐ; *ｑ＝e;?++L.lｅnｇth; retuｒnOＫ；｝intListＤelｅte_Ｓｑ（Sqliｓt&L,ｉnti,inｔｅ){ inｔ*p，＊q; ｉf(i<1|｜i>Ｌ．leｎｇth)returnＥRRＯR; p=&(L.eleｍ［ｉ－１])；?ｅ=*p;?q=Ｌ.eｌeｍ+L.leｎｇth－1;?foｒ(++p;p<=ｑ;++p)??＊(p-1)＝*p;?-－L.lengｔｈ;?reｔurｎOK;｝iｎtmain(){?SqlistL; InｉtＬist＿Sq(L）；//初始化 ｉｎti，a［]=｛３,-５,6,8,2,-5,4,7,-９};?ｆor(i=1;i<10；i＋+)ＬｉstIｎsert＿Sq(Ｌ,i,ａ[ｉ-1]）;?ｆｏr(ｉ=0；i<9；i++)? ｐrintf("%d"，Ｌ.elem[ｉ]);? pｒiｎtf("\n"）;／/插入9個(gè)數(shù)?LｉｓtInsｅrt＿Sｑ（L,3,2４);?for(i=0;i<１0；ｉ++) ?pｒintf("%ｄ"，L.elｅm［i]）;??priｎtf("\n"）;／／插入一個(gè)數(shù) inｔe； LｉstDeｌｅte＿Sq(L,2,ｅ)； ｆoｒ(ｉ=０;i<９；ｉ++） ?ｐｒintf（"％d＂，L.elem[i]);/／刪除一個(gè)數(shù) pｒinｔf(＂\n")；??rｅｔurｎ0;}實(shí)驗(yàn)結(jié)果：3，-5，6，8,２,-5,4,7,-93,-５,24,６,８,2，-5,4，7,-９3,24,6,8,2,－５，４,7,-9心得體會(huì):順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時(shí)間是一個(gè)常數(shù),速度快；結(jié)構(gòu)簡樸，邏輯上相鄰的元素在物理上也相鄰；不使用指針，節(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ù)域定義為字符類型的單鏈表,在鏈表中不允許有反復(fù)的字符；根據(jù)輸入的字符,先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。實(shí)驗(yàn)重要環(huán)節(jié)：分析、理解給出的示例程序。調(diào)試程序,并設(shè)計(jì)輸入數(shù)據(jù)(如：A，C,E,F,Ｈ,J，Q，M）,測試程序的如下功能:不允許反復(fù)字符的插入;根據(jù)輸入的字符,找到相應(yīng)的結(jié)點(diǎn)并刪除。修改程序：增長插入結(jié)點(diǎn)的功能。建立鏈表的方法有“前插”、“后插”法。程序代碼:#inclｕde＜sｔdｉo.h>#inclｕｄe<malloc.h>#defｉｎｅNＵLＬ０#defｉnｅOK1＃definｅＥRRＯR0ｔｙｐedefstrｕctLNode{ ｉntdaｔa; stｒｕctLNode*nexｔ;｝LNｏｄe,*LinkLｉsｔ;intInitList_L(LｉnkList&L){ L＝（LinkLiｓｔ)malｌoc(ｓizｅof（ＬN(yùn)oｄe）);?Ｌ-＞neｘt=NUＬＬ; ｒetuｒnＯK;}inｔＬｉstIｎsｅrt_L(LinｋLisｔ&Ｌ，iｎti，iｎtｅ）{?LinkＬistp，s;?iｎtj；?ｐ=L;j=0;?while(p＆＆j<ｉ-1)｛ p=p－＞ｎｅｘt；++ｊ； ｝ if（!p｜｜ｊ>ｉ－1) ?rｅturnＥRRＯR;?ｓ=（LinｋＬist)malloc（sizeof(ＬN(yùn)ｏｄe)）； s－＞data=ｅ;?s->neｘt=p->next; p-＞neｘｔ=s; ｒeturnOK;}intLｉstＤeｌete＿L(LinkLisｔ&L,inti,ｉnt＆e）｛?LiｎkListp,q；?inｔj; p=L;j=0；?while（p->next&&ｊ<i-1)｛? p=ｐ->nexｔ;+＋j； } if（！(p->next)||j<ｉ-１)? retuｒnERROR；?q=p->ｎext；p->next=q->neｘt;?ｅ=q－>ｄata;free(ｑ）; ｒeturnOK;}ｉntmａin(）{ LinkＬistL,p;?ｃｈaｒa［8]={'Ａ','Ｃ','Ｅ＇,＇F＇,'Ｈ＇,'J','Ｑ','U＇｝;?inti,j;?InitＬｉsｔ_L(Ｌ); fｏｒ(ｉ=１，j=0；i<＝8,j＜８;i++,j+＋)? LiｓｔＩnsert_L(L,i,a[j］)； ｐ＝L->next；?wｈiｌe（p!＝ＮULL){??pｒinｔｆ("％c\t＂,p－＞data)； ｐ=p－>ｎext;?}／/插入八個(gè)字符 priｎtｆ（"\n");?ｉ=2;?ｉｎte; LｉstＩnｓｅrt＿L（Ｌ,ｉ,'B'); p=L->neｘt;?whｉle(ｐ!＝NULL)｛ ?prinｔf("%ｃ\t",p->data）;? p=p-＞next；?}／/插入一個(gè)字符?ｐrinｔf（＂＼n"）; i＝３；?LiｓｔDeleｔe＿L(Ｌ,i,e）;?p＝L->nｅxt; whｉｌｅ（ｐ!=NＵＬL）{ ｐrintf(＂%c\t",p-＞datａ); ?p=p->neｘt; ｝?pｒｉntf("\n＂);?ｒetｕrn０；}實(shí)驗(yàn)結(jié)果：ACＥFHJQUABＣEFＨJＱUABEFHJQU心得體會(huì):單鏈表是通過掃描指針P進(jìn)行單鏈表的操作；頭指針唯一標(biāo)記點(diǎn)鏈表的存在；插入和刪除元素快捷，方便。實(shí)驗(yàn)3實(shí)驗(yàn)題目：棧操作設(shè)計(jì)和實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康模?、掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際中靈活應(yīng)用。2、掌握棧的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。３、掌握棧的基本運(yùn)算，如：入棧與出棧等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。實(shí)驗(yàn)規(guī)定：回文判斷:對于一個(gè)從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如“ａbbａ”是回文，而“abab”不是回文。實(shí)驗(yàn)重要環(huán)節(jié)(1）數(shù)據(jù)從鍵盤讀入;(2)輸出要判斷的字符串;(3)運(yùn)用棧的基本操作對給定的字符串判斷其是否是回文,若是則輸出“Yeｓ”,否則輸出“Ｎo”。程序代碼:#iｎclｕｄe<stｄio.h＞#iｎclude<stdlib．h>＃defineTRUＥ１#dｅfｉneFＡLSE０＃defiｎeＯＫ1#ｄefineEＲROR0#defineＯＶERFＬOW-2#definｅN１０0＃dｅfineSTACＫ＿ＩＮIＴ_ＳIZE 100 ＃dｅｆｉｎeＳTAＣKINＣRＥＭENT? １0 typeｄefｓtruｃｔ{ｉnt *bａse; ???//在棧構(gòu)造之前和銷毀之后,baｓｅ的值為NULLｉnｔ ＊top；?? ?//棧頂指針int???staｃkｓize;? ／/當(dāng)前已分派的存儲(chǔ)空間，以元素為單位}SｑStack;intIｎｉtStａｃk（SqＳtack&S)｛//構(gòu)造一個(gè)空棧Sｉｆ(!(S.ｂａse=(int*)ｍaｌloc（ＳTAＣK_ＩＮＩＴ＿SIＺE*sizeoｆ(iｎｔ))))eｘit(ＯVERFLOW);??? //存儲(chǔ)分派失敗S.top=S．basｅ；S.stａcksizｅ=ＳTACK_INIＴ＿ＳＩZE；ｒeｔurnOK;}intStａcｋEmｐｔy（SqＳtackS){//若棧S為空棧，則返回ＴRＵE，否則返回FALSＥif(Ｓ.toｐ==Ｓ.base）retｕrnＴRＵE;elｓｅreturnFALSＥ;｝inｔPuｓh（SqStack＆S，inte）{//插入元素e為新的棧頂元素ｉf(S．toｐ-S.ｂａse>=S.stacｋsizｅ)//棧滿,追加存儲(chǔ)空間{S.bａse＝(iｎt＊)ｒeａｌloc(S.baｓe,（S.sｔacksｉze+STACKINCREＭENT)*sｉｚeof(int));ｉf(！S．base)eｘiｔ(OVEＲFＬOW)；/／存儲(chǔ)分派失敗S.ｔｏp＝S.ｂａse＋S.ｓtackｓiｚe；S．sｔａckｓｉｚe+＝STACKINＣREMENT;}*(S.ｔop)++=e;reｔuｒｎOK;}ｉntPop（SqSｔack&S，inｔ&ｅ）{／/若棧不空，則刪除S的棧頂元素,用ｅ返回其值,并返回OK;否則返回EＲRORif(Ｓ.top==Ｓ.base)rｅtｕrnＥRRＯＲ;e＝*－-S．toｐ;reｔurnOＫ；｝ｉntmａiｎ(){SqSｔａｃks;iｎti,e,j,k=1；ｃharch[N]={0｝,*ｐ,b[Ｎ]={0};if(ＩnｉｔSｔaｃk(s))//初始化棧成功{pｒiｎtf(＂請輸入表達(dá)式:\n");ｇｅts（ch）;p＝ch;ｗhile（*p)/／沒到串尾Push(ｓ,*p++);?for(i=0;i<Ｎ;i++)｛?ｉf(!SｔackＥmpｔy(s))｛//棧不空Pｏｐ(ｓ,e）；／/彈出棧頂元素? b［i]=ｅ; }?｝ foｒ(i=0;i<Ｎ;i++）{ ?if(ch［i]!=b[ｉ]） ?k＝0；}?iｆ(k＝＝0）? ｐrinｔf(＂NO!＂）; ｅｌsｅｐｒiｎｔf("輸出:"）prｉntf("YＥS！");} returｎ0；}實(shí)驗(yàn)結(jié)果:請輸入表達(dá)式：aｂcbａ輸出:YＥS!心得體會(huì):棧是僅能在表尾驚醒插入和刪除操作的線性表,具有先進(jìn)后出的性質(zhì),這個(gè)固有性質(zhì)使棧成為程序設(shè)計(jì)中的有用工具。實(shí)驗(yàn)4實(shí)驗(yàn)題目:二叉樹操作設(shè)計(jì)和實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康?掌握二叉樹的定義、性質(zhì)及存儲(chǔ)方式，各種遍歷算法。實(shí)驗(yàn)規(guī)定:采用二叉樹鏈表作為存儲(chǔ)結(jié)構(gòu),完畢二叉樹的建立,先序、中序和后序以及按層次遍歷的操作,求所有葉子及結(jié)點(diǎn)總數(shù)的操作。實(shí)驗(yàn)重要環(huán)節(jié):分析、理解程序。調(diào)試程序,設(shè)計(jì)一棵二叉樹,輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)（空指針),如ABD##＃CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。程序代碼:實(shí)驗(yàn)結(jié)果:心得體會(huì)：?實(shí)驗(yàn)5實(shí)驗(yàn)題目：圖的遍歷操作實(shí)驗(yàn)?zāi)康模赫莆沼邢驁D和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu);掌握DＦS及BFＳ對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。實(shí)驗(yàn)規(guī)定：采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu),完畢有向圖和無向圖的DＦS和ＢFS操作。實(shí)驗(yàn)重要環(huán)節(jié):設(shè)計(jì)一個(gè)有向圖和一個(gè)無向圖，任選一種存儲(chǔ)結(jié)構(gòu),完畢有向圖和無向圖的DFS（深度優(yōu)先遍歷)和ＢFS(廣度優(yōu)先遍歷)的操作。鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)#ｉnclude"ｓｔdｉｏ．h"#ｉncｌude"ｓtｄlｉb.ｈ"#definｅMaxＶertexNｕm1０0//定義最大頂點(diǎn)數(shù)typedeｆｓｔｒuｃt{cｈarvexs[MaxＶertexNｕm];／／頂點(diǎn)表ｉnteｄges[ＭaxVerｔexＮum］[MaxＶeｒtexNum];/／鄰接矩陣，可看作邊表iｎtn,e;//圖中的頂點(diǎn)數(shù)n和邊數(shù)e}MGraｐh;//用鄰接矩陣表達(dá)的圖的類型／/====＝====建立鄰接矩陣＝＝＝＝===vｏidＣrｅａt(yī)MGｒaｐh(MGrapｈ*Ｇ）｛iｎti,j，k;chara;ｐrinｔf("InｐｕｔVｅrｔeｘNum(n)aｎdＥdｇeｓNｕm（ｅ):");sｃanf（"%d,%ｄ"，&G->ｎ，&Ｇ->e）;//輸入頂點(diǎn)數(shù)和邊數(shù)sｃanf("%c",&ａ）;ｐrintf（"InputVｅｒｔeｘstring:");ｆｏr（i＝0;i<Ｇ->n；i++){ ｓcanf("%c",&a); G->vexｓ[i]=a;／/讀入頂點(diǎn)信息，建立頂點(diǎn)表}foｒ（i=0;i<G->n;i++)? for(j=０;j<G－>n；j++)? Ｇ->edgｅs［i]［ｊ]=0；/／初始化鄰接矩陣prｉｎtf("Ｉnputedges，CreatAdjacencyＭａt(yī)rix\ｎ＂);ｆor(k=０；k＜G-＞ｅ;k+＋)｛//讀入ｅ條邊，建立鄰接矩陣 scaｎf(＂％ｄ％d",&ｉ,＆ｊ);/／輸入邊（Vi,Vｊ）的頂點(diǎn)序號(hào)?Ｇ->edgｅs[i][ｊ]=１； G－>edｇeｓ[j][i］=１;／/若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//＝=====＝=＝定義標(biāo)志向量,為全局變量＝===＝==tyｐeｄefｅｎum{FALSE,ＴＲＵE}Boolean；Boｏleanviｓitｅd［MａxＶerteｘNum];／/＝=====＝=DFＳ:深度優(yōu)先遍歷的遞歸算法=====＝voｉdDＦSＭ（MGｒaph＊G,inti）｛//以Vｉ為出發(fā)點(diǎn)對鄰接矩陣表達(dá)的圖G進(jìn)行DＦS搜索，鄰接矩陣是０，1矩陣給出你的編碼//＝=====＝====ＢＦS：廣度優(yōu)先遍歷＝==＝=＝＝voidBFS(MGｒａph*G,iｎｔｋ）{//以Vk為源點(diǎn)對用鄰接矩陣表達(dá)的圖G進(jìn)行廣度優(yōu)先搜索給出你的編碼//==＝====＝==主程序main＝====voidmain(){iｎti;MＧraph*G;G=(MGｒaph*)mallｏc（ｓizeof(MGraph));//為圖G申請內(nèi)存空間CreatMＧraph(G);//建立鄰接矩陣prｉntf("ＰriｎｔGraphDFS:＂);ＤFS(G）;/／深度優(yōu)先遍歷printf("＼n"）;ｐriｎtｆ("PｒiｎｔＧrapｈＢFS:")；BFS(G,3);／/以序號(hào)為３的頂點(diǎn)開始廣度優(yōu)先遍歷priｎｔｆ（"\n"）;}鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)＃includｅ"stdｉｏ．ｈ"#iｎclude"ｓtｄlｉb.h＂#defｉneMaｘVｅrtexNｕm5０/／定義最大頂點(diǎn)數(shù)ｔypedefｓｔrｕctnode{//邊表結(jié)點(diǎn)iｎtadｊvex;/／鄰接點(diǎn)域ｓtrｕcｔnode*next；//鏈域}ＥdgeNｏde;ｔypｅｄefsｔructvｎode{/／頂點(diǎn)表結(jié)點(diǎn)chａrveｒtex；/／頂點(diǎn)域EdgeNode*firsｔeｄge;／／邊表頭指針｝ＶertｅｘNode；tyｐedefVertexＮodeAｄjList［ＭａxＶerｔexNuｍ］;//AdjLisｔ是鄰接表類型typｅdeｆstｒuｃt{ＡdｊListａdjｌiｓt;//鄰接表intn，e;//圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)｝ＡLGrａｐｈ；//圖類型//=＝=======建立圖的鄰接表＝===＝==ｖoidＣrｅatALＧraph（ＡLGraph*G)｛inｔｉ,ｊ,k;cｈara;EｄgeNｏｄe*ｓ;//定義邊表結(jié)點(diǎn)pｒintｆ("InputVｅｒteｘNum(ｎ)anｄEdgesNum(e)：")；sｃaｎｆ("%d,％d",＆G->n,&G－>e);／／讀入頂點(diǎn)數(shù)和邊數(shù)scanｆ("%c"，＆ａ);priｎｔｆ("InputVertexstring:");for(i=０;i<G－>n;i++)//建立邊表{ scanf(＂%c",&a）; G->adjlist[i].vertｅx=a;//讀入頂點(diǎn)信息 Ｇ->adｊｌｉｓt[ｉ］.fｉrstedge=NULL;//邊表置為空表}priｎtf（"Inｐutedgeｓ,CreatAｄjａcencyLisｔ\n＂)；for（k＝0;ｋ＜G-＞ｅ；k+＋）｛//建立邊表?sｃａnｆ("%d％ｄ",&i，＆ｊ);//讀入邊（Vｉ，Ｖj）的頂點(diǎn)對序號(hào) s＝(EｄｇeＮｏdｅ*）malｌoc（sizeof(EdgｅNode）)；//生成邊表結(jié)點(diǎn)?s->adｊｖeｘ=j;//鄰接點(diǎn)序號(hào)為j?s-＞ｎexｔ=Ｇ->adｊlist[i］.fｉrstedge; Ｇ->ａdjliｓt[i］.fｉrstedge＝ｓ;//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vｉ的邊表頭部 ｓ＝(ＥdｇｅNoｄｅ*）mallｏc(siｚｅｏf(EdgeＮｏde)）;?s->aｄjｖｅx=i;//鄰接點(diǎn)序號(hào)為i s->nexｔ＝G-＞adjlist[j].fiｒsteｄge; G－＞adｊliｓｔ[j].fｉrsteｄge=ｓ;//將新結(jié)點(diǎn)＊S插入頂點(diǎn)Ｖj的邊表頭部}}／/＝=＝======定義標(biāo)志向量，為全局變量==＝==