《数据结构》课程实验指导书

数据结构课程实验指导书线性表的插入和删除实验一实验目的（1）熟练掌握线性表的逻辑特征。（2）熟练掌握顺序表的表示方法，存储结构及其基本操作的实现。实验要求（1）顺序表的插入和删除操作，掌握数据元素前移、后移的操作技巧。（2）单链表的插入和删除操作，包括有序（递减或递增）单链表的插入和删除操作。插入操作要求表中不允许有关键字相同的数据元素。实验内容（1）设计一个顺序表，实现下列基本运算：①初始化线性表：②在第1个元素前插入一个元素e：③删除第1个元素；（2）设计一个单链表，实现下列基本运算：①生成一个带头结点的单链表：②在第1个元素前插入一个元素e；③删除第1个元素。算法实现程序（源程序代码）（1）顺序表的基本操作#include #define MAX151/顺序表的定义typedef struct(int elem[MAX];int length;}Sqlist,void Initlist sq(Sqlist &L),void Listlnsert_sq(Sqlist &L,int i, int e);void ListDel _sq(Sqlist &L,int i, int &e),void print_sq(Sqlist L);II函数的定义void Initlist_sq(Sqlist &L)L.length =0;1void Listlnsert_sq(Sqlist &L,int i, int e)(int *p,*q,if(iL.length +1)return,q=&L.elem[i-1]；1插入位置for(p=&L.elem[L.length -1];p>=q;-p )*(p+1)=*p;*q=e,++L.length ;return,1void ListDel sq(Sqlist &L,inti, int &e)1

1 数据结构课程实验指导书 实验一 线性表的插入和删除 实验目的 （1）熟练掌握线性表的逻辑特征。 （2）熟练掌握顺序表的表示方法，存储结构及其基本操作的实现。 实验要求 （1）顺序表的插入和删除操作，掌握数据元素前移、后移的操作技巧。 （2）单链表的插入和删除操作，包括有序（递减或递增）单链表的插入和删除操作。插入操作要 求表中不允许有关键字相同的数据元素。 实验内容 （1）设计一个顺序表，实现下列基本运算：①初始化线性表；②在第 1 个元素前插入一个元素 e； ③删除第 1 个元素； （2）设计一个单链表，实现下列基本运算：①生成一个带头结点的单链表；②在第 1 个元素前插 入一个元素 e；③删除第 1 个元素。 算法实现程序（源程序代码） （1）顺序表的基本操作 #include #define MAX 15 //顺序表的定义 typedef struct{ int elem[MAX]; int length; }Sqlist; void Initlist_sq(Sqlist &L); void ListInsert_sq(Sqlist &L,int i, int e); void ListDel_sq(Sqlist &L,int i, int &e); void print_sq(Sqlist L); // 函数的定义 void Initlist_sq(Sqlist &L){ L.length =0; } void ListInsert_sq(Sqlist &L,int i, int e){ int *p,*q; if(iL.length +1) return; q=&L.elem[i-1]; //插入位置 for(p=&L.elem[L.length -1];p>=q;-p ) *(p+1)=*p; *q=e; ++L.length ; return; } void ListDel_sq(Sqlist &L,int i, int &e){

