delphi.数据结构.链表

页面导航:首页 > 软件编程 > Delphi > delphi.数据结构.链表

delphi.数据结构.链表

来源: 作者: 时间:2016-01-15 15:17 【

链表作为一种基础的数据结构,用途甚广,估计大家都用过。链表有几种,常用的是:单链表及双链表,还有N链表,本文着重单 双链表,至于N链表。。。不经常用,没法说出一二三来
链表作为一种基础的数据结构,用途甚广,估计大家都用过。
链表有几种,常用的是:单链表及双链表,还有N链表,本文着重单/双链表,至于N链表。。。不经常用,没法说出一二三来。
 
在D里面,可能会用Contnrs.pas.TStack/TQueue相关类,进行操作,不过里面的实现,并非使用的是链表实现,只是用TList,然后。。。实现的。
 
呵,TList怎么实现那些不是重点,本文着重是说一下自己使用链表的一些心得。 
 
 
 
一:单链表: 
 
  单链表的用途,主要一个场景:队列(stack/queue),两者区别在于:stack: 先进先出(fifo), queue:后进先出(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,然后出队,测度是lifo,将中间的某结点记录,进行删除中间某结点。
 
  上述双链表队列,适合push&pop&delete操作,可独立运作,也可与其它数据结构一块进行,比如hash什么的。
 
  与单链表不同的是,多了一个dlink_delete函数,因为双链表,所以删除就几行,不进行循环。
 
  
 
  与单链表实现不同的是:它在通用的基础上,将结点的分配与释放集成在一块,而单链表那个实现,只是一个通用的情况,结点的分配与释放得另外处理,这点要注意,当然,你可以自己去写集成在一块的写法,这里只是一个举例。
 
 
 
  双链表使用场合甚广,写成这种集成模式,不好不说,且不知如何调用。
 
  因为本人用的比较多这种模式,比如:
 
    1:hash中,根据key找到一个entry,然后删除就调用dlink_delete,操作多快
 
    2:更多的情况下,上面的示例,只是一个示例,我会更多的扩展它里的头信息,而不只是next,prev几个字段,
 
      增删改查时,进行相应处理。dlink_delete只是一个示例。:)
 
  目地,还是想给大家一个抛砖的作用。
 
  
Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<