数据结构图的存储结构及基本操作
2019-03-15 23页 doc 46KB 29阅读
is_005190
暂无简介
举报
数据结构图的存储结构及基本操作1. 实验目的
通过上机实验进一步掌握图的存储结构及基本操作的实现。
2. 实验内容与要求
要求：
⑴能根据输入的顶点、边/弧的信息建立图；
⑵实现图中顶点、边/弧的插入、删除；
⑶实现对该图的深度优先遍历；
⑷实现对该图的广度优先遍历。
备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。
3. 数据结构设计
逻辑结构：图状结构
存储结构：顺序存储结构、链式存储结构
4. 算法设计
#include
#include
#include
#define MAX_VERTEX_NUM 20
typedef str...
1. 实验目的
通过上机实验进一步掌握图的存储结构及基本操作的实现。
2. 实验内容与要求
要求：
⑴能根据输入的顶点、边/弧的信息建立图；
⑵实现图中顶点、边/弧的插入、删除；
⑶实现对该图的深度优先遍历；
⑷实现对该图的广度优先遍历。
备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。
3. 数据结构
逻辑结构：图状结构
存储结构：顺序存储结构、链式存储结构
4. 算法设计
#include
#include
#include
#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
char data[2]; //顶点就设置和书上V1等等一样吧
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct
{
int data[MAX_VERTEX_NUM+10];
int front;
int rear;
}queue;
int visited[MAX_VERTEX_NUM];
queue q;
int main()
{
ALGraph G;
int CreateUDG(ALGraph &G);
int DeleteUDG(ALGraph &G);
int InsertUDG(ALGraph &G);
void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v));
int PrintElement(ALGraph G,ArcNode v);
void menu();
void depthfirstsearch(ALGraph *g,int vi);
void travel(ALGraph *g);
void breadfirstsearch(ALGraph *g);
int i;
G.arcnum = G.vexnum = 0;
while(1)
{
menu();
do
{
printf ( "请输入要进行的操作\n" );
scanf ("%d",&i);
if (i<1||i>6)
printf("错误数字，请重新输入\n");
}while (i<1||i>6);
switch (i)
{
case 1: CreateUDG(G); system("pause"); system("cls"); break;
case 2: DeleteUDG(G); system("pause"); system("cls"); break;
case 3: InsertUDG(G); system("pause"); system("cls"); break;
case 4: travel(&G); system("pause"); system("cls"); break;
case 5: breadfirstsearch(&G); system("pause"); system("cls"); break;
case 6: exit(0); break;
}
}
return 1;
}
void enterqueue(int v)
{
q.data[q.rear]=v;
q.rear++;
}
int deletequeue()
{
int t;
t=q.data[q.front];
q.front++;
return(t);
}
int empty()
{
if(q.front==q.rear)
return 1;
return 0;
}
int LocateVex(ALGraph G,char node[2])
{
int i;
for(i = 0 ; i < G.vexnum ; i++)
{
if(strcmp(G.vertices[i].data,node)==0)
return i;
}
return -1;
}
int CreateUDG(ALGraph &G)
{
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
int i,j,k;
char node1[2],node2[2];
ArcNode *p,*q;
printf("请输入顶点数和弧数\n");
printf("例如:5,6\n");
scanf("%d,%d",&G.vexnum,&G.arcnum);
printf("请输入各顶点\n");
for(i = 0 ; i < G.vexnum ; i++)
{
printf("第%d个\n",i+1);
scanf("%s",&G.vertices[i]);
G.vertices[i].firstarc = NULL;
}
//这里开始构造边
printf("请输入边的信息\n");
printf("例如:v1 v2\n");
for(i = 0 ; i < G.arcnum ; i++)
{
printf("第%d条边\n",i+1);
scanf("%s %s",&node1,&node2);
j = LocateVex(G,node1);
k = LocateVex(G,node2);
p = (ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k;
q->adjvex = j;
p->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p;
q->nextarc = G.vertices[k].firstarc;
G.vertices[k].firstarc = q;
}
PrintUDG(G);
return 1;
}
int DeleteUDG(ALGraph &G)
{
int i,j;
ArcNode *p,*q;
char node[2];
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
if(G.arcnum == 0)
{
printf("请先生成图\n");
return 0;
}
printf("请输入要删除的节点\n");
scanf("%s",&node);
i = LocateVex(G,node);
if(i == -1)
{
printf("无此节点\n");
return 0;
}
else
{
G.vexnum--;
if((p = q = G.vertices[i].firstarc) != NULL)
{
G.arcnum--;
p = p->nextarc;
G.vertices[i].firstarc = p;
free(q);
q = p;
while(p != NULL)
{
G.arcnum--;
p = p->nextarc;
G.vertices[i].firstarc = p;
free(q);
q = p;
}
}
for(j = 0 ; j < G.vexnum ; j++ )
{
if(j >= i)
{
strcpy(G.vertices[j].data , G.vertices[j+1].data);
G.vertices[j].firstarc = G.vertices[j+1].firstarc;
}
if(G.vertices[j].firstarc->nextarc != NULL)
{
p = G.vertices[j].firstarc;
q = p->nextarc;
if(p->adjvex == i)
{
G.vertices[j].firstarc = q;
p = q;
q = q->nextarc;
continue;
}
else if(p->adjvex > i)
p->adjvex--;
while(q != NULL)
{
if(q->adjvex == i)
{
p->nextarc = q->nextarc;
free(q);
q = p->nextarc;
}
else if(q->adjvex > i)
q->adjvex--;
else
{
p = p->nextarc;
q = q->nextarc;
}
}
}
else if( (G.vertices[j].firstarc->nextarc == NULL) && (G.vertices[j].firstarc != NULL) )
if( G.vertices[j].firstarc->adjvex == i )
{
G.vertices[j].firstarc = NULL;
}
}
}
PrintUDG(G);
return 1;
}
int InsertUDG(ALGraph &G)
{
//默认一次插入一个节点吧,不然太麻烦
int i,j,k,l;
char node1[2],node2[2];
ArcNode *p,*q;
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
if(G.arcnum == 0)
{
printf("请先生成图\n");
return 0;
}
printf("请输入插入节点的名称\n");
printf("WARNING:绝不可以和之前的节点重名!\n");
scanf("%s",&G.vertices[G.vexnum].data);
G.vertices[G.vexnum].firstarc = NULL;
printf("请输入需要插入的边的数目\n");
scanf("%d",&i);
G.arcnum += i;
G.vexnum++;
printf("请输入边的信息\n");
printf("例如:v6 v2\n");
printf("WARNING:一定要包含刚加入的节点名称!\n");
for(j = 0 ; j < i ; j++)
{
printf("第%d条边\n",j+1);
scanf("%s %s",&node1,&node2);
l = LocateVex(G,node1);
k = LocateVex(G,node2);
p = (ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k;
q->adjvex = l;
p->nextarc = G.vertices[l].firstarc;
G.vertices[l].firstarc = p;
q->nextarc = G.vertices[k].firstarc;
G.vertices[k].firstarc = q;
}
PrintUDG(G);
return 1;
}
void depthfirstsearch(ALGraph *g,int vi)
{
ArcNode *rear;
printf("%s\t",g->vertices[vi].data);
visited[vi]=1;
rear=g->vertices[vi].firstarc;
while((rear!=NULL)&&(!visited[rear->adjvex]))
{
depthfirstsearch(g,rear->adjvex);
rear=rear->nextarc;
}
}
void travel(ALGraph *g)
{
int v;
for(v=0;vvexnum;v++)
if(!visited[v])
depthfirstsearch(g,v);
}
void breadfirstsearch(ALGraph *g)
{
int v,t,i;
ArcNode *rear;
for(i = 0 ; i vexnum ; i++)
visited[i] = 0;
for(v=0;vvexnum;v++)
{
if(!visited[v])
{
printf("%s",g->vertices[v].data);
visited[v]=1;
enterqueue(v);
}
while(!empty())
{
t=deletequeue();
rear=g->vertices[t].firstarc;
while((rear!=NULL)&&(!visited[rear->adjvex]))
{
printf("%s\t",g->vertices[rear->adjvex].data);
visited[rear->adjvex]=1;
enterqueue(rear->adjvex);
rear=rear->nextarc;
}
}
}
}
void menu()
{
printf("*********************************************\n");
printf("* 作者：Dick *\n");
printf("* 信计1001 xxxxxxxxxx *\n");
printf("*********************MENU********************\n");
printf("1 建立无向图\n");
printf("2 删除图中节点\n");
printf("3 插入节点\n");
printf("4 深度优先遍历图\n");
printf("5 广度优先遍历图\n");
printf("6 退出程序\n");
}
void PrintUDG(ALGraph G)
{
int i;
ArcNode *p;
for(i = 0 ; i < G.vexnum ; i++)
{
if(G.vertices[i].firstarc != NULL)
{
printf("与节点%s相邻的节点为:\n",G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p != NULL)
{
printf("%s\t",G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
else
printf("无与节点%s相邻的节点\n",G.vertices[i].data);
}
}
5. 测试结果
图一：菜单项
图五：深度优先遍历图
图四：广度优先遍历图
图三：插入节点
图二：建立图
图一：菜单项
图二：建立图
图三：插入节点
/
本文档为【数据结构图的存储结构及基本操作】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
相关资料
- 稀盐酸配制标准操作规程规程
- 公路工程设计师年终工作总结（通用3篇）
- led大屏使用登记表
- 电子计算器常用按键功能说明
- 北海职业学院学生实验报告
- 渠道建设运作方案
- 上海建筑面积计算规划管理暂行规定2011版
- 公路技术状况评定标准
- 第八册M7U1It's very hot.教学设计
- 男装促销方案
- 泰州市姜堰区教育局
- 读书报告 苏联亡党亡国二十年祭
- 疾控中心督导表
- 员工旷工确认单
- 3《弘扬优秀家风》教学设计（人教版部编版小学五年级道德与法治下册）
- 2022考察组在民主测评会上的讲话发言材料
- 贷款明细表
- SMT制程改善方案8
- 地质构造影响区采煤工作面瓦斯治理技术研究
- 2006年全国中学生天文奥林匹克竞赛预赛前100名名单-欢迎光临北京天文馆(1)
热门搜索
- A1《法拉第电磁感应定律》学情分析方案
- Definition of a Football Fan
- arcgis中自动合并细碎小班的方法
- 我是一只小鸟
- 国有企业薪酬管理制度
- 达旗街道划分情况
- 曝气器性能对比和趋势分析
- 感谢有你作文600字 - 1高分作文
- 医疗保险异地就医申请表
- 保险精算流量三角形
- 武汉抗疫英雄事迹材料800字左右
- 基于QGIS和QTCreator的应急制图自动化研究
- 鼻病康复指南
- 建筑物垂直度标高全高测量记录(已填内容)
- A1《法拉第电磁感应定律》学情分析方案
- Definition of a Football Fan
- arcgis中自动合并细碎小班的方法
- 我是一只小鸟
- 国有企业薪酬管理制度
- 达旗街道划分情况
- 曝气器性能对比和趋势分析
- 感谢有你作文600字 - 1高分作文
- 医疗保险异地就医申请表
- 保险精算流量三角形
- 武汉抗疫英雄事迹材料800字左右
- 基于QGIS和QTCreator的应急制图自动化研究
- 鼻病康复指南
- 建筑物垂直度标高全高测量记录(已填内容)
你可能还喜欢
- 苏教版五年级数学上册：小数的意义和读、写课件
- 矿山地质环境保护与土地复垦方案编制指南
- 生产与仓储循环 - 控制测试
- 健康长寿，美容塑身-元气养生舱
- 喊的反义词是
- 《医疗质量管理办法解读》PPT课件教案模板
- 真了不起_六年级作文
- 英威腾GD整理变频器调试说明
- 杯子的结构
- 自动武器结构设计-武器发射工程教学大纲
- 综合项目施工便道和便桥综合项目施工专项方案
- 泰嘉在ACS和PCI术中的应用
- 实验十五 I3-I- I2平衡常数的测定(2)
- 三级微型消防站配备标准
- 小学数学竞赛：加乘原理之数字问题(一).教师版解题技巧 培优 易错 难
- 新《食品安全法》学习笔记
- 知识产权机构管理制度
- 知识产权机构管理制度
- 知识产权机构管理制度
- 知识产权机构管理制度
浙公网安备 33021202002483