2020-10-15 //严蔚敏《数据结构》 //图:*伺判

发布于:2021-09-22 04:49:10

//严蔚敏《数据结构》
//图:*伺判
//自学中,加油!!
#include
using namespace std;
#define InfoType double
#define VertexType string
const int MaxVertexNum=20;
typedef struct ArcBox
{
int tailvex,headvex;//该弧的尾邻接点、头邻接点位置下标
struct ArcBox* tlink,* hlink;//分别为弧尾相同、弧头相同的弧的链域
InfoType* info;
}ArcBox;//弧

typedef struct VexNode
{
VertexType data;
ArcBox* firstin,* firstout;
}VexNode;

typedef struct
{
VexNode xlist[MaxVertexNum];
int vexnum,arcnum;
}OLGraph;

int Locate_xlist(OLGraph G,VertexType v)
{
for(int i=0;i!=G.vexnum;i++){
if(G.xlist[i].data==v)
return i;
}
cout<<"未找到
";
return -1;
}

bool Creat_OLGraph(OLGraph& G)//用十字链表创建有向网
{
cout<<"输入有向网的顶点数和弧数:";
cin>>G.vexnum>>G.arcnum;
cout<<"输入"<";
for(int i=0;i!=G.vexnum;i++){//输入的同时对十字链表进行初始化
cin>>G.xlist[i].data;
G.xlist[i].firstin=G.xlist[i].firstout=nullptr;
}
VertexType v1,v2;
InfoType w;
int i,j;
ArcBox* p;
for(int k=0;k!=G.arcnum;k++){
cout<<"输入两个顶点以及权值
";
cin>>v1>>v2>>w;
i=Locate_xlist(G,v1);
j=Locate_xlist(G,v2);
p=new ArcBox;
if(!p)
return false;
p->tailvex=i;p->headvex=j;
p->info=new InfoType;
*p->info=w;
p->tlink=G.xlist[i].firstout;
G.xlist[i].firstout=p;
p->hlink=G.xlist[j].firstin;
G.xlist[j].firstin=p;
}
return true;
}

void Output_OLGraph(OLGraph G)
{
ArcBox* p;
cout<<"各个顶点的出度
";
for(int i=0;i!=G.vexnum;i++){
cout<<"顶点信息:"< p=G.xlist[i].firstout;
while(p){
cout<<"以该顶点为弧尾的邻接点->"<headvex;
if(p->info)
cout<<" 权值:"<<*p->info;
p=p->tlink;
}
cout< }
cout<<"------"< cout<<"各个顶点的入度
";
for(int i=0;i!=G.vexnum;i++){
cout<<"顶点信息:"< p=G.xlist[i].firstin;
while(p){
cout<<"以该顶点为弧头的邻接点->"<tailvex;
if(p->info)
cout<<" 权值:"<<*p->info;
p=p->hlink;
}
cout< }
}
//栈为*伺判蚍
#define ElemType int
typedef struct SNode
{
ElemType data;
struct SNode* next;
}SNode,* LinkStack;

bool Init_SNode(LinkStack& s)//初始化链栈
{
s=new SNode;
if(!s)
return false;
s->next=nullptr;
return true;
}

bool IsEmpty_SNode(LinkStack s)//若链栈s无数据,返回true;否则返回false
{
if(!s->next)
return true;
return false;
}

int Length_SNode(LinkStack s)//返回链栈s的数据长度(不包含头结点)
{
int i=0;
LinkStack p=s->next;
while(p){
p=p->next;
i++;
}
return i;
}

bool GetTop_SNode(LinkStack s,ElemType& e)//e存储栈顶元素
{
LinkStack p=s;
while(p->next){
p=p->next;
}
e=p->data;
return true;
}

bool Push_SNode(LinkStack& s,ElemType e)//压栈
{
LinkStack r=s;
while(r->next){
r=r->next;
}
LinkStack p=new SNode;
if(!p)
return false;
p->data=e;
p->next=r->next;
r->next=p;
r=p;
return true;
}

bool Pop_SNode(LinkStack& s,ElemType& e)//出栈
{
LinkStack r=s;
while(r->next){
r=r->next;
}
e=r->data;
LinkStack p=s;//bug1 刚开始无p来指向 r指向结点的前驱结点(即无126~131行代码)
//如果直接释放尾结点(即free(r)),则释放后链栈的尾结点的next指针不是nullptr,不导致错误
while(p->next!=r){
p=p->next;
}
p->next=nullptr;
free(r);
return true;
}


void Output_SNode(LinkStack s)//遍历输出链栈数据
{
LinkStack p=s->next;
cout<<"链栈元素(从栈底到栈顶遍历):
";
cout<<"--------"< while(p){
cout<data< p=p->next;
}
cout<<"--------"<}

void GetInDegree(OLGraph G,int InDegree[])//将G中同一下标的每个顶点的入度赋值给相应的InDegree元素
{
int count;
ArcBox* p;
for(int i=0;i!=G.vexnum;i++){
count=0;
p=G.xlist[i].firstin;
while(p){
count++;
p=p->hlink;
}
InDegree[i]=count;
}
}

bool Topo_Graph(OLGraph G)//*伺判
{
LinkStack s;
Init_SNode(s);
int InDegree[G.vexnum];
GetInDegree(G,InDegree);
int i;
for(i=0;i!=G.vexnum;i++){
if(!InDegree[i])
Push_SNode(s,i);
}
int count=0,k;
while(!IsEmpty_SNode(s)){
Pop_SNode(s,i);
cout<<"删除的顶点:"< for(ArcBox* p=G.xlist[i].firstout;p;p=p->tlink){
k=p->headvex;
if(!(--InDegree[k]))
Push_SNode(s,k);
}
}
if(count return false;
else return true;
}

int main()
{
OLGraph G;
if(Creat_OLGraph(G))
Output_OLGraph(G);
Topo_Graph(G);
return 0;
}



测试图例:


输入有向网的顶点数和弧数:5 6
输入5个顶点信息
v1 v3 v4 v5 v2
输入两个顶点以及权值
v1 v2 1
输入两个顶点以及权值
v1 v4 2
输入两个顶点以及权值
v1 v3 3
输入两个顶点以及权值
v4 v5 4
输入两个顶点以及权值
v3 v5 5
输入两个顶点以及权值
v3 v2 6
各个顶点的出度
顶点信息:v1以该顶点为弧尾的邻接点->1 权值:3以该顶点为弧尾的邻接点->2 权值:2以该顶点为弧尾的邻接点->4 权值:1
顶点信息:v3以该顶点为弧尾的邻接点->4 权值:6以该顶点为弧尾的邻接点->3 权值:5
顶点信息:v4以该顶点为弧尾的邻接点->3 权值:4
顶点信息:v5
顶点信息:v2
------
各个顶点的入度
顶点信息:v1
顶点信息:v3以该顶点为弧头的邻接点->0 权值:3
顶点信息:v4以该顶点为弧头的邻接点->0 权值:2
顶点信息:v5以该顶点为弧头的邻接点->1 权值:5以该顶点为弧头的邻接点->2 权值:4
顶点信息:v2以该顶点为弧头的邻接点->1 权值:6以该顶点为弧头的邻接点->0 权值:1
删除的顶点:v1
删除的顶点:v4
删除的顶点:v3
删除的顶点:v5
删除的顶点:v2

Process returned 0 (0x0) execution time : 45.843 s
Press any key to continue.


相关推荐

最新更新

猜你喜欢