if(iL.length )return,e=L.elem[i-1];for(int j=i.jstructNODEint data,NODE *next;;voidprint(NODE*&head)；I/遍历int data[6]=(25,41,17,98,5,6);voidSetup_L(NODE*&head,intn);I/生成单链表voidInsertL(NODE*&head, intI, int e),//插入void Delete_L(NODE *&head, int I,int&e),I删除void mainOtNODE *L;Setup_ L(L,6),2

2 if(iL.length ) return; e=L.elem[i-1]; for(int j=i;j struct NODE{ int data; NODE *next; }; void print(NODE *&head); //遍历 int data[6]={25,41,17,98,5,6}; void Setup_L(NODE *&head,int n); //生成单链表 void Insert_L(NODE *&head, int I, int e); //插入 void Delete_L(NODE * &head, int I,int &e); //删除 void main(){ NODE *L; Setup_L(L,6);

print(L);Insert_L(L,7,50);print(L);int x,Delete L(L,0,x);printf("X=-",x,"In"),print(L),void print(NODE *&head)NODE*p;p=head->next ;while(p):printf(p->data,"，");//输出元素值p=p->next;//后移指针1print("n");/void Setup_L(NODE * &head,int n)(NODE *q,*p;head=(NODE*)newNODE;head->next=NULL;I/先建立一个带头结点的单链表q=head;for(int i=0;idata=data[i];,q->next=p;q=p;//插入到表头q->next =NULL;1void Insert_L(NODE *&L,int i, int e)(NODE *p=L,*q;int j=0;while(p&&jnext;j++;if(pli>i-1)printf("插入值超出范围！");return,1q=(NODE*)newNODE;q->data=e;q->next =p->next ;p->next =q;1n

3 print(L); Insert_L(L,7,50); print(L); int x; Delete_L(L,0,x); printf("X=",x,"\n"); print(L); } void print(NODE *&head){ NODE *p; p=head->next ; while(p){ printf(p->data,", "); //输出元素值 p=p->next; //后移指针 } print("\n"); } void Setup_L(NODE * &head,int n){ NODE *q,*p; head=(NODE*)new NODE; head->next=NULL; //先建立一个带头结点的单链表 q=head; for(int i=0;idata=data[i]; q->next=p; q=p; //插入到表头 } q->next =NULL; } void Insert_L(NODE *&L,int i, int e){ NODE *p=L,*q; int j=0; while(p&&jnext ; j++; } if(!p||j>i-1){ printf("插入值超出范围！"); return; } q=(NODE*)new NODE; q->data=e; q->next =p->next ; p->next =q; }

void Delete_L(NODE *&L,int i,int &e)NODE *p=L,*q;int j=0;while(p&&jnext ;j++;1if(!plli>i-1)printf("删除值超出范围！");return,1q=p->next ;e=q->data ;p->next =q->next;delete q;上机调试情况说明（包括调试数据、调试过程中遇到的问题及解决方法）将实验程序上机调试运行。测试结果和输出数据，对结果的分析和说明实验二二叉树操作实验目的（1）掌握二叉树的非线性、递归特点，熟练掌握二叉树的存储结构。（2）熟练掌握二叉树的各种遍历操作和其它操作的实现方法。基本要求（1）要求采用二叉链存储结构，编写程序完成二叉树的建立，输出先序、中序及后序遍历二叉树的遍历序列，清楚各种递归遍历算法中递归调用语句的位置和功能。（2）求二叉树的结点总个数、叶结点个数和符合指定条件的结点个数（比如，二叉树结点的值为整数，求该树中值为偶数的结点的个数）的操作。实验内容采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。二叉树以链式结构表示，主程序以菜单方式的用户界面。算法实现程序（源程序代码）#include"stdio.h"#include"string.h"#defineMax20//结点的最大个数typedef struct nodechar data,struct node *lchild,*rchild;//自定义二叉树的结点类型BinTNode;/定义二叉树的指针typedef BinTNode *BinTree;4

4 void Delete_L(NODE *&L,int i,int &e){ NODE *p=L,*q; int j=0; while(p&&jnext ; j++; } if(!p||j>i-1){ printf("删除值超出范围！"); return; } q=p->next ; e=q->data ; p->next =q->next; delete q; } 上机调试情况说明（包括调试数据、调试过程中遇到的问题及解决方法） 将实验程序上机调试运行。 测试结果和输出数据，对结果的分析和说明 实验二 二叉树操作 实验目的 （1）掌握二叉树的非线性、递归特点，熟练掌握二叉树的存储结构。 （2）熟练掌握二叉树的各种遍历操作和其它操作的实现方法。 基本要求 （1）要求采用二叉链存储结构，编写程序完成二叉树的建立，输出先序、中序及后序遍历二叉树 的遍历序列，清楚各种递归遍历算法中递归调用语句的位置和功能。 （2）求二叉树的结点总个数、叶结点个数和符合指定条件的结点个数（比如，二叉树结点的值为 整数，求该树中值为偶数的结点的个数）的操作。 实验内容 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求 所有叶子及结点总数的操作。 二叉树以链式结构表示，主程序以菜单方式的用户界面。 算法实现程序（源程序代码） #include"stdio.h" #include"string.h" #define Max 20 //结点的最大个数 typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针

I/NodeNum为结点数，leaf为叶子数intNodeNum leaf:1/基于先序遍历算法创建二叉树I/要求输入先序序列，其中加入虚结点“#”以示空指针的位置BinTree CreatBinTree(void)BinTree T,char ch,if(ch=getcharO)-#")return(NULL）；//读入#，返回空指针elselT=(BinTNode*)malloc(sizeof(BinTNode);I/生成结点T->data=ch;T->Ichild=CreatBinTreeO;1/构造左子树T->rchild=CreatBinTreeO;I/构造右子树return(T);1I先序遍历void Preorder(BinTree T)if(T)(1/访问结点printf("%c",T->data);Preorder(T->Ichild);I先序遍历左子树Preorder(T->rchild);I/先序遍历右子树111/中序遍历void Inorder(BinTree T)if(T)1/中序遍历左子树Inorder(T->lchild);1/访问结点printf("%c",T->data);1/中序遍历右子树Inorder(T->rchild),1/后序遍历void Postorder(BinTree T)if(T) Postorder(T->Ilchild);1/后序遍历左子树1/后序遍历右子树Postorder(T->rchild);//访问结点printf("%c",T->data),1结点数及叶子数的递归算法/采用后序遍历求二叉树的深度、int TreeDepth(BinTree T))int hl,hr,max;if(T)(求左深度hl-TreeDepth(T->lchild);5

5 int NodeNum,leaf; //NodeNum 为结点数，leaf 为叶子数 //基于先序遍历算法创建二叉树 //要求输入先序序列，其中加入虚结点“#”以示空指针的位置 BinTree CreatBinTree(void){ BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //读入#，返回空指针 else{ T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->lchild=CreatBinTree(); //构造左子树 T->rchild=CreatBinTree(); //构造右子树 return(T); } } //先序遍历 void Preorder(BinTree T){ if(T){ printf("%c",T->data); //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } } //中序遍历 void Inorder(BinTree T){ if(T){ Inorder(T->lchild); //中序遍历左子树 printf("%c",T->data); //访问结点 Inorder(T->rchild); //中序遍历右子树 } } //后序遍历 void Postorder(BinTree T){ if(T){ Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf("%c",T->data); //访问结点 } } //采用后序遍历求二叉树的深度、结点数及叶子数的递归算法 int TreeDepth(BinTree T){ int hl,hr,max; if(T){ hl=TreeDepth(T->lchild); //求左深度

I求右深度hr-TreeDepth(T->rchild);max=hl>hr? hl:hr,//取左右深度的最大值NodeNum=NodeNum+1;/求结点数if(hl==0&&hr==0)leaf-leaf+1：I/若左右深度为0，即为叶子。return(max+1)1else return(0);31/主函数void mainOBinTree root,int i,depth;printf("n");printf("Creat Bin_Tree;Inputpreorder:");//输入完全二叉树的先序序列，I用#代表虚结点，如ABD###CE##F##root=CreatBinTreeO;//创建二叉树，返回根结点dotI/从菜单中选择遍历方式，输入序号。print(“"l*素***** select *******(n");printf("t1: Preorder Traversalln");printf("It2: Iorder Traversal\n"),printf("lt3: Postorder traversalln");printf("lt4: PostTreeDepth,Node number,Leaf numberln");printf("Ito: Exit)n");printf("\t***************事***n");scanf("%d",&i);//输入菜单序号（0-4)switch (i)case I: printf("Print Bin_tree Preorder: ");I1先序遍历Preorder(root);break,case 2: printf("Print Bin_ Tree Inorder: ");1/中序遍历Inorder(root);break,case 3: printf("Print Bin_Tree Postorder:");1/后序遍历Postorder(root),break,case 4: depth=TreeDepth(root);/求树的深度及叶子数printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);printf("BinTree Leaf number-%d",leaf);break,case 5:printf("LevePrint Bin Tree:");1/按层次遍历Levelorder(root),break,default: exit(1),1printf("In");6

6 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为 0，即为叶子。 return(max+1); } else return(0); } //主函数 void main(){ BinTree root; int i,depth; printf("\n"); printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如 ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 do{ //从菜单中选择遍历方式，输入序号。 printf("\t********** select ************\n"); printf("\t1: Preorder Traversal\n"); printf("\t2: Iorder Traversal\n"); printf("\t3: Postorder traversal\n"); printf("\t4: PostTreeDepth,Node number,Leaf number\n"); printf("\t0: Exit\n"); printf("\t*******************************\n"); scanf("%d",&i); //输入菜单序号（0-4） switch (i){ case 1: printf("Print Bin_tree Preorder: "); Preorder(root); //先序遍历 break; case 2: printf("Print Bin_Tree Inorder: "); Inorder(root); //中序遍历 break; case 3: printf("Print Bin_Tree Postorder: "); Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum); printf(" BinTree Leaf number=%d",leaf); break; case 5: printf("LevePrint Bin_Tree: "); Levelorder(root); //按层次遍历 break; default: exit(1); } printf("\n");

while(il=0);1实验三图的遍历操作实验目的（1）掌握图的邻接矩阵和邻接表的存储结构。（2）掌握图的两种常用存储结构下的深度优先搜索和广度优先搜索操作的实现。基本要求分别采用邻接矩阵和邻接表存储结构，完成图的深度优先遍历（DFS）和广度优先遍历（BFS）的操作。搞清楚BFS算法中队列的作用。实验内容分别用图的邻接矩阵和邻接表的存储结构实现下列基本运算：（1）创建图；（2）深度优先遍历图；（3）广度优先遍历图。算法实现程序（源程序代码）（1）邻接矩阵作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定义最大顶点数typedef struct!/顶点表char vexs[MaxVertexNum];int edges[MaxVertexNum][MaxVertexNum];邻接矩阵，可看作边表int n,e;//图中的顶点数n和边数e)MGraph;/用邻接矩阵表示的图的类型1/建立邻接矩阵void CreatMGraph(MGraph *G)int i.j,k,char a,printf("Input VertexNum(n) and EdgesNum(e):");1/输入顶点数和边数scanf("%d.%d"&G->n.&G->e)scanf("%c",&a);printf("Input Vertex string:"),for(i=0,in;i++)(scanf("%c",&a),G->vexs[i]=a,//读入顶点信息，建立顶点表1for(i=0;in;i++)for(i=0;jn;j++)G->edges[i][i]=0;1初始化邻接矩阵printf("Input edges,Creat Adjacency Matrixln");/读入e条边，建立邻接矩阵for(k=0;ke;k++)(scanf("%d%d"&i,&i);1/输入边（V，V）的顶点序号G->edges[i][i]=1;G->edges[il[i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句7

7 }while(i!=0); } 实验三 图的遍历操作 实验目的 （1）掌握图的邻接矩阵和邻接表的存储结构。 （2）掌握图的两种常用存储结构下的深度优先搜索和广度优先搜索操作的实现。 基本要求 分别采用邻接矩阵和邻接表存储结构，完成图的深度优先遍历（DFS）和广度优先遍历（BFS）的 操作。搞清楚 BFS 算法中队列的作用。 实验内容 分别用图的邻接矩阵和邻接表的存储结构实现下列基本运算：（1）创建图；（2）深度优先遍历图； （3）广度优先遍历图。 算法实现程序（源程序代码） （1）邻接矩阵作为存储结构 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数 n 和边数 e }MGraph; //用邻接矩阵表示的图的类型 //建立邻接矩阵 void CreatMGraph(MGraph *G){ int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++){ scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 } for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵 printf("Input edges,Creat Adjacency Matrix\n"); for(k=0;ke;k++){ //读入 e 条边，建立邻接矩阵 scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 }

