athlete(正确).cpp

数据结构源程序

#include <stdio.h>
#include <string.h>

typedef char ElemType[10]; //项目数据类型定义

/*项目表结构定义*/
typedef struct List{
   ElemType *elem;
   int length;
}ItemList;

/*确定指定项目在项目表中的位置*/
int GetPos(ItemList &itemList,char *mItem)
{
	for(int i=0;i<itemList.length;i++)
		if(strcmp(mItem,itemList.elem[i])==0)
			return i;
	return 0;
}
/*初始化表*/
void InitList(ItemList &itemList,int iNum)
{
	itemList.elem = new ElemType[iNum];
	itemList.length = 0;
}

/*输入项目*/
int InsertList(ItemList &itemList,ElemType mItem)
{
    strcpy(itemList.elem[itemList.length++],mItem);
 
	return 1;
}

void DestroyList(ItemList &itemList)
{
	delete []itemList.elem;
	itemList.elem = NULL;
	itemList.length = 0;
}

/*链队列结构定义*/
typedef struct ListNode{
   ElemType elem;
   struct ListNode *pnext;
}LNode;
typedef struct LQueue{
LNode *front;
LNode *rear;
}LinkQueue;

typedef int status;

/*链队列函数声明*/
void   InitQueue(LinkQueue &lq);
status InQueue(LinkQueue &lq,ElemType elem);
status OutQueue(LinkQueue &lq,ElemType &elem);
int    Empty(const LinkQueue lq);
void   Destroy(LinkQueue &lq);

/*函数声明*/
void   SetschedTable(int *schedTable,int *fItem,int athNum);
void   AttendItem(int *fItem,int athNum);

void InitQueue(LinkQueue &lq)
{
	LNode *p;
	p = new LNode;
	p->pnext = NULL;

	lq.front = lq.rear = p;
	
}

status InQueue(LinkQueue &lq,ElemType elem)
{
	LNode *p;
	p = new LNode;

	if(!p) return 0;

	strcpy(p->elem,elem);
	p->pnext = NULL;

	lq.rear->pnext = p;
	lq.rear = p;
	
	return 1;
}

status OutQueue(LinkQueue &lq,ElemType &elem)
{
	if(lq.front == lq.rear)
		return 0;
	LNode *p = lq.front->pnext;
    strcpy(elem,p->elem);

	lq.front->pnext = p->pnext;
	
	if(p == lq.rear)
	{
		delete p;
		lq.rear = lq.front;
	}
	else
		delete p;
	return 1;
}

int Empty(const LinkQueue lq)
{
	if(lq.front == lq.rear)
		return 1;
	return 0;
}

void Destroy(LinkQueue &lq)
{
	LNode *p;
	
	while(lq.front->pnext)
	{
		p = lq.front->pnext;
		lq.front->pnext = p->pnext;
		delete p;
	}

	lq.front = lq.rear;
}

int GetQueueLen(LinkQueue q)
{
    LNode *p = q.front->pnext;
    int len=0;
    
    while(p)
	   len++,p = p->pnext;
	return len;
}

void SetschedTable(int *schedTable,int *fItem,int athNum,ItemList itemList)
{
	LinkQueue q;
    ElemType  *mTempList = new ElemType[itemList.length]; //临时存放已经入当前组的项目号
	ElemType elem1,elem2;
    int seqNum = 1;

	InitQueue(q);
    for(int i=0;i<itemList.length;i++)
		InQueue(q,itemList.elem[i]);

	while(!Empty(q))
	{
		int count = 0;

		OutQueue(q,elem1);
		if(!schedTable[GetPos(itemList,elem1)]) 
			schedTable[GetPos(itemList,elem1)] = seqNum;
		
		strcpy(mTempList[count++],elem1);
		int len = GetQueueLen(q);
        for(int k=0;k<len;k++)
		{
		    OutQueue(q,elem2);
		    for(i=0;i<athNum;i++)
			{
				for(int j=0;j<count;j++)
				{
					strcpy(elem1,mTempList[j]);
				  if(fItem[i*itemList.length+GetPos(itemList,elem2)]==1 
					       && fItem[i*itemList.length+GetPos(itemList,elem1)]==1)
				  {
				     InQueue(q,elem2);
				     break;
				  }
				}
				if(j<count) break;
			}
			if(i== athNum) 
				if(!schedTable[GetPos(itemList,elem2)]) 
				{
					schedTable[GetPos(itemList,elem2)] = seqNum;
					strcpy(mTempList[count++],elem2);
				}
		}
        seqNum++;
	}

}

void AttendItem(int *fItem,int athNum,ItemList itemList)
{	
	char *mName = new char[10];
	int itemNum;

	for(int i=0; i<athNum;i++)
	{
		printf("\n请输入第%d个运动员的参赛项目数:",i+1);
		scanf("%d",&itemNum);
		printf("请输入第%d个运动员的参赛项目名（空格隔开）:\n",i+1);
        for(int j=0;j<itemNum;j++)
		{
		    scanf("%s",mName);
			fItem[i*itemList.length+GetPos(itemList,mName)] = 1;
		}
	}

	//输出参赛关系表
	for(i=0;i<athNum;i++)
	{
		for(int j=0;j<itemList.length;j++)
			printf("%d ",fItem[i*itemList.length+j]);
		printf("\n");
	}
}

main()
{
	int      *fItem;       //指向冲突标志表
	int      *schedTable;  //赛事安排表
	int      athNum;       //运动员数
	ItemList itemList;     //项目表
    int      itemNum;      //项目数
	char     *mItem;       //项目名称

	mItem = new char[10];  

	printf("请输入项目数:\n");
	scanf("%d",&itemNum);
	InitList(itemList,itemNum);
	
	printf("请输入%d个项目名称(用空格隔开):\n",itemNum);
	for(int i=0;i<itemNum;i++)
	{
		scanf("%s",mItem);
		InsertList(itemList,mItem);
	}

	schedTable = new int[itemNum];       //赛事安排表初始化
	for(i=0;i<itemNum;i++)
		schedTable[i] = 0;

    printf("\n开始报名参赛!\n");         
	printf("请输入运员数\n");
	scanf("%d",&athNum);
	
	//参赛表初始化
	fItem = new int[itemNum*athNum];
	for(i=0;i<athNum;i++)
		for(int j=0;j<itemNum;j++)
			fItem[i*itemNum+j]=0;

	AttendItem(fItem,athNum,itemList);

	SetschedTable(schedTable,fItem,athNum,itemList);
    
	printf("\n");
	for(i=0;i<itemNum;i++)
		printf("%d ",schedTable[i]);

}