教學(xué)計(jì)劃的編制問題(實(shí)驗(yàn)10實(shí)驗(yàn)報告)

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告題目：教學(xué)計(jì)劃的編制問題姓名：楊維學(xué)號：20090810229班級：物聯(lián)網(wǎng)工程0901班指導(dǎo)老師：李曉鴻完成日期：2010年11月26日一、問題描述：若用有向網(wǎng)表示教學(xué)計(jì)劃，其中頂點(diǎn)表示某門課程，有向邊表示課程之間的先修關(guān)系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設(shè)計(jì)一個教學(xué)計(jì)劃編制程序，獲取一個不沖突的線性的課程教學(xué)流程。（課程線性排列，每門課上課時其先修課程已經(jīng)被安排）。基本要求（1）輸入?yún)?shù)：課程總數(shù)，每門課的課程號（固定占3位的字母數(shù)字串）和直接先修課的課程號。（2）若根據(jù)輸入條件問題無解，則報告適當(dāng)?shù)男畔?；否則將教學(xué)計(jì)劃輸出到用戶指定的文件中。二．需求分析：1、本程序需要基于圖的基本操作來實(shí)現(xiàn)三．概要設(shè)計(jì)抽象數(shù)據(jù)類型：為實(shí)現(xiàn)上述功能需建立一個結(jié)點(diǎn)類，線性表類，圖類。算法的基本思想：圖的構(gòu)建：建立一個結(jié)點(diǎn)類，類的元素有字符型變量用來存儲字母，整形變量用來存儲位置，該類型的指針，指向下一個元素。建立一個線性表類，完成線性表的構(gòu)建。建立一個圖類，完成圖的信息的讀取，（如有n個點(diǎn)，則建立n個線性表，將每個結(jié)點(diǎn)與其指向的結(jié)點(diǎn)組成一個線性表，并記錄線性表的長度）。Topsort算法：先計(jì)算每個點(diǎn)的入度，保存在數(shù)組中。找到第一個入度為0的點(diǎn)，將該點(diǎn)所連的各點(diǎn)的入度減一。再在這些點(diǎn)中找入度為0的點(diǎn)。如果找到，重復(fù)上述操作。如果找不到，則跳出while循環(huán)，再搜索其他的點(diǎn)，看入度是否為0。再重復(fù)上述操作，如果所有的入度為0的點(diǎn)都被尋找到，但個數(shù)少于輸入頂點(diǎn)的個數(shù)，說明該圖存在環(huán)。程序的流程：輸入模塊：讀入圖的信息（頂點(diǎn)和邊，用線性表進(jìn)行存儲）。處理模塊：topsort算法。輸出模塊：將結(jié)果輸出。四．詳細(xì)設(shè)計(jì)：算法的具體步驟：classNode{//結(jié)點(diǎn)類public:stringnode;intposition;//位置Node*next;boolvisit;//是否被訪問Node(){visit=false;next=NULL;position=0;node='';}};classLine{//線性表類public: intnum; Node*head; Node*rear; Node*fence; Line(){num=0;head=fence=rear=newNode();} voidinsert(intv,stringch){//插入元素 Node*current=newNode(); current->node=ch; current->position=v; fence->next=current; fence=current; num++; }};classGraph{//圖類private: intnumVertex; intnumEdge; Line*line;public: Graph(intv,inte){numVertex=v;numEdge=e;line=newLine[v];} voidpushVertex(){//讀入點(diǎn) stringch; for(inti=0;i<numVertex;i++){ cout<<"請輸入頂點(diǎn)"<<i+1<<":"; cin>>ch; line[i].head->node=ch; line[i].head->position=i; } } voidpushEdge(){//讀入邊 stringch1,ch2; intpos1,pos2; for(inti=0;i<numEdge;i++) { cout<<"請輸入邊"<<i+1<<":"; cin>>ch1>>ch2; for(intj=0;j<numVertex;j++){ if(line[j].head->node==ch1) pos1=j;//找到該字母對應(yīng)的位置 if(line[j].head->node==ch2){ pos2=line[j].head->position; break; } } line[pos1].insert(pos2,ch2); } } voidtopsort(){//拓?fù)渑判? inti; int*d=newint[numVertex]; for(i=0;i<numVertex;i++) d[i]=0;//數(shù)組初始化 for(i=0;i<numVertex;i++){ Node*p=line[i].head; while(p->next!=NULL){ d[p->next->position]++;//計(jì)算每個點(diǎn)的入度 p=p->next; } } inttop=-1,m=0,j,k; for(i=0;i<numVertex;i++){ if(d[i]==0){ d[i]=top;//找到第一個入度為0的點(diǎn) top=i; } while(top!=-1){j=top;top=d[top]; cout<<line[j].head->node<<""; m++; Node*p=line[j].head; while(p->next!=NULL){ k=p->next->position; d[k]--;//當(dāng)起點(diǎn)被刪除，時后面的點(diǎn)的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } }cout<<endl; if(m<numVertex)//輸出點(diǎn)的個數(shù)小于輸入點(diǎn)的個數(shù)，不能完全遍歷 cout<<"網(wǎng)絡(luò)存在回路"<<endl; delete[]d; }};intmain(){intn,m; cout<<"請輸入節(jié)點(diǎn)的個數(shù)和邊的個數(shù)"<<endl; cin>>n>>m; GraphG(n,m); G.pushVertex(); G.pushEdge(); G.topsort(); system("pause");return0;}五．調(diào)試分析：將建立的線性表輸出來檢驗(yàn)圖的信息是否完全被讀入，構(gòu)建是否正確。六．測試結(jié)果：七．實(shí)驗(yàn)心得：1、本實(shí)驗(yàn)是在圖的遍歷問題的基礎(chǔ)上做的，圖的構(gòu)建大部分是采用圖的遍歷問題中的代碼（不過要將結(jié)點(diǎn)類中的char改為string型），自己另外寫了topsort函數(shù)，就完成了整個程序。2、topsort函數(shù)中一開始采用的方法是找到一個入度為0的點(diǎn)，完成相應(yīng)的操作后，重新進(jìn)行搜索，后來改進(jìn)代碼，先搜索入度為0的點(diǎn)后面連接的點(diǎn)，這樣減少了算法復(fù)雜度。八、附件教學(xué)計(jì)劃的編制問題.cpp#include<iostream>#include<string.h>usingnamespacestd;classNode{//結(jié)點(diǎn)類public:stringnode;intposition;//位置Node*next;boolvisit;//是否被訪問Node(){visit=false;next=NULL;position=0;node='';}};classLine{//線性表類public: intnum; Node*head; Node*rear; Node*fence; Line(){num=0;head=fence=rear=newNode();} voidinsert(intv,stringch){//插入元素 Node*current=newNode(); current->node=ch; current->position=v; fence->next=current; fence=current; num++; }};classGraph{//圖類private: intnumVertex; intnumEdge; Line*line;public: Graph(intv,inte){numVertex=v;numEdge=e;line=newLine[v];} voidpushVertex(){//讀入點(diǎn) stringch; for(inti=0;i<numVertex;i++){ cout<<"請輸入頂點(diǎn)"<<i+1<<":"; cin>>ch; line[i].head->node=ch; line[i].head->position=i; } } voidpushEdge(){//讀入邊 stringch1,ch2; intpos1,pos2; for(inti=0;i<numEdge;i++) { cout<<"請輸入邊"<<i+1<<":"; cin>>ch1>>ch2; for(intj=0;j<numVertex;j++){ if(line[j].head->node==ch1) pos1=j;//找到該字母對應(yīng)的位置 if(line[j].head->node==ch2){ pos2=line[j].head->position; break; } } line[pos1].insert(pos2,ch2); } } voidtopsort(){//拓?fù)渑判? inti; int*d=newint[numVertex]; for(i=0;i<numVertex;i++) d[i]=0;//數(shù)組初始化 for(i=0;i<numVertex;i++){ Node*p=line[i].head; while(p->next!=NULL){ d[p->next->position]++;//計(jì)算每個點(diǎn)的入度 p=p->next; } } inttop=-1,m=0,j,k; for(i=0;i<numVertex;i++){ if(d[i]==0){ d[i]=top;//找到第一個入度為0的點(diǎn) top=i; } while(top!=-1){j=top;top=d[top]; cout<<line[j].head->node<<""; m++; Node*p=line[j].head; while(p->next!=NULL){ k=p->next->position; d[k]--;//當(dāng)起點(diǎn)被刪除，時后面的點(diǎn)的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } }