摘 要：本文提出了一種普通高校計(jì)算機(jī)輔助教學(xué)計(jì)劃編制的實(shí)現(xiàn)方法。通過仿真實(shí)驗(yàn)，該方法在教學(xué)計(jì)劃編制的精確性和其他性能方面是可行的。

關(guān)鍵詞：計(jì)算機(jī) 教學(xué)計(jì)劃

中圖分類號(hào)：G434 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1673-8454（2008）13-0054-04

在高等院校，制定各專業(yè)各學(xué)期的教學(xué)計(jì)劃越來越成為一件繁重的工作。為了降低教務(wù)工作者的勞動(dòng)強(qiáng)度，提高勞動(dòng)效率，筆者通過實(shí)驗(yàn)研究給出了高等院校計(jì)算機(jī)輔助教學(xué)計(jì)劃編制系統(tǒng)的實(shí)現(xiàn)方法。

每個(gè)專業(yè)都有固定的學(xué)習(xí)年限，每年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排上必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有多門，也可以沒有。每門課程恰好占一個(gè)學(xué)期，如果某門課在一學(xué)期不能修完，則可將此看作兩門或兩門以上的課程處理（如英語(yǔ)，可將其看作英語(yǔ)1、英語(yǔ)2等）。另外，教學(xué)計(jì)劃要求課程盡可能地集中在前幾個(gè)學(xué)期中但不能超過學(xué)分上限。

一、算法設(shè)計(jì)思想

1.有的課程（如政治等）既沒有先修課又不是其它課的先修課，用戶可以事先指定在某個(gè)學(xué)期學(xué)習(xí)這些課程；有的課程可能是其它課的先修課，也可能是以其它課為先修課，對(duì)這些課程的安排可以通過構(gòu)造AOV網(wǎng)（如圖1所示，用頂點(diǎn)表示課程，用有向弧表示先修關(guān)系）然后進(jìn)行拓?fù)渑判驔Q定其在某學(xué)期學(xué)習(xí)，對(duì)此采用圖的鄰接表表示存儲(chǔ)結(jié)構(gòu)。

2.制定第i學(xué)期的教學(xué)計(jì)劃時(shí)，首先選擇同時(shí)符合下列條件（后稱條件1）的所有課程：

（１）指定學(xué)習(xí)某門課的時(shí)間ｌｅａｎｅｄ＿ｉｎ＿ｔｅｒｍ＝ｉ；

（２）標(biāo)志位leaned=0。

將其標(biāo)志位leaned置為1（已修），用輔助變量crednum存儲(chǔ)符合該條件的所有課程的學(xué)分和，由于這些課程總數(shù)無法預(yù)先知道，故對(duì)此采用線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。為了使課程盡可能地集中在前幾個(gè)學(xué)期中但不能超過學(xué)分上限limt，那么需要對(duì)同時(shí)符合以下條件（后稱條件2）的K門課程組成的集合的m個(gè)子集進(jìn)行探索：

（１）入度ｂａｓｅｓｕｂｎｕｍ＝０（已沒有先修課）；

（２）標(biāo)志位 ｌｅａｎｅｄ＝０（未修）；

（３）ｌeaned_in_term=0（“0”表示未指定在某學(xué)期學(xué)習(xí)）。

查找某集合的各門課程的學(xué)分之和subcred符合下面兩個(gè)條件（后稱條件3）：

（１）ｃｒｅｄｎｕｍ＋ｓｕｂｃｒｅｄ＜＝ｌｉｍｔ；

（２）設(shè)subcred[i]（i=1、2、3···）是符合關(guān)系1的k門課程組成的集合的m個(gè)子集中的n(0

在符合先修關(guān)系的前提下，為了使學(xué)分高的課程排在前幾個(gè)學(xué)期，需將上述K門課程對(duì)學(xué)分進(jìn)行降序排序，然后按層次從上到下、從左到右生成帶有指向雙親結(jié)點(diǎn)的三叉鏈表。

如制定第一學(xué)期的教學(xué)計(jì)劃時(shí)，由表2可知課程代號(hào)為C13、C17的課程符合上述條件1，則crednum=2+1=3同時(shí)將相應(yīng)leaned置為1。代號(hào)為C1、C9的課程是符合該上述條件2的k（k=2）門課程，對(duì)學(xué)分進(jìn)行降序排序?yàn)椋?/p>

