这篇文章主要介绍了php数据结构之顺序链表与链式线性表,结合实例形式较为详细的分析了php实现顺序链表与链式线性表的各种常用操作技巧,需要的朋友可以参考下。

本文实例讲述了php数据结构之顺序链表与链式线性表，分享给大家供大家参考，具体如下：

链表操作

1、InitList(L)：初始化链表

2、DestroyList(L)：删除连接

3、ClearList(L)：清空链表

4、ListEmpty(L)：判断是否为空

5、 ListLength(L)：链表长度

6、 getElem(L,i)：取出元素

7、LocateElem(L,e)：判断e是否在链表中

8、PriorElem(L,i)：前驱

9、 NextElem(L,i)：后继

10、ListInsert(L,i,e)：插入元素

11、ListDelete(L,i,)：删除元素

顺序链表操作

1. <?php
2. class ArrayList{
3. private $list;
4. private $size;
5. //构造函数
6. public function __construct(){
7. $this->list=array();
8. $this->size=0;
9. }
10. public function initList(){
11. $this->list=array();
12. $this->size=0;
13. }
14. //删除链表
15. public function destoryList(){
16. if(isset($this->list)){
17. unset($this->list);
18. $this->size=0;
19. }
20. }
21. //清空链表
22. public function clearList(){
23. if(isset($this->list)){
24. unset($this->list);
25. }
26. $this->list=array();
27. $this->size=0;
28. }
29. //判断链表是否为空
30. public function emptyList(){
31. if(isset($this->list)){
32. if($this->size=0)
33. return TRUE;
34. else
35. return FALSE;
36. }
37. }
38. //链表长度
39. public function lenghtList(){
40. if(isset($this->list)){
41. return $this->size;
42. }
43. }
44. //取元素
45. public function getElem($i){
46. if($i<1||$i>$this->size){
47. echo "溢出<br>";
48. exit();
49. }
50. if(isset($this->list)&&is_array($this->list)){
51. return $this->list[$i-1];
52. }
53. }
54. //是否在链表中
55. public function locateElem($e){
56. if(isset($this->list)&&is_array($this->list)){
57. for($i=0;$i<$this->size;$i++){
58. if($this->list[$i]==$e){
59. return $i+1;
60. }
61. }
62. return 0;
63. }
64. }
65. //前驱
66. public function priorElem($i){
67. if($i<1||$i>$this->size){
68. echo "溢出";
69. exit();
70. }
71. if($i==1){
72. echo "没有前驱";
73. exit();
74. }
75. if(isset($this->list)&&is_array($this->list)){
76. return $this->list[$i-2];
77. }
78. }
79. //后继
80. public function nextElem($i){
81. if($i<1||$i>$this->size){
82. echo "溢出";
83. exit();
84. }
85. if($i==$this->size){
86. echo "没有后继";
87. exit();
88. }
89. if(isset($this->list)&&is_array($this->list)){
90. return $this->list[$i];
91. }
92. }
93. //插入元素
94. public function insertList($i,$e){
95. if($i<1||$i>$this->size+1){
96. echo "插入元素位置有误";
97. exit();
98. }
99. if(isset($this->list)&&is_array($this->list)){
100. if($this->size==0){
101. $this->list[$this->size]=$e;
102. $this->size++;
103. }else{
104. $this->size++;
105. for($j=$this->size-1;$j>=$i;$j--){
106. $this->list[$j]=$this->list[$j-1];
107. }
108. $this->list[$i-1]=$e;
109. }
110. }
111. }
112. //删除元素
113. public function deleteLlist($i){
114. if($i<1||$i>$this->size){
115. echo "删除元素位置有误";
116. exit();
117. }
118. if(isset($this->list)&&is_array($this->list)){
119. if($i==$this->size){
120. unset($this->list[$this->size-1]);
121. }else{
122. for($j=$i;$j<$this->size;$j++){
123. $this->list[$j-1]=$this->list[$j];
124. }
125. unset($this->list[$this->size-1]);
126. }
127. $this->size--;
128. }
129. }
130. //遍历
131. public function printList(){
132. if(isset($this->list)&&is_array($this->list)){
133. foreach ($this->list as $value){
134. echo $value." ";
135. }
136. echo "<br>";
137. }
138. }
139. }
140. ?>

链式线性表

