delphi.數據結構.鏈表，delphi數據結構

delphi.數據結構.鏈表，delphi數據結構

鏈表作為一種基礎的數據結構，用途甚廣，估計大家都用過。
鏈表有幾種，常用的是：單鏈表及雙鏈表，還有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只是一個示例。:)

　　目地，還是想給大家一個拋磚的作用。

沒了。

水平有限，如有雷同，就是盜鏈，:D

2014.10.25 by qsl