教学计划数据结构课程设计说明书

1

）

、图的邻接表的存储表示，即结构体的定义

typedef char VertexType[MAX_NAME];

typedef struct ArcNode

{

int adjvex;

//

该弧所指向的顶点的位置

struct ArcNode *nextarc;

//

指向下一条弧的指针

}ArcNode;

//

链表结点

typedef struct

//

链接表

{

VertexType data;

//

顶点信息

int grades;

//

存储学分信息

ArcNode *firstarc;

//

指向第一条依附该顶点的弧的指针

}VNode, AdjList[MAX_VERTEX_NUM];

//

头结点

typedef struct

{

AdjList vertices;

//vertices

存储课程名

int vexnum, arcnum;

//

图的当前顶点数和边数

}ALGraph;

2

、利用前插法，建立图的邻接链表

请输入下列课程的先修课程

(

无先修课程输入

0

结束后也输入

for (k=0;k

.vexnum;++k) //

构造表结点链表

,

{

pri ntf(

的先修课程

:

.vertic es[k].data);

scanf(

while (va[0]!='0')

{

i = LocateVex(G

, va);//

弧头

j = k;

//

弧尾

p = (ArcNode*)malloc(sizeof(ArcNode));

p->adjvex = j;

p->nextarc = G

.vertices[i].firstarc; //

插在表头

G

.vertices[i].firstarc = p;

scanf(

}

}

3

）

、输出 图的顶点和边

printf(

个顶点

.vexnum);

for (i = 0;i < G

.vexnum;++i)

printf(

printf(

条弧边

:n

.arcnum);

for (i = 0;i < G

.vexnum;i++)

{

p = G

.vertices[i].firstarc;

while (p)

{

printf(

.vertices[p->adjvex].da ta);

p = p->nextarc;

}

}

< /p>

4

）

、通过栈实现拓扑排序

FindInDegree(G

, indegree);

//

对各顶点求入度

InitStack(S);

//

初始化栈

for (i = 0;i < G

.vexnum;++i)

//

建零入度顶点栈

S

if (!indegree[i]) Push(S, i);

//

入度为

0

者进栈

count = 0;

//

对输出顶点计数

while (!StackEmpty(S))

{

Pop(S, i);

printf(

分

< br>),

.vertices[i].data,G

.ver tices[i].grades);

Temp[j++] = es[i];

//

将当前的拓扑序列保存起来

++count;

//

输出

i

号顶点并计数

for (p =G

.vertices[i].firstarc; p; p=p->nextarc)//

对

i

号顶点的每个邻接点

的入度减

1

{

k = p->adjvex;

if (!(--indegree[k])) //

若入度减为

0 ,

则入栈

Push(S, k);

}

}

if (count < )

{

printf(

< br>此有向图有回路无法完成拓扑排序

return ERROR;

}

else printf(

为一个拓扑序列

printf(

Return OK

Return ERROR

0

的顶点存入

InDegree

中

对每个顶点求 入度，并存入数组

InDegree[i]

中（

i=0

…

n

）

初始化栈

Stack,Counter=0

对以

i

号顶点为尾弧的每个邻接点的入度减< /p>

1

，

并将入度减

1

后为零的顶点号压入栈中，

输出

i< /p>

，计数器加

1(Counter++)

推出栈顶的一个元素（入度为零的顶点号）至

i

，输出

i

，计数器加

1

（

Counter++

）

< br>依次将入度为

0

的顶点存入

In Degree

中

5)

、解决问题

根据学分上限决定出每学期应学课程，其中

Temp[]

中 存储的是经过拓扑排序后的课程

先后顺序。

int q=1,Z=0;

while (q <= TotalTerms)

{

int C = Temp[Z].grades

printf(

< br>第

%d

个学期应学课程

:

while (C <= MaxScores)

{

C = C + Temp[Z+1].grades;

if (Z < G

.vexnum)

printf(

++Z;

}

printf(

if (q == TotalTerms)printf(

课程编制完成！

q++;

}

例如输出如下结果：

………………………

.

4.2

核心代码

#include

#include

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define MAX_NAME 3

#define MAXCLASS 100

//

顶点字符串的最大长度

#define MAX_VERTEX_NUM 100

//

最大顶点数

#define N 35

typedef char VertexType[MAX_NAME];

int TotalTerms ;

//

学期总数

int MaxScores;

//

学分上限

/* ----

图的邻接表存储表示

---- */

typedef struct ArcNode

{

int adjvex;

//

该弧所指向的顶点的位置

弧的节点结构

struct ArcNode *nextarc;

//

指向下一条弧的指针

}ArcNode;

//

链表结点

typedef struct

//

链接表

{

VertexType data;

//

顶点信息

int grades;

//

存储学分信息

ArcNode *firstarc;

//

指向第一条依附该顶点的弧的指针

}VNode, AdjList[MAX_VERTEX_NUM];

//

头结点

typedef struct

{

AdjList vertices;

//vertices

存储课程名

int vexnum, arcnum;

//

图的当前顶点数和弧数

}ALGraph;

void OUTPUT()

{

int s;

printf(

教学计划编制菜单

n

printf(

课程代码

|

课程名称

|

优先课程

n

printf(

|C++

语言程序设计

|

无

n

printf(

|

高等数学

|

无

n

printf(

|

程序设计基础

|

无

n

printf(

|

汇编语言

| C1

n

printf(

|

线性代数

| C2

n

printf(

|

数字逻辑

| C2

n

printf(

|

计算机组成原理

| C11

n

printf(

|

离散数学

| C3

n

printf(

|

语言的设计与分析

| C1,C3

n

printf(

|

数据结构

| C3,C8

n

printf(

|

普通物理

| C2

n

printf(

|

数值分析

| C3,C5,C11 n

printf(

|

数据库系统原理

| C3,C4

n

printf(

|*

面向 对象程序设计（

C#

）

| C3

n

printf(

|

软件工程

| C3

，

C10

n

printf(

|

面向对象系统分析

| C14,C15

n

printf(

|

操作系统

| C7

，

C10

n

printf(

|

计算机通信与网络

| C11

n

printf(

|*UML

与

Rational Rose

| C7

，

C18

n

printf(

|*

编译原理

| C9

，

C10

n

printf(

|

软件测试技术

| C15

n

printf(

|*

新型计算机网络技术

| C18

n