《数据结构》实验教学大纲
课程编号：17012030 课程类别：专业基础课适用专业：计算机科学与技术实验学时：12
一、本门课程实验的性质、任务与目的
《数据结构》课程是计算机科学与技术专业的一门重要的专业基础课。通过此实验教学和学生的上机实践，要求学生掌握各种数据结构的具体物理实现方法，掌握用数据结构知识解决实际问题的方法，以达到理论指导实践的目的。从而进一步提高学生的编程能力、算法设计能力及分析问题、解决问题的能力。
二、实验项目
三、实验概述
实验一：线性表
目的：掌握线性表的表示及其基本操作的实现方法与算法。
原理概述：顺序表及链表的实现方法
方法与手段：利用顺序序表及各种链表的实现方法，学生自行设计并编写程序实现线性表的存储表示及其主要的基本操作，并上机调试、运行及进行验证。还可以进一步设计并编程实现集合的表示及并、交等操作，一元多项式的表示及其相加等操作。
应得到的实验结果和数据：能够编程实现线性表的一种或多种表示，通过输出相应操作结果（如各种操作后线性表中的元素）验证设计算法的正确性。
实验二：栈与队列
目的：掌握栈与队列的表示及其基本操作的实现方法与算法。
原理概述：栈的特性及其实现方法；队列的特性及链队列、循环队列的实现方法。
方法与手段：利用栈与队列的实现方法，学生自行设计并编写程序实现栈与队列存储表示及其主要的基本操作，并上机调试、运行及进行验证。还可以进一步设计并编程实现进制转换问题、括号匹配问题。
应得到的实验结果和数据：能够编程实现栈与队列的一种或多种表示，通过输出相应操作结果（如各种操作后栈或队列中的元素）验证设计算法的正确性。
实验三：二叉树
目的：掌握二叉树的表示及其创建、遍历、求深度等基本操作的实现方法与算法。
原理概述：二叉树的二叉链表表示方法与二叉树的创建、遍历等算法的实现方法。
方法与手段：利用二叉树的二叉链表存储实现方法，学生自行设计并编写程序实现二叉树的表示及其创建、遍历等主要操作，并上机调试、运行及进行验证。亦可进一步完成哈夫曼树及哈夫曼编码算法。
应得到的实验结果和数据：能够编程实现二叉树的二叉链表表示，通过输出相应操作结果（如二叉树的各种遍历序列、二叉树的深度等）验证设计算法的正确性。
实验四：图
目的：掌握图的存储表示（邻接矩阵或邻接表）及相关操作的实现方法。
原理概述：图的邻接矩阵表示法、邻接表表示法；图的创建、遍历等基本操作算法；以及最小生成树、拓扑排序等算法。
方法与手段：利用图的一种存储实现方法，学生自行设计并编写程序实现图的表示及其创建、遍历等等主要操作，并上机调试、运行及进行验证。还可以进一步设计并编程实现图的最小生成树、拓扑排序等。
应得到的实验结果和数据：能够编程实现图的一种存储表示，通过输出相应操作结果（如存储结构图、图的遍历序列等）验证设计算法的正确性。
实验五：查找
目的：通过上机，掌握顺序查找、折半查找及二叉排序树等的相关查找算法。
原理概述：顺序查找算法；折半查找（二分法查找）算法；二叉排序树及其创建、查找等算法。
方法与手段：学生自行设计并编写程序实现顺序表上的顺序查找与折半查找算法，以及二叉排序树及其创建、查找等主要操作，并上机调试、运行及进行验证。
应得到的实验结果和数据：
（1）能够编程实现顺序表上顺序查找、折半查找算法的一种存储表示，通过输出相应操作结果（如查找表中的元素、查找结果等）验证设计算法的正确性。
（2）能够编程完成二叉树排序树的创建、查找、中序遍历等操作，通过输出其中序（根）序列验证设计算法的正确性。
实验六：排序
目的：通过上机，掌握相关排序算法的设计思想及实现方法。
原理概述：直接插入排序、希尔（Shell）排序、快速排序、堆排序及二路归并排序等排序算法的设计思想及方法。
方法与手段：利用相关的排序方法，学生自行设计并编写程序实现顺序表上排序，并上机调试、运行及进行验证。
应得到的实验结果和数据：能够编程实现排序表的创建、排序等操作，并通过输出排序前及排序后排序表中元素的值，以验证设计的排序算法的正确性。
四、主要仪器设备配置
硬件环境：微机（每生一台）
软件环境：VC++(或TC3.0）
五、教学形式
应用多媒体讲授实验内容、要求及注意事项，上机辅导，最后进行实验总结，学生给出每次实验的实验报告。
六、考核方式及成绩评定办法
每次完成实验内容，进行总结分析，写出实验报告。按照学生每次的实验态度、实验内容完成情况及实验报告书写情况等方面进行考核，实验总成绩占期末成绩的20%。具体分配如下：（1）平时成绩（包括学生的实验态度、实验完成情况等）：占实验总成绩的50%；
（2）实验报告：占实验总绩的50%。
数据结构上机实验编程指南
为了更好地帮助同学们做好数据结构实验，在此给出数据结构上机编程的一般思路和程序的基本框架结构。具体程序结构按先后顺序可分为以下3个部分：
1．预定义常量及类型
对于相关的常量与类型（如状态类型）进行定义，如：
#define OK 1
#define ERROR 0
#define OVERFLOW –2
#define TRUE 1
#define FALSE 0
typedef int Status;
2．相关数据结构类型定义
此部分包括对所使用的数据结构给出其类型定义及其基本操作函数定义。（具体内容可参见实验一）
3．主调程序的定义
此部分给出相关的主调程序，在此程序中定义相关数据结构变量，并通过调用其操作函数，实现设计目的。（具体内容可参见实验一）
实验一线性表
一、实验目的
1．掌握顺序表及其基本操作的实现；
2．掌握链表及其基本操作的实现；
3．掌握利用C编程语言实现数据结构的编程方法；
4．通过上机实践进一步加深对线性表的顺序存储方式及链式存储方式的理解；
5．通过上机实践加强利用数据结构解决实际应用应用问题的能力。
二、实验要求
1．实验前做好充分准备，包括复习第一章、第二章所学内容，事先预习好本次实验内容；
2．实验时记录实验结果，按要求完成各题；
3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。
三、实验题目与要求
1．实验题目一：顺序表的定义及其相关操作算法的实现
要求：编程实现顺序表的类型定义及顺序表的初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。
2．实验题目二：链表的定义及其相关操作算法的实现
要求：编程实现单链表（或双向链表、循环链表）的类型定义及其初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。
3．实验题目三：集合的表示与运算
要求：利用题目一或题目二所定义的线性表（顺序表或链表）实现集合的表示及其并、交等运算，并进行验证给出结果。
4．实验题目四：一元多项式的表示与运算
要求：利用线性表（顺序表或链表）实现一元多项的类型定义及其相加等等运算，并进行验证给出结果。
说明：
（1）实验题目一与实验题目二为必做内容；
（2）实验题目三与实验题目四为选做内容。
四、实验程序示例
本指导书所给出的示例程序均为VC环境下完成的，若使用其它C开发环境，则部分语句要进行少许修改。例如，对于如下的文件包含命令：
#include “malloc.h”
则在TC3.0环境中需改为：
#include “alloc.h”
示例1：顺序表的实现
#include "stdio.h"
#include "malloc.h"
//-------------（1）预定义常量及类型-----------------
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int Status;
//-------（2）顺序表类型及其基本操作函数的定义---------
#define InitSize 100
#define INCR 20
typedef int LElemType; //定义元素类型(LElemType)为int类型
typedef struct
{ LElemType *Elem;
int Length;
int ListSize;
}SqList; //SqList类型为顺序表类型
Status InitList_sq(SqList &L) //初始化操作函数定义
{ L.Elem=(LElemType *)malloc(InitSize*sizeof(LElemType));
if (!(L.Elem))return(OVERFLOW);
L.Length=0; L.ListSize=InitSize;
return OK;
}
Status ListInsert_sq(SqList &L, int i, LElemType e) //插入操作函数定义
{ int j;
if (i<1||i>L.Length+1) return ERROR;
if (L.Length>=L.ListSize)
{ L.Elem=( LElemType *)malloc((L.ListSize+INCR)*sizeof(LElemType));
if(!(L.Elem)) return(OVERFLOW);
L.ListSize+=INCR;
}
for(j=L.Length-1;j>=i-1;j--)
L.Elem[j+1]=L.Elem[j];
L.Elem[i-1]=e;
L.Length++;
return OK;
}
void ListOutput_sq(SqList L) //顺序表输出操作
{ int i;
for(i=0;i<=L.Length-1;i++)
printf("%6d",L.Elem[i]);
printf("\n");
}
//其它操作如删除、查找、判空等操作略
//-------------（3）主函数定义--------------------
void main()
{ SqList La;
int i;
InitList_sq(La);
for (i=0;i<5;i++) ListInsert_sq(La,i+1,2*i);
ListOutput_sq(La);
ListInsert_sq(La,1,999); ListOutput_sq(La);
ListInsert_sq(La,4,888); ListOutput_sq(La);
ListInsert_sq(La,La.Length+1,111); ListOutput_sq(La);
}
0 2 4 6 8
999 0 2 4 6 8
999 0 2 888 4 6 8
999 0 2 888 4 6 8 111
Press any key to continue
说明：对于顺序表的其它操作函数，本示例程序未给出，学生上机实验时可以自行给出定义，并在主程序中加以验证。本指导书中后面的示例程序也有这种情况，将不在说明。
示例2：单链表(带头结头)实现
#include "stdio.h"
#include "malloc.h"
//------------------（1）预定义常量及类型---------------
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int Status;
//------------（2）单链表类型及其基本操作函数的定义------
typedef int LElemType; //定义元素类型（LElemType）为int类型
typedef struct Lnode
{ LElemType data;
struct Lnode *next;
}*LinkList; //LinkList为单链表类型
Status InitList_l(LinkList &L) //初始化操作函数定义
{ L=(LinkList)malloc(sizeof(struct Lnode));
if(!L) return(OVERFLOW);
L->next=NULL;
return OK;
}
Status ListInsert_l(LinkList &L,int i, LElemType e) //插入操作函数定义
{ LinkList p,s;
int j;
p=L;j=0;
while(p&&j
if (!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(struct Lnode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
void ListOutput_l(LinkList L) //输出操作函数定义
{ LinkList p;
p=L->next;
while(p)
{ printf("%6d",p->data); p=p->next; }
printf("\n");
}
//其它操作如删除、查找、判空等操作略
//-------------（3）主函数定义------------------
void main()
{ int i;
LinkList La;
InitList_l(La);
for (i=0;i<5;i++) ListInsert_l(La,i+1,3*i);
ListOutput_l(La);
ListInsert_l(La,1,999); ListOutput_l(La);
ListInsert_l(La,4,888); ListOutput_l(La);
}
0 3 6 9 12
999 0 3 6 9 12
999 0 3 888 6 9 12
Press any key to continue
示例3：一元多项式的单链表表示与相加操作的实现
#include "stdio.h"
#include "malloc.h"
typedef struct PNode
{ int coef;
int expn;
struct PNode *next;
}*POL Y; //POLY为一元多项式的类型
void CreatPoly(POL Y &L,int n) //一元多项式的创建操作，其中n为一元多项式的项数{ int i,coef,expn;
POL Y p,s;
L=(POL Y)malloc(sizeof(struct PNode));
L->next=NULL;
p=L;
for(i=1;i<=n;i++)
{ printf("input %dth coef:",i);
scanf("%d",&coef);
printf("input %dth expn:",i);
scanf("%d",&expn);
s=(POL Y)malloc(sizeof(struct PNode));
s->coef=coef;s->expn=expn;
s->next=NULL;p->next=s;p=s;
}
}
void OutputPoly(POL Y L) //一元多项式的输出操作
{ int flag=1; //flag用来是否为第一项的标识
POL Y p;
p=L->next;
while(p)
{ if(flag) { printf("%dX^%d",p->coef,p->expn); flag=0; }
else printf("%+dX^%d",p->coef,p->expn);
p=p->next;
}
printf("\n");
}
void AddPoly(POL Y La, POL Y Lb, POL Y &Lc) //一元多项式的相加操作，即实现Lc=La+Lb { int x;
POL Y pa,pb,pc,s;
Lc=(POL Y)malloc(sizeof(struct PNode));
Lc->next=NULL;pc=Lc;
pa=La->next;pb=Lb->next;
while(pa&&pb)
{ if(pa->expn
{ s=(POL Y)malloc(sizeof(struct PNode));
s->coef=pa->coef;s->expn=pa->expn;
s->next=NULL;pc->next=s;pc=s;
pa=pa->next;
}
else if(pa->expn>pb->expn)
{ s=(POL Y)malloc(sizeof(struct PNode));
s->coef=pb->coef;s->expn=pb->expn;
s->next=NULL;pc->next=s;pc=s;
pb=pb->next;
}
else
{ x=pa->coef+pb->coef;
if(x!=0)
{ s=(POLY)malloc(sizeof(struct PNode));
s->coef=x;s->expn=pa->expn;
s->next=NULL;pc->next=s;pc=s;
}
pa=pa->next; pb=pb->next;
}
}
while(pa)
{ s=(POL Y)malloc(sizeof(struct PNode));
s->coef=pa->coef;s->expn=pa->expn;
s->next=NULL;pc->next=s;pc=s;
pa=pa->next;
}
while(pb)
{ s=(POL Y)malloc(sizeof(struct PNode));
s->coef=pb->coef;s->expn=pb->expn;
s->next=NULL;pc->next=s;pc=s;
pb=pb->next;
}
}
void main()
{ POL Y La,Lb,Lc;
int n;
printf("Creat Poly La:\n");
printf("\t Input the number of items of La:");
scanf("%d",&n);
CreatPoly(La,n);
printf("\nLa(x)=");
OutputPoly(La);
printf("Creat Poly Lb:\n");
printf("\tInput the number of items of Lb:");
scanf("%d",&n);
CreatPoly(Lb,n);
printf("\nLb(x)=");
OutputPoly(Lb);
AddPoly(La,Lb, Lc);
printf("Lc(x)=La(x)+Lb(x)=");
OutputPoly(Lc);
}
实验二栈与队列
一、实验目的
1．掌握栈的存储实现方式及其基本操作的实现；
2．掌握队列的存储实现方式及其基本操作的实现；
3．进一步掌握利用TC实现数据结构的编程方法。
二、实验要求
1．实验前做好充分准备，包括复习第三章所学内容，事先预习好本次实验内容；
2．实验时记录实验结果，按要求完成各题；
3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。
三、实验题目与要求
1．实验题目一：顺序栈的定义及其操作算法的实现
要求：编程实现顺序栈表的类型定义及顺序表的初始化操作、入栈操作、出栈操作、取栈顶元素操作、输出操作等，并对其进行验证。
2．实验题目二：链式队列的定义及其相关操作算法的实现
要求：编程实现链式队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。
3．实验题目三：循环队列定义及其操作算法的实现
要求：编程实现循环队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。
4．实验题目四：利用栈实现进制转换
要求：利用栈（顺序栈或链式栈）实现进制转换问题
说明：
（1）实验题目一与实验题目三为必做内容。
（2）实验题目二与实验题目四为选做内容。
四、实验程序示例
示例1：顺序栈的定义及其操作算法的实现
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int Status;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
typedef int SElemType; //定义栈内元素类型（SElemType）为int类型
typedef struct
{ SElemType *base;
SElemType *top;
int stackSize;
}SqStack;
Status InitStack(SqStack &S)
{
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(overflow);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,SElemType e)
{
if(S.top-S.base=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
//代码略
}
Status GetTop(SqStack S, SElemType &e)
{
//代码略
}
void StackOutput(SqStack S)
{ int i;
for(i=0;i printf("%d ",S.base[i]); printf("\n"); } void main() { SqStack S; SElemType e; InitStack(S); for(i=1;i<=5;i++) Push(S,2*i+1); StackOutput(S); Pop(S, e); StackOutput(S); Push(S,111); StackOutput(S); Push(S,222); StackOutput(S); Pop(S, e); StackOutput(S); } 示例2：循环队列的定义及其相关操作算法的实现 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; #define MAX 10 typedef int QElemType; //定义队列内元素类型（QElemType）为int类型typedef struct { QElemType *base; int front; int rear; }CirQueue; Status InitQueue(CirQueue &Q) { Q.base =( QElemType *)malloc(MAX*sizeof(QElemType)); if(!Q.base) return(OVERFLOW); Q.front=Q.rear=0; return OK; } Status EnQueue(CirQueue &Q, QElemType e) { //代码略 } Status DeQueue(CirQueue &Q, QElemType &e) { //代码略 } void QueueOutput(CirQueue Q) { int i; for(i=Q.front;i!=Q.rear;i=(i+1)%MAX) printf("%5d",Q.base[i]); } void main() { CirQueue Q; QElemType e; int i; InitQueue(Q); for(i=1;i<=5;i++) EnQueue(Q,i); QueueOutput(Q); DeQueue(Q, e); QueueOutput(Q); for(i=1;i<=3;i++) DeQueue(Q, e); QueueOutput(Q); for(i=6;i<=13;i++) EnQueue(Q,i); QueueOutput(Q); } 实验三二叉树 一、实验目的 1．掌握二叉树的链式存储结构及其相关操作的实现； 2．掌握二叉树的先序、中序、后序的递归遍历算法； 3．理解二叉树的各种非递归遍历算法的实现。 二、实验要求 1．实验前做好充分准备，包括复习第六章所学内容，事先预习好本次实验内容； 2．实验时记录实验结果，按要求完成各题； 3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。 三、实验题目与要求 1．实验题目一：二叉树的创建、递归遍历及其它基本操作的实现。 要求：定义用二叉链表表示的二叉树，并实现二叉树的创建、遍历（先序、中序后序）的递归算法及求深度操作等，并对其进行验证。 2．实验题目二：二叉树非递归遍历算法的实现 要求：在题目一的基础上，实现二叉树的非递归遍历算法（先序、中序、后序或按层），并对其进行验证。 3．实验题目三：哈夫曼树及哈夫曼编码的算法实现 要求：编程实现哈夫曼树的创建及利用哈夫曼树求解哈夫曼编码。 说明： （1）实验题目一为必做内容； （2）实验题目二与实验题目三为选做内容。 四、实验程序示例 示例1：二叉树的创建、递归遍历算法及其它基本操作的实现 #include "stdio.h" #include "malloc.h" typedef struct BNode { char data; //二叉树中的元素类型为char类型 struct BNode *lchild; struct BNode *rchild; } *BiTree; void CreatBiTree(BiTree &T) //先序创建二叉树 { char ch; scanf("%c",&ch); if(ch=='$') T=NULL; //当输入'$'时表示创建的二叉树为空树 else { T=(BiTree)malloc(sizeof(struct BNode)); T->data=ch; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } } void Preorder(BiTree T)//先序遍历二叉树的递归算法 { if (T) { printf("%c",T->data); Preorder(T->lchild); Preorder(T->rchild); } } void Inorder(BiTree T) //中序遍历二叉树的递归算法 { //代码略 } void Postorder(BiTree T) //后序遍历二叉树的递归算法 { //代码略 } int DepthTree(BiTree T) //求二叉树深度的递归算法 { int d1,d2; if(!T) return 0; //当树空时 else { d1=DepthTree(T->lchild); //求左子树的深度 d2=DepthTree(T->rchild); //求右子树的深度 return d1>=d2?d1+1:d2+1; //返回左、右子树深度较大者加1 } } void main() { BiTree T; printf("请输入相应的序列来创建树：\n"); break; CreatBiTree(T); printf("Preorder binary tree :\n" ); Preorder(T); printf("\nInorder binary tree:\n"); Inorder(T); printf("\nPostorder binary tree:\n"); Postorder(T); printf("\nThe depth of this binary tree is:%d\n",DepthTree(T)); } 程序运行说明： 若创建的二叉树如右图3-1所示，则应输入： ABD$$EG$$$C$F$$ 示例2：二叉树非递归遍历算法的实现 在题目一的基础上，利用栈和队列实现二叉树先序、中序、按层遍历的非递归遍历。以下只给出要应的遍历函数。 图3-1 欲创建的二叉树 void Preorder_N(BiTree T) //先序非递归遍历 //利用顺序栈实现二叉树的先序非递归遍历算法；顺序栈的实现参见实验二{ SqStack S; //定义一个栈S，栈中元素为BiTree类型 BiTree p; InitStack(S); Push(S,T); while(!StackEmpty(S)) //当栈非空时 { while (GetTop(S,p)&&p) { printf("%c",p->data); Push(S,p->lchild);} Pop(S, p);//空指针出栈 if(!StackEmpty(S)) { Pop(S,p); Push(S,p->rchild);} } } void Inorder_N(BiTree T) //中序非递归遍历 { //代码略 } void LevelOrder(BiTree T) //按层遍历 //利用循环队列实现二叉树的按层遍历算法；循环队列的实现参见实验二{ CirQueue Q; //定义循环队列Q，队列中元素为BiTree类型 BiTree p; InitQueue(Q); if(T) EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p);printf("%c",p->data); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } } 实验四图 一、实验目的 1．掌握图的邻接矩阵作为存储结构的方法及其相关操作的实现； 2．掌握图的邻接表作为存储结构的方法及其相关操作的实现； 3．掌握图的最小生树的Prim算法； 4．通过实践掌握图的的拓扑排序、最短路径算法的实现。 二、实验要求 1．实验前做好充分准备，包括复习第七章所学内容，事先预习好本次实验内容； 2．实验时记录实验结果，按要求完成各题； 3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。 三、实验题目与要求 1．实验题目一：图的邻接矩阵存储的实现、图的遍历算法 要求：采用邻接矩阵作为图的存储结构，实现图的相关基本操作的算法，并对其进行验证。 2．实验题目二：图的邻接表存储方的实现、图的遍历算法 要求：采用邻接表作为图的存储结构，实现图的相关基本操作的算法，并对其进行验证。 3．实验题目三：图最小生成树算法 要求：在题目一或题目二的基础上利用邻接矩阵（或邻接表）作为图的存储结构，编程实现最小生成树求解，并对其进行验证。 4．图的拓扑排序算法 要求：在题目二的基础上利用邻接表作为图的存储结构，编程实现有向图的拓扑排序算法，并对其进行验证。 5．图的最短路径算法 要求：在题目一或题目二的基础上利用邻接矩阵（或邻接表）作为图的存储结构，编程实现最短路径算法，并对其进行验证。 说明： （1）实验题目一、二为必做内容； （2）实验题目三、四、五为选做内容。 四、实验程序示例 示例1：无向图的邻接矩阵存储的实现、图的遍历算法 #include #include #define INFINITY INT_MAX 999 #define MAX_VERTEX_NUM 20 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //矩阵类型 typedef char VexType[10]; //顶点类型 typedef struct { VexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; int kind; //图的种类：1-无向图 2-无向网 3-有向图 4-有向网 }MGraph; //图的类型 int LocateVex(MGraph &G,VexType v); //在图G中查找顶点v，若存在返回位置，否则返回-1 void CreatUDG(MGraph &G) //无向图的创建操作 { VexType v1,v2; int i,j,k; G.kind=1; printf("Input vertex number and edg number:"); scanf("%d%d",&G.vexnum,&G.arcnum); printf("Input vertexs:\n"); for(i=0;i for(i=0;i for(j=0;j for(k=0;k { printf("Input edge(v1v2):"); scanf("%s%s",v1,v2); i=LocateVex(G,v1); if(i==-1) { printf(" Error!\n"); return;} j=LocateVex(G,v2); if(j==-1) { printf(" Error!\n"); return;} G.arcs[i][j]=G.arcs[j][i]=1; } } int LocateVex(MGraph &G,VexType v) //在图G中查找顶点v，若存在返回位置，否则返回-1 { int i; for(i=0;i if(strcmp(G.vexs[i],v)==0) return i; return -1; } void GraphOutput(MGraph &G) //图的邻接矩阵的输出操作 { int i,j; switch(G.kind) { case 1: printf("\n无向图：\n"); break; case 2: printf("\n无向网：\n"); break; case 3: printf("\n有向图：\n"); break; case 4: printf("\n有向网：\n"); break; default: printf("\n出错：\n"); } printf("\t"); for(i=0;i printf("%8s",G.vexs[i]); printf("\n"); for(i=0;i { printf("%s\t",G.vexs[i]); for(j=0;j printf("%8d",G.arcs[i][j]); printf("\n"); } } int FirstAdjVex(MGraph &G, int v) //求v的第一个邻接顶点 { //代码略 } int NextAdjVex(MGraph &G, int v,int w) //求v的相对于w的下一个邻接顶点{ //代码略 } void DFSTraverse(MGraph &G) //图的深度优先遍历算法 { //代码略 } void BFSTraverse(MGraph &G) //图的深度优先遍历算法 { //代码略 } //其他操作略 void main() { MGraph G; CreatUDG(G); GraphOutput(G); DFSTraverse(G); BFSTraverse(G); } 示例2：有图的邻接表存储的实现 #include "stdio.h" #include "malloc.h" #define max 20 #define Null 0 struct arcnode { int adjvex; struct arcnode *nextarc; }; struct vexelem { char data; struct arcnode *firstarc; }; typedef struct { struct vexelem vex[max];
相关主题
文本预览