前言

20级cqut的别抄！

一、题目

 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
具体要求如下：
(1) 输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
(2) 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
(3) 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。

二、系统设计

2.1 功能模块图

2.2 “课程逻辑”即课程先修关系图

 1 9为第一层 2 4 10 11为第二层 3 12 6为第三层 5 8为第四层 7为第五层

 最先输出的第一层节点不是入度为0，而应该最慢输出的节点入度为0，在这里我们可以采用栈，先将入度为0的节点输出到栈，最后弹出到结果数组。

2.3 主要函数设计

三、问题分析

按照问题描述，设计各功能，再对功能具体实现进行分析。

1. 用户菜单：打印文本界面，从键盘获取字符，按字符选择对应操作，switch结束后再次调用mainmenu，直到switch中选择结束exit。
2. 读取课程信息：图的message先开辟空间，然后由文件读取学期数，每学期最大学分，课程总数给图赋值；图的节点数组开辟空间并初始化，循环读取文件课程号，课程学分，邻接表头指针记得置空；检查有无邻接点，有的话循环挂到邻接链表上。
3. 打印信息：打印 学期总数 每学期最大学分 必修课程数量；循环打印，课程号、学分、所有先修课程；打印完提示 “任意键回主菜单”，获取字符，然后调用主菜单、
4. 修改信息：提示允许修改的信息，获取字符判断哪个信息需要修改；提示输入修改后的值，获取该值，判断是否合法；合法的话赋值给图的相应数据域，提示成功并更新文件内容；非法的话提示出错，按任意键回主菜单，获取字符后调用主菜单。
5. 拓扑排序：最先输出的第一层节点不是入度为0，而应该最慢输出的节点入度为0，在这里我们可以采用栈，先将入度为0的节点输出到栈，最后弹出到结果数组。循环打印拓扑排序结果的数据。
6. 策略选择：用户选择某种策略后，会调用该函数。该函数的功能首先是调用拓扑排序得到结果，然后显示所有结果给用户，通过用户的选择，使用那个选择的结果序列去调用安排函数。

四、实验结果及分析

根据题目要求设置数据文件如下图：第一行展示学期总数，每学期最大学分，课程总数。
接着，第一列为课程号，第二列为课程对应学分，第三列为先修课程。

实验结果如下：
主菜单界面

课程信息界面

信息修改界面

课程安排界面

分析：
如上图已完成题目要求，并设置了简单的界面。但由于不了解c++如何绘制图形化界面，总体界面非常简陋。另外，所使用数据也为书中数据，与真实教学中的课程相差甚大，因此只能算是完成了一个demo，还有很大修改提升的空间。

五、源码

strcture.h

#ifndef STRUCTURE_H_INCLUDED
#define STRUCTURE_H_INCLUDED

#define AVERAGE   1//均匀安排策略
#define QUICKLY   0//尽快安排策略
#define MaxClass  99//课程总数不超过99
#define MaxTerm   12//学期总数不超过12
#define MaxCredit 30            //每学期学分不超过30


//   邻接表表示
typedef struct AdjVexNode {
    int AdjVex;//邻接点位序
    AdjVexNode * Next;//指向下一个邻接点的指针
}AdjVexNode;//邻接表结点


typedef struct  {//顶点表结点
    char data[3];//课程编号
    int credit;//节点学分（每门课学分）
    AdjVexNode* FirstArc;//指向邻接表第一个邻边节点的指针域
    int In_degree;//课程入度
}VexNode;//图节点

typedef struct  {
    int term_num;//学期数
    int max_credit;//每学期学分上限
}Message;//学期信息

typedef struct  {
    VexNode* Vex;//节点数组域
    int VexNum;//节点数
    Message* mes;//每学期的信息(允许修改)
}Class_arrange_Graph;//图
#endif // STRUCTURE_H_INCLUDED

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func.h

#ifndef FUNC_H_INCLUDED
#define FUNC_H_INCLUDED
#include "structure.h"

void mainmenu();

int Locate(char* ch);

void Read_file();

void Print_message();

void Adjust_message();

void File_Update();

void Arrange_Select(int choice);

void Arrange(VexNode *result,int choice);

void Top_Sort(VexNode *result,int choice);

void Print_Top_Sort_Result();

#endif // FUNC_H_INCLUDED

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func.cpp

#include "func.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include "string.h"
#include <stack>
using namespace std;

extern VexNode result1[100];
extern VexNode result2[100];
extern VexNode result3[100];
extern VexNode result4[100];
extern Class_arrange_Graph G;