1. <?php
2. class LinkList {
3. private $head;
4. private $size;
5. private $list;
6. public function __construct(){
7. $this->head="";
8. $this->size=0;
9. $this->list=array();
10. }
11. public function initList(){
12. $this->head="";
13. $this->size=0;
14. $this->list=array();
15. }
16. //删除链表
17. public function destoryList(){
18. if(isset($this->list)&&isset($this->head)){
19. unset($this->list);
20. unset($this->head);
21. }
22. }
23. //清空链表
24. public function clearList(){
25. if(isset($this->list)){
26. unset($this->list);
27. }
28. $this->list=array();
29. $this->size=0;
30. $this->head="";
31. }
32. //判断链表是否为空
33. public function emptyList(){
34. if(isset($this->list)){
35. if($this->size==0)
36. returnTRUE;
37. else
38. returnFALSE;
39. }
40. }
41. //链表长度
42. public function lenghtList(){
43. if(isset($this->list)){
44. return$this->size;
45. }
46. }
47. //取元素
48. public function getElem($i){
49. if($i<1||$i>$this->size){
50. echo "溢出<br>";
51. exit();
52. }
53. if(isset($this->list)&&is_array($this->list)){
54. $j=1;
55. //头指针
56. $tmp=$this->head;
57. while($i>$j){
58. if($this->list[$tmp]['next']!=null){
59. $tmp=$this->list[$tmp]['next'];
60. $j++;
61. }
62. }
63. return $this->list[$tmp]['data'];
64. }
65. }
66. //是否在链表中
67. public function locateElem($e){
68. if(isset($this->list)&&is_array($this->list)){
69. $tmp=$this->head;
70. while($this->list[$tmp]['data']!=$e){
71. if($this->list[$tmp]['next']!=null){
72. $tmp=$this->list[$tmp]['next'];
73. }else{
74. returnFALSE;
75. }
76. }
77. return TRUE;
78. }
79. }
80. //前驱
81. public function priorElem($i){
82. if($i<1||$i>=$this->size){
83. echo "溢出";
84. exit();
85. }
86. if($i==1){
87. echo "没有前驱";
88. exit();
89. }
90. $tmp=$this->head;
91. $j=1;
92. while($i>$j+1){
93. if($this->list[$tmp]['next']!=null){
94. $j++;
95. $tmp=$this->list[$tmp]['next'];
96. }
97. }
98. return$this->list[$tmp]['data'];
99. }
100. //后继
101. public function nextElem($i){
102. if($i<1||$i>$this->size){
103. echo "溢出";
104. exit();
105. }
106. if($i==$this->size){
107. echo "没有后继";
108. exit();
109. }
110. $j=1;
111. $tmp=$this->head;
112. while($i>=$j){
113. if($this->list[$tmp]['next']!=null){
114. $j++;
115. $tmp=$this->list[$tmp]['next'];
116. }
117. }
118. return$this->list[$tmp]['data'];
119. }
120. //插入元素:后插法
121. public function insertList($i,$e){
122. if(isset($this->list)&&is_array($this->list)){
123. //空表
124. if($this->size==0){
125. $this->head=$this->uuid();
126. $this->list[$this->head]['data']=$e;
127. $this->list[$this->head]['next']=NULL;
128. $this->size++;
129. }else{
130. if($i<1||$i>$this->size){
131. echo"插入元素位置有误";
132. exit();
133. }
134. $j=1;
135. $tmp=$this->head;
136. while($i>$j){
137. if($this->list[$tmp]['next']!=null){
138. $j++;
139. $tmp=$this->list[$tmp]['next'];
140. }
141. }
142. $find=$tmp;
143. $id=$this->uuid();
144. if($this->list[$find]['next']==null){
145. //尾部
146. $this->list[$find]['next']=$id;
147. $this->list[$id]['data']=$e;
148. $this->list[$id]['next']=null;
149. $this->size++;
150. }else{
151. //中间
152. $this->list[$id]['next']=$this->list[$find]['next'];
153. $this->list[$find]['next']=$id;
154. $this->list[$id]['data']=$e;
155. $this->size++;
156. }
157. }
158. }
159. }
160. //删除元素
161. public function deleteLlist($i){
162. if($i<1||$i>$this->size){
163. echo "删除元素位置有误";
164. exit();
165. }
166. if(isset($this->list)&&is_array($this->list)){
167. if($i==1){
168. //删除头元素
169. $this->head=$this->list[$this->head]['next'];
170. }else{
171. $tmp=$this->head;
172. $j=1;
173. while($i>$j+1){
174. if($this->list[$tmp]['next']!=null){
175. $j++;
176. $tmp=$this->list[$tmp]['next'];
177. }
178. }
179. //找到删除元素的前驱
180. $find=$tmp;
181. //删除的元素
182. if($this->list[$find]['next']!=null){
183. //不是最后一个元素
184. $delete=$this->list[$find]['next'];
185. $this->list[$find]['next']=$this->list[$delete]['next'];
186. }else{
187. $this->list[$tmp]['next']=null;
188. }
189. }
190. }
191. }
192. public function traverstList(){
193. $tmp=$this->head;
194. while($this->list[$tmp]['next']!=NULL){
195. $this->printList($this->list[$tmp]['data'],TRUE);
196. $tmp=$this->list[$tmp]['next'];
197. }
198. $this->printList($this->list[$tmp]['data'],FALSE);
199. }
200. public function printList($str,$flag){
201. if($flag){
202. echo$str."->";
203. }else {
204. echo$str."<br>";
205. }
206. }
207. //uuid 唯一码
208. public function uuid($prefix = '') {
209. $chars =md5(uniqid(mt_rand(), true));
210. $uuid = substr($chars,0,8) . '-';
211. $uuid .=substr($chars,8,4) . '-';
212. $uuid .=substr($chars,12,4) . '-';
213. $uuid .=substr($chars,16,4) . '-';
214. $uuid .= substr($chars,20,12);
215. return $prefix. $uuid;
216. }
217. }
218. ?>