数据结构中图的建立及输出的课程设计

数据结构课程设计 图的建立及输出 1）建立图的存储结构（有向图） 2）~

邻接表还是逆邻接表？如果是逆邻接表，每个顶点出发邻接表的链表中的结点个数就是入度如果是邻接表过程如下：有一个辅助数组，大小就是顶点数量，所有元素初值都为0从头到尾遍历每个顶点出发的邻接表的结点，只要当前结点的数据是几（也就是第几个结点被有向弧进入了），这个下标的辅助数组元素加1，等所有的邻接表的小链表遍历完了，这个辅助数组中各个下标的数字就是该顶点的入度

//图的遍历算法程序

//图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，程序如下：
#include
//#include
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char *vexs; //顶点向量
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}Graph;
//队列类
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base;
int front;
int rear;
};
//图G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
//创建无向网
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("输入顶点数和弧数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点.
",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化顶点
printf("输入顶点%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回车
}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.
",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("输入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值
temp=getchar(); //接收回车
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 && i=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度优先遍历
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次执行DFS时,k为-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //访问第k个顶点
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
void BFS(Graph G){
int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i尚未访问
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w]=true;
printf("%c ",G.vexs[w]);
Q.EnQueue(w);
}
}
}
}

//主函数
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("
广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("
深度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("
程序结束.
");
}
输出结果为（红色为键盘输入的数据，权值都置为1）：
输入顶点数和弧数:8 9
输入8个顶点.
输入顶点0:a
输入顶点1:b
输入顶点2:c
输入顶点3:d
输入顶点4:e
输入顶点5:f
输入顶点6:g
输入顶点7:h
输入9条弧.
输入弧0:a b 1
输入弧1:b d 1
输入弧2:b e 1
输入弧3:d h 1
输入弧4:e h 1
输入弧5:a c 1
输入弧6:c f 1
输入弧7:c g 1
输入弧8:f g 1
广度优先遍历: a b d h e c f g
深度优先遍历: a b c d e f g h
程序结束.

1、一元稀疏多项式相加

详细设计

4.1 程序头的设计:
#include<stdio.h>
#include<malloc.h>
typedef struct pnode
{int coef;/*系数 */
int exp;/*指数 */
struct pnode *next;/*下一个指针*/
}pnode;

4.2 用头插法生成一个多项式，系数和指数输入0时退出输入
pnode * creat()
{int m,n; pnode *head,*rear,*s;
/*head为头指针，rear和s为临时指针*/

head=(pnode *)malloc(sizeof(pnode));
rear=head;
/*指向头*/
printf("input coef:");/*输入系数*/
scanf("%d",&n);
printf("input exp:");/*输入指数*/
scanf("%d",&m);
while(n!=0)/*输入0就退出*/
{s=(pnode *)malloc(sizeof(pnode));
s->coef=n;
s->exp=m;
s->next=NULL;
rear->next=s;/*头插法*/
rear=s;
printf("input coef:");/*输入系数*/
scanf("%d",&n);
printf("input exp:");/*输入指数*/
scanf("%d",&m);
}
head=head->next;/*第一个头没有用到*/
return head;
}
4.3 显示一个多项式
void display(pnode *head)
{pnode *p;int one_time=1; p=head;
while(p!=NULL)/*不为空的话*/
{
if(one_time==1)
{if(p->exp==0)/*如果指数为0的话，直接输出系数*/
printf("%d",p->coef); /*如果系数是正的话前面就要加+号*/
else if(p->coef==1||p->coef==-1)
printf("x^%d",p->exp);/*如果系数是1的话就直接输出+x*/
/*如果系数是-1的话就直接输出-x号*/
else if(p->coef>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/
printf("%dx^%d",p->coef,p->exp);
else if(p->coef<0)/*如果系数是小于0的话就输出系数x^指数的形式*/
printf("%dx^%d",p->coef,p->exp);
one_time=0;
}
else{
if(p->exp==0)/*如果指数为0的话，直接输出系数*/
{if(p->coef>0)
printf("+%d",p->coef); /*如果系数是正的话前面就要加+号*/
}
else if(p->coef==1)
printf("+x^%d",p->exp);
else if(p->coef==-1)
printf("x^%d",p->exp);/*如果系数是1的话就直接输出+x号*/
else if(p->coef>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/
printf("+%dx^%d",p->coef,p->exp);
else if(p->coef<0)/*如果系数是小于0的话就输出系数x^指数的形式*/
printf("%dx^%d",p->coef,p->exp);
}
p=p->next;/*指向下一个指针*/
}
printf("\n");

4.4 两个多项式的加法运算
pnode * add(pnode *heada,pnode *headb)
{pnode *headc,*p,*q,*s,*r;
/*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并并向右移动*/
int x;
/*x为系数的求和*/
p=heada;
/*指向第一个多项式的头*/
q=headb;
/*指向第二个多项式的头*/
headc=(pnode *)malloc(sizeof(pnode));
r=headc;
/*开辟空间*/
while(p!=NULL&&q!=NULL)
/*2个多项式的某一项都不为空时*/
{if(p->exp==q->exp)/*指数相等的话*/
{x=p->coef+q->coef;/*系数就应该相加*/
if(x!=0)/*相加的和不为0的话*/
{s=(pnode *)malloc(sizeof(pnode));/*用头插法建立一个新的节点*/
s->coef=x;
s->exp=p->exp;
r->next=s;
r=s;
}
q=q->next;p=p->next;
/*2个多项式都向右移*/
}
else if(p->exp<q->exp)/*p的系数小于q的系数的话，就应该复制q接点到多项式中*/
{s=(pnode *)malloc(sizeof(pnode));
s->coef=q->coef;
s->exp=q->exp;
r->next=s;
r=s;
q=q->next;/*q向右移动*/
}
else/*p的系数大于q的系数的话，就应该复制p接点到多项式中*/
{s=(pnode *)malloc(sizeof(pnode));
s->coef=p->coef;
s->exp=p->exp;
r->next=s;
r=s;
p=p->next;/*p向右移动*/
}
}
当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生
while(p!=NULL)
{s=(pnode *)malloc(sizeof(pnode));
s->coef=p->coef;
s->exp=p->exp;
r->next=s;
r=s;
p=p->next;
}
当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生
while(q!=NULL)
{s=(pnode *)malloc(sizeof(pnode));
s->coef=q->coef;
s->exp=q->exp;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;
/*最后指向空*/
headc=headc->next;/*第一个头没有用到*/
return headc;/*返回头接点*/

4.5 两个多项式的减法运算，和加法类似，不同的地方已经注释
pnode * sub(pnode *heada,pnode *headb)
{pnode *headc,*p,*q,*s,*r;
int x;
p=heada;q=headb;
headc=(pnode *)malloc(sizeof(pnode));
r=headc;
while(p!=NULL&&q!=NULL)
{if(p->exp==q->exp)
{x=p->coef-q->coef;/*系数相减*/
if(x!=0)
{s=(pnode *)malloc(sizeof(pnode));
s->coef=x;
s->exp=p->exp;
r->next=s;
r=s;
}
q=q->next;p=p->next;
}
else if(p->exp<q->exp)/*p的系数小于q的系数的话*/
{s=(pnode *)malloc(sizeof(pnode));
s->coef=-q->coef;/*建立的接点的系数为原来的相反数*/
s->exp=q->exp;
r->next=s;
r=s;
q=q->next;
}
else
{s=(pnode *)malloc(sizeof(pnode));
s->coef=p->coef;
s->exp=p->exp;
r->next=s;
r=s;
p=p->next;
}
}
while(p!=NULL)
{s=(pnode *)malloc(sizeof(pnode));
s->coef=p->coef;
s->exp=p->exp;
r->next=s;
r=s;
p=p->next;
}
while(q!=NULL)
{s=(pnode *)malloc(sizeof(pnode));
s->coef=-q->coef;/*建立的接点的系数为原来的相反数*/
s->exp=q->exp;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;
headc=headc->next;
return headc;

4.6 界面设计:
printf("\n ****************************************\n");
printf("\n ************** 03 Computer *************\n");
printf("\n ******** Class:two **** Num:34 *********\n");
printf("\n *********** Name: xie pan **********\n");
printf("\n ****************************************\n");
printf("\n --------------1: add -------------\n");
printf("\n --------------2: sub -------------\n");
printf("\n --------------3: exit ------------\n");
printf("\n ****************************************\n");

4.7 连接程序:
case 1:add_main();break;/*加法*/
case 2:sub_main();break;/*减法*/
case 3:break;/*退出*/

#include <iostream>
#include <malloc.h>
using namespace std;
#define int_max 10000
#define inf 9999
#define max 20

//…………………………………………邻接矩阵定义……………………
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];

typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
int i=0;
while(G.vexs[i]!=v)
{
++i;
}
return i;
}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{
char v1,v2;
int i,j,w;
printf("\n§%c %c %c 创建无向图 %c %c %c§\n",6,6,6,6,6,6);
printf("请输入图G顶点和弧的个数(4 6)不包括'()':\n");
//cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:(4 6)不包括“()”"<<endl;
cin>>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{
cout<<"输入顶点"<<i+1<<":"<<endl;
cin>>G.vexs[i];
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k!=G.arcnum;++k)
{
cout<<"输入一条边依附的顶点和权:(a b 3)不包括“()”"<<endl;
cin>>v1>>v2>>w;//输入一条边依附的两点及权值
i=localvex(G,v1);//确定顶点V1和V2在图中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
cout<<"图G邻接矩阵创建成功！"<<endl;
return G.vexnum;
}

void ljjzprint(MGraph_L G)
{
int i,j;
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
cout<<G.arcs[i][j].adj<<" ";
cout<<endl;
}
}
int visited[max];//访问标记
int we;

typedef struct arcnode//弧结点
{
int adjvex;//该弧指向的顶点的位置
struct arcnode *nextarc;//弧尾相同的下一条弧
char *info;//该弧信息
}arcnode;

typedef struct vnode//邻接链表顶点头接点
{
char data;//结点信息
arcnode *firstarc;//指向第一条依附该结点的弧的指针
}vnode,adjlist;

typedef struct//图的定义
{
adjlist vertices[max];
int vexnum,arcnum;
int kind;
}algraph;

//…………………………………………队列定义……………………
typedef struct qnode
{
int data;
struct qnode *next;

}qnode,*queueptr;

typedef struct
{
queueptr front;
queueptr rear;

}linkqueue;

//………………………………………………………………………
typedef struct acr
{
int pre;//弧的一结点
int bak;//弧另一结点
int weight;//弧的权
}edg;

int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图
{

int i=0,j=0;
arcnode *arc,*tem,*p;
for(i=0;i!=G.vexnum;++i)
{
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(gra.vertices[i].firstarc==NULL)
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
gra.vertices[i].firstarc=arc;
arc->nextarc=NULL;
p=arc;
++j;
while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
tem=(arcnode *)malloc(sizeof(arcnode));
tem->adjvex=j;
gra.vertices[i].firstarc=tem;
tem->nextarc=arc;
arc=tem;
++j;
}
--j;
}
}
else
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
p->nextarc=arc;
arc->nextarc=NULL;
p=arc;
}
}
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
cout<<"图G邻接表创建成功！"<<endl;
return 1;
}

void adjprint(algraph gra)
{
int i;
for(i=0;i!=gra.vexnum;++i)
{
arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}
}

int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点
//即以V为尾的第一个结点
{
if(v.firstarc!=NULL)
return v.firstarc->adjvex;

}

int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点
{
arcnode *p;
p=v.firstarc;
while(p!=NULL&&p->adjvex!=w)
{
p=p->nextarc;
}
if(p->adjvex==w&&p->nextarc!=NULL)
{
p=p->nextarc;
return p->adjvex;
}
if(p->adjvex==w&&p->nextarc==NULL)
return -10;
}

int initqueue(linkqueue &q)//初始化队列
{
q.rear=(queueptr)malloc(sizeof(qnode));
q.front=q.rear;
if(!q.front)
return 0;
q.front->next=NULL;
return 1;
}

int enqueue(linkqueue &q,int e)//入队
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}

int dequeue(linkqueue &q,int &e)//出队
{
queueptr p;
if(q.front==q.rear)
return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;
}

int queueempty(linkqueue q)//判断队为空
{
if(q.front==q.rear)
return 1;
return 0;
}

void bfstra(algraph gra)//广度优先遍历
{
int i,e;
linkqueue q;
for(i=0;i!=gra.vexnum;++i)
visited[i]=0;
initqueue(q);
for(i=0;i!=gra.vexnum;++i)

if(!visited[i])
{ visited[i]=1;
cout<<gra.vertices[i].data;
enqueue(q,i);
while(!queueempty(q))
{
dequeue(q,e);
// cout<<" "<<e<<" ";
for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we))
{
if(!visited[we])
{
visited[we]=1;
cout<<gra.vertices[we].data;
enqueue(q,we);
}
}
}
}
}

