c數(shù)據(jù)結(jié)構(gòu)實驗報告

第第頁c數(shù)據(jù)結(jié)構(gòu)實驗報告

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

專業(yè)：計算機科學(xué)與技術(shù)、軟件工程

學(xué)號:____202240703061___________________

班級:_________軟件二班______________

姓名:________朱海霞______________

指導(dǎo)老師:___劉遵仁________________

青島高校信息工程學(xué)院

2022年10月

試驗1

試驗題目：順次存儲結(jié)構(gòu)線性表的插入和刪除

試驗?zāi)康模?/p>

了解和掌控線性表的規(guī)律結(jié)構(gòu)和順次存儲結(jié)構(gòu)，掌控線性表的基本算法及相關(guān)的時間性能分析。

試驗要求：

建立一個數(shù)據(jù)域定義為整數(shù)類型的線性表，在表中允許有重復(fù)的數(shù)據(jù);依據(jù)輸入的數(shù)據(jù)，先找到相應(yīng)的存儲單元，后刪除之。

試驗主要步驟：

1、分析、理解給出的例如程序。

2、調(diào)試程序，并設(shè)計輸入一組數(shù)據(jù)(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：依據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲單元并刪除，顯示表中全部的數(shù)據(jù)。

程序代碼:

#include

#include

#defineOK1

#defineERROR0

#defineOVERFLOW-2

#defineLIST_INIT_SIZE100

#defineLISTINCREMENT10

typedefstruct{

int*elem;

intlength;

intlistsize;

}Sqlist;

intInitList_Sq(SqlistL){

L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L.elem)return-1;

L.length=0;

L.listsize=LIST_INIT_SIZE;

returnOK;

}

intListInsert_Sq(SqlistL,inti,inte){

if(i1||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.elem[i-1]);

for(p=(L.elem[L.length-1]);p=q;--p)

*(p+1)=*p;

*q=e;

++L.length;

returnOK;

}

intListDelete_Sq(SqlistL,inti,inte){

int*p,*q;

if(i1||iL.length)returnERROR;

p=(L.elem[i-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,a[i-1]);

for(i=0;i9;i++)

printf(%d,L.elem[i]);

printf();//插入9個數(shù)

ListInsert_Sq(L,3,24);

for(i=0;i10;i++)

printf(%d,L.elem[i]);

printf();//插入一個數(shù)

inte;

ListDelete_Sq(L,2,e);

for(i=0;i9;i++)

printf(%d,L.elem[i]);//刪除一個數(shù)

printf();

return0;

}

試驗結(jié)果：

3，-5,6,8,2，-5,4,7，-9

3，-5,24,6,8,2，-5,4,7，-9

3,24,6,8,2，-5,4,7，-9

心得體會：

順次存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快;結(jié)構(gòu)簡約，規(guī)律上相鄰的元素在物理上也相鄰;不運用指針，節(jié)約存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續(xù)的存儲空間;插入元素可能發(fā)生溢出;自由區(qū)中的存儲空間不能被其他數(shù)據(jù)共享試驗2

試驗題目：單鏈表的插入和刪除

試驗?zāi)康模?/p>

了解和掌控線性表的規(guī)律結(jié)構(gòu)和鏈式存儲結(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)建立鏈表的方法有“前插”、“后插”法。

程序代碼:

#include

#include

#defineNULL0

#defineOK1

#defineERROR0

typedefstructLNode{

intdata;

structLNode*ne*t;

}LNode,*LinkList;

intInitList_L(LinkListL){

L=(LinkList)malloc(sizeof(LNode));L-ne*t=NULL;

returnOK;

}

intListInsert_L(LinkListL,inti,inte){LinkListp,s;

intj;

p=L;j=0;

while(pj

p=p-ne*t;++j;

}

if(!p||ji-1)

returnERROR;

s=(LinkList)malloc(sizeof(LNode));s-data=e;

s-ne*t=p-ne*t;

p-ne*t=s;

returnOK;

}