3/定义标志向量，为全局变量typedef enum(FALSE,TRUE) Boolean;Boolean visited[Max VertexNum]I深度优先遍历的递归算法voidDFSM(MGraph*Ginti)//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵intj,printf("%c",G->vexs[i]);1/访问顶点V1/置已访问标志visited[i]-TRUE;1/依次搜索V,的邻接点for(j=0:jn;j++)if(G->edges[i][i]--1 && ! visited[i])DFSM(Gi);lI（V，V）EE，且Vi未访问过，故V为新出发点1void DFS(MGraph *G)(int i,for(i=0;in;i++)visited[]-FALSE;1/标志向量初始化for(i=0;in;i++)/V;未访间过if(Ivisited[i])DFSM(Gi);//以V:为源点开始DFS搜索I/广度优先遍历void BFS(MGraph *Gint k)//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i,j,f=0,r=0:1/定义队列int cq[Max VertexNum];for(i=0;in;i++)1/标志向量初始化visited[i]-FALSE:for(i=-0;in;i++)cq[]=-1;1/队列初始化printf("%c",G->vexs[k]);1/访问源点Vkvisited[k]-TRUE;cq[r]=k,I/Vk已访问，将其入队。注意，实际上是将其序号入队1/队非空则执行while(cq[f]!=-1)(i=cq[f]; f=-f+1;IV出队I/依次Vi的邻接点Vfor(i=0,jn;j++)if(G->edges[i][i]-=1&&Ivisited[i])/V,未访间1/访间Vprintf("%c",G->vexs[i]);visited[il-TRUE;r=r+1; cq[r]月j;,//访问过Vj入队111主函数8

