33,008
社区成员
发帖
与我相关
我的任务
分享有一个单向链表，如何检测该链表中存在环（若链表中下一个元素指向该元素或前面的元素则判断为存在环）？给出该算法时间复杂度和空间复杂度的说明。（可以写伪码）
帮忙答题啊，有分，谢谢！
1 、有一个单向链表，如何检测该链表中存在环（若链表中下一个元素指向该元素或前面的元素则判断为存在环）？给出该算法时间复杂度和空间复杂度的说明。（可以写伪码）
2、 设计一个多线程安全的内存池类pool，提供如下两个功能：
a) void *pool::malloc(unsigned size) 分配size大小的内存
b) void pool::free(void *p) 释放p指向的内存
要求给出思路、主要数据结构和算法，关键部分可用C/C++或伪代码辅助描述，并可结合图示。
3、 工程中的许多问题可抽象成矩阵相乘的模型，请设计实现方案，输入两个矩阵A、B，输出A*B。
1 、有一个单向链表，如何检测该链表中存在环（若链表中下一个元素指向该元素或前面的元素则判断为存在环）？给出该算法时间复杂度和空间复杂度的说明。（可以写伪码）
2、 设计一个多线程安全的内存池类pool，提供如下两个功能：
a) void *pool::malloc(unsigned size) 分配size大小的内存
b) void pool::free(void *p) 释放p指向的内存
要求给出思路、主要数据结构和算法，关键部分可用C/C++或伪代码辅助描述，并可结合图示。
3、 工程中的许多问题可抽象成矩阵相乘的模型，请设计实现方案，输入两个矩阵A、B，输出A*B。
...全文
请发表友善的回复…
发表回复
绿色夹克衫 2009-11-06
- 打赏
- 举报
快慢指针有人说了，简单说一下内存池吧！
可以使用块状链表来模拟，优点是释放简单，同一区块内没有碎片，做成双向的，
并且头有指向尾的指针，尾有指向头的指针，万一需要扩容，方便一点。
应该再包含一个读写锁，保证线程安全。
可以使用块状链表来模拟，优点是释放简单，同一区块内没有碎片，做成双向的，
并且头有指向尾的指针，尾有指向头的指针，万一需要扩容，方便一点。
应该再包含一个读写锁，保证线程安全。
gumbour 2009-11-05
- 打赏
- 举报
快慢指针
xshf12345 2009-11-05
- 打赏
- 举报
设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：
bool IsExitsLoop(slist * head)
{
slist * slow = head , * fast = head;
while ( fast && fast -> next )
{
slow = slow -> next;
fast = fast -> next -> next;
if ( slow == fast ) break ;
}
return ! (fast == NULL || fast -> next == NULL);
bool IsExitsLoop(slist * head)
{
slist * slow = head , * fast = head;
while ( fast && fast -> next )
{
slow = slow -> next;
fast = fast -> next -> next;
if ( slow == fast ) break ;
}
return ! (fast == NULL || fast -> next == NULL);
donckham 2009-11-05
- 打赏
- 举报
哈哈哈哈，百度笔试~~