int dfs(algraph gra,int i);//声明DFS

int dfstra(algraph gra)
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
dfs(gra,j);
}
return 0;
}

int dfs(algraph gra,int i)
{
visited[i]=1;
int we1;
// cout<<i<<visited[i]<<endl;
cout<<gra.vertices[i].data;
// cout<<endl;
for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))
{
// cout<<we<<visited[we]<<endl;
we1=we;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
if(visited[we]==0)
// cout<<
dfs(gra,we);//<<endl;
// cout<<i<<we1<<endl;
we=we1;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
}
return 12;
}

int bfstra_fen(algraph gra)//求连通分量
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
{
dfs(gra,j);
cout<<endl;
}
}
return 0;
}

typedef struct
{
int adjvex;
int lowcost;
}closedge;

int prim(int g[][max],int n) //最小生成树PRIM算法
{
int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
//prevex[]存储最短路径在U中的结点
int i,j,k,min;
for(i=2;i<=n;i++) //n个顶点，n-1条边
{
lowcost[i]=g[1][i]; //初始化
prevex[i]=1; //顶点未加入到最小生成树中
}
lowcost[1]=0; //标志顶点1加入U集合
for(i=2;i<=n;i++) //形成n-1条边的生成树
{
min=inf;
k=0;
for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);
lowcost[k]=0; //顶点k加入U
for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{
lowcost[j]=g[k][j];
prevex[j]=k;
}
printf("\n");
}
return 0;
}

