华为内部C/C++一级试题,简单火车订票问题,数据结构

C++语言 码拜 9年前 (2015-10-24) 1399次浏览
求高手看一下,看似很简单,但是要想简单实现还是有点难度!

/*
问题:
	简单火车售票系统
 	1. 一条单向的火车站点
	2. 每个节点表示为1,2,3,4…..依次增大,1为起始
	3. 初始时只有从站点1到末尾站点的车票若干张。
规则:
		例如:假如要买站点3~站点5 的车票
	规则1:
		(1)假如刚好有3~5的车票则售出,否则按照下面规则。
	规则2:
		(1)选择离3最近的有票的站点(包括<=3)
		(2)选择离5最近的有票的站点(包括>=5)
	规则3:
		(1)在满足规则2中选择一张车票拆分。
实例:
	假如有1,2,3,4,5,6这6个站点,且初始只有一张1到6的票,现在要买一张3~4的车票,根据规则,没有直接从3~4的票出售,离3最近且有票的只有1,离4最近且有票的只有6,则需要拆分这张1~6的车票,拆分成1~3,3~4,4~6,则3~4售出,且多了1~3和4~6各一张.
要求:
	使用C/C++,数据结构自定义,可以使用STL,至少实现以下函数接口(可以添加函数)
注意:
	为了简化,只有一条单向线路。
*/
/*1.  
	初始化函数
	StationNum :站点个数,2<=StationNum <=30,分别是从1…. StationNum 
	TicketCount :车票数,1<=TicketCount<=1000,初始时只有从起始站点1到末尾站点StationNum的车票
	成功返回0,失败返回-1
 */
 int SetOneTrainLine(int StationNum,unsigned int TicketCount)
 {
 }
/*2.
	出售车票函数
	SrcStationId为源站
	DestStationId为目标站
	成功返回0,失败返回-1(例如SrcStationId>=DestStationId则返回-1)
*/
int CellTickets(int SrcStationId, int DestStationId)
{
}
/*3. 
	查询车票数量
	SrcStationId为源站
	DestStationId为目标站
	包含大于指定查询区间的车票数。例如:1,2,3,4站,1~4有1张,2~3有1张,则查询2~3区间车票数量时就								返回2张。
	没有就返回0;
 */
 int FindLeft0,Tickets(int SrcStationId, int DestStationId)
{
}

@赵4老师 请教高手。!