intListDelete_L(LinkListL,inti,inte){LinkListp,q;

intj;

p=L;j=0;

while(p-ne*tj

p=p-ne*t;++j;

}

if(!(p-ne*t)||j

returnERROR;

q=p-ne*t;p-ne*t=q-ne*t;e=q-data;free(q);

returnOK;

}

intmain(){

LinkListL,p;

chara[8]={A,C,E,F,H,J,Q,U};inti,j;

InitList_L(L);

for(i=1,j=0;i=8,j8;i++,j++)ListInsert_L(L,i,a[j]);

p=L-ne*t;

while(p!=NULL){

printf(%c,p-data);p=p-ne*t;

}//插入八個字符printf(;試驗結(jié)果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會：;單鏈表是通過掃描指針P進行單鏈表的`操作;頭指針唯;試驗3;試驗題目：棧操作設(shè)計和實現(xiàn);試驗?zāi)康模?1、掌控棧的順次存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，以便在實;2、掌控棧的特點，即后進先出和先進先出的原那么;3、掌控棧的基本運算，如：入棧與出棧

}

}//插入八個字符printf();i=2;inte;ListInsert_L(L,i,B);p=L-ne*t;while(p!=NULL){printf(%c,p-data);p=p-ne*t;}//插入一個字符printf();i=3;ListDelete_L(L,i,e);p=L-ne*t;while(p!=NULL){printf(%c,p-data);p=p-ne*t;}printf();return0;

試驗結(jié)果：

ACEFHJQU

ABCEFHJQU

ABEFHJQU

心得體會：

單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯一標識點鏈表的存在;插入和刪除元素快捷，方便。

試驗3

試驗題目：棧操作設(shè)計和實現(xiàn)

試驗?zāi)康模?/p>

1、掌控棧的順次存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，以便在實際中敏捷應(yīng)用。

2、掌控棧的特點，即后進先出和先進先出的原那么。

3、掌控棧的基本運算，如：入棧與出棧等運算在順次存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。

試驗要求：

回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如

“abba”是回文，而“abab”不是回文。

試驗主要步驟

(1)數(shù)據(jù)從鍵盤讀入;

(2)輸出要判斷的字符串;

(3)利用棧的基本操作對給定的字符串判斷其是否是回文，假設(shè)是那么輸出“Yes”，否那么輸出“No”。

程序代碼:

#include

#include

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineOVERFLOW-2

#defineN100

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefstruct{

int*base;//在棧構(gòu)造之前和銷毀之后，base的值為NULLint*top;//棧頂指針

intstacksize;//當前已安排的存儲空間，以元素為單位

}SqStack;

intInitStack(SqStackS)

{//構(gòu)造一個空棧S

if(!(S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int))))

e*it(OVERFLOW);//存儲安排失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}

intStackEmpty(SqStackS)

{//假設(shè)棧S為空棧，那么返回TRUE，否那么返回FALSE

if(S.top==S.base)

returnTRUE;

else

returnFALSE;

}

intPush(SqStackS,inte)

{//插入元素e為新的棧頂元素

if(S.top-S.base=S.stacksize)//棧滿，追加存儲空間

{

S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base)

e*it(OVERFLOW);//存儲安排失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*(S.top)++=e;

returnOK;

}

intPop(SqStackS,inte)

{//假設(shè)棧不空，那么刪除S的棧頂元素，用e返回其值，并返回OK;否那么返回ERRORif(S.top==S.base)

returnERROR;

e=*--S.top;

returnOK;

}

intmain(){

SqStacks;

inti,e,j,k=1;

charch[N]={0},*p,b[N]={0};

if(InitStack(s))//初始化棧勝利

{

printf(請輸入表達式:);

gets(ch);

p=ch;

while(*p)//沒到串尾

Push(s,*p++);

for(i=0;i

if(!StackEmpty(s)){//棧不空

Pop(s,e);//彈出棧頂元素

b[i]=e;

}

}

for(i=0;i

if(ch[i]!=b[i])

k=0;

}

if(k==0)

printf(NO!);

else

printf(輸出:)

printf(YES!);

}

return0;

}

試驗結(jié)果：

請輸入表達式：

abcba

輸出：YES!

心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性質(zhì)，這個固有性質(zhì)使棧成為程序設(shè)計中的有用工具。

試驗4

試驗題目：二叉樹操作設(shè)計和實現(xiàn)

試驗?zāi)康模?/p>

掌控二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。

試驗要求：

采納二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求全部葉子及結(jié)點總數(shù)的操作。

試驗主要步驟：

1、分析、理解程序。

2、調(diào)試程序，設(shè)計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(空指針)，如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求全部葉子及結(jié)點總數(shù)。

程序代碼:

試驗結(jié)果：

心得體會：

試驗5

試驗題目：圖的遍歷操作

試驗?zāi)康模?/p>

掌控有向圖和無向圖的概念;掌控鄰接矩陣和鄰接鏈表建立圖的存儲結(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)先遍歷)的操作。

