熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

有限期作業排序和判斷無向圖的關節點算法設計源代碼

2013-11-15 15:32:20  來源: 數據結構 

  //判斷無向圖的關節點

  #include

  #include

  #define Vnum

  typedef struct arcnode

  {

  int adjvex;

  struct arcnode *nextarc;

  }arcnode;

  typedef struct vexnode

  {

  int vertex;

  arcnode *firstarc;

  }adjlist[Vnum];

  typedef struct graphs

  {

  adjlist adjlist;

  int vexnumarcnum;

  }graph;

  void create(graph *g)

  {

  int neijk;

  arcnode *p;

  cout<<創建一個圖:\t;

  cout<<頂點數;

  cin>>n;

  cout<<\t\t邊數;

  cin>>e;

  g>vexnum=n;

  g>arcnum=e;

  for(i=;i

  {

  g->adjlist[i].vertex=i;

  g->adjlist[i].firstarc=NULL;

  }

  for(k=0;k

  {

  cout<<"第"<

  cin>>i>>j;

  p=(arcnode *)malloc(sizeof(arcnode));

  p->adjvex=j;

  p->nextarc=g->adjlist[i].firstarc;

  g->adjlist[i].firstarc=p;

  }

  }

  void disp(graph *g)

  {

  int i,have;

  arcnode *p;

  cout<<"輸出圖:"<

  for(i=0;ivexnum;i++)

  {

  p=g->adjlist[i].firstarc;

  have=0;

  while(p!=NULL)

  {

  cout<<"("<adjvex<<")";

  p=p->nextarc;

  have=1;

  }

  if(have==1)

  cout<

  }

  }

  void dfs(graph g,int v,int visited[])

  {

  arcnode *p;

  cout<

  cin>>v;

  cout<<"深度優先序列:";

  dfs(g,v,visited);

  cout<

  }

  //有限期的作業排序

  #include

  #include "iomanip.h"

  void JOB_S(int n,int *D);

  void main()

  {

  int *D,*P; //定義變量數組,采用動態分配內存

  int i,n;

  cout<<"請輸入要處理的作業數n:";

  cin>>n;

  D=new int[n+1]; //作業的截止期限數組

  P=new int[n+1]; //作業的效益數組

  cout<<"請輸入作業i的期限值D(1-"<

  for(i=1;i<=n;i++) //按非增順序輸入

  {

  cout<<"作業"<

  cin>>D[i];

  }

  cout<

  cout<<"請輸入作業i的效益值P(1-"<

  for(i=1;i<=n;i++) //按非增順序輸入

  {

  cout<<"作業"<

  cin>>P[i];

  }

  cout<

  JOB_S(n,D);

  }

  void JOB_S(int n,int *D)

  {

  int i,k,r;

  int *J=new int[n+1];

  k=1;

  D[0]=0;

  J[0]=0;

  J[1]=1;

  for(i=2;i<=n;i++)

  {

  r=k;

  while(D[J[r]]>D[i] && D[J[r]]!=r)

  r=r-1;

  if(D[J[r]]<=D[i] && D[i]>r)

  {

  for(int x=k;x>=r+1;x--)

  J[x+1]=J[x];

  J[r+1]=i;

  k++;

  }

  }

  cout<<"該作業的最優處理順序為:";

  for(i=1;i<=k;i++)

  cout<

  cout<

  }


From:http://tw.wingwit.com/Article/program/sjjg/201311/23577.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.