数据结构课程设计

数据结构课程设计实习报告

班 级： 学生姓名： 学 号：

2011.6

1

目 录

一、需求分析 ................................................................................................. 错误！未定义书签。 二、逻辑设计 ................................................................................................................................... 2 三、详细设计 ................................................................................................................................... 5 四、程序编码 ................................................................................................................................... 9 五、程序调试与测试 ..................................................................................................................... 35 六、结果分析 ................................................................................................................................. 39

2

一、 需求分析：

1、 程序一：单链表的应用

（1）要求生成线性表时，可以键盘上读取元素。通过在键盘上输入的数据构造成单链表，进而对构造成的单链表进行插入、删除、遍历等操作的实现。

（2）限制条件是要求在生成线性表的时候，线性表中的元素是从键盘上输入而不是自动生成，这样就可以对自己想要进行的元素序列进行各种操作。

2、 程序二：表达式求值

表达式求值的程序是要求从键盘上输入一个以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。设计的程序是中缀表达式求值，即直接将表达式以一般的序列输入，从而得出结果。

3、 程序三：二叉排序树的操作（创建，插入，查询，删除）

二叉排序树的程序是通过构造程序来实现对二叉树的创建、插入、查询、删除等基本操作，从键盘上输入一序列的数据构造成二叉排序树，再对构建的二叉排序树进行插入、查询、删除等操作。

4、 程序四：二叉树的遍历

二叉树的遍历程序是通过构造一棵二叉树来实现对二叉树的前序遍历、中序遍历、后序遍历以及求出二叉树的叶子结点的个数。

5、 程序五：最小生成树

最小生成树是通过输入一个图，此图表示了各个顶点的信息以及边上的权值，用最小生成树的程序可以得出最短的路径，此路径把所有的顶点以最经济的方式联系起来，即构造成了最小的生成树。

6、 程序六：拓扑排序：

拓扑排序程序是一个建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，实现图的拓扑排序。要求选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。 7、 程序七：图的建立与遍历

该程序是一个建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，实现图的两种遍历。要求选择邻接表作为图的存储结构模拟整个过程，并输出图的深

1

度优先遍历和广度优先遍历。

二、 逻辑设计：

表达 式 求 值

单链表 二叉树 二叉排序树 拓扑排序 图的建立与遍历 最小生成树 主函数main

图一：课程设计总体分析

单链表的输出 删除 主函数 单链表的创建 插入 单链表的应用 查找 图二、单链表的功能

2

比较 计算 判断运算符和运算取栈顶元素 判断空 初始化堆栈 主函数 进栈 表达式求值 出栈 图三：表达式逻辑分析

菜单 中序遍历 插入 删除 查找结点 主函数 创建二叉树 二叉排序树 图四：二叉排序树逻辑分析

3

主函数 创建二叉树 菜单选择 二叉树的遍历 叶子结点数 后序 前序 中序

图五：二叉树遍历的逻辑分析

输出 排序 主函数 建立邻接表存储 拓扑排序 图六：拓扑排序的逻辑分析

主函数 权值比较 建立邻接矩阵 最小生成树 图七：最小生成树的逻辑分析

主函数 建立有向图或无向图 图的建立与遍历 广度优先遍历 深度优先遍历

4

图八：图的建立与遍历

三、详细设计：

图九：单链表的插入 图十：单链表的删除

5

图十一：表达式的求值（入栈）

图十二：表达式计算

图十三：二叉排序树的插入 图十四：二叉排序树的删除

6

图十五：二叉树前序遍历 图十六：二叉树中序遍历

图十七：二叉树后序遍历

7

图二十：最小生成树

图十九：拓扑排序

8

图十八：创建二叉树

四、程序编码：

主函数main

#include #include #include #include \#include \#include \#include \#include \#include \#include \void main() {

