3_1.cpp

关于稀疏矩阵的全部算法

//图的运算的实现文件graph3.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include"3_1.h"
//构造函数,初始化图的邻接矩阵与边集数组
adjMList::adjMList(RCW GE[],int n,int e)
{int i,j;
 for(i=0; i<n; i++)
 for(j=0; j<n; j++)
  if(i==j) GA[i][j]=0;
  else GA[i][j]=Default;
 for(i=0;i<e;i++) GE[i].weight=0;
 numE=0;
}
//初始化图的邻接表
void adjMList::InitGAdjoin(adjlist& GL,int n)
{GL=new edgenode*[n];
 for(int i=0; i<n; i++) GL[i]=NULL;
}
//删除图的邻接表
void adjMList::DeleteAdjoin(adjlist GL,int n)
{int i;
 edgenode* p;
 for(i=0;i<n;i++) {
   p=GL[i];
   while(p!=NULL) {GL[i]=p->next;
    delete p;p=GL[i];}}
 delete []GL;
}
//输出边集数组中的每条边
void adjMList::OutputEdgeSet(RCW ge[],int e)
{int i,k=0;
 cout<<"{";
 for(i=0; i<=e-2; i++)
  if(ge[i].weight>0){k++;
   cout<<'('<<ge[i].row<<','<<ge[i].col;
   cout<<','<<ge[i].weight<<") ";
   if(k%5==0) cout<<endl;}
  if(e>0&&ge[i].weight>0) {
   cout<<'('<<ge[e-1].row<<','<<ge[e-1].col;
   cout<<','<<ge[e-1].weight<<')';}
   cout<<'}'<<endl;
}
//建立带权图的邻接矩阵
void adjMList::CreateMatrix(int n,int &e,RCW r[])
{int i,j,k=0,w;
 cout<<"依次输入带权图的每条边的起点和终点"<<endl;
 cout<<"序号及权值!直到输入权值为0的边为止!"<<endl;
 do {i=r[k].row;j=r[k].col;w=r[k].weight;
     Check(n,i,j);
     if(k==e-1) break;
     GA[i][j]=GA[j][i]=w;k++;
   }while(1);
 numE=e=k;
 cout<<"邻接矩阵:\n";
 for(i=0;i<n;i++)
 {for(j=0;j<n;j++)
   cout<<setw(4)<<GA[i][j];
   cout<<endl;}
}
//检查输入的边序号是否越界,若越界则重输
void adjMList::Check(int n, int& i, int& j)
{while(1) {
   if(i<0 || i>=n ||j<0 || j>=n)
    cout<<"输入有误,请重输!";
   else return;
  cin>>i>>j;}
}
//根据图的邻接矩阵生成图的边集数组
void adjMList::ChangeEdgeSet(RCW GE[],int n,int e)
{//假定只考虑无向图的情况
 int i,j,k=0;
 for(i=0; i<n; i++)
 for(j=i+1; j<n; j++)
  if(GA[i][j]!=0 && GA[i][j]!=Default)
   {if(k==e) {cout<<"数组GE下标越界!\n";
     exit(1);}
    GE[k].row=i;
    GE[k].col=j;
    GE[k].weight=GA[i][j];
    k++;
   }
}