技术CTO-关注编程入门知识,提供编程入门教程

您的位置: 首页 > 操作系统 > linux专区 > 正文

这样的消息队列如何出列?

来源: 技术CTO 阅读:


//以链表形式存储数据,容量有限
struct _linkTable
{
int ntype; //类型
char data[255]; //数据
struct _linkTable *pNext;
}TLinkTable;

//插入队列
int Push(TLinkTable stLinkTable )
{
//插入到队列尾
}

//返回队首第一个元素
int Pull()
{

}

//返回指定类型的第一个元素,失败返回0
int Pull(int ntype)
{
//如何快速找到并出列??
}


队列的顺序不能打乱。
或者有其它实现的方法?
楼主似乎没有理解不同数据结构的适用范围,链表这种数据结构,决定了查找一定是线性的,不可能更快。如果需要更快的查找,建议更换为哈希表
引用 1 楼 jiqiang01234 的回复:
楼主似乎没有理解不同数据结构的适用范围,链表这种数据结构,决定了查找一定是线性的,不可能更快。如果需要更快的查找,建议更换为哈希表


我这个功能是Linux的消息队列是一样的,只是考虑到跨平台不想用系统api
因为队列里面有很多消息,ntype是一样的。用哈希的话查找快一点点,入队比较麻烦。
可以用glib库,包含了常用的数据结构,而且跨平台。如果是c++就无所谓了,STL本身就跨平台
链表只能顺序查找,不用哈希的话可以采用数组来存,这样可以使用折半查找(前提是入队时要排序,如果不排序,也只能顺序查找)
另外,如果ntype不大的话,楼主可以考虑为每种类型建立一个映射表,映射表存放的是最近的一个元素对应的指针,要查找时,找这个映射表就好了,在入队的时候,更改这张表的相应元素,出队时麻烦些,要顺序查到最近的元素
如果出队比较多,可考虑出队时将对应元素置空,查到空元素时,再到整个链表进行顺序查找
引用 3 楼 jiqiang01234 的回复:
可以用glib库,包含了常用的数据结构,而且跨平台。如果是c++就无所谓了,STL本身就跨平台

这是另外一回事了,
我现在想的是怎么实现这个消息队列
引用 4 楼 r_Jimy 的回复:
链表只能顺序查找,不用哈希的话可以采用数组来存,这样可以使用折半查找(前提是入队时要排序,如果不排序,也只能顺序查找)
另外,如果ntype不大的话,楼主可以考虑为每种类型建立一个映射表,映射表存放的是最近的一个元素对应的指针,要查找时,找这个映射表就好了,在入队的时候,更改这张表的相应元素,出队时麻烦些,要顺序查到最近的元素
如果出队比较多,可考虑出队时将对应元素置空,查到空元素时,再到整个链表进行顺序查找


意思就是用ntype作为数组下标定位元素,如果有多个ntype重复的话,再用链表连接起来呗。
ntype大不大这个固定不了,也不可能是连续的。有可能是:1,2,3,5000。

总体上是用HASH然后解决冲突用链表了?

^_^ 如果您热爱技术、热爱编程,想与更多的朋友一起交流学习,欢迎加入本站官方QQ群:345733473 ^_^