1.鄰接矩陣作為存儲結(jié)構(gòu)

#includestdio.h

#includestdlib.h

#defineMa*Verte*Num100//定義最大頂點數(shù)

typedefstruct{

charve*s[Ma*Verte*Num];//頂點表

intedges[Ma*Verte*Num][Ma*Verte*Num];//鄰接矩陣，可看作邊表intn,e;//圖中的頂點數(shù)n和邊數(shù)e

}MGraph;//用鄰接矩陣表示的圖的類型

//=========建立鄰接矩陣=======

voidCreatMGraph(MGraph*G)

{

inti,j,k;

chara;

printf(InputVerte*Num(n)andEdgesNum(e):);

scanf(%d,%d,G-n,G-e);//輸入頂點數(shù)和邊數(shù)

scanf(%c,a);

printf(InputVerte*string:);

for(i=0;in;i++)

{

scanf(%c,a);

G-ve*s[i]=a;//讀入頂點信息，建立頂點表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G-edges[i][j]=0;//初始化鄰接矩陣

printf(Inputedges,CreatAdjacencyMatri*);

for(k=0;ke;k++){//讀入e條邊，建立鄰接矩陣

scanf(%d%d,i,j);//輸入邊(Vi，Vj)的頂點序號

G-edges[i][j]=1;;G-edges[j][i]=1;//假設(shè)為;//=========定義標識向量，為全局變量=;typedefenum{FALSE,TRUE}B;Booleanvisited[Ma*Verte*;//========DFS：深度優(yōu)先遍歷的遞歸算;voidDFSM(MGraph*G,inti);{//以Vi為出發(fā)點

G-edges[i][j]=1;

G-edges[j][i]=1;//假設(shè)為無向圖，矩陣為對稱矩陣;假設(shè)建立有向圖，去掉該條語句}

}

//=========定義標識向量，為全局變量=======

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[Ma*Verte*Num];

//========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()

{

inti;

MGraph*G;

G=(MGraph*)malloc(sizeof(MGraph));//為圖G申請內(nèi)存空間

CreatMGraph(G);//建立鄰接矩陣

printf(PrintGraphDFS:);

DFS(G);//深度優(yōu)先遍歷

printf();

printf(PrintGraphBFS:);

BFS(G,3);//以序號為3的頂點開始廣度優(yōu)先遍歷

printf();

}

2.鄰接鏈表作為存儲結(jié)構(gòu)

#includestdio.h

#includestdlib.h

#defineMa*Verte*Num50//定義最大頂點數(shù)

typedefstructnode{//邊表結(jié)點

intadjve*;//鄰接點域

structnode*ne*t;//鏈域

}EdgeNode;

typedefstructvnode{//頂點表結(jié)點

charverte*;//頂點域

EdgeNode*firstedge;//邊表頭指針

}Verte*Node;

typedefVerte*NodeAdjList[Ma*Verte*Num];//AdjList是鄰接表類型typedefstruct{

AdjListadjlist;//鄰接表

intn,e;//圖中當前頂點數(shù)和邊數(shù)

}ALGraph;//圖類型

//=========建立圖的鄰接表=======

voidCreatALGraph(ALGraph*G)

{

inti,j,k;

chara;

EdgeNode*s;//定義邊表結(jié)點

printf(InputVerte*Num(n)andEdgesNum(e):);

scanf(%d,%d,G-n,G-e);//讀入頂點數(shù)和邊數(shù)

scanf(%c,a);

printf(InputVerte*string:);

for(i=0;in;i++)//建立邊表

{

scanf(%c,a);

G-adjlist[i].verte*=a;//讀入頂點信息

G-adjlist[i].firstedge=NULL;//邊表置為空表

}

printf(Inputedges,CreatAdjacencyList);

for(k=0;ke;k++){//建立邊表

scanf(%d%d,i,j);//讀入邊(Vi，Vj)的頂點對序號

s=(EdgeNode*)malloc(sizeof(EdgeNode));//生成邊表結(jié)點

s-adjve*=j;//鄰接點序號為j

s-ne*t=G-adjlist[i].firstedge;

G-adjlist[i].firstedge=s;//將新結(jié)點*S插入頂點Vi的邊表頭部

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s-adjve*=i;//鄰接點序號為i

s-ne*t=G-adjlist[j].firstedge;

G-adjlist[j].firstedge=s;//將新結(jié)點*S插入頂點Vj的邊表頭部

}

}

//=========定義標識向量，為全局變量=======

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[Ma*Verte*Num];

//========DFS：