delphi.数据结构.链表

来源:互联网 时间:1970-01-01

链表作为一种基础的数据结构,用途甚广,估计大家都用过。
链表有几种,常用的是:单链表及双链表,还有N链表,本文着重单/双链表,至于N链表。。。不经常用,没法说出一二三来。

在D里面,可能会用Contnrs.pas.TStack/TQueue相关类,进行操作,不过里面的实现,并非使用的是链表实现,只是用TList,然后。。。实现的。

呵,TList怎么实现那些不是重点,本文着重是说一下自己使用链表的一些心得。 

 

一:单链表: 

单链表的用途,主要一个场景:队列(stack/queue),两者区别在于:queue: 先进先出(fifo), stack:后进先出(lifo)

在单链表操作中,我的建议是:只做:进队(push), 出队(pop) 操作,不做delete操作,原因就一个:

删除需要循环,如果需要删除操作,请使用双链表的实现。

我不建议使用删除操作,所以,就不贴出delete代码了。

(个人理解:在不同场景,选择更合适的数据结构来处理,我是理解是不用这操作,所以就不说明。)

      下面给出一个基础的,简单的单链表操作:

 1 type

2 PSingleEntry = ^TSingleEntry;

3 TSingleEntry = record

4 next: PSingleEntry;

5 data: Pointer;

6 end;

7

8 //

9 // 定义单链表队列:

10 // 1: head: 第一个结点;

11 // 2: tail: 最后一个结点(为fifo准备)

12 PSingleLink = ^TSingleLink;

13 TSingleLink = record

14 head, tail: PSingleEntry;

15 end;

16

17 // 初始化

18 procedure slink_init(var link: TSingleLink);

19 begin

20 link.head := nil;

21 link.tail := nil;

22 end;

23

24 // 反初始化,或清空代码也类似,请自行写single_clear

25 procedure slink_uninit(var link: TSingleLink);

26 var

27 entry, next_entry: PSingleEntry;

28 begin

29 entry := link.head;

30 while entry <> nil do

31 begin

32 next_entry := entry.next;

33 FreeMem(entry);

34 entry := next_entry;

35 end;

36 link.head := nil;

37 link.tail := nil;

38 end;

39

40 // 出队操作: result = false,表示无数据,否则出队成功,且data值正确

41 function slink_pop(link: PSingleLink; var data: Pointer): Boolean;

42 var

43 entry: PSingleEntry;

44 begin

45 result := link.head <> nil;

46 if result then

47 begin

48 entry := link.head;

49 data := entry.data;

50 link.head := entry.next;

51 FreeMem(entry);

52 end;

53 end;

54

55 // fifo入队:

56 procedure slink_push_fifo(link: PSingleLink; data: Pointer);

57 var

58 entry: PSingleEntry;

59 begin

60 GetMem(entry, sizeof(entry^));

61

62 entry.next := nil;

63 entry.data := data;

64 if link.head <> nil then

65 link.tail.next := entry

66 else

67 link.head := entry;

68 link.tail := entry;

69 end;

70

71 // lifo入队:

72 procedure slink_push_lifo(link: PSingleLink; data: Pointer);

73 var

74 entry: PSingleEntry;

75 begin

76 GetMem(entry, sizeof(entry^));

77

78 entry.data := data;

79 entry.next := link.head;

80 link.head := entry;

81 end;

上面,只是一个简单的示例。不过,上面的基本操作,基本不会有变动,欢迎各位提出更简化的版本。

一般说来,上面的示例已经足够使用了。

不过,有些场景,需要更多的减少GetMem/FreeMem的使用,所以,会将这种操作,集成在所需要的对象中,如上例中的data: Pointer,它可能是TObject,又或是某数据类型的指针。。。不可避免的是它需要GetMem+FreeMem,所以,有时单链表的处理,又会如下:

 1 type

2 PMyDataEntry = ^TMyDataEntry;

3 PMyDataEntry = record

4 next: PSingleEntry;

5

6 field1: Integer;

7 field2: string;

8 timestamp: Cardinal;

9 ...

10 end;

使用PMyDataEntry, 即自己所需要的数据类型,也可以是TMyObject = class,形式不重要,重要的是上面的push&pop方法。

估计写完PMyDataEntry,用了后,又会发现,如果我有N多这类需要,MyDataEntry1, MyDataEntry2....

如果这种写法,那不得写N次,就不能弄个通用型的法子?

回答是:可以的。

