拓撲排序數(shù)據(jù)結構實驗

1、拓撲排序問題描述：若用有向網(wǎng)表示教學計劃，其中頂點表示某門課程，有向邊表示課程之間的先修關系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從 A指向B）。試設計一個教學計劃編制程序，獲取一個不沖突的線性的課程教學 流程。（課程線性排列，每門課上課時其先修課程已經(jīng)被安排）?；疽螅海?） 輸入?yún)?shù)：課程總數(shù)，每門課的課程號（固定占3位的字母數(shù)字串） 和直接先修課的課程號。（2）若根據(jù)輸入條件問題無解，則報告適當?shù)男畔?；否則將教學計劃輸出 到用戶指定的文件中。需求分析：（測試數(shù)據(jù)加強版）1、輸入形式：第一行是是個整數(shù)t，表示有t組測試數(shù)據(jù)；每一組測試數(shù)據(jù)的第一行是一個整數(shù) n,表示結

2、點數(shù)目接下來的n行是n個頂點的信息接下來的一行是一個整數(shù) m，表示有向邊的數(shù)目接下來是m行數(shù)據(jù)每一行是一條有向邊的起止結點信息2、輸出形式：如果可以實現(xiàn)拓撲排序，輸出其得到的合法線性序列否則，輸出 “ In put Error!3、功能描述:Z幫助判斷當前的課程是否可以安排得當;如果得當，輸出一個合法的修讀順序;4、樣例輸入輸出：輸入:5MathEn glishPhysicsChin eseMusic5Math En glishMath PhysicsEn glish Chin ese Physic Chin ese Chin ese Music5MathEn glishPhysicsChin

3、 eseMusicMath En glishMath Physics En glish Chin ese Physic Chin ese輸出：In put Error ！Math En glishPhysicsChin eseMusic抽象數(shù)據(jù)結構類型描述（ADT）：采用鄰接表的方式來存儲數(shù)據(jù):抽象數(shù)據(jù)類型描述:Typedef struct Arc * link;struct ArcInt adjvex; nfo)return i;void creat()cout«"課程總數(shù)："<<e ndl;cin>>n;coutvv" 請輸入

4、各個頂點信息(即課程的編號)："<<endl;for(int i=1;i<=n;i+)cin> >vi.i nfo;vi.i ndgree=0; vi.firstarc=NULL;coutvv" 請輸入有向邊數(shù)目："cin>>m;coutvv"輸入有向邊(先修課程編號在前)："<<endl;for(int i=0;i<m;i+)char ss15,tt15;cin> >ss»tt;int s=fi nd(ss),t=fi nd(tt);vt.i ndgree+;l

5、ink p=(link)malloc(sizeof(Arc);strcpy(p->i nfo,vt.i nfo); p->adjvex=t;p->n extarc=vs.firstarc; vs.firstarc=p;void update(i nt no de)link p=vno de.firstarc;while(p)if(vp->adjvex.indgree>0) vp->adjvex.indgree-; p=p->n extarc;int main()int relMax,le n=0,t;cout«"請輸入測試數(shù)據(jù)數(shù)目：

6、"<<e ndl;cin> >t;while(t-)creat();for(i nt k=1;k<=n ;k+)for(int i=1;i<=n;i+) if(!vi.i ndgree) relle n+=i;vi.i ndgree=_1; update(i);/ cout«""<<e ndl;if(len<n) cout<<"Input Error！ "<<endl;elsefor(int i=0;i<len;i+) cout<<<<"" cout«e ndl;cout«""<<e ndl;system("pause");return 0;/*25MathEn glishPhysicsChin eseMusic5Math En glishMath PhysicsEn glish Chin esePhysic Chin eseChin ese Music5MathEn glishPhysicsChin eseMusic4Math