西西软件园多重安全检测下载网站、值得信赖的软件下载站!
软件
软件
文章
搜索

首页编程开发其它知识 → 数组作链表 数组作链表有哪些优点?

数组作链表 数组作链表有哪些优点?

相关软件相关文章发表评论 来源:本站整理时间:2010/8/22 9:39:07字体大小:A-A+

作者:佚名点击:347次评论:0次标签: 数组 链表

  • 类型:文本编辑大小:978KB语言:中文 评分:6.6
  • 标签:
立即下载

一般传统链表的物理结构,是由指针把一个一个的节点相互连接而成:

view sourceprint?1 struct node

2 {

3 DataType data;

4 node* previous;

5 node* next;

6 }

其特点是按需分配节点,灵活动态增长。

但是此外,还有另外一种方式是使用数组实现链表,这里所有的node都在预先分配好的数组中,不使用指针,而是用数组下标来指向前一个、下一个元素:

view sourceprint?1 struct node

2 {

3 DataType data;

4 int previous;

5 int next;

6 }

其特点是预先分配节点,并且如果需要链表长度随需增加,需要reallocation ,和vector类似。

 


下面就我自己的一些了解,谈一下其优缺点与应用。

数组作链表有哪些优点
能要省些内存吗?不见得;速度要快吗?没看出来,那么为什么要使用这种不那么直观的方式来实现链表呢?
数组的内存布局比较紧凑,能占些局部性原理的光 在不提供指针的语言中实现链表结构,如vb等 进程间通信,使用index比使用指针是要靠谱 - 一个进程中的指针地址在另外一个进程中是没有意义的 对一些内存奇缺应用,当其值类型为整型,且值域与数组index相符时,可以将next指针与data复用,从而节省一些内存
实现与应用
Id allocator
这里第一个例子针对上面第四点展开,其主要的应用在于ID的分配与回收,比如数据库表中的每条记录都需要一个unique id,当你增增减减若干次之后,然后新建一个表项,你该分配给它哪个id呢?
维持一个id,每增加一行就加1,删行不回收id --- 这样id会无限增加,太浪费了 每次分配都遍历一遍,找到最小的那个还没被用过的id --- 这样太浪费时间了
一个比较合理的做法是维护一个“可用ID”的链表,每次增加就从链表中拿一个,每次删除就把被删的ID链接到链表中,但是,对于传统链表结构而言,其节点的定义类似于:
view sourceprint?1 struct idnode

2 {

3 int availableID;

4 idnode* next;

5 };

这里,因为链表的值的类型与值域都与数组的index相符,我们可以复用其值和next,从而只需一个int数组,而不是一个idnode数组,数组中某个元素的值代表的即是链表节点的值,也是链表的下一个节点下标。下面是一个idallocator的实现,主要提供allocate和free两个函数用来满足上述要求:
view sourceprint?01 const static char LIST_END = -1;

02 template < typename integer>

03 class idallocator

04 {

05 public:

06 idallocator(int _num): num(_num)

07 {

08 array = new integer[num];

09 // Initialize the linked list. Initially, it is a full linked list with all elements linked one after another.

10 head = 0;

11 for (integer i = 0; i < num; i++)

12 {

13 array[i] = i + 1;

14 }

15 array[num-1] = LIST_END;

16 count = num;

17 }

18 ~idallocator()

19 {

20 delete [] array;

21 }

22 integer allocate() // pop_front, remove a node from the front

23 {

24 int id = head;

25 if(id != LIST_END)

26 {

27 head = array[head];

28 count--;

29 }

30 return id;

31 }

32 // push_front, add a new node to the front

33 void free(const integer& id)

34 {

35 array[id] = head;

36 count++;

37 head = id;

38 }

39 // push_front, add a new node to the front

40 bool free_s(const integer& id)

41 {

42 // make sure this id is not in the list before we add it

43 if(exist(id)) return false;

44 free(id);

45 return true;

46 }

47 size_t size()

48 {

49 return count;

50 }

51 private:

52 bool exist(const integer& id)

53 {

54 int i = head;

55 while (i != LIST_END)

56 {

57 if(i == id) return true;

58 i = array[i];

59 }

60 return false;

61 }

62 private:

63 integer* array;

64 int num;// totall number of the array

65 int count;// number in the linked list

66 int head;// index of the head of the linked list

67 };

Double linked list
用数组实现链表,大多数情况下,是与传统链表类似的,无非是在添加、删除节点后,调整previous,next域的指向。但是有一点,当我在添加一个新的节点时,如何从数组中拿到一个还未被使用过的节点呢?这里有两种方法:

如果你看懂了上面的id allocator,你也许已经意识到,使用上面那个idallocator类就可以简单的实现这个需求 另外一种方法,其实原理上也类似,就是在这个double linked list类中维护两个链表,一个是已使用的,一个是未使用的
第一种因为借助于一个工具类,实现看起来会简洁很多,但是idallocator会消耗额外的内存,因此第二种方法相对来讲会比较好。

    相关评论

    阅读本文后您有什么感想? 已有人给出评价!

    • 8 喜欢喜欢
    • 3 顶
    • 1 难过难过
    • 5 囧
    • 3 围观围观
    • 2 无聊无聊

    热门评论

    最新评论

    发表评论 查看所有评论(0)

    昵称:
    表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
    字数: 0/500 (您的评论需要经过审核才能显示)