在指针应用篇中,曾提到过偏移的作法,在push&pop中,根据data: Pointer(不管是pop&push),都进行指针偏移,然后得到PDataEntry类型指针,然后,再进行pop&push操作。

当时,这种法子在data.create时,必须得先申请sizeof(TDataEntry) + sizeof(data)长度,再偏移sizeof(TDataEntry),释放时反操作。

是不是有点麻烦?是的,麻烦到死,不过写一次,全部通用,还是值的花时间的。

不过,单链表的这种方式不写了,因为下面的双链表方式,得用这法子写,所以省略。

 

单链表大概如此,其它附加操作,如线程保护,自行解决吧。建议是直接在push&pop内部代码处理,而不是在外面(减少锁定的代码行操作)。

个人友情提示:单链表只用在队列,只有push&pop的操作的场景,而不是有delete或循环操作的场合。

 

二:双链表。

上面的单链表,没有删除delete操作,因为,是发现在实际使用过程中,如果带有循环操作,一般都会慢。

慢的原因当然是数量多,所以慢。也许,看者可能会说:我这边的场合,就不可能有大量数据的可能,写个循环多简单。不过我真心建议不使用,因为写通用型算法的时候,A场景不慢,也量少,不代表B场景,C场景,且测试期快,软件实际运行上线后,量的可能性不是刚开始开发时能考虑的。所以,在开发阶段,就尽量使用不会因为量大的情况下形成瓶颈的算法。这是一个习惯问题。要让我们的脑子,习惯于用更快,更优的的解决方法去解决问题的做法。

言归正传。还是队列,下面给出的是通用+集成型的双链表队列实现。 

 1 type

2 // 双链表每项定义,与单链表相比,多了prev指针

3 // 请注意:必须要用packet record,否则计算偏移会有误。

4 PDoubleEntry = ^TDoubleEntry;

5 TDoubleEntry = packed record

6 next, prev: PDoubleEntry;

7 data: array [0..0] of Byte;

8 end;

9

10 //

11 // 定义链表:

12 // head: 第一个结点

13 // tail: 最后一个结点(为fifo准备)

14 //

15 PDoubleLink = ^TDoubleLink;

16 TDoubleLink = record

17 head, tail: PDoubleEntry;

18 end;

19

20 const

21 // 双链表结点的偏移字节数

22 DLINK_OFFSET_SIZE = sizeof(TDoubleEntry) - 1;

23

24 // 初始化

25 procedure dlink_init(var link: TDoubleLink);

26 begin

27 link.head := nil;

28 link.tail := nil;

29 end;

30

31 // 反初始化,或清空代码也类似,请自行编写dlink_clear

32 procedure dlink_uninit(var link: TDoubleLink);

33 var

34 entry, next_entry: PDoubleEntry;

35 begin

36 entry := link.head;

37 while entry <> nil do

38 begin

39 next_entry := entry.next;

40 FreeMem(entry);

41 entry := next_entry;

42 end;

43 link.head := nil;

44 link.tail := nil;

45 end;

46

47 function dlink_entry_alloc(size: Integer): Pointer;

48 var

49 entry: PDoubleEntry;

50 begin

51 entry := AllocMem(DLINK_OFFSET_SIZE + size);

52 result := @entry.data[0];

53 end;

54

55 procedure dlink_entry_free(data: Pointer);

56 begin

57 FreeMem(PAnsiChar(data) - DLINK_OFFSET_SIZE);

58 end;

59

60 // 出队操作: result = false,表示无数据,否则出队成功,且data值正确

61 function dlink_pop(link: PDoubleLink; var data: Pointer): Boolean;

62 var

63 entry: PDoubleEntry;

64 begin

65 result := link.head <> nil;

66 if result then

67 begin

68 entry := link.head;

69 data := @entry.data[0];

70 link.head := entry.next;

71 end;

72 end;

73

74 // fifo入队

75 procedure dlink_push_fifo(link: PDoubleLink; data: Pointer);

76 var

77 entry: PDoubleEntry;

78 begin

79 entry := Pointer(PAnsiChar(data) - DLINK_OFFSET_SIZE);

80 entry.next := nil;

81 if link.head <> nil then

82 begin

83 link.tail.next := entry;

84 entry.prev := link.tail;

85 end else

86 begin

87 link.head := entry;

88 entry.prev := nil;

89 end;

90 link.tail := entry;

91 end;

92

93 // lifo入队:

94 procedure dlink_push_lifo(link: PDoubleLink; data: Pointer);

95 var

96 entry: PDoubleEntry;

97 begin