解决方案:60分
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TICKET_NODES_ST
{
	int srcStationId;
	int endStationId;
	struct TICKET_NODES_ST *pNext;
}TICKET_NODES_T;
TICKET_NODES_T freeNodesHead = {0,0,NULL};
TICKET_NODES_T useNodesHead  = {0,0,NULL};
//create nodes
TICKET_NODES_T *createNode(int srcStationId,int endStationId)
{
	TICKET_NODES_T *pTickNode;
	pTickNode = (TICKET_NODES_T *)malloc(sizeof TICKET_NODES_T);
	assert(pTickNode != NULL);
	pTickNode->srcStationId = srcStationId;
	pTickNode->endStationId = endStationId;
	return pTickNode;
}
//append nodes
void appendNode(TICKET_NODES_T *nodesList,TICKET_NODES_T *pNode)
{
	while(nodesList->pNext != NULL) 
	{
		nodesList = nodesList->pNext;
	}
	pNode->pNext = NULL;
	nodesList->pNext = pNode;
}
//delete nodes
void deleteNodeByAddress(TICKET_NODES_T *nodesList,TICKET_NODES_T *pNode)
{
	while(nodesList != NULL)
	{
		if(nodesList->pNext != pNode)
		{
			nodesList = nodesList->pNext;
			continue;
		}
		nodesList->pNext = pNode->pNext;
		free(pNode);
		break;
	}
}
//get nodes score
int getNodeScore(TICKET_NODES_T *pNode,int srcStationId,int endStationId)
{
	if(pNode->srcStationId > srcStationId || pNode->endStationId < endStationId)
	{
		return -1;
	}
	return (srcStationId - pNode->srcStationId) + (pNode->endStationId - endStationId);
}
int querTickes(int srcStation,int endStation)
{
	int tickes;
	TICKET_NODES_T *pNodes = freeNodesHead.pNext;
	tickes = 0;
	while(pNodes != NULL)
	{
		if(getNodeScore(pNodes,srcStation,endStation) >= 0)
		{
			tickes++;
		}
		pNodes = pNodes->pNext;
	}
	return tickes;
}
int sellTickes(int srcStation,int endStation)
{
	int tmpScore;
	TICKET_NODES_T *pNodes,*pTmp,*pBefore,*pMid,*pEnd;
	tmpScore = 0x0FFFFFF;
	pNodes = freeNodesHead.pNext;
	while(pNodes != NULL)
	{
		int score = getNodeScore(pNodes,srcStation,endStation);
		if(score > 0 && score < tmpScore)
		{
			tmpScore = score;
			pTmp = pNodes;
		}
		pNodes = pNodes->pNext;
	}
	if(tmpScore == 0x0FFFFFF)
	{
		return -1;
	}
	//success
	pBefore = pMid = pEnd = NULL;
	if(pTmp->srcStationId < srcStation)
	{
		pBefore = createNode(pTmp->srcStationId,srcStation);
	}
	pMid = createNode(srcStation,endStation);
	if(endStation < pTmp->endStationId)
	{
		pEnd = createNode(endStation,pTmp->endStationId);
	}
	deleteNodeByAddress(&freeNodesHead,pTmp);
	if(NULL != pBefore)
	{
		appendNode(&freeNodesHead,pBefore);
	}
	appendNode(&useNodesHead,pMid);
	if(NULL != pEnd)
	{
		appendNode(&freeNodesHead,pEnd);
	}
	return 0;
}
int querySoldTicks(void)
{
	int num;
	TICKET_NODES_T *pNode = useNodesHead.pNext;;

	num = 0;
	while(pNode != NULL)
	{
		printf("srcId %d -->endId %d\n",pNode->srcStationId,pNode->endStationId);
		pNode = pNode->pNext;
	}
	return 0;
}
int initTickSystemParam(int stationNum,int ticksNum)
{
	int i;
	for(i = 0; i < ticksNum; i++)
	{
		appendNode(&freeNodesHead,createNode(1,stationNum));
	}
	return 0;
}
int main()
{
	int stationNum,ticksNum,userInputId;
	int startId,endId;
	printf("input how many stations:");
	scanf("%d",&stationNum);
	printf("input how many ticksNumber");
	scanf("%d",&ticksNum);
	if(stationNum < 2 || ticksNum< 1)
	{
		printf("param err\n");
		return 0;
	}
	initTickSystemParam(stationNum,ticksNum);
	while(1)
	{
		printf("=============================================\n");
		printf("1 Query Ticks by srcStationId and endStationId\n");
		printf("2 SellTickes by srcStationId and endStationId\n");
		printf("3 Query Ticks that has sold\n");
		printf("please entry:");
		scanf("%d",&userInputId); 
		printf("\n\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
		switch(userInputId)
		{
			case 1:
				printf("startId:");
				scanf("%d",&startId);
				printf("endId:");
				scanf("%d",&endId);
				if((ticksNum = querTickes(startId,endId)) < 0)
				{
					printf("on ticks \n");
				}
				else
				{
					printf("has %d ticks\n",ticksNum);
				}
				break;
			case 2:
				printf("startId:");
				scanf("%d",&startId);
				printf("endId:");
				scanf("%d",&endId);
				if(sellTickes(startId,endId) < 0)
				{
					printf("sell error no ticks\n");
				}
				else
				{
					printf("sell success\n");
				}
				break;
			case 3:
				querySoldTicks();
				break;
			defalut:
				break;
		}
		printf("\n\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
	}
}

稍微测试了下,可能还有问题,你看满足不


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明华为内部C/C++一级试题,简单火车订票问题,数据结构
喜欢 (0)
[1034331897@qq.com]
分享 (0)