8 } //定义标志向量，为全局变量 typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //深度优先遍历的递归算法 void DFSM(MGraph *G,int i){ //以 Vi 为出发点对邻接矩阵表示的图 G 进行 DFS 搜索，邻接矩阵是 0，1 矩阵 int j; printf("%c",G->vexs[i]); //访问顶点 Vi visited[i]=TRUE; //置已访问标志 for(j=0;jn;j++) //依次搜索 Vi的邻接点 if(G->edges[i][j]==1 && ! visited[j]) DFSM(G,j); //（Vi，Vj）∈E，且 Vj 未访问过，故 Vj为新出发点 } void DFS(MGraph *G){ int i; for(i=0;in;i++) visited[i]=FALSE; //标志向量初始化 for(i=0;in;i++) if(!visited[i]) //Vi未访问过 DFSM(G,i); //以 Vi为源点开始 DFS 搜索 } //广度优先遍历 void BFS(MGraph *G,int k){ //以 Vk为源点对用邻接矩阵表示的图 G 进行广度优先搜索 int i,j,f=0,r=0; int cq[MaxVertexNum]; //定义队列 for(i=0;in;i++) visited[i]=FALSE; //标志向量初始化 for(i=0;in;i++) cq[i]=-1; //队列初始化 printf("%c",G->vexs[k]); //访问源点 Vk visited[k]=TRUE; cq[r]=k; //Vk 已访问，将其入队。注意，实际上是将其序号入队 while(cq[f]!=-1){ //队非空则执行 i=cq[f]; f=f+1; //Vf出队 for(j=0;jn;j++) //依次 Vi 的邻接点 Vj if(G->edges[i][j]==1 && !visited[j]){ //Vj 未访问 printf("%c",G->vexs[j]); //访问 Vj visited[j]=TRUE; r=r+1; cq[r]=j; //访问过 Vj 入队 } } } //主函数

