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

vaMnKrtM?1<T

SHUJUJIEGOUCYUYANBAN]!

數(shù)相結(jié)前（C語言悔）

姓名：關(guān)宏新

學(xué)號：

班級：計(jì)084班

指導(dǎo)教師：儲岳中

實(shí)驗(yàn)一線性表基本操作的實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康?/p>

1、掌握使用TurboC2.0上機(jī)調(diào)試線性表的基本方法；

2、掌握線性表的基本操作:插入、刪除、查找等運(yùn)算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的運(yùn)算。

二、實(shí)驗(yàn)規(guī)定

1、鏈表插入、刪除和查找算法的代碼；

2,程序運(yùn)營結(jié)果及分析；

3、實(shí)驗(yàn)總結(jié)。

三、實(shí)驗(yàn)內(nèi)容

1、認(rèn)真閱讀和掌握本實(shí)驗(yàn)的參考程序。

2、上機(jī)運(yùn)營本程序，并完善刪除、查找等運(yùn)算。

3、保存程序的運(yùn)營結(jié)果，并結(jié)合程序進(jìn)行分析。

4、按照你對鏈表操作需要，重新改寫算法并運(yùn)營，實(shí)現(xiàn)鏈表的插入、刪除、查找等運(yùn)算，并保存運(yùn)營結(jié)

果。

四、程序流程圖、算法及運(yùn)營結(jié)果

1-1

#include'*stdio.h”

#include"std1ib.h"

#defineMAXSIZE100

structSeqList

{

intdata[MAXSIZE]；

int1ength;

}；

typedefstructSeqList*PSeqList;

PSeqListcreaeNullList_seq()

PSeqListpalist=(PSeqList)mal1oc(sizeof(structSeqList));

if(palist!=NULL)

(

palist->length=0;

return(palist);

}

printf(MOutofspace!!\n")；

returnNULL;

}

intisNullList_seq(PSeqListpalist)

(

return(pa1ist->length~O);

}

intinsertPre_seq(PSeqListpalist,intp,intx)

(

intq；

if(palist—>1ength>=MAXSIZE)

(

printf("overflow!\n")；

return(0);

}

if(p<0IIp>palist->length)

(

printf("Notexist!\n");

return(0)；

}

if(isNul1List_seq(pa1ist))

pa1ist->data[0]=x；

palist->length=l;

return(l);

}

for(q=palist->length-l;q>=p;q—)

Palist->data[q+l]=palist->data[q];

pa1ist->data[p]=x;

palist—>1ength=palist->length+1；

return(1);

}

voidmain()

