xuefen.cpp

c开发的选课算法

#define OK 1;
#define ERROR -1;
#include<malloc.h>
#include<iostream>
#include<fstream>
using namespace std;
typedef struct node{
	float  _coursescore;//课程序号
    int  _courseserial;//课程学分
    int _precedencecourse;//先修课程序号
    struct node *_rchild;
	struct node *_lchild;
}node,*LinkList;
int initList(LinkList &L);//构造连表函数； 
int OpenFile(LinkList&L,char file_name[ ]);//文件的打开函数； 
bool emptyLinkList(LinkList L);//判断连表是否为空函数； 
int LinkInsert(LinkList &L,int CNum,int PreCourse,int CScore);//连表的插入函数； 
int PrintLinkLIst(LinkList &L);//打印整个链表，右指针指向后继结点，左指针空;
LinkList Serach(LinkList &L,int c);//查找连表中接点函数； 
int CreateBiTree(LinkList &L,LinkList&T,int c);//构造二叉树； 
void preorder(LinkList T);//递归前序遍历二叉树;
void inorder(LinkList T);//中序遍历的递归二叉树;
void lastcout(LinkList T);
void delet(LinkList &L,int c);//删除连表接点函数;
int main()
{
	char file_name[20]="学分.txt";
	LinkList L;//链表的头指针
	LinkList T;//树的根
	cout<<"*************学生选课系统**********"<<endl;
	initList(L);
	cout<<"读出的文件内容:"<<endl;
	OpenFile(L,file_name);
	cout<<"构成的链表的结果是（头节点插入法）:"<<endl; 
	cout<<"课程号"<<"  "<<"先修号"<<"  "<<"\t"<<"学分"<<endl;
	PrintLinkLIst(L);
    CreateBiTree(L,T,0);//生成二叉树
	cout<<"先序遍历二叉树的结果:";
	preorder(T);
	cout<<endl<<"中序遍历二叉树的结果:";
	inorder(T);
    cout<<endl<<"后序遍历二叉树的结果:";
	lastcout(T);
    cout<<endl;
	return 0;
}
int 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);
	}
	cout<<"课程号"<<"\t"<<"先修课程号"<<"\t"<<"课程学分"<<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;
}//文件读取
int initList(LinkList &L)//创建一个链表；
{   L= (LinkList)malloc(sizeof(node));
	if(!L)
	return ERROR;
	L->_lchild=NULL;
	L->_rchild=NULL;
	L->_courseserial=0;
	L->_coursescore=0;
	L->_precedencecourse=0;
	return OK;
} 
bool emptyLinkList(LinkList L)//判断链表是否为空
{
	if(L->_rchild=NULL)
		return true;
	else
		return false;
}
void delet(LinkList &L,int c)//删除连表接点函数；
{
	LinkList head,next;
	head=L;
	next=head->_rchild;
	while(next&&(next->_precedencecourse!=c))
	{
		head=next;
		next=next->_rchild;
	}
	head->_rchild=next->_rchild;
} 
int LinkInsert(LinkList &L,int CNum,int PreCourse,int CScore)
//把新得到的结点插入链表，从头结点处插入
{
	LinkList p;
	p=(LinkList)malloc(sizeof(node));
	if(!p)
		return ERROR;
	p->_courseserial=CNum;
	p->_coursescore=CScore;
	p->_precedencecourse=PreCourse;
	p->_lchild=NULL;
	p->_rchild=L->_rchild;
	L->_rchild=p;
	return OK;
}//元素插入到链表中
int PrintLinkLIst(LinkList &L)//打印整个链表，右指针指向后继结点，左指针空
{
	LinkList p;
	p=L->_rchild;//右指针指向链表的后继元素
	while(p)
	{
		cout<<p->_courseserial<<"\t"<<p->_precedencecourse<<"\t"<<"\t"<<p->_coursescore<<endl;
		p=p->_rchild;
	}
	return OK;
}//打印链表
LinkList Serach(LinkList &L,int c)
{//第一次寻找PreCourse值为0的结点
	LinkList head,next;
	head=L;
	next=head->_rchild;
	while(next&&(next->_precedencecourse!=c))
	{
		head=next;
		next=next->_rchild;
	}
	if(next==NULL)
		return NULL;//没有找到
	else//找到了
		return next;//返回第一个PreCourse值为c的结点
}//查找节点
int CreateBiTree(LinkList &L,LinkList&T,int c)
{
	LinkList p;
	if(!(p=Serach(L,c)))
		T=NULL;
	else
	{
		T=p;   //用Serach(L,c)返回的结点生成根节点
		delet(L,c);//删除p结点
		CreateBiTree(L,T->_lchild,T->_courseserial);
		//找出以当前结点的序号为先修关系的结点，构造左子树。第一次为空
		CreateBiTree(L,T->_rchild,T->_precedencecourse);
		//找出以当前结点的PreCourse值为先修关系的结点，构造右子树。也就是当前结点的兄弟结点　　　　　　　　　　　　　　　　　　　　
	}
	return OK;
}//构造一棵二叉树； 
void preorder(LinkList T)//递归前序遍历二叉树  
{
  if(T==NULL) return;
  else{
  	 cout<<T->_courseserial<<"  ";
	 preorder(T->_lchild);
     preorder(T->_rchild);
  }
}
void inorder(LinkList T)//中序遍历的递归
{
  if(T)
 {
  inorder(T->_lchild);//遍历左子树
   //访问结点
  cout<<T->_courseserial<<"  ";
  inorder(T->_rchild);//遍历右子树
 }
}

void lastcout(LinkList T)//后序遍历的递归
{
  if(T==NULL) return;
  else
 {
  lastcout(T->_lchild);//遍历左子树
 
lastcout(T->_rchild);  //遍历右子树
  cout<<T->_courseserial<<"  ";  //访问结点

 }
}