資源簡介
拓撲排序,可以輸出所有可能的拓撲排序~~!??!

代碼片段和文件信息
#include?
using?namespace?std;
//函數結果狀態代碼?
#?define?ERROR?0?
#?define?INFEASIBLE?-1?
#?define?OVERFLOW?-2
#?define?MAX_VERTEX_NUM?40
int?*temp;??//用于儲存VERTEX_NUM次回歸后得到的序列
//用于拓撲排序的圖的鄰接表的定義
typedef?int?Status;
typedef?struct?ArcNode{????//弧結點
int?adjvex;
bool?deleteed;?????????//標志是否被刪除
struct?ArcNode?*nextarc;
}ArcNode;
typedef?struct?VNode{?????//頂結點
char?data;????????????//頂點名稱
int?indegree;
bool?deleteed;????????//標志是否被刪除
ArcNode?*firstarc;
}VNodeAdjList[MAX_VERTEX_NUM];
typedef?struct{?????//圖
AdjList?vertices;
int?vexnumarcnum;
}ALGraph;
//int型的隊列
class?linkQueue
{
private:
struct?QNode
{
int?date;
QNode?*next;
};
QNode?*front;
QNode?*rear;
public:
linkQueue()
{
front=rear=(QNode*)malloc(sizeof(QNode));
if?(!front)?exit(OVERFLOW);
front->next=NULL;
}
void?Destroy()
{
while(front)
{
rear=front->next;
free(front);
front=rear;
}
front=rear=(QNode*)malloc(sizeof(QNode));
if?(!front)?exit(OVERFLOW);
front->next=NULL;
}
void?EnQueue(int?e)
{
QNode?*p=new?QNode;
if?(!p)?exit(OVERFLOW);
p->date=e;p->next=NULL;
rear->next=p;
rear=p;
}
int?Size()
{
int?count=0;
if?(front==rear)?return?count;
QNode?*p=front->next;
while(p)
{
++count;
p=p->next;
}
return?count;
}
int?DeQueue()?????//輸出單個元素
{
int?a;
if?(front==rear)?{cout<<“隊列空!“< QNode?*p=front->next;
a=p->date;
front->next=p->next;
if?(rear==p)?rear=front;
free(p);
return?a;
}
void?PrintQueue(ALGraph?G)??//用于輸出全部隊列元素
{
QNode?*p=front->next;
while(p)
{
cout<date].data;
p=p->next;
}
cout< }
};
//建立鄰接表
//定位頂點的函數
int?LocateVex(ALGraph?Gchar?u)
{
int?i;
for?(i=0;i if(G.vertices[i].data==u)?return?i;
if?(i==G.vexnum)?{cout<<“錯誤的頂點名!“;exit(1);}
return?-1;
}
//建立有向圖的鄰接表的函數
void?CreateALGraph_adjlist(ALGraph?&G)
{
int?ijk;??
char?v1v2;
ArcNode?*p;
cout<<“請輸入頂點數和弧數:“;
cin>>G.vexnum>>G.arcnum;
cout<<“開始構造鄰接表:“< for?(i=0;i {
cout<<“輸入第“< cin>>G.vertices[i].data;
G.vertices[i].deleteed=false;
G.vertices[i].firstarc=NULL;
G.vertices[i].indegree=0;
}
for?(k=0;k {
cout<<“請輸入第“< cin>>v1>>v2;
i=LocateVex(Gv1);
j=LocateVex(Gv2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->deleteed=false;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
G.vertices[j].indegree++;
}
return;
}
int?*InDegree(ALGraph?Gint?&numint?n)??//返回一個int型數組的指針,內含圖中0度頂點的序號num返回其0度頂點數n是初始的頂點個數
{
int?*a=(int?*)malloc(sizeof(int));
a[0]=-1;??????//a[0]=-1時無0度頂點
num=0;
for(int?i=0j=0;i {
if?(G.vertices[i].deleteed==true)??//如果已經刪除
continue;
if?(G.vertices[i].indegree==0)
{
if?(a[0]==-1)
{
a[0]=i;
++j;
++num;
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????4793??2009-07-02?13:43??拓撲排序\chuopu.cpp
?????文件???????4284??2009-07-01?17:13??拓撲排序\ChuoPu.dsp
?????文件????????537??2009-07-01?15:39??拓撲排序\ChuoPu.dsw
?????文件??????41984??2009-07-02?14:44??拓撲排序\ChuoPu.ncb
?????文件??????53760??2009-07-02?14:44??拓撲排序\ChuoPu.opt
?????文件???????1267??2009-07-02?13:43??拓撲排序\ChuoPu.plg
?????文件?????532534??2009-07-02?13:43??拓撲排序\Debug\ChuoPu.exe
?????文件?????263005??2009-07-02?13:43??拓撲排序\Debug\chuopu.obj
?????文件????1090560??2009-07-02?13:43??拓撲排序\Debug\ChuoPu.pdb
?????文件?????110592??2009-07-02?13:43??拓撲排序\Debug\vc60.pdb
?????文件?????417792??2009-07-02?16:33??拓撲排序\數據結構課程設計-拓撲排序.doc
?????目錄??????????0??2009-10-25?09:28??拓撲排序\Debug
?????目錄??????????0??2009-11-11?17:23??拓撲排序
-----------?---------??----------?-----??----
??????????????2521108????????????????????13
評論
共有 條評論