高手请进!一个难题求算法!真的很难!
题目:有一新闻报刊系统数据库,如下图所示:
报刊1 报刊2 报刊3 …… 报刊n
| | | |
事件1 …… 事件n …… 事件m …… 事件t ……
报刊1,报刊2等分别是不同的报刊,如人民日报,参考消息,环球日报等。
事件1,事件n等分别是在不同的报刊中的报道的事件。
其中所有的报刊(每个报刊都包含若干事件)是存在一个链表中的,结构如下:
Typedef struct _ST_NEWSPAPERS
{
Unsigned int uiNewsPaperID;/*报刊号,从1到n*/
ST_EVENT *pstEventHead;/*该指针指向本报刊中的第一个事件。*/
struct _ST_NEWSPAPERS *pstNextNewPaper;/*指向下一个报刊*/
} ST_NEWSPAPERS;
所有的事件是存在一个数组中的(同一报刊的事件一定是存在一起的,如上图中,报刊1中报道的事件不可能出现在“事件n”及以后的位置上;并且同一报刊内的事件是按照时间从小到大排好序的),每个事件的结构如下:
Typedef struct _ST_EVENT
{
Unsigned int uiEventID;/*事件编号*/
Unsigned int uiTtime;/*事件发生的时间*/
Unsigned char ucEventClass;/*事件的类别,如财经,政治,汽车,时尚等*/
} ST_EVENT;
问题来了:
要求编写一个查询函数,函数的接口如下:
Unsigned int QuaryEvent(unsigned char ucEventClass, unsigned int uiStartTime,
Unsigned int uiGetMaxEventNum, unsigned int * puiEventID);
函数说明:
该函数中ucEventClass的所要查询的事件类别,uiStartTime是所要查询的事件的开始时间(获取到的事件发生的时间必须大于等于此时间),uiGetMaxEventNum是一次获取的事件最大个数,puiEventID是由外部传进来的一个数组的指针,由该函数内部将查询到的事件的事件号(uiEventID)存到该指针指向的空间中。
返回值是实际查询到的事件个数
查询要求:
(1) 要求puiEventID中存的事件必须按照时间从小到大的顺序排列好,如果碰到时间相同的事件,必须按照该事件所属报刊的报刊号从小到大排列好。举个例子:
现在要求查询“财经”这个类别,发生在8点之后的新闻事件。在报刊系统数据库中,报刊1中的有一个财经新闻事件在8点半(假设为事件1),报刊2中有一个财经新闻事件在8点20(假设为事件2),报刊3中有一个财经新闻事件在8点半(假设为事件3)。
那么最后的排序结果应该是:事件2,事件1,事件3。
(2) 要求查询具有延续性。举例说明:
现在要求查询“财经”这个类别,发生在8点之后的新闻事件。在报刊系统数据库中,报刊1中的有一个财经新闻事件在8点半(假设为事件1),报刊2中有一个财经新闻事件在8点20(假设为事件2),报刊3中有一个财经新闻事件在8点半(假设为事件3),还有另一个财经新闻发生在9点(事件4)。报刊4中有一个财经新闻发生在8点50(事件5)
第一次调用QuaryEvent查询时,uiGetMaxEventNum(最大事件个数)为3,第二次调用QuaryEvent查询时,uiGetMaxEventNum也为3
那么第一次的查询结果应该是:事件2,事件1,事件3。函数的返回值为3
第二次的查询结果应该是:事件5,事件4。函数的返回值为2
这个题目,我已经想了一两天了,都没有好的办法,请各位聪明的高手指教一下,提供一下思路。当然如果有相应的参考代码就更好了,呵呵。
[ 本帖最后由 liqingyulipeng 于 2010-4-14 01:23 编辑 ]