int acrvisited[100];//kruscal弧标记数组

int find(int acrvisited[],int f)
{
while(acrvisited[f]>0)
f=acrvisited[f];
return f;
}

void kruscal_arc(MGraph_L G,algraph gra)
{

edg edgs[20];
int i,j,k=0;
for(i=0;i!=G.vexnum;++i)
for(j=i;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=10000)
{
edgs[k].pre=i;
edgs[k].bak=j;
edgs[k].weight=G.arcs[i][j].adj;
++k;
}
}
int x,y,m,n;
int buf,edf;
for(i=0;i!=gra.arcnum;++i)
acrvisited[i]=0;
for(j=0;j!=G.arcnum;++j)
{
m=10000;
for(i=0;i!=G.arcnum;++i)
{
if(edgs[i].weight<m)
{
m=edgs[i].weight;
x=edgs[i].pre;
y=edgs[i].bak;
n=i;
}

}
// cout<<x<<y<<m;
// cout<<endl;
buf=find(acrvisited,x);
edf=find(acrvisited,y);
// cout<<buf<<" "<<edf<<endl;
edgs[n].weight=10000;
if(buf!=edf)
{
acrvisited[buf]=edf;

cout<<"("<<x<<","<<y<<")"<<m;
cout<<endl;
}
}
}

