delphi.数据协会.链表,delphi数据结构

链表作为意气风发种幼功的数据结构,用场甚广,估量我们都用过。

链表有二种,常用的是:单链表及双链表,还会有N链表,本文珍视单/双链表,至于N链表。。。不日常用,无法说出风流倜傥二三来。

 

在D里面,恐怕会用Contnrs.pas.TStack/TQueue相关类,举行操作,但是此中的兑现,并非使用的是链表完成,只是用TList,然后。。。实现的。

 

呵,TList怎么贯彻那个不是根本,本文注重是说一下团结行使链表的部分经历。 

 

 

 

一:单链表: 

 

  单链表的用项,主要多个情况:队列(stack/queue卡塔尔,两个分别在于:stack:
先进先出(fifo卡塔 尔(阿拉伯语:قطر‎, queue:后进先出(lifo卡塔 尔(英语:State of Qatar)

 

  在单链表操作中,小编的提出是:只做:进队(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,然后出队,测度是lifo,将中间的某结点记录,进行删除中间某结点。

 

  上述双链表队列,适合push&pop&delete操作,可单独运维,也可与任何数据结构一块实行,比方hash什么的。

 

  与单链表差异的是,多了八个dlink_delete函数,因为双链表,所以删除就几行,不进行巡回。

 

  

 

  与单链表实现分歧的是:它在通用的底子上,将结点的分红与释放集成在一齐,而单链表那么些完结,只是三个通用的状态,结点的分红与释放得别的管理,这点要注意,当然,你能够协和去写集成在一块的写法,这里只是一个例如。

 

 

 

  双链表使用项所甚广,写成这种购并格局,不好阅读不说,且不知怎么样调用。

 

  因为自己用的超级多这种格局,举个例子:

 

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

 

    2:越多的意况下,上面的演示,只是一个演示,作者会越多的扩大它里的头新闻,而不只是next,prev多少个字段,

 

      增加和删除改查时,进行相应管理。dlink_delete只是二个演示。:)

 

  目地,照旧想给我们一个抛砖的成效。

 

  

链表作为生机勃勃种根底的数据结构,用场甚广,估量我们都用过。
链表有二种,常用的是:单链表及双链表…

相关文章