voidmain(inti,MGraph *G;G-(MGraph *)malloc(sizeof(MGraph));//为图G申请内存空间I建立邻接矩阵CreatMGraph(G);printf("Print Graph DFS: ");DFS(G);//深度优先遍历printf("n");printf("Print Graph BFS: ");BFS(G3);//以序号为3的顶点开始广度优先遍历printf("\n"),1执行顺序：Input VertexNum(n) and EdgesNum(e): 8, 9voOInput Vertex string: 01234567V1Input edges,CreatAdjacencyMatrix0102131425V7C2637图G的示例4756PrintGraphDFS:01374256PrintGraphBFS:31704256（2）邻接链表作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50I定义最大顶点数1/边表结点typedef struct nodeI邻接点域int adjvex,1/链域struct node *next,jEdgeNode;//顶点表结点typedef struct vnode1/顶点域char vertex,1/边表头指针EdgeNode *firstedge;!VertexNode;lIAdjList是邻接表类型typedef VertexNode AdjList[Max VertexNum];typedef struct!I邻接表AdjList adjlist,1/图中当前顶点数和边数int n,e,/图类型ALGraph;9

9 void main(){ int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph)); //为图 G 申请内存空间 CreatMGraph(G); //建立邻接矩阵 printf("Print Graph DFS: "); DFS(G); //深度优先遍历 printf("\n"); printf("Print Graph BFS: "); BFS(G,3); //以序号为 3 的顶点开始广度优先遍历 printf("\n"); } 执行顺序： Input VertexNum(n) and EdgesNum(e): 8，9 Input Vertex string: 01234567 Input edges,Creat Adjacency Matrix 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 6 Print Graph DFS: 01374256 Print Graph BFS: 31704256 （2）邻接链表作为存储结构 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode; typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; //AdjList 是邻接表类型 typedef struct{ AdjList adjlist; //邻接表 int n,e; //图中当前顶点数和边数 }ALGraph; //图类型 V4 V5 V6 V7 V2 V3 V1 V0 图 G 的示例