void main()
{
algraph gra;
MGraph_L G;
int i,d,g[20][20];
char a='a';
d=creatMGraph_L(G);
creatadj(gra,G);
vnode v;
printf("\n\n");
printf("\t§%c %c %c %c 图的遍历和生成树求解实现 %c %c %c %c§\n",6,6,6,6,6,6,6,6,6,6);
printf("\t | %c1.显示该图的邻接矩阵 |\n",3);
printf("\t | %c2.显示该图的邻接表 |\n",3);
printf("\t | %c3.深度优先遍历 |\n",3);
printf("\t | %c4.广度优先遍历 |\n",3);
printf("\t | %c5.最小生成树PRIM算法 |\n",3);
printf("\t | %c6.最小生成树KRUSCAL算法 |\n",3);
printf("\t | %c0.该图的连通分量 |\n",3);
printf("\t | %c0.退出 |\n",3);
printf("\t§ (+﹏+) § (+﹏+) § (+﹏+) § \n");
int s;
char y='y';
while(y='y')
{
printf("请选择菜单：");
cin>>s;
switch(s)
{
case 1:
printf("邻接矩阵显示如下：");
ljjzprint(G);
break;
case 2:
printf("邻接表显示如下：");
adjprint(gra);
break;
case 3:
printf("广度优先遍历：");
bfstra(gra);
//cout<<endl;
break;
case 4:
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
printf("深度优先遍历：");
dfstra(gra);
//cout<<endl;
break;
case 5:
for(i=0;i!=G.vexnum;++i)
for(int j=0;j!=G.vexnum;++j)
g[i+1][j+1]=G.arcs[i][j].adj;
printf("prim:");
prim(g,d);
break;
case 6:
printf("kruscal:");
kruscal_arc(G,gra);
break;
case 7:
printf("连通分量:");
bfstra_fen(gra);
break;
case 0:exit(0);break;

}
printf("是否继续？y/n:");
//cin>>y;
if(y=='n')
break;
}
}

---