98 entry := Pointer(PAnsiChar(data) - DLINK_OFFSET_SIZE);

99 entry.next := link.head;

100 entry.prev := nil;

101 if link.head <> nil then

102 link.head.prev := entry;

103 link.head := entry;

104 end;

105

106

107 //

108 // 双链表.delete结点操作

109 // 标准几步操作,然后没了。

110 //

111 procedure dlink_delete(link: PDoubleLink; data: Pointer);

112 var

113 entry: PDoubleEntry;

114 begin

115 entry := Pointer(PAnsiChar(data) - DLINK_OFFSET_SIZE);

116 if entry.prev <> nil then

117 begin

118 entry.prev.next := entry.next;

119 if entry.next <> nil then

120 entry.next.prev := entry.prev;

121 end else

122 begin

123 link.head := entry.next;

124 if entry.next <> nil then

125 entry.next.prev := nil;

126 end;

127 FreeMem(entry);

128 end;

129

130

131 type

132 // 这是调用: 自定义数据类型,以上双链表,可以自定义数据类型,如下:

133 PMyTestRec = ^TMyTestRec;

134 TMyTestRec = record

135 v: Integer;

136 s: string;

137 end;

138

139 procedure TForm1.Button1Click(Sender: TObject);

140 var

141 i: Integer;

142 data, temp: PMyTestRec;

143 link: TDoubleLink;

144 pop_count, push_count, error_count: Integer;

145 begin

146 dlink_init(link);

147

148 // 测试1

149 pop_count := 0;

150 push_count := 0;

151 error_count := 0;

152

153 // 入队1

154 for i := 0 to 10 do

155 begin

156 data := dlink_entry_alloc(sizeof(TMyTestRec));

157 data.v := i;

158 data.s := IntToStr(i);

159 dlink_push_fifo(@link, data);

160 inc(push_count);

161 end;

162

163 // 出队1

164 while dlink_pop(@link, Pointer(data)) do

165 begin

166 inc(pop_count);

167 if data.v <> StrToIntDef(data.s, -1) then

168 inc(error_count);

169 dlink_entry_free(data);

170 end;

171 ShowMessageFmt('test1: push: %d, pop: %d, error: %d', [push_count, pop_count, error_count]);

172

173 // 测试2

174 pop_count := 0;

175 push_count := 0;

176 error_count := 0;

177 temp := nil;

178

179 // 入队2

180 for i := 0 to 10 do

181 begin

182 data := dlink_entry_alloc(sizeof(TMyTestRec));

183

184 // 从中间找个entry赋于temp,用于测试dlink_delete

185 if i = 5 then

186 temp := data;

187

188 data.v := i;

189 data.s := IntToStr(i);

190

191 dlink_push_lifo(@link, data);

192 inc(push_count);

193 end;

194

195 // 测试:删除中间的结点。

196 dlink_delete(@link, temp);

197

198

199 // 出队2

200 while dlink_pop(@link, Pointer(data)) do

201 begin

202 inc(pop_count);

203 if data.v <> StrToIntDef(data.s, -1) then

204 inc(error_count);

205 dlink_entry_free(data);

206 end;

207 ShowMessageFmt('test2: push: %d, pop: %d, error: %d', [push_count, pop_count, error_count]);

208

209 dlink_uninit(link);

210 end;

请看测试代码Button1Click,里面中的测试1是fifo,然后出队,测试2是lifo,将中间的某结点记录,进行删除中间某结点。

上述双链表队列,适合push&pop&delete操作,可独立运作,也可与其它数据结构一块进行,比如hash什么的。

与单链表不同的是,多了一个dlink_delete函数,因为双链表,所以删除就几行,不进行循环。

  

与单链表实现不同的是:它在通用的基础上,将结点的分配与释放集成在一块,而单链表那个实现,只是一个通用的情况,结点的分配与释放得另外处理,这点要注意,当然,你可以自己去写集成在一块的写法,这里只是一个举例。

 

双链表使用场合甚广,写成这种集成模式,不好阅读不说,且不知如何调用。

因为本人用的比较多这种模式,比如:

1:hash中,根据key找到一个entry,然后删除就调用dlink_delete,操作多快

2:更多的情况下,上面的示例,只是一个示例,我会更多的扩展它里的头信息,而不只是next,prev几个字段,

增删改查时,进行相应处理。dlink_delete只是一个示例。:)

目地,还是想给大家一个抛砖的作用。

没了。

水平有限,如有雷同,就是盗链,:D

2014.10.25 by qsl

 


相关阅读:
Top