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

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

/学年第一学期

姓名：________________

学号：______________

班级：______________

指导教师：______________

数学与统计学院

2011

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

一、实验目的

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

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

二、实验预习

说明以下C语言中的概念

1、函数：

2、数组：

3、指针：

4、结构体

5、共用体

三、实验内容和要求

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

#include<>

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

intm;

for(m=2;01*01<=0;m++)

if(n%m=0)return0;

return1;

}

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

inti;printf("\nH)；

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

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

return0;

1

运行结果：

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

#include<>

#defineN10

intmain(){

inta[N]={0,1,2,3,4,5,6,7,8,9],i.temp;

printf(H\ntheoriginalArrayis:\n");

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

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

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

temp=a[i];

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

a[N-i-1]=temp;

)

printf("\nthechangedArrayis:\n");

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

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

return0;

运行结果:

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

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

找出来。

#incIude<>

#defineM3

#defineN4

intmain(){

inta[M][N],i,j,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[i][j]);

printf("\n")；

)

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

k=0;

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

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

k=j；

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

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

break;

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

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

)

return0;

)

运行结果：

4、调试程序：利用指针输出二维数组的元素。

#incIude<>

intmain(){

inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};

int*p;

for(p=a[0];p<a[0]+12;p++){

if((p_a[0])%4==0)printf("\n")；

printf("%4d",*p);

)

return0;

)

运行结果：

5、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、年龄、职业、教研室

四项，学生有姓名、年龄、专业、班级四项，编程输入人员的数据，再以表格输出。

#incIude<>

#defineN10