皇姑区17121824165： 数据结构中图的建立及输出的课程设计 - ？
家初必可： 1、一元稀疏多项式相加 详细设计4.1 程序头的设计: #include #include typedef struct pnode {int coef;/*系数 */ int exp;/*指数 */ struct pnode *next;/*下一个指针*/ }pnode;4.2 用头插法生成一个多项式,系数和指数输入0时退出输入 pnode * ...

皇姑区17121824165： 数据结构课程设计题目,图的建立以及遍历. - ？
家初必可： //图的遍历算法程序 //图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次.图的遍历有深度遍历算法和广度遍历算法,程序如下: #include <iostream> //#include <malloc.h> #define INFINITY 32767 ...

皇姑区17121824165： 数据结构课程设计 迪结斯特拉算法问题描述:图的存储结构的建立、Dijkstra算法.实现要求:(1)将图的信息建立文件;(2)从文件读入图的信息,建立... - ？
家初必可：[答案] 额,我这个写的已经比较清楚了.是数组模拟邻接表的,addedge里面建立的是双向边.邻接矩阵的话.cin>>n>>m;//n point m edgefor(int i=1;i<=m;i++){cin>>from>>to>>value;g[from][to] = value;}memset(dis,20,sizeof(dis)); dis[1]=0; for(int i=1;i<=n;i++...

皇姑区17121824165： 数据结构课程设计:如何以邻接矩阵的方式确定一个图⑴建立并显示出它的邻接链表;⑵给出它的关键路径(要求:显示出VE,VL,E,L,L - E的结果).？
家初必可： #include <stdio.h> #define INFI 9999 #define MAXNUM 8 typedef struct{ int arcs[MAXNUM+1][MAXNUM+1]; char vexs[MAXNUM+1]; int vexnum,arcnum; }MGraph; int Locate(MGraph &G1,char &u) { int l; G1.vexs[0]=u; for(l=G1.vexnum;l>=0 && (G1....

皇姑区17121824165： 数据结构设计？
家初必可： 设计说明 1、 算法设计的思想 建立图类,建立相关成员函数.最后在主函数中实现.具体成员函数的实现请参看源程序. 2、 主要的数据结构设计说明 图邻接矩阵、邻接表的建立.图的深度优先遍历、拓扑排序、顶点之间的最短路径. 3、 程序的主要模板template <class Type> class Graph 4、 程序的主要函数 Graph、link()、DFTraverse()、TopologicalOrder()、 TopologicalOrder()、GetVertexPos()、ShortestPath

皇姑区17121824165： 数据结构中 图的建立及输出 - ？
家初必可： package graph; public class Graphm implements Graph{ private int[][]matrix; private int numEdge; public int[]Mark; public Graphm(int n){ Mark=new int[n]; matrix=new int[n][n]; numEdge=0; } public int n() public int e() public Edge first (int v){ for(int i=0...

皇姑区17121824165： 数据结构中图的建立及算法实现 - ？
家初必可： #include<stdio.h>#include<stdlib.h>#define MaxSize 20 struct ArcNode { int adjvex; struct ArcNode *nextarc; }; struct Vnode { int data; struct ArcNode *firstarc; }; struct Vnode AdjList[MaxSize]; int m,n,v,cord; void main() { void creatgraph(struct ...

皇姑区17121824165： 数据结构课程设计:稀疏矩阵操作任务:(1)完成一稀疏矩阵转置,(2)能够完成两个稀疏矩阵相加,(3)输出稀疏矩阵 最好能写明:存储结构、稀疏矩... - ？
家初必可：[答案] 一、需求分析 二、概要设计 三、详细设计:Cpp1.cpp 四、调试分析 五、用户手册及测试数据:执行Cpp1.exe 六、附录 [数据结构]数据结构稀疏矩阵加法实验报告 一、需求分析 假设稀疏矩阵M和N均以三元组表作为存储结构...

皇姑区17121824165： 数据结构课程设计,有向图,C语言高手进 - ？
家初必可： 写C程序,随机给出n*n的邻接矩阵,并打印输出邻接矩阵,以及有向图的边的个数,每个顶点的度,并判断该图中是否存在Euler回路: (1)如果为n阶,则随机产生一个n*n的邻接矩阵; (2)输出邻接矩阵,边的个数,每个顶点的度以及图中...

皇姑区17121824165： 数据结构课程设计报告 - ？
家初必可： 1、一元稀疏多项式相加详细设计4.1 程序头的设计: #include<stdio.h> #include<malloc.h> typedef struct pnode {int coef;/*系数 */ int exp;/*指数 */ struct pnode *next;/*下一个指针*/ }pnode;4.2 用头插法生成一个多项式,系数和...