void mainmenu()
{
    char key;

    printf("\n\n\n\n");
    printf("         欢迎使用课程编排系统               \n\n\n");
    printf("______________________________________________________________________\n");
    printf("     1. 查看课程信息          \n");
    printf("______________________________________________________________________\n");
    printf("      2. 修改课程信息                  \n");
    printf("______________________________________________________________________\n");
    printf("             3. 均匀安排课程                     \n");
    printf("______________________________________________________________________\n");
    printf("             4. 尽快安排课程             \n");
    printf("______________________________________________________________________\n");
    printf("             5. 关闭程序                 \n");
    printf("______________________________________________________________________\n");
    printf("\n\n\n\n\t ") ;
    key=getch();
    key=key-'0';
    switch(key)
    {
        case 1:system("cls");
            Print_message();
            break;

        case 2:system("cls");
            Adjust_message();
            break;

        case 3:system("cls");
            Arrange_Select(AVERAGE);
            break;

        case 4:system("cls");
            Arrange_Select(QUICKLY);
            break;

        case 5:exit(0);

        default :
            cout << "该选项无效,请按任意键回主菜单" << endl;
            key=getch();
            system("cls");
            break;
    }

    mainmenu();
}



int Locate(char* ch)//将C1C2C3……等 变为0 1 2...     课程号对应的位序
{
    return (2 == strlen(ch)) ? ch[1] - '1' : (ch[1] - '0') * 10 + ch[2] - '1';
}



void Read_file()
{
    FILE* fp = fopen("C:\\Users\\50580\\Desktop\\jiaocheng\\shuju.txt", "r");
    if (NULL == fp)
    {
        printf("未找到文件,可能文件路径有误！！！");
        exit(1);
    }

    G.mes=(Message*)malloc(sizeof(Message));

    fscanf(fp,"%d%d%d",&G.mes->term_num,&G.mes->max_credit,&G.VexNum); //读取学期数，每学期最大学分，课程总数
    if(G.VexNum > MaxClass || G.mes->term_num > MaxTerm || G.mes->max_credit > MaxCredit)
    {
        cout << "课程总数或学期数目或每学期最大学分超过上限" <<endl;
        fclose(fp);
        exit(1);//异常退出
    }
    G.Vex = (VexNode*)malloc(sizeof(VexNode) * G.VexNum);
    int i=0;
    for(;i<G.VexNum;i++)
        G.Vex[i].FirstArc=nullptr;

    for (i = 0; i < G.VexNum; i++)//读取课程信息
    {
        fscanf(fp, "%s%d", G.Vex[i].data,&G.Vex[i].credit);//读取课程名称和学分

        while ('\n' != fgetc(fp)) //根据先修课程建立邻接表结点
        {
            char str[3];
            int s;
            fscanf(fp, "%s", str);
            s = Locate(str);
            if (s < 0 || s >= G.VexNum) //判断课程是否有错误
            {
                printf("%s课程错误，本专业无其先修课程！\n", G.Vex[i].data);
                fclose(fp);
                exit(1);
            }
            AdjVexNode* p = (AdjVexNode*)malloc(sizeof(AdjVexNode));//更新邻接表结点
            p->AdjVex = s;
            p->Next = G.Vex[i].FirstArc;
            G.Vex[i].FirstArc = p;

        }
    }
    fclose(fp);

    AdjVexNode * p;
    for (i=0; i<G.VexNum; i++)//初始化入度
        G.Vex[i].In_degree=0;
    for(i=0;i<G.VexNum;i++)//计算各节点入度
    {
        p=G.Vex[i].FirstArc;
        while(p!=nullptr)
        {
            G.Vex[p->AdjVex].In_degree++;
            p=p->Next;
        }
    }
}



void Print_message()
{
    printf("学期总数 :  %d \t",G.mes->term_num);
    printf("每学期最大学分 ： %d \t",G.mes->max_credit);
    printf("必修课程数量 ：   %d \n",G.VexNum);

    cout << "\n\t\t\t本专业提供课程：\n";
    for(int i=0;i<G.VexNum;i++)
    {printf("______________________________________________________________________\n");
        printf("课程号：C%d\t\t学分 ： %d\t\t先修课程： ",i+1,G.Vex[i].credit);
        for (AdjVexNode* p = G.Vex[i].FirstArc; p!=nullptr; p = p->Next)
            printf("C%d  ",p->AdjVex+1);
        printf("\n");
    }

    cout << "\n\t\t\t按任意键回主菜单" <<endl;
    getch();
    system("cls");
    mainmenu();
}