structstudent{

charname[8];/*姓名*/

intage;/*年龄*/

charjob;/*职业或专业，用s或t表示学生或教师*/

union{

intcIass;/*班级*/

charoffice[10];/*教研室*/

Jdepa;

}stu[N];

intmain(){

inti;intn;

printf("\n请输入人员数«10):\n");

scanf("%d"，&n);

for(i=0;i<n;i++){/*输入n个人员的信息*/

printf("\n请输入第%(1人员的信息：(nameagejobclass/office)\nH,i+1);

scanf("%s,%d,%c",stu[i].name,&stu[i].age,&stu[i].job);

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

scanf("%d",&stu[i].;

eIse

scanf("%sH,stu[i].;

)

printf("nameagejobcIass/officeM);

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

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

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

else

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

)

输入的数据：2

Wang19s99061

Li36tcomputer

运行结果：

四、实验小结

五、教师评语

实验一顺序表与链表

一、实验目的

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

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

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

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

二、实验预习

说明以下概念

1、线性表：

2、顺序表：

3、链表：

三、实验内容和要求

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

#include<>

#incIude<>

#defineERROR0

#defineOK1

#defineINIT_SIZE5/*初始分配的顺序表长度*/

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

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

typedefstructSqIist{

ElemType*sIist;/*存储空间的基地址*/

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

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

1SqIist;

intInitList_sq(SqIist*L);/**/

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

intListInsert_sq(SqIist*L,intiFElemTypee);/**/

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

intListDeIete_sq(SqIist*L,inti);/*删除第i个元素*/

intListLocate(SqIist*LtEIemTypee);/*查找值为e的元素*/

intInitList_sq(SqIist*L){

L->sIist=(EIemType*)maIIoc(INIT_SIZE*sizeof(EIemType));

if(!L->sIist)returnERROR;

L->Iength=0;

L->listsize=INIT_SIZE;

returnOK;

}/"InitList*/

intCreateList_sq(SqIist*L,intn){

ElemTypee;

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(SqIist*L){

inti;

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

printf("%5d"FL->sIist;

returnOK;

}/*PrintList*/

intListInsert_sq(SqIist*L,inti,EIemTypee){

intk;

if(i<1||i>L->Iength+1)

returnERROR;

if(L->Iength>=L->Iistsize){

L->sIist=(EIemType*)reaIIoc(L->sIist,

(INIT_SIZE+INCREM)*sizeof(ElemType));

if(!L->sIist)

returnERROR;

L->listsize+=INCREM;

)

for(k=L->Iength-1;k>=i-1;k—){

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

)

L->sIist[i-1]=e;

L->length++;

returnOK;

}/*ListInsert*/

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

intListDeIete_sq(SqIist*L,inti){

1

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

intListLocate(SqIist*L,EIemTypee){

}

intmain(){

SqIistsI;

intn,m,k;

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

scanf("%d",&n);

if(n>0){

printf("\n1-CreateSqIist:\n");

InitList_sq(&sI);

CreateList_sq(&sI,n);

printf("\n2-PrintSqlist:\n");

PrintList_sq(&sI);

printf("\npIeaseinputinsertlocationanddata:(Iocation,data)\n");

scanf("%d,%d",&m,&k);

Listlnsert_sq(&sI,m,k);

printf("\n3-PrintSqlist:\n");

PrintList_sq(&sI);

printf("\n")；

)

eIse

printf("ERROR");

return0;

)

运行结果

算法分析

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

删除算法代码：

运行结果

算法分析

查找算法代码:

运行结果

算法分析

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

#include<>

#include<>

#defineERROR0

#defineOK1

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

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

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

LinkListCreateList(intn);/**/

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

intGetElem(LinkListL,inti,EIemType*e);/**/

LinkListCreateList(intn){

LNode*p,*q,*head;

inti;

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

p=head;

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

q=(LinkList)maIIoc(sizeof(LNode));printf("inputdata%i:",i+1);

scanf("%d",&q->data);/*输入元素值*/

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

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

p=q;

)

returnhead;

}/*CreateList*/

voidPrintList(LinkListL){

LNode*p;

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

while(p!=NULL){

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

p=p->next;

}/*PrintList*/

intGetElem(LinkListL,inti,EIemType*e){

LNode*p;intj=1;

p=L->next;

while(p&&j<i){

p=p->next;j++;

)

if(!p||j>i)

returnERROR;

*e=p->data;

returnOK;

}/*GetElem*/

intmain(){

intn,i;ElemTypee;

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

printf(,rpleaseinputn:;/*输入单链表的元素个数*/

scanf&n);

if(n>0){

printf("\n1-CreateLinkList:\nn);

L=CreateList(n);

printf("\n2-PrintLinkList:\n");

PrintList(L);

printf("\n3-GetEIemfromLinkList:\n");

printf("inputi=");

scanf("%d",&i);

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

printf("No%iis%d",i,e);

eIse

printf("notexists");

}eIse

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<>

#incIude<>

#defineERROR0

#defineOK1

#defineSTACK,INT_SIZE10/*存储空间初始分配量*/

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

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

typedefstruct{

ElemType*base;

ElemType*top;

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

}SqStack;

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

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

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

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

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

intInitStack(SqStack*S){

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

if(!S->base)returnERROR;

S->top=S->base;

S->stacksize=STACK_INT_SIZE;

returnOK;

}/*lnitStack*/

intPush(SqStack*S,ElemTypee){

}/*Push*/

intPop(SqStack*S,ElemType*e){

}/*Pop*/

intCreateStack(SqStack*S){

inte;

if(InitStack(S))

printf("InitSuccess!\n");

else{

printf("InitFail!\nH);

returnERROR;

)

printf(ninputdata:(Terminatedbyinputingacharacter)\n");

n

while(scanf("%df&e))

Push(S,e);

returnOK;

}/*CreateStack*/

voidPrintStack(SqStack*S){

ElemTypee;

while(Pop(S,&e))

printf("%3d",e);

}/*Pop_and_Print*/

intmain(){

SqStackss;

printf("\n1"createStack\n");

CreateStack(&ss);

printf("\n2-Pop&Print\n");

PrintStack(&ss);

return0;

1

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

性

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

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

实现代码

验证

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

#include<>

#incIude<>

#incIude<>

#defineM20

#defineeIemtypechar

typedefstruct

elemtypestack[M];

inttop;

)

stacknode;

voidinit(stacknode*st);

voidpush(stacknode*st,eIemtypex);

voidpop(stacknode*st);

voidinit(stacknode*st)

(

st->top=0;

)

voidpush(stacknode*stteIemtypex)

(

if(st->top=M)

printf("thestackisoverfIow!\n");

else

(

st->top=st->top+1;

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

)

)

voidpop(stacknode*st)

(

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

eIseprintf("StackisEmpty!\n,5);

)

intmain0

chars[M];

inti;

stacknode*sp;

printf("createaemptystack!\n");

sp=maIIoc(sizeof(stacknode));

init(sp);

printf(ninputaexpression:\n");

gets(s);

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

(

if(s[i]=*(1)

push(sp,s[i]);

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

pop(sp);

)

if(sp->top-0)

printf("'('match')'!\n");

eIse

printf("'(*notmatch')'!\n");

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<>

#incIude<>

#defineMAXSIZE100

typedefstruct{

chardata[MAXSIZE];

intlength;

JSqString;

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

voidshow_strCompare();

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

/*求子串*/

voidshow_subString();

intstrCompare(SqString*s1,SqString*s2){

inti;

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

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

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

returns1->Iength-s2->Iength;

)

voidshow_strCompare(){

SqStrings1,s2;

intk;

printf("\n***showCompare***\n");

printf("inputstrings1:");

gets;

=strlen;

printf('*inputstrings2:");

gets;

=strlen;

if((k=strCompare(&s1,&s2))==0)

printf("s1=s2\n");

eIseif(k<0)

printf("s1<s2\n");

else

printf("s1>s2\n");

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

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

inti;

if(start<1||start>s->Iength||subIen>s->Iength-start+1){

sub->length=0;

}

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

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

sub->Iength=subIen;

)

voidshow_subString(){

SqStrings,sub;

intstart,subIen,i;

printf("\n***showsubString***\n");

printf(ninputstrings:;

gets;

二strlen;

printf("inputstart:");

scanf(n%d",&start);

printf("inputsubIen:");

scanf(u%d",&sublen);

strSub(&s,start,subIen,&sub);

if=0)

printf("ERROR!\n");

eIse{

printf("subStringis:");

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

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

)

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

)

intmain(){

intn;

do{

printf("\n---String---\n");

printf("1.strCompare\n");

printf("2.subString\n");

printf("0.EXIT\n,r);

printf(u\ninputchoice:");

scanf("%dH,&n);

getchar();

switch(n){

case1:show_strCompare();break;

case2:show_subString();break;

defauIt:n=0;break;

)

}while(n);

return0;

)

运行程序

输入：

1

student

students

2

ComputerDataStuctures

10

4

运行结果：

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

#include<>

#incIude<>

#defineMAXSIZE100

typedefstruct{

chardata[MAXSIZE];

intlength;

ISqString;

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

voidgetNext(SqString*t,intnext[]);

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

voidshow_index();

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

补充代码一.一

)

voidgetNext(SqString*t,intnext[]){

inti=0,j=-1;

next[0]=-1;

whiIe(i<t->Iength){

if((j=-1)||(t->data[i]==t->data[j])){

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

)eIse

j=next[j];

)

)

intindex_kmp(SqString*s,SqString*ttintstart,intnext[]){

补充代码.•・・・

voidshow_index(){

SqStrings,t;

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

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

printf("inputstrings:");

gets;

=strlen;

printf("inputstringt:n);

gets;

=strlen;

printf("inputstartposition:");

scanf(H%d",&k);

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

getNext(&t,next);

printf("KMP:\n");

printf(Hnext[]:");

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

printf("%3d"fnext[i]);

printf("\nn)；

n

printf(theresultofKMPis%d\n",index_kmp(&s,&trk,next));

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

)

intmain(){

show_index();

return0;

)

输入：

abcaabbabcabaacbacba

abcabaa

1

运行结果:

四、实验小结

五、教师评语

实验四二叉树

一'实验目的

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

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

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

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

二、实验预习

说明以下概念

1、二叉树：

2、递归遍历：

3、非递归遍历：

4、层序遍历：

三、实验内容和要求

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

#include<>

#incIude<>

#defineMAX20

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

chardata;/*节点数据*/

structBTNode*lchiId;

structBTNode*rchiId;/*指针*/

}*BiTree;

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

chars;

BiTreeq;

printf("\npIeaseinputdata:(exitfor#)");

s二getche();

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

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

if(q==NULL)(printf("MemoryallocfaiIure!");exit(0);}

q->data=s;

*t=q；

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

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

)

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

if(p!=NULL){

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

PreOrder(p->lchiId);

PreOrder(p->rchiId);

)

)

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

if(p!=NULL){

InOrder(p->IchiId);

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

InOrder(p->rchiId)

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

if(p!=NULL){

PostOrder(p->lchiId);

PostOrder(p->rchiId);

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

)

)

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

BiTreestack[MAX],q;

inttop=0,i;

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

q=P；

while(q!=NULL){

printfq->data);

if(q->rchiId!二NULL)stack[top++]=q->rchiId;

if(q->IchiId!=NULL)q=q->lchiId;

eIse

if(top>0)q=stack[—top];

elseq=NULL;

)

)

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

if(t!二NULL){

reIease(t->IchiId);

reIease(t->rchiId);

free(t);

}

)

intmain(){

BiTreet=NULL;

createBiTree(&t);

printf("\n\nPreOrderthetreeis:");

PreOrder(t);

printf("\n\nInOrderthetreeis:");

InOrder(t);

printf("\n\nPostOrderthetreeis:");

PostOrder(t);

printf("\n\n先序遍历序列(非递归)：”)；

Preorder_n(t);

reIease(t);

return0;

)

运行程序

输入：

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

运行结果:

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

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

算法代码：

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

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

算法代码：

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

算法代码:

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

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

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

四、实验小结

五、教师评语

实验五图的表示与遍历

一、实验目的

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

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

3、理解图的应用方法

二、实验预习

说明以下概念

1、深度优先搜索遍历：

2、广度优先搜索遍历：

3、拓扑排序：

4、最小生成树：

5、最短路径：

三、实验内容和要求

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

#incIude<>

#defineN20

#defineTRUE1

#defineFALSE0

intvisited[N];

typedefstruct/*队列的定义*/

intdata[N];

intfront,rear;

1queue;

typedefstruct/*图的邻接矩阵*/

intvexnum,arcnum;

charvexs[N];

intarcs[N][N];

)

graph;

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

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

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

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

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

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

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

{inti,j;

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<g->vexnum;i++)/*邻接矩阵初始化*/

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

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

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

scanf(',%d,%d,\&i,&j);/*读入边i,j*/

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

(

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

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

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

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

(

intj;

printfg->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从顶点%0开始深度优先搜索序列g->vexs[0]);

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

if(visited[i]!=TRUE)

dfs(i,g);

)

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

(

inti,j;

queueqIist,*q;

q二&qlist;

q->rear=0;

q->front=0;

printfg->vexs[k]);

visited[k]=TRUE;

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

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

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("%c”,g->vexs[j]);

visited[j]=TRUE;

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

q->rear=(q->rear+1)%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;

createGraph(&ga);

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

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

for(j=O;j<;j++)

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

printf("\n")；

init_visit();

tdfs(&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、阅读并运行下面程序，补充拓扑排序算法。

#incIude<>

#incIude<>

#defineN20

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

intadjvex;/*顶点序号*/

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

}edgenode;

typedefstructvnode{/*图的邻接表:邻接表*/

chardata;/*顶点信息*/

intind;/*顶点入度*/

structedgenode*1ink;/*指向邻接链表指针*/

}vnode;

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

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

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

inti,j,n,e;

charv;

edgenode*s;

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

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

whiIe((v=getchar())!='#')

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

adjlist[i].Iink=NULL;

adjIind=O;

i++；

)

n=i;

*P=n;

/*建立邻接链表*/

printf("\n请输入弧的信息(i=T结束):i,j：\n");

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

while(i!=-1){

s二(structedgenode*)maIIoc(sizeof(edgenode));

s->adjvex=j;

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

adjIist[i].Iink=s;

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

e++;

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

)

printf(“邻接表：”)；

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

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

s=adjIist[i].link;

whiIe(s!二NULL){

printf("->%d",s->adjvex);

s=s->next;

)

)

)

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

intmain(){

vnodeadjIist[N];

intn,*p;

p二&n;

createGraph_list(adjIist,p);

return0;

)

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

ABCDEF#

0.1

1,2

2,3

4.1

4.5

运行结果:

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

#include<>

#defineN20

#defineTRUE1

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

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

typedefstruct

{/*图的邻接矩阵*/

intvexnum,arcnum;

charvexs[N];

intarcs[N][N];

)

graph;

voidcreateGraph_w(graph*g,intfIag);

voidprim(graph*g,intu);

voiddijkstra(graphg,intv);

voidshowprim();

voidshowdij();

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

voidcreateGraph_w(graph*g,intfIag)

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;

prin"("输入边的信息：\n");

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

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

(

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

if(flag=1)

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

scanf("%df%df%d",&i,&j,&w);

}

1

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

intIowcost[N],cIosest[N],i,j,k,min;

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

(

Iowcost[i]=g->arcs[u][i];

closest[il=u;

)

Iowcost[u]=0;

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

{min=INFIN;

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

if(Iowcost[j]!=0&&Iowcost[j]<min)

(

min=Iowcost[j];

k二j；

)

printf("(%c,%c)-%d\n",g->vexs[cIosest[k]],g->vexs[k],Iowcost[k]);

/*输出该边*/

lowcost[k]=0;/*顶点k纳入最小生成树*/

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

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

(

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

cIosest[j]=k;

voidprintPath(graphg,intstartVex,intEndVex)

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

inti,k,j;

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

k二EndVex;

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

j=startVex;

n

printf(%c"f[j]);

flag[j]=1;

stack[top++]=k;

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

(

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

(

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

(