首页

文章

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

发布网友 发布时间：2022-04-19 09:43

我来回答

共2个回答

热心网友 时间：2023-07-29 04:55

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;/*退出*/

热心网友 时间：2023-07-29 04:55

#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;
}
}
ups快递客服电话24小时 贷款记录在征信保留几年? 安徽徽商城有限公司公司简介 安徽省徽商集团新能源股份有限公司基本情况 安徽省徽商集团有限公司经营理念 2019哈尔滨煤气费怎么有税? 快手删除的作品如何恢复 体育理念体育理念 有关体育的格言和理念 什么是体育理念 万里挑一算彩礼还是见面礼 绿萝扦插多少天后发芽 绿萝扦插多久发芽 扦插绿萝多久发芽 炖牛排骨的做法和配料 网络诈骗定罪标准揭秘 “流水不争先”是什么意思? mc中钻石装备怎么做 为什么我的MC里的钻石块是这样的?我想要那种。是不是版本的问题?如果是... 带“偷儿”的诗句 “君不见巴丘古城如培塿”的出处是哪里 带“奈何”的诗句大全(229句) 里翁行()拼音版、注音及读音 带“不虑”的诗句 “鲁肃当年万人守”的出处是哪里 无尘防尘棚 进出口报关流程,越详细越好。谢谢大家指教。 双线桥不是看化合价升多少就标多少的吗?为什么CL2+2KI=2KCL+I2中I失... 出师表高锰酸钾有画面了吗 2021年幼儿园新学期致家长一封信 电脑屏幕一条黑线怎么办? 销售代理商销售代理商的特点 商业代理商业代理的特征 如何看微信有没有开通微众银行 为什么微众没有开户 微众银行怎么开户 微众银行APP开户流程是什么? 唐古拉山海拔唐古拉山海拔是多少 怎么看待取消跳广场舞的人的退休金 如何选购新鲜的蓝田水柿? 恭城水柿柿树作用 创维洗衣机使用教程 创维全自动洗衣机怎么使用 自动开门器 狗羊属相婚姻相配吗 3岁的小孩不会说话怎么办 3岁孩子不会说话,应该挂什么科? 3岁小孩不会说话正常吗 鹿茸炖乌鸡怎么做? 新型冠状肺炎吃什么药可以预防 冰箱上电后一直响 食品生产许可证编号开头为“ G”。 数据结构课程设计题目，图的建立以及遍历。 图的算法中, 404 Not Found 图的最小生成树算法？ 求图的生成树的算法有哪些？ 图的建立 C语言图的创建和遍历算法，紧急 图的算法 数据结构 图的创建与访问算法 图的算法实现 急急急~~~~~~~~~ 数据结构中图的建立及算法实现 索尼电视机型号有什么含义 索尼电视机型号如何表示 sony是电视的什么牌子 索尼电视怎么样 索尼电视语音为啥叫小微 索尼电视的质量和效果怎样？ 日本的索尼电视怎么调制成中国语言啊。求解 索尼电视语音开机要喊好多次是什么原因 索尼4K HDR OLED电视A9F有语音功能么？ 图的所有生成树的算法 404 Not Found 数据结构的图的算法 一般图形voronoi图的自动生成算法怎么做？ 图算法 c++ 手机系统异常是什么意思 常用的会计软件有哪些？ 初级会计电算化 会计软件的生命周期分为哪几个阶段，并简述 会计电算化和会计软件的名词解释 专业会计软件的名词解释是什么 和会计软件是一个么 谁有免费破解版的财务软件（中小企业） 我国会计软件行业急待解决的几个问题 软件的破解版，和没破解版的什么区别？ 有没有破解版能用的会计软件？ 我国当前管理型会计软件应用遇到的主要问题是什么？如何解决 财务软件哪些好用（免费的或者破解版） 下载圆梦会计软件怎么解压?急 财务软件破解 财务软件（破解版） 金蝶会计软件出现这种问题怎么解决啊
声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com