int n;

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ do {

printf(\请选择所要操作的项目：\ scanf(\ getchar(); switch(n) {

case 1:

linemenu(); break; case 2:

bitreemenu(); break; case 3:

expressionmenu(); break; case 4: BSTmenu();

9

break; case 5:

mintreemenu(); break; case 6:

TopSortmenu(); break; case 7:

graphmenu(); break; case 0:

exit(0); default :

printf(\输入错误！\\n\\n\ }

}while(1); }

单链表头文件： #ifndef _line_h #define _line_h #define NULL 0

typedef struct LNode{ int data;

struct LNode *next; }LNode,*LinkList;

void creat(LinkList &L); void Insert(LinkList &L); void Delete(LinkList &L); void Print(LinkList L); void Inite(LinkList &L); void linemenu(); #endif

单链表源文件

#include #include #include #include \

void Inite(LinkList &L)//初始化链表 {

L=NULL; }

void creat(LinkList &L)//创建链表 {

10

int n,i;

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; if(!L) {

printf(\存储分配失败\ exit(0); }

printf(\请输入链表长度:\ scanf(\ LinkList p=L,q; for(i=0;i

printf(\请输入第%d个数据: \

q=(LinkList)malloc(sizeof(LNode)); scanf(\ p->next=q; p=q; }

p->next=NULL; }

void Insert(LinkList &L)//插入 {

int z,i=0;

LinkList p=L,s;

printf(\请输入您要插入的位置：\ scanf(\ while(p&&i

p=p->next; i++;

}

if(!p) {

printf(\插入位置不对!\\n\ exit(0); }

s=(LinkList)malloc(sizeof(LNode)); printf(\插入的元素为：\ scanf(\ s->next=p->next; p->next=s;

11

}

void Delete(LinkList &L)//删除 {

int z,i=0;

LinkList p=L,q;

printf(\请输入删除元素的位置:\ scanf(\

while(p->next&&i

p=p->next; i++; }

if(!p->next) {

printf(\删除位置不对!\\n\ exit(0); }

q=p->next;

printf(\删除的元素为:%d\\n\ p->next=q->next; free(q); }

void Print(LinkList L)//遍历 {

LinkList p=L; if(!L) {

printf(\链表为空\\n\ exit(0); }

printf(\当前链表全部元素为:\ while(p->next) {

p=p->next;

printf(\ }

printf(\}

单链表的菜单

#include #include #include \void linemenu() {

12

LinkList L; Inite(L); int i; while(1) {

printf(\ printf(\你输入的是1功能: 单链表操作\\n\ printf(\ printf(\创建链表请按 1 ************\\n\ printf(\遍历链表请按 2 ************\\n\ printf(\插入元素请按 3 ************\\n\ printf(\删除元素请按 4 ************\\n\ printf(\返回主菜单请按 0 ************\\n\ printf(\请输入您的选择(1,2,3,4,0)：\ scanf(\ if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1)creat(L); else if(i==3)Insert(L); else if(i==2)Print(L); else if(i==4)Delete(L); else {

printf(\输入选择错误！请重新输入\\n \ } } }

表达式求值的头文件 #ifndef _STACK_H #define _STACK_H #define N 100

typedef struct Stack

13

{

char *Data; int Top; }Stack;

void InitStack(Stack &s); void Push(Stack &s,char e); void Pop(Stack &s,char e); char Pop(Stack &s); int IsEmpty(Stack s); int IsFull(Stack s); char CalExp(char exp[]); void expressionmenu(); #endif

表达式的源文件 #include #include #include \

void InitStack(Stack &s) {

s.Data = (char*)malloc(N*sizeof(char)); s.Top = -1; }

void Push(Stack &s,char e) {

if(s.Top==N) {

printf(\栈溢出\ } else {

s.Top++;

s.Data[s.Top] = e; } }

void Pop(Stack &s,char e) {

if(s.Top< 0 ) {

printf(\栈为空\ } else {

e = s.Data[s.Top]; s.Top--;

14

} }

char Pop(Stack &s) {

char e;

if(s.Top< 0 ) {

printf(\栈为空\ } else {

e = s.Data[s.Top]; s.Top--; }

return e; }

int IsEmpty(Stack s) {

if(s.Top< 0 ) return 1; return 0; }

int IsFull(Stack s) {

if(s.Top==N ) return 1; return 0; }

int IsOperator(char ch) {

if(ch=='+' || ch =='-' || ch =='*'||ch=='/'||ch=='#') return 1; return 0; }

char Calculate(char a, char oper,char b) {

int c; int aa,bb; aa = atoi(&a); bb = atoi(&b); switch(oper) {

case '+':

15

c = aa + bb; break; case '-':

c = bb - aa; break; case '*':

c = aa * bb; break; case '/':

c = bb / aa; break; }

return c+'0'; }

char CalExp(char exp[]) {

Stack s; char a,b,c; int cur = 0; InitStack(s);

while(exp[cur] != '\\0') {

if(IsOperator(exp[cur])) {

a = Pop(s); b = Pop(s);

c = Calculate(a, exp[cur],b); Push(s,c); } else {

Push(s,exp[cur]); }

cur++; }

return Pop(s); }

表达式的菜单文件 #include \#include #include

void expressionmenu() {

16

}

char exp[N]; int i;

char value; while(1) {

printf(\ printf(\你输入的是1功能: 表达式求值\\n\ printf(\

printf(\输入表达式请按 1 ************\\n\ printf(\表达式结果请按 2 ************\\n\ printf(\返回主菜单请按 0 ************\\n\ scanf(\ if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1) {

printf(\请输入后缀表达式:\ scanf(\ }

else if(i==2) {

value = CalExp(exp);

printf(\表达式的结果为：\\n\

printf(\ } else {

printf(\输入选择错误！请重新输入\\n \ } }

17

二叉树的头文件 #ifndef _BITREE_H #define _BITREE_H

typedef char TreeData; //结点数据类型 typedef struct BinTreeNode { //结点定义

TreeData data;

struct BinTreeNode * leftChild, * rightchild; } BinTreeNode,* BinTree;

BinTree creatbitree(BinTree &T); void PreOrder(BinTree &T); void InOrder(BinTree &T); void PostOrder(BinTree &T); int LeafCount(BinTree &T); void bitreemenu(); #endif

二叉树的源文件 #include #include #include #include \#define NULL 0

BinTree creatbitree(BinTree &T) {

TreeData ch;

scanf(\ if(ch=='#') T=NULL; else {

if(!(T=(BinTreeNode*)malloc(sizeof(BinTreeNode)))) printf(\ T->data=ch;

creatbitree(T->leftChild); creatbitree(T->rightchild); }

return T; }

int LeafCount(BinTree &T) {

int sum=0,m,n; if(T){

if((!T->leftChild)&&(!T->rightchild)) sum++;

18

m=LeafCount(T->leftChild); sum+=m;

n=LeafCount(T->rightchild); sum+=n; }

return sum; }

void PreOrder(BinTree &T) {

if(T) {

printf(\ PreOrder(T->leftChild); PreOrder(T->rightchild); } }

void InOrder(BinTree &T) {

if(T) {

InOrder(T->leftChild); printf(\ InOrder(T->rightchild); } }

void PostOrder(BinTree &T) {

if(T) {

PostOrder(T->leftChild); PostOrder(T->rightchild); printf(\ } }

二叉树的菜单文件 #include #include #include \#include void bitreemenu() {

BinTree T; int sum,i; while(1)

19

{

printf(\printf(\你输入的是2功能: 二叉树基本操作\\n\\n\\n\printf(\printf(\二叉树的创建\\n\\n\printf(\二叉树的前序遍历\\n\\n\printf(\二叉树的中序遍历\\n\\n\printf(\二叉树的后序遍历\\n\\n\printf(\叶子结点个数 \\n\\n\printf(\退出程序\\n\\n\\n\\n\scanf(\if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1) {

printf(\请输入节点信息 :\ T=creatbitree(T); }

else if(i==3) {

printf(\中序遍历为:\ InOrder(T); }

else if(i==2) {

printf(\前序遍历为:\ PostOrder(T); }

else if(i==4) {

printf(\后序遍历为:\ PostOrder(T); }

20

else if(i==5) {

sum=LeafCount(T);

printf(\叶子节点个数：%d\ } else

printf(\输入选择错误！请重新输入\\n \ } }

二叉排序树头文件 #ifndef _BSTREE_H #define _BSTREE_H typedef struct Node{ int key;

struct Node *lchild,*rchild; }Node,*Tree;

void deleteBST(Tree &T,int data); Tree searchBST(Tree root,int data); void InsertBST(Tree &T,int k);

void searchxBST(Tree root,int data); void creatBST(Tree &T); void PrintBST(Tree &T); void BSTmenu(); #endif

最小生成树的头文件 #ifndef _mintree_h #define _mintree_h

#define MaxVertexNum 20 //最大顶点数为20 #define INF 32767 typedef struct {

int vexs[ MaxVertexNum]; //顶点表

int AdjMatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵，即边表 int vexnum,arcnum;//顶点数和边树

}MGragh; //MGragh是以邻接矩阵存储的图类型 typedef struct {

int begin,end;//边顶点序号 int cost;//边上的权值 }TreeEdge;

void CreatMGragh(MGragh &G); void Prim(MGragh &G); void mintreemenu(); #endif

21

最小生成树的源文件 #include #include \

void CreatMGragh(MGragh &G)//建立无向网G的邻接矩阵 {

int i,j,k,x;

printf(\请输入顶点数和边数（输入格式：顶点数,边数）：\\n\ scanf(\ for(i=0;i

printf(\请输入%d条边，格式：行下标,列下标,边上的权值\\n\ for(k=0;k

scanf(\ G.AdjMatrix [i][j]=x;

G.AdjMatrix[j][i]=G.AdjMatrix[i][j]; } }

void Prim(MGragh &G) {

int n=G.vexnum;

int lowerCost[MaxVertexNum],mincost=0,closeVertex[MaxVertexNum]; TreeEdge close[MaxVertexNum]; int i,j,k,sum=0; for(i=1;i

lowerCost[i]=G.AdjMatrix[0][i]; closeVertex[i]=0; }

lowerCost[0]=0; closeVertex[0]=0; for(i=1;i

mincost=INF; j=1;k=1; while(j

if (lowerCost[j]!=0 && lowerCost[j]

mincost=lowerCost[j]; k=j; }

j++;

22

}

close[i-1].begin=closeVertex[k]; close[i-1].end=k;

close[i-1].cost=mincost; sum=sum+mincost; lowerCost[k]=0; for(j=1;j

if(G.AdjMatrix[k][j]

lowerCost[j]=G.AdjMatrix [k][j];closeVertex[j]=k; } }

printf(\最小生成树如下图所示：\\n始点\\t终点\\t权值\\t\\n\ for(i=0;i

printf(\ }

printf(\最小生成树的总权和为%d\\n\}

最小生成树的菜单文件 #include #include \#include void mintreemenu() {

int i; MGragh G;

printf(\ printf(\你输入的是5功能: 最小生成树基本内容\\n\

printf(\ printf(\创建无向图\\n\\n\

printf(\算法生成树\\n\\n\ printf(\退出程序\\n\\n\\n\\n\ while(1) {

printf(\请选择所要操作的项目：\ scanf(\ if(i==0)break; else if(i==1)

CreatMGragh(G); else if(i==2)Prim(G); else

printf(\输入选择错误！请重新输入\\n \ }

23

if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\ printf(\ } }

拓扑排序的头文件 #ifndef _TOPSORT_H #define _TOPSORT_H #define MaxVex 20 typedef struct node {

int vexw;

struct node*next; }JD;//邻接表结点 typedef struct tnode {

int vex; int in;

struct node*link; }TD;//表头结点

typedef struct ALGraph {

TD header[MaxVex]; int vexnum; int arcnum; }ALGraph;

typedef struct Stack2 {

int*base; int top; }Stack2;

void InitStack(Stack2 &s); int Empty(Stack2 s);

void Push(Stack2 &s,int e);

图\\n\\n\

退出程序。\\n\\n\\n\\n\24

void Pop(Stack2 &s,int &e); void CreateAlGraph(ALGraph &G); void TopoSort(ALGraph G); void TopSortmenu(); #endif

拓扑排序的源文件 #include #include #include\

void InitStack(Stack2 &s) {

s.base=(int*)malloc(MaxVex*sizeof(int)); s.top=-1; }

int Empty(Stack2 s) {

if(s.top==-1) return 1; return 0; }

void Push(Stack2 &s,int e) {

s.base[++s.top]=e; }

void Pop(Stack2 &s,int &e) {

e=s.base[s.top--]; }

void CreateAlGraph(ALGraph &G) {

int i,k; int v1,v2;

int point1,point2; JD*p;

printf(\输入有向图顶点个数：\\n\ scanf(\

printf(\输入有向图的弧个数：\\n\ scanf(\

printf(\输入图的顶点信息:\\n\ for(i=0;i

scanf(\ }

25

for(i=0;i

G.header[i].link=NULL; G.header[i].in=0; }

for(i=0;i

printf(\输入第%d条弧的弧尾和弧头:\ scanf(\ k=0;

while(k

if(v1==G.header[k].vex) {

point1=k; break; } k++; } k=0;

while(k

if(v2==G.header[k].vex) {

point2=k; break; } k++; }

G.header[point2].in++; p=(JD*)malloc(sizeof(JD)); p->vexw=point2;

p->next=G.header[point1].link; G.header[point1].link=p; } }

void TopoSort(ALGraph G) {

int i,e,n=0; JD*p; Stack2 s; InitStack(s);

for(i=0;i

26

if(G.header[i].in==0) Push(s,i); }

while(!Empty(s)) {

Pop(s,e);

printf(\ n++;

p=G.header[e].link; while(p) {

G.header[p->vexw].in--; if(G.header[p->vexw].in==0) Push(s,p->vexw); p=p->next; } }

if(n

printf(\该图为有向有环图。\ } }

拓扑排序的菜单文件 #include #include #include\void TopSortmenu() {

ALGraph G; int i; while(1) {

printf(\ printf(\你输入的是6功能: 拓扑排序基本内容\\n\

printf(\ printf(\拓扑排序\\n\\n\\n\ printf(\创建有向图\\n\\n\ printf(\拓扑排序\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ scanf(\ if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\

27

printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1)CreateAlGraph(G); else if(i==2) {

printf(\拓扑排序为：\ TopoSort(G); } else

printf(\输入选择错误！请重新输入\\n \ } }

图的建立与遍历的头文件 #ifndef _GRAPH_H #define _GRAPH_H

#define MAX_VERTEX_NUM 20 #define maxqsize 20 typedef struct {

int*base; int front; int rear; }SqQueue;

typedef struct {

int vexs[MAX_VERTEX_NUM];

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum; //图的顶点数 int arcnum; //图的弧数 }MGraph;

void InitQueue(SqQueue &Q); int EmptyQueue(SqQueue Q);

void EnQueue(SqQueue &Q,int e); void DeQueue(SqQueue &Q,int &e);

void CreateGraph(MGraph &G,int kind); void PrintGraph(MGraph G);

void BFSTraverse(MGraph G,int *visited);//图广度遍历

28

void DFSTraverse(MGraph G,int *visited);//图深度遍历 void graphmenu(); #endif

图的建立与遍历的源文件 #include #include #include\

void InitQueue(SqQueue &Q) {

Q.base=(int*)malloc(maxqsize*sizeof(int)); Q.front=Q.rear=0; }

void EnQueue(SqQueue &Q,int e) {

if((Q.rear-Q.front+1)%maxqsize==0) {

printf(\队列已满。\ return; }

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%maxqsize; }

void DeQueue(SqQueue &Q,int &e) {

if(Q.front==Q.rear) {

printf(\队列以空\ return; }

e=Q.base[Q.front];

Q.front=(Q.front+1)%maxqsize; }

int EmptyQueue(SqQueue Q) {

if(Q.front==Q.rear) return 1; return 0; }

void CreateGraph(MGraph &G,int kind) {

int i; int j; int k; int v1,v2;

29

int point1=-1,point2=-1;

printf(\输入图的顶点数:\\n\ scanf(\ printf(\输入图的弧数:\\n\ scanf(\

printf(\输入图的顶点信息:\\n\ for(i=0;i

scanf(\ }

for(i=0;i

if(i==j)G.arcs[i][j]=0; else G.arcs[i][j]=-1; } if(kind==1) {

for(i=0;i

printf(\输入第%d条弧的弧尾和弧头:\ scanf(\ k=0;

while(k

if(v1==G.vexs[k]) {

point1=k; break; } k++; } k=0;

while(k

if(v2==G.vexs[k]) {

point2=k; break; } k++; }

if(G.arcs[point1][point2]==-1) G.arcs[point1][point2]+=2;

30

else

G.arcs[point1][point2]++; } }

else if(kind==2) {

for(i=0;i

printf(\输入弧的两端顶点信息:\ scanf(\ k=0;

while(k

if(v1==G.vexs[k]) {

point1=k; break; } k++; } k=0;

while(k

if(v2==G.vexs[k]) {

point2=k; break; } k++; }

if(G.arcs[point1][point2]==-1) G.arcs[point1][point2]+=2; else

G.arcs[point2][point1]++; if(G.arcs[point2][point1]==-1) G.arcs[point2][point1]+=2; else

G.arcs[point2][point1]++; } } else {

printf(\输入的图的类型不正确\\n\ return;

31

} }

void PrintGraph(MGraph G) {

int i; int j; int k=0;

for(i=0;i

printf(\ k++;

if(k%G.vexnum==0)putchar('\\n'); } }

void DFS(MGraph G,int *visited,int i) {

int j;

printf(\ visited[i]=1;

for(j=0;j

if(G.arcs[i][j]>0 && visited[j]==0) DFS(G,visited,j); }

void DFSTraverse(MGraph G,int *visited) {

int i;

for(i=0;i

void BFS(MGraph G,int *visited,int i) {

int j,k; SqQueue Q; int e;

int flag=0; InitQueue(Q);

printf(\ visited[i]=1;

for(j=0;j

if(G.arcs[i][j]>0 && visited[j]==0) EnQueue(Q,j);

32

while(!EmptyQueue(Q)) {

DeQueue(Q,e);

printf(\ visited[e]=1;

for(j=0;j

if(G.arcs[e][j]>0 && visited[j]==0) {

k=Q.front;

while(k!=Q.rear) {

if(j==Q.base[k]) {

flag=1; break; }

k=(k+1)%maxqsize; }

if(flag==0) {

EnQueue(Q,j); }

flag=0; } } }

void BFSTraverse(MGraph G,int *visited) {

int i;

for(i=0;i

图的建立与遍历的菜单文件 #include #include #include \void graphmenu() {

MGraph G; int kind,i;

int visited[MAX_VERTEX_NUM];

printf(\ printf(\有向图或无向图：\\n\

33

printf(\

printf(\输入图的类型\\n(输入1为有向图,输入2为无向图,输入0为退出):\\n\ scanf(\ while(kind!=0) {

CreateGraph(G,kind); if(kind==1) {

printf(\输出有向图为：\\n\ PrintGraph(G);

for(i=0;i

for(i=0;i

}

if(kind==2) {

printf(\输出无向图为：\\n\ PrintGraph(G);

for(i=0;i

printf(\有向图广度遍历：\

for(i=0;i

printf(\请选择：\ scanf(\ }

if(kind==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\

34

}

printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\}

五、 程序调试与测试：

图二十一：主菜单

图二十二：单链表建立

35

图二十三：单链表的插入

图二十四：表达式求值

图二十五：二叉树的建立

图二十六：二叉树的前序、中序、后序遍历

36

图二十七：二叉树的叶子节点个数

图二十八：二叉排序树的建立

图二十九：二叉排序树的中序遍历

37

图三十：最小生成树

图三十一：拓扑排序

38

本文来源：https://www.bwwdw.com/article/2mhg.html