数据结构#课表排序及查询

专业课程安排

摘要：利用邻接表建立专业课程的有向图，明确课程先修后修的关系，可实现拓扑排序，最后使用广度遍历，可查询每学期的课程信息，还可以查询该课程所在的学期。最后利用循环，选择功能可实现专业课程安排中所给要求。

关键词：邻接表；有向图；拓扑排序；广度遍历

功能介绍

该程序的功能是专业课程安排。输入任意一个专业的所有专业课建立有向图，可以完成拓扑排序，输出任意一个学期的课程信息：名称，课时，学分，按照课程查询任意一门课程所属的学期。

概要设计

2.1模块功能流程图

详细设计

3.1采用C语言定义结构体数据类型

3.1.1 头结点的顶点信息结构体数据类

typedef struct{

ArcNode *firstarc;

char data;//编号

char keming[20];//课程名称

int xueqi;//学期

int xueshi;//学时

int xuefen; //学分

}VNode,Vertice[MAX];//顶点信息

3.1.2 表结点结构体数据类型

typedef struct ArcNode{

struct ArcNode *nextarc; //指向下一条弧的指针

int adjvex; //该弧所指的顶点位置

}ArcNode;

3.2各模块的类C 代码

3.2.1邻接表创建创建有向图

void CreateALGraph(ALGraph &G){

int i,j,k;

char v1,v2;//顶点编号

ArcNode *p,*s;

scanf("%d%d",&G.vexnum,&G.arcnum);//输入顶点数目和边数

for(i = 0; i < G.vexnum; i++){

cin>>G.vex[i].data>>G.vex[i].keming>>G.vex[i].xuefen>>G.vex[i].xueqi>>G.vex[i].xueshi; //输入课程标号，学期，课程名称，学分，学时等所有信息

G.vex[i].firstarc = NULL;//指向的第一个节点为空

}

for(i = 0; i < G.arcnum; i++){

cin>>v1>>v2;//输入一条边上的两个顶点编号

j = LocateVex(G,v1);//获取弧尾结点存储位置

k = LocateVex(G,v2);//获取弧头结点存储位置

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

s->adjvex = k; //将弧头位置给新分配分节点

s->nextarc = NULL;

if(!G.vex[j].firstarc){

G.vex[j].firstarc = s;//如果弧尾指向的第一个节点为空，插入s

}

else{

p = G.vex[j].firstarc;//如果不为空，一直往后找，找到末位插入s

while(p->nextarc)

p = p->nextarc;

p->nextarc = s;

}

3.2.2拓扑排序

void TopologicalSort(ALGraph G){

ArcNode *p; int count=0;

FindInputDgeree(G); //对各个顶点求入度

InitStack(S);

for(i = 0; i < G.vexnum; i ++)

if(!indegree[i])//把入度为零的节点入栈

Push(S,i);

while(!StackEmpty(S)){

i=Pop(S,i); cout<<G.vex[i].data<<endl; count ++;//输出i号定点并计数

for(p = G.vex[i].firstarc; p;p=p->nextarc){

k=p->adjvex; //对i号顶点的每个邻接点入度减一

if(!(--indegree[k]))//入度为0则入栈

Push(S,k);

}

3.2.3 DFS遍历

void DFS(ALGraph G, int i,int term){

//以vi为出发点对邻接表表示的图G进行深度优先搜索

if(G.vex[i].xueqi==term){

cout<<G.vex[i].data<<""<<G.vex[i].keming<<""<<G.vex[i].xuefen<<""<<G.vex[i].xueshi<<endl;//如果学期相等，则输出该学期信息

}

visited[i] = TRUE; //标记vi已访问

p = G.vex[i].firstarc; //取vi边表的头指针

while (p) { //依次搜索vi的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvex]) //若vi尚未被访问

DFS(G, p->adjvex,term); //则以Vj为出发点向纵深搜索

p = p->nextarc; //找vi的下一邻接点

}

3.3.2 主函数

int main(){

ALGraph G;

CreateALGraph(G);//建立图

cout<<"功能1：拓扑排序"<<" "<<"功能2：查询学期课程"<<" "<<"功能3：查看课程所属学期"<<" "<<"功能4：退出"<<endl;

while(1){

cout<<"请输入1/2/3/4完成功能"<<endl;

int i; cin>>i; //选择功能

switch(i){

case 1:TopologicalSort(G);

cout<<endl;//进行拓扑排序

break;

case 2:{

cout<<"请输入学期（1-7）";

cin>>term;

DFSTraverseM(G,term);

break;

}

case 3:{

cout<<"请输入课程名称：";

cin>>name;

DFSTraverseM2(G,name);

break;

}

case 4:{

n=0;

break;

}

return 0;

}

最后附上源码：

  1 #include <stdio.h>
  2 #include<string.h>
  3 #include<iostream>
  4 using namespace std;
  5 #include <stdlib.h>
  6 #define MAX 30
  7 typedef enum{ FALSE, TRUE }Boolean;
  8 Boolean visited[30];
  9 
 10 int indegree[MAX];//用来存储所有节点的入度之和
 11 //表节点 
 12 typedef struct ArcNode{
 13     struct ArcNode *nextarc;  //指向下一条弧的指针 
 14     int adjvex;     //该弧所指的顶点位置 
 15 }ArcNode;
 16 //头节点中存储课程名称，编号，学期，学分，指向第一个节点的指针 
 17 typedef struct{
 18     ArcNode *firstarc;
 19     char data;//编号
 20     char keming[20];//课程名称
 21     int xueqi;
 22     int xueshi;
 23     int xuefen;     
 24 }VNode,Vertice[MAX];//顶点信息 
 25 
 26 typedef struct{
 27     int vexnum,arcnum;
 28     Vertice vex;
 29 }ALGraph;//图的信息
 30  
 31 typedef struct{
 32     int *top;
 33     int *base;
 34     int stacksize;
 35 }SqStack;
 36 
 37 int LocateVex(ALGraph G, char v){
 38     for(int i = 0; i < G.vexnum; i ++){
 39         if(v == G.vex[i].data)
 40             return i;
 41     }
 42     
 43     return -1;
 44 }
 45 
 46 void CreateALGraph(ALGraph &G){
 47     int i,j,k;
 48     char v1,v2;//顶点编号 
 49     ArcNode *p,*s;
 50     
 51     printf("输入节点和边的数目:
");
 52     scanf("%d%d",&G.vexnum,&G.arcnum);
 53     
 54 
 55     //getchar();
 56     cout<<"请输入所有的专业课信息"<<endl; 
 57     cout<<"请输入    编号"<<"-----"<<"课程名称"<<"-----"<<"学分"<<"-----"<<"学期"<<"-----"<<"学时"<<endl; 
 58     for(i = 0; i < G.vexnum; i++){ 
 59         cin>>G.vex[i].data>>G.vex[i].keming>>G.vex[i].xuefen>>G.vex[i].xueqi>>G.vex[i].xueshi; 
 60         G.vex[i].firstarc = NULL;    
 61     }
 62     
 63     for(i = 0; i < G.arcnum; i++){
 64     cout<<"输入一条边上的两个顶点编号 :"<<endl; 
 65         
 66         cin>>v1>>v2;
 67         
 68         j = LocateVex(G,v1);
 69         k = LocateVex(G,v2);
 70         
 71         s = (ArcNode *)malloc(sizeof(ArcNode));
 72         s->adjvex = k;        
 73         s->nextarc = NULL;
 74         
 75         
 76         if(!G.vex[j].firstarc){
 77             G.vex[j].firstarc = s;
 78         }
 79         else{
 80             p = G.vex[j].firstarc;
 81             
 82             while(p->nextarc)
 83                 p = p->nextarc;
 84             
 85             p->nextarc = s;
 86         }
 87     }
 88 }
 89 
 90 void FindInputDgeree(ALGraph G){ //计算所有节点的入度
 91     ArcNode *p;
 92     int i;
 93     
 94     for(i = 0; i < G.vexnum; i ++)
 95         indegree[i] = 0;
 96     
 97     for(i = 0; i < G.vexnum; i ++){
 98         p = G.vex[i].firstarc;
 99         
100         while(p){
101             indegree[p->adjvex] ++;
102             p = p->nextarc;
103         }
104     }
105 }
106 
107 void InitStack(SqStack &S){
108     S.base = ( int*)malloc(sizeof(int) * MAX);
109     
110     if(!S.base)
111         return ;
112     
113     S.top = S.base;
114     S.stacksize = MAX;
115 }
116 
117 void Push(SqStack &S, int i){
118     
119     *S.top++ = i;
120 }
121 
122 int StackEmpty(SqStack S){
123     if(S.top==S.base)
124         return 1;
125     
126     return 0;
127 }
128 
129 int Pop(SqStack &S, int &i){
130     if(S.base!=S.top)
131     i = *-- S.top;
132     return i;
133 }
134 
135 void TopologicalSort(ALGraph G){
136     ArcNode *p;
137     FindInputDgeree(G); 
138     int i,count = 0;
139     
140     SqStack S;    
141     InitStack(S);
142     
143     for(i = 0; i < G.vexnum; i ++)
144         if(!indegree[i])//把入度为零的节点入栈
145             Push(S,i);
146     
147     printf("拓扑序列如下:
");        
148     while(!StackEmpty(S)){
149         i=Pop(S,i);
150         cout<<G.vex[i].data<<"  ";
151         count ++;
152         
153         int k;
154         for(p = G.vex[i].firstarc; p;p=p->nextarc){
155             k=p->adjvex;
156             if(!(--indegree[k]))
157             Push(S,k);
158             
159         }
160         
161         
162         
163         
164         /*while(p){        
165             if(!(-- indegree[p->adjvex]))//判断去掉一条边后节点的入度是否为零
166                 Push(S,p->adjvex);
167             
168             p = p->nextarc;
169         }    */    
170     }
171     
172     if(count < G.vexnum)
173         cout<<"该图为有向有环图"<<endl;
174     
175 }
176 
177 void DFS(ALGraph G, int i,int term)
178 {
179     //以vi为出发点对邻接表表示的图G进行深度优先搜索
180     ArcNode *p;
181     if(G.vex[i].xueqi==term){
182          cout<<"编号"<<"    " <<"课程名称"<<"    "<<"学分" <<"   "<<"学时"<<endl; 
183     cout<<G.vex[i].data<<"    "<<G.vex[i].keming<<"   "<<G.vex[i].xuefen<<"   "<<G.vex[i].xueshi<<endl;
184     }
185       // 访问顶点vi
186     visited[i] = TRUE;              //标记vi已访问
187     p = G.vex[i].firstarc;        //取vi边表的头指针
188     while (p)
189     {                               //依次搜索vi的邻接点vj，这里j=p->adjvex
190         if (!visited[p->adjvex])    //若vi尚未被访问
191             DFS(G, p->adjvex,term);      //则以Vj为出发点向纵深搜索
192         p = p->nextarc;                     //找vi的下一邻接点
193     }
194 }
195 void DFSTraverseM(ALGraph G,int term)
196 {
197     int i;
198     for (i = 0; i < G.vexnum; i++)
199         visited[i] = FALSE;
200     for (i = 0; i < G.vexnum; i++)
201         if (!visited[i])
202             DFS(G, i,term);
203 }
204 
205 void DFS2(ALGraph G, int i,char name[20])
206 {
207     //以vi为出发点对邻接表表示的图G进行深度优先搜索
208     ArcNode *p;
209     if(strcmp(G.vex[i].keming,name)==0)
210     {
211     cout<<"所在学期" <<endl; 
212     cout<<G.vex[i].xueqi<<endl;
213     }
214     
215      else // 访问顶点vi
216     {visited[i] = TRUE;              //标记vi已访问
217     p = G.vex[i].firstarc;        //取vi边表的头指针
218     while (p)
219     {                               //依次搜索vi的邻接点vj，这里j=p->adjvex
220         if (!visited[p->adjvex])    //若vi尚未被访问
221             DFS2(G, p->adjvex,name);      //则以Vj为出发点向纵深搜索
222         p = p->nextarc;                     //找vi的下一邻接点
223     }}
224 }
225 
226 
227 void DFSTraverseM2(ALGraph G,char name[20])
228 {
229     int i;
230     for (i = 0; i < G.vexnum; i++)
231         visited[i] = FALSE;
232     for (i = 0; i < G.vexnum; i++)
233         if (!visited[i])
234             DFS2(G, i,name);
235 }
236 
237 
238 int main(){
239     ALGraph G;
240     int term;
241     char name[20];
242     
243     CreateALGraph(G);//建立图    
244     cout<<"功能1：拓扑排序"<<"    "<<"功能2：查询学期课程"<<"    "<<"功能3：查看课程所属学期"<<"   "<<"功能4：退出"<<endl;
245     
246     int n;
247     n=1;
248     
249     while(n){
250     
251     cout<<"请输入1/2/3/4完成功能"<<endl; 
252     int i;
253     cin>>i;
254     switch(i){
255         case 1:TopologicalSort(G);
256         cout<<endl;//进行拓扑排序
257         break;
258         case 2:{
259             cout<<"请输入学期（1-7）"; 
260             cin>>term;
261             DFSTraverseM(G,term);
262             break;
263         }
264         case 3:{
265             cout<<"请输入课程名称：";
266              cin>>name;
267             DFSTraverseM2(G,name);
268      
269             break;
270         }
271         case 4:{
272             n=0;
273             break;
274         } 
275     } 
276 }
277     
278     
279     
280 
281     return 0;
282 }