C语言版严蔚敏著-数据结构实验指导-2《数据结构》

涉曲&彳拓％纪

《数据结构》实验指导及报告书

/学年第一学期

姓名：______________

学号：______________

班级：______________

指导教师：______________

数学与统计学院

2011

预备实验C语言的函数数组指针结构体知识

一、实验目的

1、复习c语言中函数、数组、指针、结构体与共用体等的概念。

2、熟悉利用C语言进行程序设计的一般方法。

二、实验预习

说明以卜.C语言中的概念

1、函数：

2、数组：

3、指针：

4、结构体

5、共用体

三、实验内容和要求

1、调试程序：输出100以内所有的素数(用函数实现)，

#include<stdio.h>

intisprime(intn){/*判断一个数是否为素数*/

intm;

for(m=2;m*m<=n:m++)

if(n%m==O)return0;

return1;

)

intmain(){/*输出100以内所有素数*/

inti;printf("\n");

for(i=2;i<100;i++)

if(isprime(i)==1)prinlf("%4d",i);

return0;

)

运行结果：

2、调试程序：对一维数组中的元素进行逆序排列。

#include<stdio.h>

#dcfincN10

inimain(){

inta[N]={O,l23,4,5,6,7,8,9}上temp;

prinlf("\ntheoriginalArrayis:\n");

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

printf("%4d",a[i]);

for(i=0;i<N/2;i++){/*交换数组元素使之逆序*/

temp=a[i];

a[i]=a[N-i-l];

a[N-i-1]=temp;

}

printf("\nthcchangedArrayis:\n");

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

printf(,,%4d",a[i]);

return0;

)

运行结果：

3、调试程序：在二维数组中，若某一位置上的元素在该行中最大，而在该列中最小，则该

元素即为该二维数组的一个鞍点。要求从键盘上输入一个二维数组，当鞍点存在时，把鞍点

找出来。

#include<stdio.h>

#defineM3

#defineN4

intmain(){

inta[M][N],ij,k;

printf("\n请输入二维数组的数据：\n");

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

for(j=0;j<N;j++)

scanf("%d",&a[i][j]);

for(i=0;i<M;i++){/*输出矩阵*/

for(j=0;j<N;j++)

printf("%4d",a[il[j]);

printf("\n°);

I

for(i=0;i<M;i++){

k=0;

for(j=l;j<N;j++)芦找出第i行的最大值*/

if(a[i]U]>a[i][k])

k=j;

for(j=0;j<M;j++)/*判断第i行的最大值是否为该列的最小值*/

if(aU][k]<a[i][k])

break;

if(j==M)/*在第i行找到鞍点*/

printf("%d,%d,%d\n",a[i][k],i,k);

else

scanf("%s",stu[i].depa.office);

I

printfCnameagejobclass/office");

for(i=0;i<n;i++){/*输；H*/

if(stu[i].job==,s,)

printf("%s%3d%3c%d\n",stu[i].name,stu[i|.age,stu[i].job,stu[i].depa.class);

else

printf("%s%3d%3c%s\n",stu[,stu[i].age,stufi].job,stu[i].depa.office);

)

)

输入的数据：2

Wang19s99061

Li36tcomputer

运行结果：

四、实验小结

五、教师评语

实验一顺序表与链表

一、实验目的

1、掌握线性表中元素的前驱、后续的概念。

2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。

3、对线性表相应算法的时间好杂度进行分析.

4、理解顺序表、链表数据结构的特点（优缺点）。

二、实验预习

说明以下概念

1、线性表：

2、顺序表:

3、链表:

三、实验内容和要求

1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。

#include<stdio.h>

#include<malloc.h>

^defineERROR0

#defineOK1

ttdefineINIT^SIZE5/*初始分配的顺序表长度*/

^defineINCREM5/*溢出时，顺序表长度的增量*/

typedefintElemType;/*定义表元素的类型*/

typedefstructSqlist{

ElcmTypc*slist;/*存储空间的基地址*/

intlength;/*顺序表的当前长度*/

intlistsize;/*当前分配的存储空间*/

}Sqlist;

intInitList_sq(Sqlist*L);/**/

intCreateList_sq(Sqlist*L,intn);/**/

intListlnsertsq(Sqlist*L,inti,ElcmTypee);/**/

intPrintList_sq(Sqlist*L);/*输出顺序表的元素*/

intListDeletesq(Sqlist*L,inti);/*删除第i个元素*/

intListLocate(Sq)ist*L,ElemTypee);/*查找值为e的元素*/

intInitList_sq(Sqlist*L){

L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));

if(!L->slist)returnERROR;

L->length=0;

L->listsize=INITSIZE;

returnOK;

}/*InitList*/

intCreateList_sq(Sqlist*L,intn){

ElcmTypee;

inti;

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

printf(""inputdata%d”,i+1);

scanf(飞d",&e);

if(!Listlnsert_sq(L,i+1,e))

returnERROR;

}

returnOK;

}/*CreateList*/

/*输出顺序表中的元素*/

intPrintList_sq(Sqlist*L)(

inti;

for(i=l;i<=L->length;i++)

printf("%5d”,L->slist[i-l]);

returnOK;

}/*PrintList*/

intListInsert_sq(Sqlist*L,inti,ElcmTypee){

intk;

if(i<l||i>L->length+l)

returnERROR;

if(L->length>=L->listsize){

L->slist=(ElemType*)realloc(L->slist,

(INITSIZE+INCREM)*sizeof(E1emType));

if(!L->slist)

returnERROR;

L->listsize+=INCREM;

}

for(k=L->length-l;k>=i-l;k-){

L->slist[k+l]=L->slist[k];

)

L->slist[i-l]=e;

L->length++;

returnOK;

}/:*:ListInsert*/

/*在顺序表中删除第i个元素*/

intListDeletesq(Sqlist*L,inti){

)

/*在顺序表中查找指定值元素，返回其序号*/

intListLocate(Sqlist*L,ElcmTypee)(

)

intmain(){

Sqlistsi;

intn,m,k；

printf(，zpleaseinputn:");/*输入顺序表的元素个数*/

scanf&n);

if(n>0){

printf(Z，\nl-CreateSqlist:\n，z);

InitListsq(&sl);

CreateList_sq(&sl,n);

printf(，，\n2-PrintSqlist:\n*);

PrintList_sq(&sl);

printf(y，\npleaseinputinsertlocationanddata:(location,data)\n/z);

scanf%d”,&m,&k);

Listinsertsq(&sl,m,k);

printf(/Z\n3-PrintSqlist:\nw);

PrintList_sq(&sl);

printf("\n");

)

else

printf("ERROR");

return0;

1

j

•运行结果

算法分析

2、为第1题补充删除和支找功能函数，并在主函数中补充代码验证算法的正确性。

删除算法代码：

•运行结果

•算法分析

查找算法代码:

•运行结果

算法分析

3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。

#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

typedefintElemType;/*定义表元素的类型*/

typedefstructLNode{/*线性表的单链表存储*/

ElemTypedata;

AtruntT.Nndp*r)pxt";

}LNode,*LinkList;

LinkListCreateList(intn);/*

voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/

intGetElem(LinkListLzinti,ElemType*e);/**/

LinkListCreateList(intn){

LNode*p,*q,*head;

inti;

head=(LinkList)malloc(sizeof(LNode));head->next=NULL;

p=head;

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

q=(LinkList)malloc(sizeof(LNode));printf('*input

data%i:,i+1);

scanf(n%d'\&c->data);/*输入元素值*/

q->next=NULL;/*结点指针域置空*/

p->next=q;/*新结点连在表末尾*/

p=q；

}

returnhead;

}/*CreateList*/

voidPrintList(LinkListL){

LNode*p;

p=L->next;/*p指向单链表的第1个元素*/

while(p!=NULL){

printf(u%5d",p->data);

p=p->next;

}

}/*PrintList*/

intGetElem(LinkListL,inti,ElemType*e){

LNode*p;intj=L;

p=L->next;

while(p&&j<i){

p=p->next;j++;

}

ifdpiIj>i)

returnERROR;

*e=p->data;

returnOK;

}/*GetElem*/

intmain(){

intn,i;ElemTypee;

LinkListL=NULL;/*定义指向单链表的指针*/

printf("pleaseinputn:");/*输入单链表的元素个数*/

scanf(n%d",&n);

if(n>0){

printf("\nl-CreateLinkList:\n");

L=CreateList(n);

printf(H\n2-PrintLinkList:\nH);

PrintLiot(L);

printf(H\n3-GetElemfromLinkList:\n");

printf("inputi=n);

scanf(n%dM,&i);

if(GetElem(L,i,&e))

printf(nMo%iis%dn,i,e);

else

printf(Hnotexists*');

}else

printf("ERROR");

return0;

}

•运行结果

•算法分析

4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。

插入算法代码：

•运行结果

.算法分析

删除算法代码:

•运行结果

算法分析

以下为选做实验：

5、循环链表的应用（约瑟夫回环问题）

n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上

述过程，直至表中只剩下一个元素。

提示：用一个无头结点的循环单链表来实现n个元素的存储。

•算法代码

6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。

提示：指针P从链表的第一个元素开始，利用指针q从指针P位置开始向后搜索整个链表,

删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p==null

为至，既完成了对整个链表元素的删除相同值。

•算法代码

四、实验小结

五、教师评语

实验二栈和队列

一、实验目的

1、掌握栈的结构特性及其入栈，出栈操作；

2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

二、实验预习

说明以下概念

1、顺序栈：

2、链栈：

3、循环队列：

4、链队

三、实验内容和要求

1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列12345e,运

行结果如下所示。

#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

#defineSTACK_INT_SIZE10/*存储空间初始分配量*/

#defineSTACKINCREMENT5/*存储空间分配增量*/

typedefintElemType;/*定义元素的类型*/

typedefstruct{

ElemType*base;

ElemType*top;

intstacksize;/*当前已分酉己的存储空间*/

}SqStack;

intInitStack(SqStack*S);/*构造空栈*/

intpush(SqStack*S,ElemTypee);/*入栈*/

intPop(SqStack*S,ElemType*e);/*出栈*/

intCreateStack(SqStack*S);/*创建栈*/

voidPrintstack(SqStack*S);/*出栈并输出栈中元素*/

intTnitSfArk(SqSfflrk*S){

S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));

if(!S->base)returnERROR;

S->top=S->base;

S->stacksize=STACK_INT_SIZE;

returnOK;

}/*InitStack*/

intPush(SqStack*S,ElemTypee){

}/*Push*/

intPop(SqStack.*SzElemType*e)(

}/*Pop*/

intCreateStack(SqStack*S){

inte;

if(initstack(S))

printf(nInitSuccess!\n");

else{

printf(HInitFaillXn1');

returnERROR;

}

printf("inputdata:(Terminatedbyimputingacharacter)\nn);

while(scanf&e))

Push(S,e);

returnOK;

}/*CreateStack*/

voidPrintstack(SqStack*S){

ElemTypee;

while(Pop(Sz&e))

printf(n%3d,',e);

}/*Pop_and_Print*/

intmain(){

SqStackss;

printf(\n1-createstack\nn);

CreateStack(&ss);

printf(,,\n2-Pop&Print\nu);

Printstack(&ss);

return0;

}

•算法分析：输入元素序列12345,为什么输出序列为54321?体现了栈佐什么

特性？

2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来

实现），并验证其正确性。

・实现代码

・验证

3、阅读并运行程序，并分析程序功能。

#include<stdio.h>

#include<malloc.h>

#include<strinq.h>

#defineM20

#defineelemtypechar

typedefstruct

(

elemtypestack[M];

inttop;

}

stacknode;

voidinit(stacknode*st);

voidpush(stacknode*st,elemtypex);

voidpop(stacknode*st);

voidinit(stacknode*st)

st->top=0;

}

voidpush(stacknode*stzelemtypex)

(

if(st->top==M)

printf(nthestackisoverflow•\nn);

else

(

st->top=st->top+l;

st->stack[st->top]=x;

}

}

voidpop(stacknode*st)

(

if(st->top>0)st->top-;

elseprintf(''StackisEmpty!\nz,);

}

intmain()

(

chars[M];

inti;

stacknode*sp;

printf("createaemptystack!\nn);

sp=malloc(sizeof(stacknode));

init(sp);

printf(ninputaexpression:\n");

gets(s);

for(i=0;i<strlen(s);i++)

(

if(G[i]——»(')

push(sp,s[i]);

if(s[i]==f)')

pop(sp);

}

if(sp->top==0)

printf("'(•match1)'!\nn);

else

printf(H'(*notmatch*)'!\nM);

return0;

}

•输入：2+((c-d)*6-(f-7)*a)/6

•运行结果：

•输入：a-((c-d)*6-(s/3-x)/2

•运行结果：

•程序的基本功能：

以下为选做实验：

4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式

得结果。

•实现代码

5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针）,

试编写相应的置空队列、入队列、出队列的算法。

实现代码：

四、实验小结

五、教师评语

实验三串的模式匹配

一、实验目的

1、了解串的基本概念

2、掌握串的模式匹配算法的实现

二、实验预习

说明以下概念

1、模式匹配：

2、BF算法:

3、KMP算法:

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。

#include<stdio.h>

#include<string.h>

#defineMAXSIZE100

typedefstruct{

chardata[MAXSIZE];

intlength;

}SqString;

intstrCompare(SqString*sl,SqString*s2);/*串的比较*/

voidshow_strCompare();

voidstrSub(SqString*s,intstart,intsublen,SqString*sub);

/*求子串*/

voidshow_subString();

intstrCompare(SqString*sl,SqString*s2){

inti;

for(i=0;i<sl->length&&i<s2->length;i++)

if(sl->data[i]!=s2->data[i])

returnsl->data[i]-s2->data[i];

returnsl->length-s2->length;

)

voidshow_strCompare(){

SqStringsi,s2;

intk;

printf("Xn***showcompare***\n,f);

printf("inputstrings1:");

gets(si.data);

si.length=strlen(si.data);

printf("inputstrings2:H);

gets(s2.data);

s2.length=strlen(s2.data);

if({k=strCompare(&sl,&s2))==0)

printf("sl=s2\n");

plSPif(k<0)

printf(nsl<s2\n");

else

printf(Hsl>s2\n,');

printf("\n***showover***\nM);

}

voidstrSub(SqString*s,intstart,intsublen,SqString*sub){

inti;

if(3tart<l||3tart>o->length||3ublen>3->lcngth-Gtart+l)(

sub->length=O;

}

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

sub->data[i]=s->data[start+i-1];

sub->length=sublen;

}

voidshow_subString(){

SqStrings,sub;

intstart,sublen,1;

printf('*\n***showsubstring***\nn);

printf(''inputstrings:u);

gets(s.data);

s.length=strlen(s.data);

printf(ninputstart:“)；

scanf(n%d",&start);

printf(ninputsablen:");

scanf(n%d",&sublen);

strSub(&s,startssublen,&sub);

if(sub.length==0)

printf("ERROR!\nn);

else{

printf("subStringis;

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

printf(“*c”,sub.data[i]);

printf(n\n***showover***\n*');

}

intmain(){

intn;

do(

printf("\n——String——\nn);

printf(H1.strCompare\n");

printf("2.subString\nH);

printf(H0.EXTT\n");

printf(H\ninputchoice:;

scanf("当d”,&n);

getchar();

switch(n){

case1:show_strCompare();break;

case2:show_subString();break;

default:n=0;break;

)

}while(n);

return0;

}

・运行程序

输入：

1

student

students

2

ComputerDataStuctures

10

4

运行结果：

2、实现串的模式匹配算法。补充下面程序，实现串的EF和KMP算法。

#include<stdio.h>

#include<string.h>

#defineMAXSIZE100

typedefstruct{

chardata[MAXSIZE];

intlength;

}SqString;

intindexbf(SqString*s,SqString*t,intstart);

voidgetNext(SqString*t,intnext[]);

intindex_kmp(SqString*szSqString*t,intstart,intnext[]);

voidshowindex();

intindex_bf(SqString*s,SqString*t,intstart){

补充代码……

}

voidgetNext(SqString*t,intnext[]){

inti=0zj=-l;

next[0]=-l;

while(i<t->length){

if((j==-l)II(t->data[i]==t->data[j])){

i++;j++;next[i]=j;

}else

j=next[j];

)

}

intindex_kmp(SqString*s,SqString*t,intstart,intnext[]){

补充代码……

}

voidshow_index(){

SqStrings,t;

intk,next[MAXSIZE]={0},i;

printf("\n***showindex***\nH);

printf("inputstrings:n);

gets(s.data);

s.length=strlen(s.data);

printf("inputstringt:u);

gets(t.data);

t.length=strlen(t.data);

printf(ninputstartposition:");

scanf(n%d",&k);

printf("BF:\ntheresultofBFis%d\n",index_bf(&sz&t,k));

gpfNpxt-(,npxt);

printf(nKMP:\nn);

printf("next[]:'*);

for(i=0;i<t.length;i++)

printf("%3d",next[i]);

printf(n\nn);

printf("theresultofKMPis%d\nn,index_kmp(&s,k,next));

printf(n\n***showover***\nM);

}

intmain(){

show_index();

return0;

}

输入：

abcaabbabcabaacbacba

abcabaa

1

运行结果：

四、实验小结

五、教师评语

实验四二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法

3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念

1、二叉树：

2、递归遍历：

3、非递归遍历；

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。

#include<stdio.h>

#include<malloc.h>

#defineMAX20

typedefstructBTNode{/*节点结构声明*/

chardata;/*节点数据*/

structBTNode*lchild;

structBTNode*rchild;/*指针*/

}*BiTree;

voidcreateBiTree(BiTree*t){/*先序遍历创建二叉树*/

chars;

BiTreeq;

printf(K\npleaseinputdata:(exitfor#)”)；

s=getche();

if(s==*#'){*t=NULL;return;}

q=(BiTree)malloc(sizeof(structBTNode));

if(q==NULL){printf(uMemoryallocfailure!");exit(0);)

q->data=s;

*t=q;

createBiTree(&q->lchild);/*递归建立左子树*/

nrpatpRiTrpp(^q->rr.hi1d);/*递归建立右子树*/

}

voidPreOrder(BiTreep){/*先序遍历二叉树*/

if(p!=NULL){

printf(H%cn,p->data);

PreOrder(p->lchild);

PreOrder(p->rchild);

}

)

voidInOrder(BiTreep){/*中序遍历二叉树*/

if(p!=NULL){

InOrder(p->lchild);

printf("%cn,p->data);

InOrder(p->rchild);

}

}

voidPostOrder(BiTreep){/*后序遍历二叉树*7

if(p!=NULL)(

PostOrder(p->lchild);

PostOrder(p->rchild);

printfp->data);

}

}

voidPreorder_n(BiTreep){/*先序遍历的非递归算法*/

BiTreestack[MAX],q;

inttop=0,i;

for(i=0;i<MAX;if+)stack[i]=NULL;/*初始化栈*/

q=p；

while(q!=NULL){

printf("%cn,q->data);

if(q->rchild!=NULL)stack[top++]=c->rchild;

if(q->lchild!=NULL)q=q->lchild；

else

if(top>0)q=stack(--top];

elseq=NULL;

}

}

voidrelease(BiTreet){/*释放二叉树空间*7

if(t!=NULL){

release(t->lchild);

release(t->rchild);

free(t);

intmain(){

BiTreet=NULL;

createBiTree(&t);

printf(n\n\nPreOrderthetreeis:'*);

PreOrder(t);

printf(n\n\nTnOrdprfbptrppi55:'*);

InOrder(t);

printf(n\n\nPostOrderthetreeis:*');

PostOrder(t);

printf("\n\n先序遍历序歹I」(非递归):u);

Preorder_n(t);

release(t);

return0;

}

・运行程序

输入：

ABC##DE#G##F###

运行结果：

2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点

数），并在主函数中补充相应的调用验证正确性。

算法代码：

3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的

叶子结点数），并在主函数中补充相应的调用验证正确性。

算法代码:

4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。

算法代码：

选做实验：（代码可另附纸）

4、补充二叉树层次遍历算法。（提示：利用队列实现）

5、补充二叉树中序、后序非递归算法。

四、实验小结

五、教师评语

实验五图的表示与遍历

一、实验目的

1、掌握图的邻接矩阵和邻接表表示

2、掌握图的深度优先和广度优先搜索方法

3、理解图的应用方法

二、实验预习

说明以下概念

1、深度优先搜索遍历：

2、广度优先搜索遍历：

3、拓扑排序：

4、最小生成树：

5、最短路径:

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。

#include<stciio.h>

#defineN20

#defineTRUE1

#defineFALSE0

intvisited[N];

typedefstruct/*队列的定义*/

(

intdata[N];

intfront,rear;

}queue;

typedefstruct/*图的邻接矩阵*/

(

intvexnum,arcnjm;

charvexs[N];

intarcs(N][N];

}

graph;

voidcreateGraph(graph*g);/*建立一个无向图的邻接矩阵*/

voiddf(-inti,grAph*g);/*从第i个顶点出发深度优先搜索*/

voidtdfs(graph*g);/*深度优先搜索整个图*/

voidbfs(intk,graph*g);/*从第k个顶点广度优先搜索*/

voidtbfs(graph*g);/*广度优先搜索整个图*/

voidinit_visit();/*初始化访问标识数组*/

voidcreateGraph(graph*g)/*建立一个无向图的邻接矩阵*/

{inti,j;

charv;

g->vpxnnm=O;

g->arcnum=0;

i=0;

printf("输入顶点序列(以#结束):\nH);

while((v=getchar())!=*#')

(

g->vexs[i]=v;/*读入顶点信息*/

i++；

}

g->vexnum-i;/*顶点数目*/

for(i=0;i<g->vexnum;i++)/*邻接矩阵初始化*/

for(j=0;j<g->vexnum;j++)

g->arcs[i](j]=0;

printf("输入边的信息：\nn);

n

scanf(%cl,%d"z&L,&j);/*读入边i,j*/

while(i!=-l)/*读入i,j为一1时结束*/

(

g->arcs[i][j]=l;

g->arcs[j][i]=l;

scanf(%d"z&iz&j);

}

}

voiddfs(inti,graph*g)/*从第i个顶点出发深度优先搜索*/

(

intj;

Mn

printf(%czg->vexs(i]);

visited[i]=TRUE;

for(j=0;j<g->vexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j]))

dfs(j,g);

)

voidtdfs(graph*g)/*深度优先搜索整个图*/

(

inti;

printf(n\n从顶点SC开始深度优先搜索序列："，g->vexs[0]);

for(i=0;i<g->vexnum;i++)

if(visited[i]!=TRUE)

dfs(i,g);

}

voidbfs(intk,graph*g)/*从第k个顶点广度优先搜索*/

(

intizj;

queueqlist,*q;

q=&qlist;

q->rear=0;

q->front=0;

',,

printf(%c'/g->vexs[k]);

visited[k]=TRUE;

q->data[q->rear]=k;

q->rear=(q->rear+l)

while(q->rear!=q->front)

(

i=q->data[q->front];

q->front=(q->front+1)%N;

for(j=0;j<g->vexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j]))

(

printf(,'%cn,g->vexs[j]);

visited[j)=TRUE;

q->data[q->rear]=j;

q->rear=(q->rear+l)%N;

)

}

}

voidtbfs(graph*g)/*广度优先搜索整个图*/

(

inti;

printf(',\n从顶点告C开始广度优先搜索序列:"，g->vexs[0]);

for(i=0;i<g->vexnum;i++)

if(visited[i]!=TRUE)

bfs(i,g);

)

voidinit_visit()/*初始化访问标识数组*/

(

inti;

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

visited[i]=FALSE;

}

intmain()

graphga;

inti,j;

rrpatpGrAph;

printf("无向图的邻接矩阵：\nn);

for(i=0;i<ga.vexnum;i++)

for(j=0;j<ga.vexnum;j++)

nu

printf(%3dzga.arcs[i][j]);

printf(,,\nn);

}

init_visit();

tdf3(&ga);

init_visit();

tbfs(&ga);

return0;

}

■根据右图的结构验证实验，输入：

ABCDEFGH#

0,1

0,2

0,5

1,3

1,4

2,5

2,6

3,7

4,7

-1,-1

-运行结果：

2、阅读并运行下面程序，补充拓扑排序算法。

#include<stdio.h>

#include<malloc.h>

#defineN20

typedefstructedgenode{/大图的邻接表：邻接链表结点*/

intadjvex;/*顶点序号*/

structedgenode*next;/*下一个结点的指针*/

}edgenode;

typedefstructvnode{/*图的邻接表：邻接表*7

chardata;/*顶点信息*/

intind;/*顶点入度*/

structedgenode*link;/*指向令B接链表指针*/

}vnode;

voidcreateGraph_list(vnodeadjlist[],int*p)；/*建立有向图的邻接表*/

voidtopSort(vnodeg[],intn)；/*拓扑排序*/

voidcreateGraph_list(vnodeadjlist(]zint*p){/*建立有向图的邻接表*7

inti,j,n,e;

charv;

edgenode*3；

i=0;n=0;e=0;

printf("输入顶点序列(以#结束):\nH);

while((v=getchar())!=*#')

(

adjlist[i].data=v;/*读入顶点信息*/

adjlist[i].link=NULL;

adjlist[i].ind=0;

i++;

}

n=i;

*p=n;

/*建立邻接链表*/

printf(H\n请输入弧的信息(i=-l结束):i,j:\n'*);

scanf(n%d,%d"，&i,&j);

while(i!=-l){

s=(structedgenode*)malloc(sizeof(edgenode));

s->adjvex=j;

s->next=adjlist[i].link;

adjlist[i].link=s;

adjlist[j].ind++;/*顶点j的入度加1*/

e++;

scanf(%d",&j);

}

printf(“邻接表：“);

for(i=0;i<n;i++){/*输出邻接表*/

printf(H\n%c,%d:n,adjlist[i].data,adjlist[i].ind);

s=adjlist[i].link;

while(s!=NULL){

printfs->adjvex);

s=s->next;

}

}

)

voidtopSort(vnodeg[],intn){/*拓扑打E序*/

intmain(){

vnodeadjlist[N];

intn,*p;

p=&n;

createGraph_list(adjlist,p);

return0;

)

•根据输入，输出有向图的拓扑排序序列。并画出有向图。输入:

ABCDEF#

0,1

1/2

2,3

4,1

4,5

-1,-1

■运行结果：

3、阅读并运行下面程序。

#include<stdio.h>

#defineN20

#defineTRUE1

#defineINF32766/*邻接矩阵中的无穷大元素*/

#defineINFIN32767/*比无穷大元素大的数*/

typedefstruct

{/*图的邻接矩阵*/

intvexnum,arcnjm;

charvexs[N];

intarcs(N][N];

}

graph;

voidcreateGraph_w(graph*g,intflag);

voidprim(graph*g,intu);

voiddijkstra(graphg,intv);

voidshowprim();

voidshowdij();

/*建带权图的邻接矩阵，若flag为1则为无向图，flag为0为有向图*/

voidcreateGraph_w(graph*g,intflag)

(

inti,j,w;

charv;

g->vexnum=0;

g->arcnum=0;

i=0;

printf("输入顶点序列(以#结束)：\n”);

while((v=getchar())!=*#')

(

g->vexs[i]=v;/*读入顶点信息*/

i++；

}

g->vexnum=i;

for(i=0;i<6;i++)/*邻接矩阵初始化*/

for(j=0;j<6;j++)

g->arcs[i][j]=INF;

printf("输入边的信息：\n”)；

scanf(H%d,%d,%d",&i,&j,&w);/*读入边(二，j,w)*/

while(i!=-l)/*读入i为一1时结束*/

g->arcs[i][j]=w;

if(flag==l)

g->arcs[j][i]=w;

scanf(n%d,%d,%dn,&i,&j,&w);

}

}

voidprim(graph*g,intu)/*出发顶点u*/

(

int1cwccqT[N]znlnAPSb[N],i,j,kzmin;

for(i=0;i<g->vexnum;i++)/*求其他顶点到出发顶点u的权*/

(

lowcost(i]=g->arcs(u][i];

closest[i]=u;

}

lowcost[u]=0;

for(i=l;i<g->vexnum;i++)/*循环求最小生成树中的各条边*/

{min=INFIN;

for(j-0;j<g->vexnum;j++)/*选择得到一条代价最小的边*/

if(lowcost(j]!=0&&lowcost[j]<mm)

(

min=lowcost[j];

k=j；

}

H

printf((%c,%c)--%d\n",g->vexs[closest[k；]zg->vexs[k]zlowcost[k]);

/*输出该边*/

lowcostIkJ=0;/*顶点k纳入最小生成树*/

for(j=0;j<g->vexnum;j++)/*求其他顶点到顶点k的权*/

if(g->arcs[k][j]!=0&&g->arcs[k；[j]<lowcost[j])

{

lowcost[j]=g->arcs[k][j];

closest[j]=k;

}

}

)

voidprintPath(graphg,intstartVex,intEndVex)

(

intstack[N],top=0;/*堆栈*/

inti,k,j;

intflag[N];"输出路径顶点标志*/

k=EndVex;

for(i=0;i<g.vexnum;i++)flag[i]=0;

j=startVex;

n

printf(%c"zg.vexs[j]);

flag[j]=l;

stack[top++]=k;

while(top>0)/*找j到k的路径*/

(

for(i=0;i<g.vexnum;i++)

(

if(path[k][i]==1&&flag(i]==0)/*j到k的路径含有i顶点*/

(

if(g.arcs[j][i]!=INF)/*j到i的路径含有中间顶点*/

(

H

printf('*->%c(%d)zg.vexs[i],g.arcs[j][i]);

/*输出j到k的路径的顶点i*/

flag[i]=1;

j=i；