課程代號(hào)： C9C1

學(xué)分：72

生成的樹型三叉鏈表如圖2所示。

可以發(fā)現(xiàn)三叉鏈表的最后一層上的Credit域分別是集合{7，2}的各子集（除空集外）的各門課程的和，由于第二個(gè)結(jié)點(diǎn)的Credit的值（Credit=7）符合條件3，故從此結(jié)點(diǎn)開始順Pare指針向根結(jié)點(diǎn)搜索Credit=7的全部課程，由于第一個(gè)結(jié)點(diǎn)的Post=0，故該結(jié)點(diǎn)沒有加入新課程，順Pare找到第二結(jié)點(diǎn)，由于Post=9說明在圖中位置為9的課程可列入本學(xué)期教學(xué)計(jì)劃并將其標(biāo)志位leaned置為1（已修），依次類推直到根結(jié)點(diǎn)止。這樣就得到了第一學(xué)期的教學(xué)計(jì)劃，課程總數(shù)為3門，學(xué)分和為10分（如表1所示）。

其實(shí)，符合上述條件2的k（k=2）門課程已經(jīng)對(duì)學(xué)分降序排序，而且三叉鏈表又是按層次從上到下、從左到右生成，所以在建樹的過程中（借助循環(huán)隊(duì)列），如果當(dāng)前結(jié)點(diǎn)的Credit> limt-crednum，則以該結(jié)點(diǎn)為雙親的子樹已經(jīng)與問題無關(guān)，不必建造此子樹；一旦發(fā)現(xiàn)當(dāng)前結(jié)點(diǎn)的Credit= limt-crednum就可以提前結(jié)束循環(huán)，不必繼續(xù)建樹。后續(xù)學(xué)期如此循環(huán)就可以得到本專業(yè)的教學(xué)計(jì)劃。

二、算法的主要存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)[1]

涉及的主要數(shù)據(jù)結(jié)構(gòu)：AOE網(wǎng)、帶有指向祖先結(jié)點(diǎn)的三叉鏈表、線性鏈表和循環(huán)隊(duì)列。[2]

#define max_term_size 12/*學(xué)期總數(shù)不超過12*/

#define max_sub_size 100/* 課程總數(shù)不超過100*/

#define max_squ-size 1000/*循環(huán)隊(duì)列最大長(zhǎng)度為1000*/

/*課程結(jié)點(diǎn)*/

typedef struct {

char subno[3]；char subname[30]；}subnode，subjectlist[20]；

/*專業(yè)結(jié)點(diǎn) */

typedef struct {

char deparno[3]； char deparname[20]；}deparnode；

/* 具有相同基礎(chǔ)課的鏈表（先修關(guān)系） */

typedef struct subrelate {

int subre； struct subrelate *nextsub； }subjectrelatenode，*subjectrelate；

/*課程信息結(jié)點(diǎn)（鄰接表存儲(chǔ)結(jié)構(gòu)） */

typedef struct subjectmes {

subnode sub；/*課程結(jié)點(diǎn) */

int credit，basesubnum，leaned_in_term，leaned； /*標(biāo)志位:0為未學(xué)，1為已學(xué) */

subjectrelate firstbasesub； }subjectnode[max_sub_size]；

/* 專業(yè)信息結(jié)點(diǎn)*/

typedef struct departmes {

deparnode depart；/*專業(yè)結(jié)點(diǎn)*/

inttermnum，subjectnum，limt；/*學(xué)分上限*/

subjectnode subject；}depart_mes_node；

