下面是范文網(wǎng)小編整理的數(shù)據(jù)結(jié)構(gòu)教學(xué)計劃編制共3篇(教學(xué)計劃編制數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)，供大家閱讀。
數(shù)據(jù)結(jié)構(gòu)教學(xué)計劃編制共1
目 錄
1.需求分析.........................................錯誤！未定義書簽。 2.概要設(shè)計.........................................錯誤！未定義書簽。 3.詳細(xì)設(shè)計.........................................錯誤！未定義書簽。 4.測試分析.........................................錯誤！未定義書簽。 課程設(shè)計總結(jié).......................................錯誤！未定義書簽。 參考文獻(xiàn)...........................................錯誤！未定義書簽。
1.需求分析
根據(jù)課程之間的依賴關(guān)系制定課程安排計劃，輸入課程數(shù)及課程之間的關(guān)系。需要利用代碼實(shí)現(xiàn)排序，以及對各個學(xué)期課程安排進(jìn)行排序并輸出。
問題描述
大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等，每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。
設(shè)計思路
首先利用拓?fù)渑判驅(qū)φn程先后順序進(jìn)行分析，鄰接表位主要存儲結(jié)構(gòu)，棧為主要輔助結(jié)構(gòu)，給出課程之間的先后關(guān)系比如AOV網(wǎng)，然后進(jìn)行拓?fù)渑判颍?dāng)又向圖中存在環(huán)時，無法查找該圖的一個拓?fù)渑判?，?dāng)圖中的所有頂點(diǎn)全部輸出，表示對該圖排序成功，實(shí)現(xiàn)拓?fù)渑判蛩惴〞r，相應(yīng)的建立鄰接表存儲AOV網(wǎng)，為了避免重復(fù)檢測入度為零的頂點(diǎn)，建立一個棧來對入度為零的頂點(diǎn)進(jìn)行存放。根據(jù)課程的先后關(guān)系，對個學(xué)期的課程進(jìn)行排序，輸出。
設(shè)計環(huán)境、原理
設(shè)計環(huán)境和器材： 硬件：計算機(jī)；軟件：Microsoft Visula C++。
設(shè)計原理說明：運(yùn)用圖的拓?fù)渑判驅(qū)φn程先修排列的實(shí)現(xiàn)，并調(diào)用遞歸完成拓?fù)渑判颉?/p>
實(shí)驗?zāi)康?/strong>
培養(yǎng)學(xué)生用學(xué)到的書本知識解決實(shí)際問題的能力；培養(yǎng)實(shí)際工作所需要的動手能力；培養(yǎng)學(xué)生以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件具有關(guān)鍵性作用。通過課程設(shè)計的實(shí)踐，學(xué)生可以在程序設(shè)計方法、上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。
實(shí)驗內(nèi)容
針對計算機(jī)系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同。
2.概要設(shè)計：
流程圖
void FindInDegree(ALGraph G, int indegree[])//求圖中各節(jié)點(diǎn)的入度（如下左圖）void CreatGraph(ALGraph *G)//構(gòu)件圖（如下右圖）。
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) //有向圖G采用鄰接表存儲結(jié)構(gòu)(如下左圖)；
void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) //有向圖G采用鄰接表存儲結(jié)構(gòu)（如下右圖）。
主函數(shù)： void main()
抽象數(shù)據(jù)類型圖的定義 ADT Graph{
數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系R: R={VR} VR={(v,w)|v,w∈V,(v,w)表示v和w之間存在直接先修關(guān)系} 基本操作P: void CreatGraph(ALGraph *); void FindInDegree(ALGraph , int * ); void TopologicalSort_1(ALGraph G,int numterm,int maxcredit); void TopologicalSort_2(ALGraph G,int numterm,int maxcredit); }ADT Graph 棧的定義: ADT Stack{ 數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0} 數(shù)據(jù)關(guān)系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n} 基本操作: void InitStack (SqStack *S); int StackEmpty(SqStack S); void Push(SqStack *S, int ); int Pop(SqStack *S, int *e); }ADT Stack 主程序
int main() //主函數(shù) {
int numterm; //學(xué)期總數(shù)
int uplcredit; //一個學(xué)期的學(xué)分上限
int selectway;
ALGraph G;
printf("請輸入學(xué)期總數(shù):\\\\n");
scanf("%d",&numterm);
printf("請輸入一個學(xué)期的學(xué)分上限:\\\\n");
scanf("%d",&uplcredit);
CreatGraph(&G);
printf("請選擇編排策略:1.課程盡可能集中到前幾個學(xué)期；2.課程盡量均勻分布\\\\n");
scanf("%d",&selectway);
if(selectway==1)
TopologicalSort_1(G,numterm,uplcredit);
if(selectway==2)
TopologicalSort_2(G,numterm,uplcredit);
system("pause");
return 0; } 本程序只有兩個模塊,調(diào)用關(guān)系簡單
主程序模塊→拓?fù)渑判蚰K
3.詳細(xì)設(shè)計
頭結(jié)點(diǎn)、表結(jié)點(diǎn)、鄰接表的定義
#define MAX_VERTEX_NUM 100 //最大課程總數(shù) typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ char name[24];
//課程名 int claid;
//課程號
int credit;
//課程的學(xué)分 int indegree;
//該結(jié)點(diǎn)的入度 int state;
//該節(jié)點(diǎn)的狀態(tài) ArcNode *firstarc; //指向第一條依附該頂點(diǎn)的弧的指針 }VNode,AdjList[MAX_VEXTEX_NUM]; typedef struct{ AdjList vertices; int vexnum, arcnum; }ALGraph; 鄰接表的基本操作：
void CreatGraph(ALGraph *); 創(chuàng)建鄰接表
void FindInDegree(ALGraph , int * ); 求一個結(jié)點(diǎn)的入度
void TopologicalSort_1(ALGraph G,int numterm,int maxcredit); 拓?fù)渑判騺砭幣耪n程
void TopologicalSort_2(ALGraph G,int numterm,int maxcredit); 拓?fù)渑判騺砭幣耪n程
棧的定義
#define STACk_INIT_SIZE 100 //存儲空間的初時分配量 #define STACKINCREMENT 10
//存儲空間的分配增量
typedef int ElemType; typedef struct { AdjList vertices; int vexnum, arcnum; }ALGraph; 基本操作：
void InitStack (SqStack *S); 棧的初始化
int StackEmpty(SqStack S); 判斷棧是否為空
void Push(SqStack *S, int ); 入棧操作
int Pop(SqStack *S, int *e); 出棧操作
主程序和其他算法：
#include #include #include // malloc()等 #include // INT_MAX等 #include // EOF(=^Z或F6),NULL #include // atoi()52 #include // eof() #include // floor(),ceil(),abs() #include<> // exit() #include // cout,cin// 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; // Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
Typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE #define MAX_NAME 10 /* 頂點(diǎn)字符串的最大長度 */ #define MAXCLASS 100 int Z=0; int X=0; int xqzs,q=1,xfsx; typedef int InfoType; typedef char VertexType[MAX_NAME]; /* 字符串類型 */ /* 圖的鄰接表存儲表示 */ #define MAX_VERTEX_NUM 100 typedef enum{DG}GraphKind; /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */ typedef struct ArcNode { int adjvex; /* 該弧所指向的頂點(diǎn)的位置 */ struct ArcNode *nextarc; /* 指向下一條弧的指針 */ InfoType *info; /* 網(wǎng)的權(quán)值指針） */ } ArcNode; /* 表結(jié)點(diǎn) */ typedef struct { VertexType data; /* 頂點(diǎn)信息 */ ArcNode *firstarc; /* 第一個表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針 */ } VNode,AdjList[MAX_VERTEX_NUM]; /* 頭結(jié)點(diǎn) */ typedef struct { AdjList vertices,verticestwo; int vexnum,arcnum; /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) */ int kind; /* 圖的種類標(biāo)志 */ }ALGraph;/* 圖的鄰接表存儲的基本操作 */ int LocateVex(ALGraph G,VertexType u) { /* 初始條件: 圖G存在,u和G中頂點(diǎn)有相同特征 */ /* 操作結(jié)果: 若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1 */ int i; for(i=0;iadjvex=j; p->info=NULL; /* 圖 */ p->nextarc=(*G).vertices[i].firstarc; /* 插在表頭 */ (*G).vertices[i].firstarc=p; } return OK; } void Display(ALGraph G) { /* 輸出圖的鄰接矩陣G */ int i; ArcNode *p; switch() { case DG: printf("有向圖\\\\n"); } printf("%d個頂點(diǎn)：\\\\n",); for(i=0;iadjvex].data); p=p->nextarc; } printf("\\\\n"); }
void FindInDegree(ALGraph G,int indegree[]) { /* 求頂點(diǎn)的入度，算法調(diào)用 */ int i; ArcNode *p; for(i=0;iadjvex]++; p=p->nextarc; } } } typedef int SElemType; /* 棧類型 */ /*棧的順序存儲表示 */ #define STACK_INIT_SIZE 10 /* 存儲空間初始分配量 */ #define STACKINCREMENT 2 /* 存儲空間分配增量 */ typedef struct SqStack { SElemType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */ SElemType *top; /* 棧頂指針 */ int stacksize; /* 當(dāng)前已分配的存儲空間，以元素為單位 */ }SqStack; /* 順序棧 */ /* 順序棧的基本操作 */ Status InitStack(SqStack *S) { /* 構(gòu)造一個空棧S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存儲分配失敗 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(==) return TRUE; else return FALSE; } Status Pop(SqStack *S,SElemType *e) { /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; } Status Push(SqStack *S,SElemType e) { /* 插入元素e為新的棧頂元素 */ if((*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲空間 */ { (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof
(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存儲分配失敗 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; return OK; } typedef int pathone[MAXCLASS]; typedef int pathtwo[MAXCLASS]; Status TopologicalSort(ALGraph G) { /* 有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路,則輸出G的頂點(diǎn)的一個拓?fù)湫蛄胁⒎祷豋K, */ /* 否則返回ERROR。 */ int i,k,j=0,count,indegree[MAX_VERTEX_NUM]; SqStack S; pathone a; pathtwo b; ArcNode *p; FindInDegree(G,indegree); /* 對各頂點(diǎn)求入度indegree[0..vernum-1] */ InitStack(&S); /* 初始化棧 */ for(i=0;inextarc) { /* 對i號頂點(diǎn)的每個鄰接點(diǎn)的入度減1 */ k=p->adjvex; if(!(--indegree[k])) /* 若入度減為0,則入棧 */ Push(&S,k); } } if(count
while(q
4.用戶使用和說明
使用VC++，打開文件，接著編譯，無錯誤，然后重建也沒有錯誤，最后執(zhí)行該文件。顯示如下圖：
要求輸入學(xué)期總數(shù)、一個學(xué)期的學(xué)分上限、需要編排課程總數(shù)、課程名、課程號、該課程的學(xué)分，按照出現(xiàn)的每一步來輸入該課程設(shè)計所提供的相關(guān)數(shù)據(jù)。然后還要輸入課程先修課程總數(shù)，依據(jù)教科書圖7．26，可以算出有16種關(guān)系，分別輸出如下圖所示。接著程序會根據(jù)這些數(shù)據(jù)，自動生成建立好的鄰接表，用戶可以根據(jù)系統(tǒng)顯示的選擇編排策略進(jìn)行選擇，有兩種編排策略，最后結(jié)果體現(xiàn)在實(shí)驗的正確測試結(jié)果里（如上圖）。
5.調(diào)試分析
實(shí)驗過程中出現(xiàn)的問題及解決方法
我們在實(shí)驗過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴ǎ瑢τ谡n程設(shè)計要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。
測試數(shù)據(jù)
學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學(xué)分順序為2，3，4，3，2，3，4，4，7，5，2，3。
測試結(jié)果（包含正確和錯誤的）
正確測試結(jié)果：
錯誤測試結(jié)果：
測試數(shù)據(jù)及程序運(yùn)行情況
輸入的內(nèi)容如下: 課程編號
課程名稱
學(xué)分
先決條件 01
程序設(shè)計基礎(chǔ)
無 02
離散數(shù)學(xué)
01 03
數(shù)據(jù)結(jié)構(gòu)
01，02 04
匯編語言
01 05 語言的設(shè)計和分析
03，04 06
計算機(jī)原理
11 07
編譯原理
05，03 08
操作系統(tǒng)
03，06 09
高等數(shù)學(xué)
無 10
線性代數(shù)
09 11
普通物理
09 12
數(shù)值分析
09，10，01 兩種編排方法都輸出結(jié)果為: 第一學(xué)期學(xué)的課程有:高等數(shù)學(xué)程序設(shè)計基礎(chǔ)； 第二學(xué)期學(xué)的課程有:普通物理 線性代數(shù) 匯編語言； 第三學(xué)期學(xué)的課程有:數(shù)值分析 計算機(jī)原理 離散數(shù)學(xué)； 第四學(xué)期學(xué)的課程有:數(shù)據(jù)結(jié)構(gòu)；
第五學(xué)期學(xué)的課程有:操作系統(tǒng) 語言的設(shè)計和分析； 第六學(xué)期學(xué)的課程有:編譯原理。
6.總結(jié)
剛開始學(xué)的時候確實(shí)有很多地方我很不理解，每次上課時老師都會給我們出不同的設(shè)計題目，對于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。老師會給我們需要編程的內(nèi)容一些講解，順著老師的思路，來完成自己的設(shè)計，我們可以開始運(yùn)行自己的程序，可是好多處的錯誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯誤，但是程序還是得繼續(xù)下去，我多次請教了老師和同學(xué)，逐漸能自己找出錯誤，并加以改正。經(jīng)過了這次課程設(shè)計，現(xiàn)在已經(jīng)可以了解很多錯誤在英文里的提示，這對我來說是一個突破性的進(jìn)步，眼看著一個個錯誤通過自己的努力在我眼前消失，覺得很是開心。此次的程序設(shè)計能夠成功，是我和我的同學(xué)三個人共同努力作用的結(jié)果。在這一段努力學(xué)習(xí)的過程中，我們的編程設(shè)計有了明顯的提高。
其實(shí)現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費(fèi)了好多心血，覺得它很難，是需用花費(fèi)了大量的時間編寫出來的。現(xiàn)在真正的明白了一些代碼的應(yīng)用，每個程序都有一些共同點(diǎn)，通用的結(jié)構(gòu)，相似的格式。同時也對教學(xué)編制問題有了進(jìn)一步的認(rèn)識。只要努力去學(xué)習(xí)，就會靈活的去應(yīng)用它。
7.參考文獻(xiàn)
［1］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2003。 ［2］《數(shù)據(jù)結(jié)構(gòu)題集》，嚴(yán)蔚敏，清華大學(xué)出版社，2005。 ［3］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），劉大有，高等教育出版社，2004。 ［4］《Data Structure with C++》，William Ford．William Topp，清華大學(xué)出版社，2003。
數(shù)據(jù)結(jié)構(gòu)教學(xué)計劃編制共2
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
題目：教學(xué)計劃編制
一.需求分析
（1）實(shí)驗內(nèi)容和實(shí)驗?zāi)康模?/p>
1.大學(xué)的每個專業(yè)都要編制教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限都相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程的開設(shè)時間的安排必須滿足先修關(guān)系。每個課程的先修關(guān)系都是確定的，可以有任意多門，也可以沒有。每一門課程恰好一個學(xué)期。試在這樣的情況下設(shè)置一個教學(xué)計劃編制程序。 2.在大學(xué)的某個專業(yè)中選取幾個課程作為頂點(diǎn),通過各門課的先修關(guān)系來構(gòu)建個圖,該圖用鄰接表來存儲,鄰接表的頭結(jié)點(diǎn)存儲每門課的信息.
3.本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信息來編排出每學(xué)期要學(xué)的課程.（2）測試數(shù)據(jù)：
學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學(xué)分順序為2，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見教科書圖7．26。 （3）測試結(jié)果（包含正確和錯誤的）： 正確測試結(jié)果：
錯誤測試結(jié)果：
二.概要設(shè)計
1.抽象數(shù)據(jù)類型圖的定義如下: ADT Graph{ 數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系R:
r={VR}
vR={(v,w)|v,w∈V,(v,w)表示v和w之間存在直接先修關(guān)系} 基本操作P: void CreatGraph(ALGraph *); void FindInDegree(ALGraph , int * ); void TopologicalSort_1(ALGraph G,int numterm,int maxcredit); void TopologicalSort_2(ALGraph G,int numterm,int maxcredit); }ADT Graph 棧的定義: ADT Stack{
數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}
數(shù)據(jù)關(guān)系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n} 基本操作: void InitStack (SqStack *S); int StackEmpty(SqStack S); void Push(SqStack *S, int ); int Pop(SqStack *S, int *e); }ADT Stack 2.主程序
int main()
//主函數(shù) {
int numterm; //學(xué)期總數(shù)
int uplcredit; //一個學(xué)期的學(xué)分上限
int selectway;
ALGraph G;
printf(\"請輸入學(xué)期總數(shù):\\n\");
scanf(\"%d\",&numterm);
printf(\"請輸入一個學(xué)期的學(xué)分上限:\\n\");
scanf(\"%d\",&uplcredit);
CreatGraph(&G);
printf(\"請選擇編排策略:1.課程盡可能集中到前幾個學(xué)期；2.課程盡量均勻分布\\n\");
scanf(\"%d\",&selectway);
if(selectway==1)
TopologicalSort_1(G,numterm,uplcredit);
if(selectway==2)
TopologicalSort_2(G,numterm,uplcredit);
system(\"pause\");
return 0; } 3.本程序只有兩個模塊,調(diào)用關(guān)系簡單.
主程序模塊
↓
拓?fù)渑判蚰K 三．詳細(xì)設(shè)計 1．頭結(jié)點(diǎn)，表結(jié)點(diǎn)，鄰接表的定義
#define MAX_VERTEX_NUM 100 //最大課程總數(shù) typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode; typedef struct VNode{
Char name[24];
//課程名
int claid;
//課程號
int credit;
//課程的學(xué)分
int indegree;
//該結(jié)點(diǎn)的入度
int state;
//該節(jié)點(diǎn)的狀態(tài)
ArcNode *firstarc; //指向第一條依附該頂點(diǎn)的弧的指針
}VNode,AdjList[MAX_VEXTEX_NUM]; typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph; 鄰接表的基本操作：
void CreatGraph(ALGraph *); 創(chuàng)建鄰接表
void FindInDegree(ALGraph , int * ); 求一個結(jié)點(diǎn)的入度
void TopologicalSort_1(ALGraph G,int numterm,int maxcredit); 拓?fù)渑判騺砭幣耪n程
void TopologicalSort_2(ALGraph G,int numterm,int maxcredit); 拓?fù)渑判騺砭幣耪n程 2．棧的定義：
#define STACk_INIT_SIZE 100 //存儲空間的初時分配量 #define STACKINCREMENT 10
//存儲空間的分配增量 typedef int ElemType; typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph; 基本操作：
void InitStack (SqStack *S); 棧的初始化
int StackEmpty(SqStack S); 判斷棧是否為空
void Push(SqStack *S, int ); 入棧操作
int Pop(SqStack *S, int *e); 出棧操作
3．主程序和其他算法
int main()
//主函數(shù) { int numterm; //學(xué)期總數(shù)
int uplcredit; //一個學(xué)期的學(xué)分上限
int selectway;
ALGraph G;
printf(\"請輸入學(xué)期總數(shù):\\n\");
scanf(\"%d\",&numterm);
printf(\"請輸入一個學(xué)期的學(xué)分上限:\\n\");
scanf(\"%d\",&uplcredit); CreatGraph(&G); printf(\"請選擇編排策略:1.課程盡可能集中到前幾個學(xué)期；2.課程盡量均勻分布\\n\");
scanf(\"%d\",&selectway);
if(selectway==1)
TopologicalSort_1(G,numterm,uplcredit);
if(selectway==2)
TopologicalSort_2(G,numterm,uplcredit);
system(\"pause\");
return 0; } void CreatGraph(ALGraph *G)//構(gòu)件圖 {
int i, m, n;
ArcNode *p;
printf(\"請輸入需要編排課程總數(shù):\\n\");
scanf(\"%d\",&G->vexnum);
for( i=1;ivexnum;i++)
{
printf(\"請輸入課程名\\n\");
scanf(\"%s\",&G->vertices[i].name);
printf(\"請輸入課程號\\n\");
scanf(\"%d\",&G->vertices[i].claid);
printf(\"請輸入該課程的學(xué)分\\n\");
scanf(\"%d\",&G->vertices[i].credit);
G->vertices[i].indegree=0;
G->vertices [i].state=NOTSTUDY;
G->vertices[i].firstarc=NULL;
}
printf(\"請輸入課程先修關(guān)系總數(shù)：\");
scanf(\"%d\",&G->arcnum);
printf(\"請順序輸入每個課程先修關(guān)系(先修課程在前并以逗號作為間隔):\\n\");
for (i = 1; i arcnum; i++)
{
printf(\"\\n請輸入存在先修關(guān)系的兩個課程的序號:\");
scanf(\"%d,%d\",&n,&m);
while (n G->vexnum || m G->vexnum)
{
printf(\"輸入的頂點(diǎn)序號不正確 請重新輸入:\");
scanf(\"%d,%d\",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{
printf(\"memory allocation failed,goodbey\");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf(\"\\n建立的鄰接表為:\\n\");
//輸出建立好的鄰接表
for(i=1;ivexnum;i++)
{
printf(\"%d:->\",G->vertices[i].claid);
for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc)
printf(\"%d->\",p->adjvex);
printf(\"NULL\");
printf(\"\\n\");
} } void InitStack(SqStack *S) {
s->base=(int *)malloc(STACK_INIT_SIZE *sizeof(int));
if (!S->base)
{
printf(\"ERROR\");
exit(1);
}
s->top=S->base;
s->stacksize=STACK_INIT_SIZE; } int StackEmpty(SqStack *S) {
if(S->top==S->base)
return OK;
else
return ERROR; } void Push(SqStack *S,int e) {
if(S->top - S->base >= S->stacksize)
{
s->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(int));
if(!S->base)
{
printf(\"ERROR\");
exit(1);
}
s->top = S->base + S->stacksize;
s->stacksize += STACKINCREMENT;
}
*S->top++ = e; } int Pop(SqStack *S, int *e) {
if(S->top == S->base) exit(1);
*e = * --S->top;
return 0; } void FindInDegree(ALGraph G, int indegree)//求圖中各節(jié)點(diǎn)的入度 {
int i;
for (i = 1; i
indegree[i] = 0;
for (i = 1; i
{
while ([i].firstarc)
{
indegree[[i].firstarc->adjvex]++;
[i].firstarc = [i].firstarc->nextarc;
}
} } void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) {
fILE *fp;
fp=fopen(\"\",\"w\");
ArcNode *p;
sqStack S;
int indegree[M];//存放各節(jié)點(diǎn)的入度
int i,j, k, m,n;
int count; //課程編排數(shù)目計數(shù)器
int sumcredit;//每個學(xué)期的課程學(xué)分累加器
findInDegree(G, indegree);
for (i = 1; i
[i].indegree=indegree[i];
initStack(&S);
Count=0;
k=0;
while(count!= && k
{
sumcredit=0;
for(i=1;i
if(([i].indegree==0)&&([i].state==NOTSTUDY))
{
push(&S,i);
[i].state = STUDY;//避免入度為零節(jié)點(diǎn)重復(fù)入棧
}
if(!StackEmpty(&S)&&(sumcredit
{
k= k+1;
printf(\"\\n\");
printf(\"第%d個學(xué)期學(xué)得課程有:\\n\",k);
sumcredit = 0;
for(i=1;i
if(([i].indegree==0)&&([i].state==NOTSTUDY))
push(&S,i);
while((!StackEmpty(&S))&&(sumcredit
{
pop(&S,&j);
sumcredit = sumcredit + [j].credit;
if(sumcredit
{
printf(\" %s \",[j].name);
fprintf(fp,\" %s \",[j].name);
Count++;
for(p=[j].firstarc;p;p=p->nextarc)//對j號頂點(diǎn)每個鄰接點(diǎn)的入度減一
[p->adjvex].indegree--;
}
else Push(&S,j);//將未輸出的節(jié)點(diǎn)重新壓入棧
}
}
fprintf(fp,\"\\n\");
}
printf(\"\\n\");
if(count
printf(\"\\n課程編排出錯\\n\");
else
{
printf(\"\\n課程編排成功\\n\");
}
fclose(fp); } void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) {
fILE *fp;
fp=fopen(\"\",\"w\");
ArcNode *p;
sqStack S;
int indegree[M];
int i,j, k, m,n;
int maxnum;
int sumnum;
int count; //課程編排數(shù)目計數(shù)器
int sumcredit;//每個學(xué)期的課程學(xué)分累加器
findInDegree(G, indegree);
for (i = 1; i
[i].indegree = indegree[i];
initStack(&S);
Count=0;
k=0;
maxnum = /numterm+1;
sumnum = 0;
while(count!= && k
{
for(i=1;i
if(([i].indegree==0)&&([i].state==NOTSTUDY))
{
push(&S,i);
[i].state = STUDY;
}
if(!StackEmpty(&S)&&(sumcredit
{
k= k+1;
printf(\"\\n\");
printf(\"第%d個學(xué)期學(xué)得課程有:\",k);
sumcredit = 0;
sumnum = 0;
for(i=1;i
if(([i].indegree==0)&&([i].state==NOTSTUDY))
push(&S,i);
while((!StackEmpty(&S))&&(sumcredit
//棧非空&&學(xué)分總數(shù)小于學(xué)分上限&&學(xué)期課程數(shù)目小于學(xué)期最大數(shù)目
{
pop(&S,&j);//出棧
sumcredit = sumcredit + [j].credit;
sumnum = sumnum+1;
if((sumcredit
{
printf(\" %s \",[j].name);
fprintf(fp,\" %s \",[j].name);
Count++;
for(p=[j].firstarc;p;p=p->nextarc)//對j號頂點(diǎn)每個鄰接點(diǎn)的入度減一
[p->adjvex].indegree--;
}
else Push(&S,j);
}
}
} fprintf(fp,\"\\n\"); } printf(\"\\n\"); if(count
printf(\"課程編排出錯\\n\"); else {
printf(\"課程編排成功\\n\"); } fclose(fp); 流程圖如下所示：
void FindInDegree(ALGraph G, int indegree)//求圖中各節(jié)點(diǎn)的入度（如下左圖）
void CreatGraph(ALGraph *G)//構(gòu)件圖（如下右圖）
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) //向圖G采用鄰接表存儲結(jié)構(gòu)(如下左圖)
有 void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) //有向圖G采用鄰接表存儲結(jié)構(gòu)（如下右圖）
主函數(shù)：void main()
四．調(diào)試分析：
（1）實(shí)驗過程中出現(xiàn)的問題及解決方法
我們在實(shí)驗過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴ǎ瑢τ谡n程設(shè)計要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。
（2）實(shí)驗體會:
經(jīng)過此次課程設(shè)計，我們認(rèn)識到了理論與實(shí)踐結(jié)合的重要性，僅僅只是從課本上學(xué)到算法原理是遠(yuǎn)遠(yuǎn)不夠的。在實(shí)踐中，我們總會出現(xiàn)許多錯誤。這就要求我們以一個腳踏實(shí)地的態(tài)度來處理問題。我們深刻地認(rèn)識到自己寫程序的不足，使我們學(xué)到了好多有用的知識，讓我們明白了C語言的語句用法。
五．用戶使用和說明：
使用VC++，打開教學(xué)計劃編制問題.cpp文件，接著編譯，無錯誤，然后重建也沒有錯誤，最后執(zhí)行該文件。顯示如下圖：
要求輸入學(xué)期總數(shù)、一個學(xué)期的學(xué)分上限、需要編排課程總數(shù)、課程名、課程號、該課程的學(xué)分，按照出現(xiàn)的每一步來輸入該課程設(shè)計所提供的相關(guān)數(shù)據(jù)。然后還要輸入課程先修課程總數(shù)，依據(jù)教科書圖7．26，可以算出有16種關(guān)系，分別輸出如下圖所示。接著程序會根據(jù)這些數(shù)據(jù)，自動生成建立好的鄰接表，用戶可以根據(jù)系統(tǒng)顯示的選擇編排策略進(jìn)行選擇，有兩種編排策略，最后結(jié)果體現(xiàn)在實(shí)驗的正確測試結(jié)果里（如上圖）。
六.測試數(shù)據(jù)及程序運(yùn)行情況: 輸入的內(nèi)容如下: 課程編號
課程名稱
學(xué)分
先決條件
01
程序設(shè)計基礎(chǔ)
2
無 02
離散數(shù)學(xué)
3
01 03
數(shù)據(jù)結(jié)構(gòu)
4
01，02 04
匯編語言
3
01 05
語言的設(shè)計和分析
2
03，04 06
計算機(jī)原理
3
11 07
編譯原理
4
05，03 08
操作系統(tǒng)
4
03，06 09
高等數(shù)學(xué)
7
無 10
線性代數(shù)
5
09 11
普通物理
2
09 12
數(shù)值分析
3
09，10，01
兩種編排方法都輸出結(jié)果為: 第一學(xué)期學(xué)的課程有:高等數(shù)學(xué) 程序設(shè)計基礎(chǔ) 第二學(xué)期學(xué)的課程有:普通物理 線性代數(shù) 匯編語言 第三學(xué)期學(xué)的課程有:數(shù)值分析 計算機(jī)原理 離散數(shù)學(xué) 第四學(xué)期學(xué)的課程有:數(shù)據(jù)結(jié)構(gòu)
第五學(xué)期學(xué)的課程有:操作系統(tǒng) 語言的設(shè)計和分析 第六學(xué)期學(xué)的課程有:編譯原理 七.參考文獻(xiàn): 《數(shù)據(jù)結(jié)構(gòu)》、《C程序設(shè)計》、互聯(lián)網(wǎng)
數(shù)據(jù)結(jié)構(gòu)教學(xué)計劃編制共3
問題描述：
若用有向網(wǎng)表示教學(xué)計劃，其中頂點(diǎn)表示某門課程，有向邊表示課程之間的先修關(guān)系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設(shè)計一個教學(xué)計劃編制程序，獲取一個不沖突的線性的課程教學(xué)流程。（課程線性排列，每門課上課時其先修課程已經(jīng)被安排）。
基本要求：
（1） 輸入?yún)?shù)：課程總數(shù)，每門課的課程號（固定占3位的字母數(shù)字串）和直接先修課的課程號。
（2） 若根據(jù)輸入條件問題無解，則報告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計劃輸出到用戶指定的文件中。
一、需求分析：
本程序需要基于圖的基本操作來實(shí)現(xiàn)
二、概要設(shè)計 ：
抽象數(shù)據(jù)類型 ：
為實(shí)現(xiàn)上述功能需建立一個結(jié)點(diǎn)類，線性表類，圖類。
算法的基本思想 ：
1、圖的構(gòu)建：
建立一個結(jié)點(diǎn)類，類的元素有字符型變量用來存儲字母，整形變量用來存儲位置，該類型的指針，指向下一個元素。建立一個線性表類，完成線性表的構(gòu)建。建立一個圖類，完成圖的信息的讀取，（如有n個點(diǎn)，則建立n個線性表，將每個結(jié)點(diǎn)與其指向的結(jié)點(diǎn)組成一個線性表，并記錄線性表的長度）。
2、Topsort算法：
先計算每個點(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è)計
算法的具體步驟： cla Node{//結(jié)點(diǎn)類 public: string node; int position; //位置 Node* next; bool visit; //是否被訪問
Node(){visit=false;next=NULL;position=0;node=' ';} }; cla Line{ //線性表類 public: int num; Node* head; Node* rear; Node* fence; Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素
Node* current=new Node();
Current->node=ch;
Current->position=v;
fence->next=current;
fence=current;
Num++; } }; cla Graph{ //圖類 private: int numVertex; int numEdge; Line* line; public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //讀入點(diǎn)
string ch;
for(int i=0;i
Cout
Cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
} } void pushEdge(){ //讀入邊
string ch1,ch2;
int pos1,pos2;
for(int i=0;i
{
Cout
Cin>>ch1>>ch2;
for(int j=0;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);
} } void topsort(){ //拓?fù)渑判?/p>
int i;
int *d=new int[numVertex];
for(i=0;i
d[i]=0; //數(shù)組初始化
for(i=0;i
Node* p=line[i].head;
while(p->next!=NULL){
d[p->next->position]++; //計算每個點(diǎn)的入度
p=p->next;
}
} int top=-1,m=0,j,k;
for(i=0;i
if(d[i]==0){
d[i]=top; //找到第一個入度為0的點(diǎn)
Top=i;
}
while(top!=-1){ j=top; top=d[top];
coutnode
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
cout>n>>m; Graph G(n,m); (); (); (); system("pause"); return 0; }
四、調(diào)試分析
略。
五、測試結(jié)果
本實(shí)驗的測試結(jié)果截圖如下：
注：此處由于不會用文件流輸入和輸出，故在命令提示符上直接進(jìn)行輸入。
六、用戶使用說明（可選）
1、本程序的運(yùn)行環(huán)境為windows 操作系統(tǒng)，執(zhí)行文件為 2、運(yùn)行程序時
提示輸入數(shù)據(jù) 并且輸入數(shù)據(jù)然后回車就可以繼續(xù)輸入相應(yīng)數(shù)據(jù)，最后即可得到結(jié)果。
七、實(shí)驗心得（可選）
1、本實(shí)驗是在圖的遍歷問題的基礎(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ù)雜度。
附錄（實(shí)驗代碼）：
#include #include using namespace std; cla Node{//結(jié)點(diǎn)類 public: string node; int position; //位置 Node* next; bool visit; //是否被訪問
Node(){visit=false;next=NULL;position=0;node=' ';} }; cla Line{ //線性表類 public: int num; Node* head; Node* rear; Node* fence; Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素
Node* current=new Node();
Current->node=ch;
Current->position=v;
fence->next=current;
fence=current;
Num++; } }; cla Graph{ //圖類 private: int numVertex; int numEdge; Line* line; public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //讀入點(diǎn)
string ch;
for(int i=0;i
Cout
Cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
} } void pushEdge(){ //讀入邊
string ch1,ch2;
int pos1,pos2;
for(int i=0;i
{
Cout
Cin>>ch1>>ch2;
for(int j=0;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);
} } void topsort(){ //拓?fù)渑判?/p>
int i;
int *d=new int[numVertex];
for(i=0;i
d[i]=0; //數(shù)組初始化
for(i=0;i
Node* p=line[i].head;
while(p->next!=NULL){
d[p->next->position]++; //計算每個點(diǎn)的入度
p=p->next;
}
} int top=-1,m=0,j,k;
for(i=0;i
if(d[i]==0){
d[i]=top; //找到第一個入度為0的點(diǎn)
Top=i;
}
while(top!=-1){ j=top; top=d[top];
coutnode
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
cout>n>>m; Graph G(n,m); (); (); (); system("pause"); return 0; }
數(shù)據(jù)結(jié)構(gòu)教學(xué)計劃編制共3篇(教學(xué)計劃編制數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)相關(guān)文章：
相關(guān)熱詞搜索：數(shù)據(jù)結(jié)構(gòu)教學(xué)計劃編制（共5篇）