那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

另类的链表数据结构以及算法

一般情况下,我们使用链表无非就是在链表结点中保存该链表中下一个元素的指针.如果为了删除方便,可能需要保存前一个元素的指针,也就是双向链表,这样在删除一个结点的时候就可以很快的定位到前面和后面的结点,并且改变它们相应的指向.在这些操作里面,指向链表元素的指针无疑是最关键的数据.

考虑这样一个问题,如果两个进程进行通信,A进程负责管理链表,B进程向A进程发出分配或者删除链表元素的请求.这种情况下,像上面所描述的那样A进程直接向B进程返回链表元素的指针是不能做到的了,很自然的,可以想到返回另一个key标示该链表元素.但是,当需要查找或者删除该链表元素的时候,就不能像上面那样马上定位到链表元素的位置了,需要遍历整个链表.原来常量级时间复杂度的算法,在使用情形变换了之后变成了O(n)级别的复杂度.

可以找到别的办法来解决这个问题.第一可以返回一个key标示该链表元素,第二保证了时间的复杂度,在这里需要定义一种新的数据结构和算法来解决这个问题.

首先,我们使用一个数组,数组中的元素是指向链表元素的指针,而指针的索引则是每个链表元素的id,这样,通过id就可以马上定位到对应的链表元素.
但是这里又会出现另一个问题,该id是从零开始的,假如在一段时间之后,需要分配一个新的链表元素,如何知道数组中的哪个位置是可以分配的?在这里,使用了一个整型数据的数组,数组中的每个元素是该id对应的链表元素在链表中下一个结点的id(有点拗口).我们使用两个链表头,一个将已经使用的链表元素id连接起来,另一个则将未使用的链表元素id连接起来.于是,在程序初始化的时候,未使用的链表中保存了所有的id,而已经使用的链表为空.每次分配了一个新的链表元素,将它的id放在使用链表的最开始;而每次释放一个链表元素,将它的id放到未使用的链表头部.
同时,改变原先链表元素的定义,在该结构体中,保存的不再是指针,而是链表中前一个元素的数组索引id.而它的下一个元素id则保存在上面的那个数组中.

如果上面我的解释还不够明白,可以看看下面的代码:

#include 
<stdio.h>

#define LIST_NODE_NULL -1
#define ARRAY_SIZE 200

/* 链表元素定义 */
typedef 
struct list_node
{
    
int prev;   /* 下一个链表元素在list_array中的id */
}list_node;

/* 存放链表元素指针的数组 */
list_node
* list_array[ARRAY_SIZE];
/* 未使用链表的头结点id */
int top_of_free;
/* 已使用链表的头结点id */
int top_of_used;
/* 保存链表下一个元素结点id的链表 */
int next_list[ARRAY_SIZE];

void init_list()
{
    
int i;

    
for (i = 0; i < ARRAY_SIZE; ++i)
    {
        list_array[i] 
= NULL;
        
/* 初始时,next_list中每个结点的值都是下一个id */
        next_list[i] 
= i + 1;
    }

    
/* 最后一个结点是空 */
    next_list[i 
- 1= LIST_NODE_NULL;

    top_of_free 
= 0;
    top_of_used 
= LIST_NODE_NULL;
}

int alloc_list_node()
{
    
int id;
    
    
/* 从未使用链表头部取出一个id */
    id 
= top_of_free;

    
if (LIST_NODE_NULL == id)
    {
        
return LIST_NODE_NULL;
    }

    
/* 未使用链表头结点往下走一步 */
    top_of_free 
= next_list[top_of_free];

    
if (NULL == list_array[id])
    {
        list_array[id] 
= (list_node*)malloc(sizeof(list_node));
        
if (NULL == list_array[id])
        {
            
return LIST_NODE_NULL;
        }
    }

    
if (LIST_NODE_NULL == top_of_used)
    {
       
next_list[id] = top_of_used; 
        top_of_used = id;

    }
    
else
    {
        
/* 修改prev和next */ 
        list_array[top_of_used]
->prev = id;
        list_array[id]
->prev = LIST_NODE_NULL;

        next_list[id] 
= top_of_used;
        top_of_used 
= id;
    }

    
return id;
}

void free_list_node(int id)
{
    
int prev, next;

    prev 
= list_array[id]->prev;
    next 
= next_list[id];

    
/* 修改next和prev */
    if (
LIST_NODE_NULL != prev)
    {
        next_list[prev] 
= next_list[id];
    }
    
if (LIST_NODE_NULL != next && NULL != list_array[next])
    {
        list_array[next]
->prev = prev;
    }

    
if (id == top_of_used)
    {
        top_of_used 
= next_list[id];
    }

    
/* 将链表id返回到free链表头部并且修改free链表头结点 */
    next_list[id] 
= top_of_free;
    top_of_free 
= id;
}

int main()
{
    
int id;

    init_list();

    id 
= alloc_list_node();
    free_list_node(id);

    
return 0;
}



这个想法很巧妙,有效的避免了查找和删除数组元素带来的开销.我不知道具体的出处在哪里,如果您知道,劳烦告诉我一声:)


posted on 2009-03-22 19:14 那谁 阅读(4375) 评论(7)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 另类的链表数据结构以及算法  回复  更多评论   

如果我没理解错误的话:
1 这个应该是静态链表的变形。
2 示例程序似乎有些地方有问题.
(1)分配算法里边的:
if (LIST_NODE_NULL == top_of_used)
{
top_of_used = id;
}
是否应该改为:
if (LIST_NODE_NULL == top_of_used)
{
next_list[id] = top_of_used;
top_of_used = id;

}
(2)释放函数:
next_list[prev] = next_list[next_list[id]];
if (NULL != list_array[next])
{
list_array[next]->prev = prev;
}
next_list[prev]和list_array[next]都有可能造成数组越界。

另外,这个next_list[prev] = next_list[next_list[id]];是否应该改为
next_list[prev] = next_list[id]?
2009-03-27 13:31 | capable

# re: 另类的链表数据结构以及算法  回复  更多评论   

感谢指出错误,已经做了修改了.
2009-03-27 19:03 | 那谁

# re: 另类的链表数据结构以及算法  回复  更多评论   

别客气,应该的。
从你的博客,我学到了不少东西,希望能够在这里看到更多你的大作。
2009-03-27 22:14 | capable

# re: 另类的链表数据结构以及算法  回复  更多评论   

为什么不直接使用链表节点指针作为key呢?
2009-03-28 15:22 | t

# re: 另類的鏈表數據結構以及算法  回复  更多评论   

应该是 Justin Heyes-Jones 在 A* Algorithm code 中的 fast simple allocator 使用的结构
http://code.google.com/p/a-star-algorithm-implementation/downloads/list
2009-04-11 01:48 | alan5281

# re: 另类的链表数据结构以及算法  回复  更多评论   

申请新结点空间后,应该初始化结点,否则释放时会出现问题。
list_array[identity] = new list_node;
if(NULL == list_array[identity])
{
return(list_node_null);
}
list_array[identity]->prev = list_node_null;
2009-06-03 08:59 | zuima

# re: 另类的链表数据结构以及算法  回复  更多评论   

算法导论10.3介绍了这种用法,包括后面提到的用两个链表来维护用过的和为用过的节点
2010-08-22 02:00 | Dbger

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理