void Adjust_message()
{
    printf("允许修改的内容有: 1.学期总数  2.个人每学期最大学分 ");
    printf("\n\n请选择要修改的内容 ,或按其他键取消修改\n\n");
    char key=getch();
    key=key-'0';

    if(key==1)
    {int term;
        printf("请输入学期总数：");
        scanf("%d",&term);
        fflush(stdin);//清除键盘缓存
        if(term > MaxTerm || term < 1)
        {
            cout << "\n输入的学期数不合法 (大于最大允许的学期数 或 小于1 或 不是正整数)\n" <<endl;
            cout<< "请按任意键回主菜单"<< endl;
            getch();
            system("cls");
            mainmenu();
        }
        G.mes->term_num=term;

        cout << "\n修改成功    (注：如果输入 数字+字符 那么只读入数字)\n" <<endl;
        cout << "按任意键回主菜单" <<endl;
        File_Update();//更新文件信息
        getch();
    }
    else if(key==2)
    {
        int credit;
        printf("请输入个人每学期最大学分：");
        scanf("%d",&credit);
        fflush(stdin);//清除键盘缓存
        if( credit < 1 || credit > MaxCredit)
        {
            cout << "\n输入的学分数不合法 (小于1或大于30)\n" <<endl;
            cout<< "请按任意键回主菜单"<< endl;
            getch();
            system("cls");
            mainmenu();
        }

        G.mes->max_credit=credit;
        cout << "\n修改成功    (如果输入 数字+字符 那么只读入数字)\n" <<endl;
        cout << "按任意键回主菜单" <<endl;
        File_Update();//更新文件信息
        getch();
    }

    system("cls");
    mainmenu();

}



void File_Update()
{
    ofstream ofs;
    ofs.open("C:\\Users\\50580\\Desktop\\jiaocheng\\shuju.txt",ios::in | ios::out | ios::binary);  // in | out 保持原内容不变

    ofs << G.mes->term_num << " "<< G.mes->max_credit << " " << G.VexNum << "\n" ;
    ofs.close();
}


void Arrange_Select(int choice)
{
    Top_Sort(result1,1);
    Top_Sort(result2,2);//调用4种拓扑排序，存到result 1~4
    Top_Sort(result3,3);
    Top_Sort(result4,4);
    Print_Top_Sort_Result();
    cout << "\n\n\n请输入你选择的课程安排先后顺序：";
    char key=getch();

    if     (key=='1')
        Arrange(result1,choice);//根据用户输入，确定使用哪种拓扑排序结果
    else if(key=='2')
        Arrange(result2,choice);
    else if(key=='3')
        Arrange(result3,choice);
    else if(key=='4')
        Arrange(result4,choice);

    else
    {
        cout<<"\n\n选择有误，请按任意键回主菜单";
        getch();
        system("cls");
        mainmenu();
    }

}


void Arrange(VexNode *result,int choice)
{
    system("cls");
    FILE *fp=fopen("./各学期课程安排结果.txt","w");

    int arranged_num=0;//已经安排了的课程数
    int j;  //控制循环的变量
    int k;//控制循环的变量
    int course_num;//本学期安排的课程总数
    int per_max_num;//每学期最大允许课程总数
    int sumcredit;//本学期已安排课程的总学分
    int tag;//标志，用来判断即将安排到本学期的课程 是否有先修课程在本学期
    AdjVexNode* p;//用来遍历 即将安排课程的邻接表 的指针

    if(choice==QUICKLY)
        per_max_num=G.VexNum;//计算不同情况下的每学期最大课程数。
    else
    {if(G.VexNum % G.mes->term_num <  G.mes->term_num/2 )
            per_max_num = G.VexNum/G.mes->term_num;
        else
            per_max_num = (G.VexNum/G.mes->term_num+1);
    }

    VexNode this_term_courses[per_max_num];  //存放本学期已经安排的课程

    for(k=0;k<G.VexNum;k++)
    {
        if(arranged_num==G.VexNum)break;

        fprintf(fp, "\n第%d个学期的课程为：", k+1);
        printf("\n第%d个学期的课程为：", k + 1);
        sumcredit=0;       //本学期安排课程的总学分
        course_num=0;   //本学期安排课程的总数
        p=result[arranged_num].FirstArc;  //先修课指针
        tag=0;            //标志本学期是否有该课程的先修课程
        while(sumcredit + result[arranged_num].credit <= G.mes->max_credit  && tag==0 && course_num<per_max_num)
        {
            while(p!=nullptr && tag==0)
            {
                for(j=0;j<course_num;j++)
                {
                    if(p->AdjVex == Locate(this_term_courses[j].data) )
                    {
                        tag=1;
                        break;
                    }
                }
                p=p->Next;
            }

            if(tag==1) break;

            fprintf(fp, " %s ", result[arranged_num].data);
            printf( " %s ", result[arranged_num].data);
            sumcredit+=result[arranged_num].credit;
            this_term_courses[course_num]=result[arranged_num];
            if(arranged_num==G.VexNum)break;
            arranged_num++;
            course_num++;
            p=result[arranged_num].FirstArc;
        }

    }

    fclose(fp);

    if(k>G.mes->term_num)
    {
        fp=fopen("./各学期课程安排结果.txt","w");
        fprintf(fp,"%s%d","该课程安排先后顺序下，此策略无解,因为安排所需学期数超过学期总数",G.mes->term_num);
        fclose(fp);
        cout << "\n\n\n该课程安排先后顺序下，此策略无解,因为安排所需学期数超过学期总数"<< G.mes->term_num<<endl;
        cout <<"\n\n请按任意键回主菜单" <<endl;
        getch();
        system("cls");
        mainmenu();
    }

    cout << "\n\n\n 课程安排信息已经存入当前目录下，“各学期课程安排结果.txt” \n\n请按任意键回主菜单";
    getch();
    system("cls");
    mainmenu();

}