Ⅱ建立图的邻接表void CreatALGraph(ALGraph *G)int ij,k,char a,I/定义边表结点EdgeNode *s,printf("Input VertexNum(n) and EdgesNum(e): ")//读入顶点数和边数scanf("%d,%d",&G->n,&G->e);scanf("%c",&a);printf("Input Vertex string:"),Ⅱ建立边表for(i=0;in;i++)(scanf("%c",&a);G->adjlist[i].vertex=a;/读入顶点信息G->adjlist[].firstedge=NULL；I/边表置为空表7printf("Input edges,CreatAdjacencyListln"):Ⅱ建立边表for(k=0;ke;k++)(scanf("%d%d",&i&);//读入边（Vi，Vi）的顶点对序号1生成边表结点s=(EdgeNode *)malloc(sizeof(EdgeNode);I邻接点序号为js->adjvex=j;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;//将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode));1/邻接点序号为is->adjvex=i,s->next-G->adjlist[il.firstedge;G->adjlist[i].firstedge=s;I/将新结点*S插入顶点Vi的边表头部131/定义标志向量，为全局变量typedef enum (FALSE,TRUE) Boolean;Boolean visited[Max VertexNum];1深度优先遍历的递归算法void DFSM(ALGraph *G,int i)//以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode *p;printf("%c",G->adjlist[i].vertex),/访问顶点Vivisited[i]-TRUE;//标记Vi已访间I/取Vi边表的头指针p-G->adjlist[].firstedge;while(p)tI/依次搜索Vi的邻接点Vj，这里j-p->adjvexl/若Vj尚未被访间if(! visited[p->adjvex])DFSM(Gp->adjvex),I/则以Vi为出发点向纵深搜索//找Vi的下一个邻接点p=p->next;13void DFS(ALGraph*G)int i,10

10 //建立图的邻接表 void CreatALGraph(ALGraph *G){ int i,j,k; char a; EdgeNode *s; //定义边表结点 printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++){ //建立边表 scanf("%c",&a); G->adjlist[i].vertex=a; //读入顶点信息 G->adjlist[i].firstedge=NULL; //边表置为空表 } printf("Input edges,Creat Adjacency List\n"); for(k=0;ke;k++){ //建立边表 scanf("%d%d",&i,&j); //读入边（Vi，Vj）的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s->adjvex=j; //邻接点序号为 j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; //将新结点*S 插入顶点 Vi 的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; //邻接点序号为 i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; //将新结点*S 插入顶点 Vj 的边表头部 } } //定义标志向量，为全局变量 typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //深度优先遍历的递归算法 void DFSM(ALGraph *G,int i){ //以 Vi 为出发点对邻接链表表示的图 G 进行 DFS 搜索 EdgeNode *p; printf("%c",G->adjlist[i].vertex); //访问顶点 Vi visited[i]=TRUE; //标记 Vi 已访问 p=G->adjlist[i].firstedge; //取 Vi 边表的头指针 while(p){ //依次搜索 Vi 的邻接点 Vj，这里 j=p->adjvex if(! visited[p->adjvex]) //若 Vj 尚未被访问 DFSM(G,p->adjvex); //则以 Vj 为出发点向纵深搜索 p=p->next; //找 Vi 的下一个邻接点 } } void DFS(ALGraph *G){ int i;