/*存儲(chǔ)指定某個(gè)學(xué)期學(xué)習(xí)的課程的線性鏈表 */

typedef struct sub {

int subno; struct sub * next; } *plist;

/*帶有指向祖先結(jié)點(diǎn)的三叉樹*/

typedef struct bitree {

int cred，int post；struct bitree *lch，*rch，*pare; }*tpstr;

/*循環(huán)隊(duì)列*/

typedef struct seq {

int fore，rear； struct bitree *sub[max_squ_size]；} cycsqu；

后面的算法以上述結(jié)構(gòu)定義為準(zhǔn)。

三、算法實(shí)現(xiàn)

為了說明問題，本文僅給出主要算法pro_plan_instru（），而數(shù)據(jù)的輸入函數(shù)input（）讀者可以自行編寫。主要程序代碼如下（用C語(yǔ)言編寫）：[3]

depart_mes_node department;

{ int i，j，k，m，exch，subnum，crednum，crednum1，subcred，credsort[max_sub_size];

int count，n，max; subjectrelate ts;plist p，q; tpstr tp，tq;cycsqu plan;

printf(\"\following is the plan instructure for department of %s:\\"，department.depart.deparname);

for(i=1;i＜=department.termnum;++i) /*開始制定department.termnum個(gè)學(xué)期的計(jì)劃*/

{p=0;crednum=0;subnum=0;k=0; count=0; subcred=0;

for(j=1; j＜=department.subjectnum;++j) /*選擇指定第i個(gè)學(xué)期學(xué)習(xí)的課程*/

{if(department.subject[j].leaned_in_term==i)

{ department.subject[j].leaned=1; q=(struct sub *)malloc(sizeof(struct sub));

q-＞subno=j;q-＞next=p; p=q;crednum+=department.subject[j].credit;}

if(!(department.subject[j].leaned_in_term)department.subject[j].basesubnum＜=0)!(department.subject[j].leaned))

{ ++k; credsort[k]=j;}

}

subcred=department.limt-crednum;

for(m=1;m＜k;++m)

{for(j=1;j＜k-m+1;++j)

if(department.subject[credsort[j]].credit＜department.subject[credsort[j+1]].credit)

{ exch=credsort[j];credsort[j]=credsort[j+1];credsort[j+1]=exch; }

}

tp=(struct bitree*)malloc(sizeof(struct bitree)); tp-＞cred=0; tp-＞post=0; tp-＞lch=0; tp-＞rch=0; tp-＞pare=0; plan.fore=0; plan.rear=0;

if(k) /*如果符合條件3的課程總數(shù)k＞0生成三叉鏈表*/

plan.sub[plan.rear]=tp; plan.rear=(plan.rear+1)% max_squ-size;count=1; /*三叉鏈表第j層的結(jié)點(diǎn)數(shù)*/

for(j=1;j＜=k; ++j)

{n=count; count=0;

for(m=1;m＜=n;++m)

{tp=plan.sub[plan.fore];plan.fore=(plan.fore+1)%max_squ-size; crednum1=tp-＞cred+department.subject[credsort[j]].credit;

if(crednum1＜=subcred)

{tq=(structbitree*)malloc(sizeof(structbitree));

tq-＞pare=tp;tq-＞lch=0;tq-＞rch=0;tq-＞cred=crednum1;tq-＞post=credsort[j];tp-＞lch=tq;plan.sub[plan.rear]=tq;plan.rear=(plan.rear+1)% max_squ-size;++count;

}

if(crednum1==subcred)

{

tp=tq; printf(\"%d\\"，department.subject[tp-＞post].credit); goto equal;

}

tq=(structbitree*)malloc(sizeof(structbitree));

tq-＞pare=tp;tq-＞lch=0;tq-＞rch=0;tq-＞cred=tp-＞cred;

tq-＞post=0;tp-＞rch=tq; ++count;

plan.sub[plan.rear]=tq;plan.rear=(plan.rear+1)% max_squ-size;

}

}

equal:

if(subcred!=crednum1)

{plan.fore=(plan.rear-count+ max_squ-size)% max_squ-size;max=0;

for(;plan.fore＜=count; ++plan.fore)

if((plan.sub[plan.fore]-＞cred＜subcred)(plan.sub[plan.fore]-＞cred＞max))

{max=plan.sub[plan.fore]-＞cred;tp=plan.sub[plan.fore]; }

}

printf(\"term%2d:\\\"，i); count=0;n=0;

while(p)

{printf(\"%s:%d: ，department.subject[p-＞subno].sub.subno，department.subject[p-＞subno].credit);

++count;n+=department.subject[p-＞subno].credit; q=p;p=p-＞next; free(q)；

}

if(k)

{ while(tp)

{if(tp-＞post!=0) {printf(\"%s:%d\"，department.subject[tp-＞post].sub.subno，department.subject[tp-＞post].credit);

++count;n+=department.subject[tp-＞post].credit;department.subject[tp-＞post].leaned=1;

ts=department.subject[tp-＞post].firstbasesub;

while(ts)

{ department.subject[ts->subre].basesubnum;ts=ts-＞nextsub; }

}tq=tp; tp=tp-＞pare; free(tq);

}

}

printf(\"\subjectnum:%dcreditnum:%d\\"，count，n);

}

}

四、算法測(cè)試及結(jié)果分析

輸入數(shù)據(jù)如表2所示，打印結(jié)果如下：

following is the plan of instructure for department of software：

term 1： C17：1 C13：2 C09：7 subjectnum：3 creditnum：10

term 2： C18：1 C14：2 C01：2 C10：5subjectnum：4 creditnum:10

term 3: C19：1 C15：2 C11：2 C04：2 C02：3 subjectnum：5 creditnum：10

term 4: C16：2 C06：3 C03：4 subjectnum：3creditnum：9

term 5： C05：2 C12：3 C08：4 subjectnum：3creditnum：9

term 6： C07：4 subjectnum：1 creditnum：4

term 7： subjectnum：0 creditnum：0

term 8： subjectnum：0 creditnum：0

由打印結(jié)果可知第1~3學(xué)期學(xué)分總數(shù)均為10分，達(dá)到學(xué)分上限值，第4、5學(xué)期學(xué)分總數(shù)均為9分，第6學(xué)期學(xué)分總數(shù)為4分，第7、8學(xué)期學(xué)分總數(shù)均為0分。說明該算法完全符合課程盡可能地集中在前幾個(gè)學(xué)期中但不能超過學(xué)分上限的要求；而且學(xué)分大的課程在先修關(guān)系約束的前提下集中在前幾個(gè)學(xué)期中，如代號(hào)為C9、學(xué)分為7的課程在第1學(xué)期學(xué)習(xí)，代號(hào)為C10、學(xué)分為5的課程在第2學(xué)期學(xué)習(xí)。所以該設(shè)計(jì)思想基本上符合普通高校教學(xué)計(jì)劃編制的要求，可作為解決教學(xué)計(jì)劃編制及類似問題的軟件人員的參考。

五、結(jié)束語(yǔ)

通過仿真實(shí)驗(yàn)，表明本文提出的計(jì)算機(jī)輔助教學(xué)計(jì)劃編制的實(shí)現(xiàn)方法在精確性和其他性能方面是可行的。由于算法是用傳統(tǒng)的數(shù)學(xué)方法實(shí)現(xiàn)的，故該系統(tǒng)缺乏智能性，容錯(cuò)性較差，這將在以后的研究工作中逐步解決。

參考文獻(xiàn)：

[1]王珊編著.數(shù)據(jù)組織與管理[M].北京：經(jīng)濟(jì)科學(xué)出版社，1999.

[2]嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.

[3]譚浩強(qiáng)編著.C語(yǔ)言程序設(shè)計(jì)（第二版）[M].北京：清華大學(xué)出版社，1999.