求高手看一下，看似很简单，但是要想简单实现还是有点难度！
/*
问题：
简单火车售票系统
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++一级试题，简单火车订票问题，数据结构！