学生选课系统
大学里实行学分制。每门课都有一定的学
分
。每个学生均需要修满规定数量的课程才能毕业。其中有些课程可以直接修读，有些课程需要一定的基础知识，必须在选了其他一些课程的基础上才能修读。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的“先修课”。在我们的大学里，假定每门课的直接先修课至多只有一门，两门课可能存在相同的先修课。例如：
|
课号
|
先修课号
|
学分
|
|
1
|
0
|
1
|
|
2
|
1
|
1
|
|
3
|
2
|
3
|
|
4
|
0
|
3
|
|
5
|
2
|
4
|
上例中，1是2的先修课，即如果要选修2，则1必定被选。
学生不可能学完大学里开设的所有课程，因此每个学生必须在入学时选定自己要学的课程。每个学生可选课程的总数目是给定的。现在请你们小组编写一个“学生选课系统”，任意给定一种课程体系（总课程数，课程之间的修读先后制约关系，学生毕业要求修的课程数目），该系统能帮助学生找出一种选课方案，使得他能得到的学分最多，并且必须满足先修课程优先的原则
具体实现如下：
1.
将课程体系存放为课程体系文件
CourseHierarchy.txt
；
2.
将课程体系文件
CourseHierarchy.txt
转换左孩子右兄弟二叉树表示；
3.
在此基础上对二叉树进行先序、中序、后序遍历。
4. 给出最多学分选课方案。
将课程体系文件转换为二叉树
思想：从
CourseHierarchy.txt
头部开始扫描，第一个先修课为
0
（即没有先修课）的课程为整棵二叉树的根节点
i
。从
CourseHierarchy.txt
头部开始扫描，所有
i
的后续课程作为
i
的左子树；课程体系中，其他先修课为
0
的节点，及其后续课程构成
i
的右子树。第一个先修课为
i
的节点作为
i
的左子树的根节点
，从
CourseHierarchy.txt
头部开始扫描，其他以
i
为先修课的课程构成
的右子树。如此低归构造出课程体系二叉树。
步骤
1
：从文件
CourseHierarchy.txt
生成课程链表
Course_Slist
（参数表）。
步骤
2
：将指针
CousreSystem_root
指引的
课程链表递归转换为课程体系二叉树
步骤
3
：先序输出二叉树，以验证生成的二叉树是否正确
实现代码
tree_binary.cpp
// tree_binary.cpp : 定义控制台应用程序的入口点。
//
#pragma once
#include <iostream>
#include <tchar.h>
//#include<fstream>
//#include<iostream>
//#include<cstdlib>
#include"tree_binaryHF.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
char file_name[20]="CourseHierarchy.txt";
LinkList L;//链表的头指针
LinkList T;//树的根
cout<<"\t本程序的作用是从文件(文件内容可按需求改写)"<<endl
<<" 中读取信息，放到链表中，最后生成二叉树，"<<endl
<<" 然后先序中序，后续遍历二叉树."<<endl;
InitList(L);
cout<<"读出的文件内容:"<<endl;
OpenFile(L,file_name);
cout<<"生成链表后的结果:"<<endl;
PrintLinkLIst(L);
CreateBiTree(L,T,0);//生成二叉树
cout<<"先序遍历二叉树的结果:";
PreOrder(T);
cout<<endl<<"中序遍历二叉树的结果:";
InOrder(T);
cout<<endl<<"后序遍历二叉树的结果:";
BackOrder(T);
cout<<endl;
return 0;
}
tree_binaryHF.h
#include"cao.hpp"
//*************************************//
//打开文件，并读取里面的所有内容
Status OpenFile(LinkList&L,char file_name[])//由于这里需要把数据插入链表中
{
int CNum,CScore,PreScore;
ifstream in_stream;
in_stream.open(file_name);
if(in_stream.fail())//if the file is not opened successfully
{
cout<<"can't open the file of "<<file_name<<endl;
exit(0);
}
//i
cout<<"CNum"<<"\t"<<"PreScore"<<"\t"<<"CScore"<<endl;
while(in_stream>>CNum>>PreScore>>CScore)//读取三个数据(课程编码,学分,先修课)
{
cout<<CNum<<"\t"<<PreScore<<"\t"<<"\t"<<CScore<<endl; //放到节点中
LinkInsert(L,CNum,PreScore,CScore);//insert the node to the linklist L
}
in_stream.close();
return OK;
}
Status InitList(LinkList &L)
{
L= (LinkList)malloc(sizeof(LNode));
if(!L)
return ERROR;
L->lchild=NULL;
L->rchild=NULL;
L->CNumber=0;
L->CScore=0;
L->PreCourse=0;
return OK;
}
Status LinkInsert(LinkList &L,Status CNum,Status PreCourse,Status CScore)//把新得到的结点插入链表，从头结点处插入
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p)
return ERROR;
p->CNumber=CNum;
p->CScore=CScore;
p->PreCourse=PreCourse;
p->lchild=NULL;
p->rchild=L->rchild;
L->rchild=p;
return OK;
}
Status PrintLinkLIst(LinkList &L)//打印整个链表，右指针指向后继结点，左指针空
{
LinkList p;
p=L->rchild;
while(p)
{
cout<<p->CNumber<<"\t"<<p->PreCourse<<"\t"<<"\t"<<p->CScore<<endl;
p=p->rchild;
}
return OK;
}
Status CreateBiTree(LinkList &L,LinkList&T,Status c)
{
LinkList p;
//while(!EmptyLinkList(L))
//{
if(!(p=Serach(L,c)))
T=NULL;
else
{
T=p;//生成根节点
delet(L,c);//删除p结点
CreateBiTree(L,T->lchild,T->CNumber);//构造左子树
CreateBiTree(L,T->rchild,T->PreCourse);//构造右子树
}
//}
return OK;
}
LinkList Serach(LinkList &L,Status c)
{
LinkList head,next;
head=L;
next=head->rchild;
while(next&&(next->PreCourse!=c))
{
head=next;
next=next->rchild;
}
if(next==NULL)
return NULL;//没有找到
else//找到了
return next;
}
void delet(LinkList &L,Status c)
{
LinkList head,next;
head=L;
next=head->rchild;
while(next&&(next->PreCourse!=c))
{
head=next;
next=next->rchild;
}
head->rchild=next->rchild;
//free(next);
}
Status EmptyLinkList(LinkList L)
{
if(L->rchild=NULL)
return OK;
else
return ERROR;
}
//先序遍历的递归
void PreOrder(LinkList T)
{
if(T)
{
//访问结点
cout<<T->CNumber<<" ";
PreOrder(T->lchild); //遍历左子树
PreOrder(T->rchild); //遍历右子树
//cout<<endl;
}
}
//中序遍历的递归
void InOrder(LinkList T)
{
if(T)
{
InOrder(T->lchild); //遍历左子树
//访问结点
cout<<T->CNumber<<" ";
InOrder(T->rchild); //遍历右子树
}
}
//后序遍历的递归
void BackOrder(LinkList T)
{
if(T)
{
BackOrder(T->lchild); //遍历左子树
BackOrder(T->rchild); //遍历右子树
cout<<T->CNumber<<" ";
}
}
cao.hpp
#include<fstream>
#include<iostream>
#include<cstdlib>
using namespace std;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode
{
struct LNode *lchild;
struct LNode *rchild;
Status CNumber;
Status CScore;
Status PreCourse;
}LNode,*LinkList;
Status OpenFile(LinkList&L,char file_name[]);
//打开文件，并且插入节点
//*************************//
LinkInsert(LinkList &L,Status CNum,Status CScore,Status PreScore);
//insert the node to the linklist L
//*************************//
Status InitList(LinkList &L);//初始化链表
//****************************************//
Status PrintLinkList(LinkList &L);//输出链表
//********************************//
LinkList Serach(LinkList &L,Status c);//查找节点
//*********************************************//
void delet(LinkList&L,Status c);//删除节点
//*************************************//
Status EmptyLinkList(LinkList L);//检查链表是否为空（没用到）
//***********************************//
//先序遍历二叉树
void PreOrder(LinkList T);
//***********************************//
void InOrder(LinkList T);//中序遍历二叉树
//*****************************//
void BackOrder(LinkList T);//后续遍历二叉树
CourceSource.txt
1 2 2
2 0 1
3 0 4
4 2 1
5 7 1
6 7 6
7 2 2
运行结果
先序遍历二叉树：3 2 7 6 5 4 1
中序遍历二叉树：3 6 5 7 4 1 2
后序遍历二叉树：5 6 1 4 7 2 3
posted on 2006-10-29 14:57
matthew 阅读(1369)
评论(0) 编辑 收藏 所属分类:
数据结构与算法设计