(

inti；

PSeqListlist;

1ist=creaeNullList__seq();

printf(〃插入前的順序表為:\n");

for(i=0；i<=9;i++)

(

insertPre_seq(list,i,i*i);

printf("％d”,list->data[i]);

)

insertPre_seq(list,5,55);

printf("\n插入后的順序表為：\n〃);

for(i=0;i<list->1ength;i++)

printf%d”,list—>data[i]);

printf(〃\n〃);

getchO;

)

□*C:\Docuaentsand5?t1:11183：\人(1>11115t1：a10八桌面\實(shí)裝內(nèi)容1\源代不

0149162536496481

插入后的順序表為：

014916552536496481

1-2

#includenstdio.hn

#include"stdlib.h"

#defineMAXSIZE100

structSeqList

(

intdata[MAXSIZE];

intIength;

｝；

typedefstructSeqList*PSeqList；

PSeqListcreaeNulIList_seq()

(

PSeqListpaIist=(PSeqList)ma11oc(sizeof(structSeqList));

if(paIist!=NULL)

palist->Iength=0;

return(paIist);

)

printf(nOutofspace!!\n");

returnNULL;

I

intisNu11List_seq(PSeqListpaIist)

(

return(palist->length==0);

I

/*插入*/

intinsertPre_seq(PSeqListpaIist,intp,intx)

(

intq;

if(palist->Iength>=MAXSIZE)

(

printf("overflow!\n");

return(0);

1

if(p<0|Ip>paIist->Iength)

(

printf("Notexist!\nM);

return(0);

}

if(isNuIIList_seq(palist))

paIist->data[0]=x;

paIist->Iength=1;

return(1);

1

for(q=palist->length-1;q>=p；q—)

paIist->data[q+1]=palist—>data[q];

palist—>data[p]=x;

paIist->Iength=paIist->Iength+1；

return(1)；

)

/*刪除*/

intdeIetePre_seq(PSeqListpalist,inti)

(

intj;

if(!paIist)

(

printf("表不存在”)；

return(-1);

}

if(i<1|Ii>paIist->Iength)

(

printf("刪除位置不合法”);

return(0);

)

for(j=i;j<paIist->Iength;j++)

paIist->data[j-1]=paIist—>data[j];

palist->Iength—;

return(1);

)

/*檢索ElementType*/

intIocationPre_seq(PSeqListpaIist,intx)

(

inti=0;

if(!paIist)

(

printf("表不存在”)；

return(-1);

1

while(i<palist—>length&&palist->data[i]!=x)

i++；

if(i>=paIist->Iength)return0；

elsereturn(i+1);

}

voidmain()

(

inti;

PSeqListlist;

Iist=creaeNullList_seq0;

printf("插入前的順序表為：\n“)；

for(i=0;i<=9;i++)

insertPre_seq(Iist,i,i*i);

printf(H%d,list—>data[i]);

1

insertPre_seq(Iist,5,55);

printf("\n插入后的順序表為:\n");

for(i=0;i<1ist—>length;i++)

printf("%d",Iist—>data[i]);

printf("\n,r);

printf("刪除前的順序表為：\n”)；

for(i=0;i<=9；i++)

(

insertPre_seq(Iist,i,i*i);

printf(n%dn,Iist—>data[i]);

)

deletePre_seq(Iist,5);

printf(”\n刪除后的順序表為:\n")；

for(i=0;i<=8;i++)

printf("%d,Iist->data[i]);

printf("\n");

if(IocationPre_seq(list,9)==0)

printf(“檢索的內(nèi)容不存在！”);

if(IocationPre_seq(Iist,9)!=0&&IocationPre_seq(list,9)!=-1)

printf("檢索的內(nèi)容下標(biāo)為:％d",IocationPre_seq(Iist,9));

printf(n\nM)；

getch();

c、*C:\Docu>entsandSettings'AdAinistrator'桌面'實(shí)驗(yàn)內(nèi)容1\源代碼\Sl\Debug.

0149162536496481

植入后的順序表為:

014916552536496481

對除前的順序表為:

0149162536496481

刷除后的順序表為:

01492536496481

檢索的內(nèi)容下標(biāo)為:4

實(shí)驗(yàn)二棧的基本操作

一、實(shí)驗(yàn)?zāi)康?/p>

掌握棧的基本操作:初始化棧、判棧為空、出棧、入棧等運(yùn)算。

二、實(shí)驗(yàn)規(guī)定

i.認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法。

2.上機(jī)將本算法實(shí)現(xiàn)。

3.保存程序的運(yùn)營結(jié)果,并結(jié)合程序進(jìn)行分析。

三、實(shí)驗(yàn)內(nèi)容

運(yùn)用棧的基本操作實(shí)現(xiàn)將任意一個十進(jìn)制整數(shù)轉(zhuǎn)化為R進(jìn)制整數(shù)

算法為：

1、定義棧的順序存取結(jié)構(gòu)

2、分別定義棧的基本操作(初始化棧、判棧為空、出棧、入棧等)

3、定義一個函數(shù)用來實(shí)現(xiàn)上面問題：

(1)十進(jìn)制整數(shù)X和R作為形參

(2)初始化棧

(3)只要X不為。反復(fù)做下列動作

將X%R入棧，X=X/R

(4)只要棧不為空反復(fù)做下列動作

棧頂出棧，輸出棧頂元素

四、程序流程圖、算法及運(yùn)營結(jié)果

2-1

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#definestack_init_size100

#definestackincrement10

typedefstructsqstack

(

int*base;

int*top;

intstacksize;

}sqstack;

intStacklnit(sqstack*s)

(

s->base=(int*)maHoc(stack_init_size*sizeof(int));

if(!s—>base)

return0；

s->top=s—>base;

s->stacksize=stack_init_size；

return1；

)

intPush(sqstack*s,inte)

if(s->top-s->base>=s->stacksize)

(

s->base=(int*)rea11oc(s->base,(s->stacksize+stackincrement)*sizeof(in

t));

if(!s->base)

return0；

s->top=s->base+s->stacksize;

s->stacksize+=stackincrement;

)

*(s->top++)=e;

returne;

}

intPop(sqstack*s,inte)

(

if(s->top=s—>base)

return0;

e=*-s->top；

returne;

)

intstackempty(sqstack*s)

{

if(s—>top==s->base)

return1；

)

else

(

return0;

}

)

intconversion(sqstack*s)

(

intn,e=0,flag=0；

printf("輸入要轉(zhuǎn)化的十進(jìn)制數(shù):\n");

scanf("%d”,&n)；

printf("要轉(zhuǎn)化為多少進(jìn)制：2進(jìn)制、8進(jìn)制、16進(jìn)制填數(shù)字!\n");

scanf&flag);

printf("將十進(jìn)制數(shù)%(1轉(zhuǎn)化為%d進(jìn)制是:\n"，n,flag);

whi1e(n)

(

Push(s,n%flag)；

n=n/flag；

}

while(!stackempty(s))

(

e=Pop(s,e)；

switch(e)

(

case10:printf('*A*);

break;

case11:printf("B");

break;

case12:printf("C");

break；

case13:printf("D")；

break;

case14：printf(*E*1)；

break;

case15:printf("F")；

break;

defau1t:printf("%d",e);

)

}

printf("\n");

return0;

}

intmain()

(

sqstacks;

StackInit(&s);

conversion(&s);

return0;

}

c\*C:\Docu>entsandSettings\Ad>ini3trator\桌面'賣套內(nèi)容1\源代碼

輸入要轉(zhuǎn)化的十進(jìn)制數(shù):

量轉(zhuǎn)化為多少進(jìn)制：2進(jìn)制、8進(jìn)制、16進(jìn)制填數(shù)字！

2

將十進(jìn)制數(shù)25轉(zhuǎn)化為2進(jìn)制是：

11001

Pressanykeytocontinue.

2-2

#include<stdlib.h>

#defineMAXSIZE100

structstack

(

intdata[MAXSIZE];

inttop;

};

voidinit(structstack*s)

(

s->top=-l;

)

intempty(structstack*s)

{

if(s->top==-1)return1;

eIsereturn0;

)

voidpush(structstack*s,inti)

if(s->top==MAXSIZE-1){

printf("Stackisfull.\n'*);

return;

)

s->top++;

s->data[s->top]=i；

}

intpop(structstack*s)

(

if(empty(s)){

printf("Stackisempty.");

return-1;

)

return(s->data[s->top—])；

}

voidtrans(intnum)

(

structstacks;

intk；

init(&s);

while(num){

k=num%16;

push(&s,k);

num=num/16;

}

while(!empty(&s)){

k=pop(&s);

if(k<10)

printfk);

e1se

printf("%c”,k+55)；

)

printf("\n");

}

main()

{

intnum；

clrscr()；

printf("Inputanum(-1toquit):\n")

scanf("%d”,&num);

whi1e(num!=-1){

trans(num);

scanf&num);

)

getch();

}

c\C:\DOCUIE~1\曲口N1~1\桌面,實(shí)驗(yàn)內(nèi)~1\源代碼\S2\2-

llnputanum<-ltoquit>：

45

2D

實(shí)驗(yàn)三串的模式匹配

一、實(shí)驗(yàn)?zāi)康?/p>

1.運(yùn)用順序結(jié)構(gòu)存儲串，并實(shí)現(xiàn)串的匹配算法。

2.掌握簡樸模式匹配思想，熟悉KMP算法。

二、實(shí)驗(yàn)規(guī)定A1.認(rèn)真理解簡樸模式匹配思想，高效實(shí)現(xiàn)簡樸模式匹配；

2.結(jié)合參考程序調(diào)試KMP算法,努力算法思想；

3.保存程序的運(yùn)營結(jié)果,并結(jié)合程序進(jìn)行分析。

三、實(shí)驗(yàn)內(nèi)容

1、通過鍵盤初始化目的串和模式串，通過簡樸模式匹配算法實(shí)現(xiàn)串的模式匹配，匹配成功后規(guī)定輸出模式

串在目的串中的位置；

2、參考程序給出了兩種不同形式的next數(shù)組的計(jì)算方法，請完善程序從鍵盤初始化一目的串并設(shè)計(jì)

匹配算法完整調(diào)試KMP算法,并與簡樸模式匹配算法進(jìn)行比較。

四、程序流程圖、算法及運(yùn)營結(jié)果

3-1

#include<stdio.h>

#include<string.h>

#defineMAXSIZE100

intStrIndex_BF(chars[MAXSIZE],chart[MAXSIZE])

{

inti=1,j=1;

whi1e(i<=s[0]&&j<=t[0])

if(s[i]=t[j]){

i++；

j++；

}

eIse{

i=i-j+2;

j=1;

)

)

if(j>t[0])

return(i-t[0]);

else

return-1;

)

intmain()

(

chars[MAXSIZE];

chart[MAXSIZE];

intanswer,i;

printf("SString—>\n");

gets(s)；

printf(*TString->\n")；

gets(t)；

printfStrindex_BF(s,t))；/*驗(yàn)證*/

if((answer=Strindex_BF(s,t))>=0)

printf("\n");

printf("%s\n",s)；

for(i=0;i<answer；i++)

printfC")；

printf(”％s”,t);

printf(*\n\nPatternFoundat1ocation：%d\n”,answer)；

}

else

printf("\nPatternNOTFOUND.\n");

getch()；

return0;

}

c\*C:\DocuaentsandSettings\Ad>inisatrator\桌面,實(shí)驗(yàn)內(nèi)容

SString—>

asdfdsassd

TString——>

ass

-1

PatternNOTFOUND.

3-2

#inc1ude<stdio.h>

#include<string.h>

#defineMAXSIZE100

voidget_nextval(unsignedcharpat[],intnextva1[])

intlength=strlen(pat);

inti=1;

intj=0;

nextva1[1]=0;

while(i<length)

(

if(j=0||pat[i-1]=pat[j-1])

(

++i;

++j；

if(pat[i—l]!=pat[j-1])nextva1[i]=j;

elsenextva1[i]=nextval[j]；

}

eIsej=nextval[j];

)

)

intIndex_KMP(unsignedchartext[],unsignedcharpat[1,intnextval[])

(

inti=1；

intj=1;

intt_len=strlen(text)；

intp_1en=strlen(pat);

while(i<=t_len&&j<=p_1en)

if(j=0I11ext[i-1]==pat[j-1]){++i;++j;}

elsej=nextval[j];

}

if(j>P_1en)returni-1-pn;

elsereturn-1；

}

intmain()

(

unsignedchartext[MAXSIZE];

unsignedcharpat[MAXSIZE]；

intnextval[MAXSIZE];

intanswer,i；

printf("\nBoyer-MooreStringSearchingProgram");

printf(〃\n================—==-=—==-==/z)?

printf(\n\nTextString—>”);

gets(text);

printf(H\nPatternString―>”);

gets(pat);

get__nextval(pat,nextval);

if((answer=Index_KMP(text,pat,nextval))>=0)

(

printf("\n");

printf('1%s\n”,text);

for(i=0；i<answer;i++)

printf("")；

printfpat)；

printf("\n\nPatternFoundat1ocation%d\n”,answer)；

}

eIse

printff\nPatternNOTFOUND.\n")；

getch();

return0;

}

c\*C:\Docu>entsandSettings'AdMinistrator\桌面,賣瞼內(nèi)容

Boyer-MooreStringSearchingProgram

TextString——>asdfdddssa

PatternString一一>ds

asdfdddssa

ds

PatternFoundatlocation6

3-3

#include"stdio.h

voidGetNext1(char*t,intnext[])

{

inti=1,j=0;

next[l]=0;

while(i<=9)

if(j=OI|t[i]==t[j])

{++i；++j;next[i]=j;}

else

j=next[j];

voidGetNext2(char*t,intnext[])

(

inti=1,j=0；

next[l]=0;

while(i<=9)

(

while(j>=l&&t[i]!=t[j])

j=next[j];

i++;j++;

if(t[i]==t[j])next[i]=next[j];

elsenext[i]=j;

)

)

voidmain()

(

char*p=z，abcaababc”；

inti,str[10];

GetNext1(p,str);

printf(',Putout:\n");

for(i=l;i<10;i++)

printf(**%d”,str[i]);

GetNext2(p,str);

printf("\n");

for(i=l;i<10;i++)

printf("%d”,str[i])；

printf("\n");

getch();

)

1~*C:\Docu>entsandSettings\Ad>inistra

|Putout：

|011112123

|011102013

L_

實(shí)驗(yàn)四二叉樹操作

一、實(shí)驗(yàn)?zāi)康?/p>

1.進(jìn)一步掌握指針變量的含義。

2.掌握二叉樹的結(jié)構(gòu)特性，以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。

3.掌握用指針類型描述、訪問和解決二叉樹的運(yùn)算。

二、實(shí)驗(yàn)規(guī)定

1.認(rèn)真閱讀和掌握本實(shí)驗(yàn)的參考程序。

2.按照對二叉樹的操作需要，在創(chuàng)建好二叉樹后再通過遍歷算法驗(yàn)證創(chuàng)建結(jié)果。

3.保存程序的運(yùn)營結(jié)果，并結(jié)合程序進(jìn)行分析。

三、實(shí)驗(yàn)內(nèi)等以下參考程序是按完全二叉樹思想將輸入的字符串生成二叉樹，并通過遍歷來驗(yàn)證

二又樹創(chuàng)建對的與否，但不能創(chuàng)建非完全二叉樹，請認(rèn)真研究該程序，然后模仿教材例6.4初始化方式創(chuàng)

建二叉樹:所有的空指針均用井表達(dá)，如教材圖6-13相應(yīng)的二叉樹，建立時(shí)的初始序列為:AB#D##CE#卵

四、程序流程圖、算法及運(yùn)營結(jié)果

4-1

#include"stdio.h”

#definemax30

#defineNULL0

typedefstructBNode

(

chardata;/*數(shù)據(jù)域*/

structBNode*1child,*rchild；/*指向左右子女*/

}BinTree;

voidpreorder(BinTree*t)；/*聲明先根遍歷函數(shù)*/

voidinorder(BinTree*t);/*聲明中根遍歷函數(shù)*/

voidpostorder(BinTree*t)；/*聲明后根遍歷函數(shù)*/

intleafs(BinTree*b);/*聲明求葉子數(shù)函數(shù)*/

inttreedeep(BinTree*p);/*聲明求樹的深度函數(shù)*/

BinTree*swap(BinTree*p);/*聲明互換二叉樹的所有結(jié)點(diǎn)的左右子樹的函數(shù)*/

/*將字符串中的第i個字符開始的m個字符作為數(shù)據(jù)生成相應(yīng)的二叉樹*/

BinTree*cre_tree(char*str,inti,intm)

{

BinTree*p;

if(i>=m)/*無效結(jié)點(diǎn)*/

returnNULL；

p=(BinTree*)maHoc(sizeof(BinTree));/*生成新結(jié)點(diǎn)*/

p->data=str[i];

p->lchi1d=cre_tree(str,2*i+1,m);/*創(chuàng)建新結(jié)點(diǎn)的左子樹*/

p->rchild=cre_tree(str,2*i+2,m);/*創(chuàng)建新結(jié)點(diǎn)的右子樹*/

returnp;

)

voidmain()

{

inti,n；

charstr[max]；

BinTree*root;/*根結(jié)點(diǎn)*/

Printf(〃請輸入二叉樹的結(jié)點(diǎn)數(shù):〃)；

scanf&n);

getchar();/*輸入數(shù)字*/

printf("請輸入長度為%d的字符串：",n);

for(i=0；i<n;i++)

seanf("%c11,&str[i]);

printf("\n");

root=cre_tree(str,0,n)；

printf("二叉樹已成功創(chuàng)建！結(jié)點(diǎn)序列為:“)；

for(i=0;i<n;i++)

printf("%c”,str[i]);

printf("\n");

/*先根遍歷*/

printf("\n先根遍歷結(jié)果:");

preorder(root)；

printf("\n")；

/*中根遍歷*/

printf(”\n中根遍歷結(jié)果:");

inorder(root);

printfC\n")；

/*后根遍歷*/

printf("\n后根遍歷結(jié)果：”)；

postorder(root);

printf("\n");

printf(”\n葉子數(shù)為:%d\n”,1eafs(root));

printf(”\n樹的深度為：％d\n",treedeep(root));

printf("\n互換左右子樹后先序遍歷序列為:")；

preorder(swap(root));

printf(”\n\n");

}

voidpreorder(BinTree*t)

(

if(t!=NULL)

(

printfC%c”,t—>data);

if(t->lchi1d)

(

printf

preorder(t->lchi1d)；

}

if(t—>rchi1d)

printf;

preorder(t->rchild);

)

)

}

voidinorder(BinTree*t)

(

if(t!=NULL)

(

inorder(t->lchild)；

printf("%c",t—>data)；

inorder(t->rchi1d);

)

)

voidpostorder(BinTree*t)

(

if(t!=NULL)

(

postorder(t->lchild);

postorder(t->rchiId);

printf("%c”,t->data);

)

)

intleafs(BinTree*b)/*求葉子數(shù)*/

intnuml,num2;

if(b==NULL)return(0);

eIseif(b->lchi1d==NULL&&b->rchi1d==NULL)return(1)；

else

(

numl=leafs(b->1child)；

num2=leafs(b->rchi1d);

return(numl+num2)；

}

}

inttreedeep(BinTree*p)/*求樹的深度*/

(

int1deep,rdeep>deep;

if(p==NULL)deep=0；

else

(

Ideep=treedeep(p->1chi1d);

rdeep=treedeep(p->rchild);

deep=(1deep>rdeep?1deep：rdeep)+1;

}

returndeep；

)

BinTree*swap(BinTree*p)/*互換二叉樹的所有結(jié)點(diǎn)的左右子樹*/

(

BinTree*stack[max];

intk=0;

stack[k]=NULL;

if(p!=NULL)

(

stack[++k]=p—>1child;

p->1child=p->rchi1d；

p->rchild=stack[k];

p->lchild=swap(p->lchi1d);

p->rchi1d=swap(p->rchiId);

}

returnp；

)

c\*C:\Docu>entsandSettingsVAdainistratl\?ttS5\S4\Debug

請輸入長度為8的字符串：asdfqwer

二叉樹己成功創(chuàng)建？結(jié)點(diǎn)序列為：asdFqwer

先根遍歷結(jié)果：a->s->￡->r->q->d->w->e

中根遍歷結(jié)果：i*￡sqawde

后根遍歷結(jié)果：犬￡qsweda

葉子數(shù)為：4

樹的深度為：4

交換左右子樹后先序遍歷序列為：a->d->e->w->s->q->f->r

Pi*essanykeytocontinue

實(shí)驗(yàn)五圖的創(chuàng)建與遍歷.

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握圖的含義;

2.掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結(jié)構(gòu)；

3.理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲結(jié)構(gòu)。

二、實(shí)驗(yàn)規(guī)定

1.認(rèn)真閱讀和掌握本實(shí)驗(yàn)的參考程序。

2.按照對圖的操作需要，在創(chuàng)建好圖后再通過遍歷算法驗(yàn)證創(chuàng)建結(jié)果。

3.保存程序的運(yùn)營結(jié)果，并結(jié)合程序進(jìn)行分析。

三、實(shí)驗(yàn)內(nèi)等以下參考程序是按鄰接表的方法創(chuàng)建圖，然后用深度優(yōu)先遍歷方法遍歷圖。請認(rèn)真理解

程序,然后實(shí)現(xiàn)圖的廣度優(yōu)先遍歷。

四、程序流程圖、算法及運(yùn)營結(jié)果

5-1

#include"stdio.h"

#definemaxsize1024/*假定線性表的最大長度為1024*/

^definenlOO/*圖的頂點(diǎn)最大個數(shù)*/

typedefintdatatype；/*假定線性表元素的類型為整型*/

typedefcharVEXTYPE；/*頂點(diǎn)的數(shù)據(jù)類型*/

typedeff1oatADJTYPE；/*權(quán)值類型*/

typedefstruct

(

VEXTYPEvexs[n];/*頂點(diǎn)信息數(shù)組*/

ADJTYPEarcs[n][n];/*邊權(quán)數(shù)組*/

intnum;/*頂點(diǎn)的實(shí)際個數(shù)*/

}GRAPH;

/*1.置空圖*/

voidGraphlnit(GRAPH*L)

L->num=0;

)

/*2.求結(jié)點(diǎn)數(shù)*/

intGraphVexs(GRAPH*L)

(

return(L->num);

)

/*3.創(chuàng)建圖*/

voidGraphCreate(GRAPH*L)

{

inti,j;

GraphInit(L)；

printf("請輸入頂點(diǎn)數(shù)目：”)；

scanf("%d",&L->num);

printf(〃請輸入各頂點(diǎn)的信息(單個符號)：〃);

for(i=0;i<L->num;i++)

(

fflush(stdin);

scanf(”％c”,&L->vexs[i]);

)

printf("請輸入邊權(quán)矩陣的信息：”)；

for(i=0;i<L->num;i++)

(

for(j=0;j<L->num;j++)

scanf&L->arcs[i][j])；

)

printf（"圖已經(jīng)創(chuàng)建完畢!”）;

)

/*4.圖的輸出*/

voidGraphOut(GRAPHL)

(

inti,j;

printf("\n圖的頂點(diǎn)數(shù)目為：％d",L.num);

printf("\n圖的各頂點(diǎn)的信息為：\n");

for(i=0；i<L.num;i++)

printf("%c",L.vexs[i]);

printf(〃\n圖的邊權(quán)矩陣的信息為：\n");

for(i=0;i<L.num;i++)

(

for(j=0;j<L.num;j++)

(

printfC%6.2f",L.arcs[i][j]);

)

printf("\n*);

)

printf("圖已經(jīng)輸出完畢!”)：

)

/*5.圖的深度環(huán)游*/

voidDFS(GRAPHg,intqidian,intmark[])

/*從第qidian個點(diǎn)出發(fā)深度優(yōu)先環(huán)游圖g中能訪問的各個頂點(diǎn)*/

intv1;

mark[qidian]=1；

printf("%c”,g.vexs[qidian]);

for(v1=0；vl<g.num；vl++)

(

if(g.arcs[qidian][vl]!=0&&mark[v1]==0)

DFS(g,v1,mark);

)

)

/*6.圖的深度環(huán)游*/

voidGraphDFS(GRAPHg)

/*深度優(yōu)先環(huán)游圖g中能訪問的各個頂點(diǎn)*/

(

intqidian,v,vl,mark[maxsize];

printf("\n深度環(huán)游：”)；

printf("\n請輸入起點(diǎn)的下標(biāo):“)；

scanf("%d”,&qidian);

for(v=0；v<g.num;v++)

(

mark[v]=0;

}

for(v=qidian;v<g.num+qidian;v++)

(

vl=v%g.num;

if(mark[vl]==0)

DFS(g,vl,mark);

}

/*隊(duì)列元素的數(shù)據(jù)類型*/

typedefintDATATYPE；

typedefstruct

{

DATATYPEdata[maxsize];/*隊(duì)中元素*/

intfront,rear;/*隊(duì)頭元素下標(biāo)、隊(duì)尾元素后面位置的下標(biāo)*/

}SEQQUEUE;

voidQueuelnit(SEQQUEUE*sq)

/*將順序循環(huán)隊(duì)列sq置空(初始化)*/

(

sq—>front=0;

sq->rear=0；

)

intQueuelsEmpty(SEQQUEUEsq)

/*假如順序循環(huán)隊(duì)列sq為空,成功返回1,否則返回0*/

{

if(sq.rear-sq.front)

return(1);

els

return(0);

}

intQueueFront(SEQQUEUEsq,DATATYPE*e)

/*將順序循環(huán)隊(duì)列sq的隊(duì)頭元素保存到e所指地址,成功返回L失敗返回0*/

(

if(QueueIsEmpty(sq))

{printf("queueisempty!\n")；return0;}

e1se

{*e=sq.data[(sq.front)];return1;}

}

intQueueIn(SEQQUEUE*sq,DATATYPEx)

/*將元素x入隊(duì)列sq的隊(duì)尾,成功返回1,失敗返回0*/

(

if(sq->front==(sq->rear+1)%maxsize)

{

printf(^queueisfull!\n")；

return0；

)

else

(

sq->data[sq->rear]=x;

sq->rear=(sq->rear+1)%maxsize;

return(1);

)

)

intQueueOut(SEQQUEUE*sq)

/*將隊(duì)列sq隊(duì)首元素出隊(duì)列,成功返回1,失敗返回0*/

{

if(QueueIsEmpty(*sq))

(

printf(*queueisempty!\n");

return0;

)

e1se

(

sq->front=(sq->front+1)%maxsize；

return1;

)

)

/*7.圖的廣度環(huán)游*/

voidBFS(GRAPHg,intv,intmark[])

/*從v出發(fā)廣度優(yōu)先環(huán)游圖g中能訪問的各個頂點(diǎn)*/

(

intvl,v2；

SEQQUEUEq；

QueueInit(&q)；

Queueln(&q,v)；

mark[v]