void Top_Sort(VexNode* result,int choice)
{
    int i;//循环控制变量
    int tag=0;  //判断图中还有没有入度为0的节点
    AdjVexNode *  p;    //指向选中课程邻接表域的指针
    stack<VexNode> S;     //用来存储已被排序完的节点
    stack<AdjVexNode *> S1;//用来存储每一层的节点的邻接表指针
    Read_file();//读文件更新入度
    if(choice==1)

        while(tag==0)
        {
            tag=1;
            for(i=G.VexNum-1;i>=0;i--)
                if(G.Vex[i].In_degree==0)//将一个层次的节点入栈S，同时邻接表头入栈S1
                {
                    S.push(G.Vex[i]);
                    G.Vex[i].In_degree--;
                    p=G.Vex[i].FirstArc;
                    S1.push(p);
                    tag=0;
                }

            while(S1.empty()==false)//一个层次的邻接点入度减一
            {p=S1.top();
                S1.pop();

                while(p!=nullptr)
                {
                    G.Vex[p->AdjVex].In_degree--;
                    p=p->Next;
                }
            }
        }



    else if(choice==2)

        while(tag==0)
        {
            tag=1;
            for(i=0;i<G.VexNum;i++)
                if(G.Vex[i].In_degree==0)
                {
                    S.push(G.Vex[i]);
                    G.Vex[i].In_degree--;
                    p=G.Vex[i].FirstArc;
                    S1.push(p);
                    tag=0;
                }

            while(S1.empty()==false)
            {p=S1.top();
                S1.pop();

                while(p!=nullptr)
                {
                    G.Vex[p->AdjVex].In_degree--;
                    p=p->Next;
                }
            }
        }



    else if(choice==3)

        for(i=G.VexNum-1;i>=0;i--)
        {
            if(G.Vex[i].In_degree==0)//找到一个节点入度0就入栈并使邻接点入度减一
            {
                S.push(G.Vex[i]);
                G.Vex[i].In_degree--;
                p=G.Vex[i].FirstArc;
                while(p!=nullptr)
                {
                    G.Vex[p->AdjVex].In_degree--;
                    p=p->Next;
                }

                i=G.VexNum;
            }
        }



    else

        for(i=0;i<G.VexNum;i++)
        {
            if(G.Vex[i].In_degree==0)
            {
                S.push(G.Vex[i]);
                G.Vex[i].In_degree--;
                p=G.Vex[i].FirstArc;
                while(p!=nullptr)
                {
                    G.Vex[p->AdjVex].In_degree--;
                    p=p->Next;
                }

                i=-1;
            }
        }




    i=S.size();
    if(i <G.VexNum)//查看节点是否都入栈了
    {
        cout<< "拓扑排序失败，课程先修关系可能存在环路，请按任意键回主菜单\n";
        getch();
        system("cls");
        mainmenu();
    }

    for(i=0;i<G.VexNum;i++)//结果存到result数组
    {
        if(S.empty()==false)
        {
            result[i]=S.top();
            S.pop();
        }
        else
        {
            cout << "拓扑排序弹栈失败,请按任意键回主菜单" << endl;
            getch();
            mainmenu();
        }

    }
}



void Print_Top_Sort_Result()
{
    printf("各课程安排先后顺序为:\n");
    cout << "选择1：" ;
    for(int i=0;i<G.VexNum;i++)
    {
        cout<< result1[i].data<< "  " ;
    }

    cout << "\n\n选择2：" ;
    for(int i=0;i<G.VexNum;i++)
    {
        cout<< result2[i].data<< "  " ;
    }

    cout << "\n\n选择3：" ;
    for(int i=0;i<G.VexNum;i++)
    {
        cout<< result3[i].data<< "  " ;
    }

    cout << "\n\n选择4：" ;
    for(int i=0;i<G.VexNum;i++)
    {
        cout<< result4[i].data<< "  " ;
    }

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512

main.cpp

#include <iostream>
#include "structure.h"
#include "func.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include "string.h"
#include <stack>
#include <cstddef>
using namespace std;

VexNode result1[100];
VexNode result2[100];
VexNode result3[100];
VexNode result4[100];
Class_arrange_Graph G;

int main()
{
    Read_file();
    mainmenu();
    return 0;



}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

总结

此为本人2022年大二下学期数据结构课设中的一道题目。特此记录。