php數(shù)據(jù)結(jié)構(gòu)課程---2、鏈表（php中 是如何實(shí)現(xiàn)單鏈表的（也就是php中如何實(shí)現(xiàn)對(duì)象引用的））

一、總結(jié)

一句話總結(jié)：

php是弱類(lèi)型語(yǔ)言，變量即可表示數(shù)值，也可表示對(duì)象：鏈表節(jié)點(diǎn)的數(shù)據(jù)域的值就是數(shù)值，鏈表節(jié)點(diǎn)的指針域的值就是對(duì)象（new Node()出來(lái)的產(chǎn)物）

用class來(lái)構(gòu)建節(jié)點(diǎn)，也用class來(lái)構(gòu)建比如單鏈表啊，雙鏈表啊

?

1、鏈表是什么？

鏈表是一種物理存儲(chǔ)(內(nèi)存)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)對(duì)象引用來(lái)實(shí)現(xiàn)的。

節(jié)點(diǎn)=數(shù)據(jù)域+下一個(gè)結(jié)點(diǎn)的引用

鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)的引用。

?

2、php實(shí)現(xiàn)單鏈表實(shí)例？

節(jié)點(diǎn)是一個(gè)類(lèi)：class Node{}：Node節(jié)點(diǎn)里面有兩個(gè)變量（$data和$next）和一個(gè)構(gòu)造函數(shù)__construct()

php構(gòu)造函數(shù)：public function __construct(){}

單鏈表也是一個(gè)類(lèi)：有$header,$last,$size三個(gè)變量

1 <?php 2 3 4 class Node{ 5 public $data = null; 6 public $next = null; 7 public function __construct($data,$next=null){ 8 $this->data = $data; 9 $this->next = $next; 10 } 11 } 12 13 class singleLinkList{ 14 private $header = null; 15 private $last = null; 16 public $size = 0; 17 18 public function __construct(){ 19 20 } 21 22 public function add($data){ 23 $node = new Node($data); 24 if($this->header == null and $this->last==null){ 25 $this->header = $node; 26 $this->last = $node; 27 }else{ 28 $this->last->next = $node; 29 $this->last = $node; 30 } 31 } 32 33 public function del($data){ 34 $node=$this->header; 35 if($node->data == $data){ 36 $this->header = $this->header->next; 37 return true; 38 }else{ 39 while($node->next->data == $data){ 40 $node->next = $node->next->next; 41 return true; 42 } 43 } 44 return false; 45 } 46 47 public function update($old,$new){ 48 $node = $this->header; 49 while($node->next != null){ 50 if($node->data == $old){ 51 $node->data = $new; 52 return true; 53 } 54 $node = $node->next; 55 } 56 echo "not found!"; 57 return false; 58 } 59 60 public function find($data){ 61 $node = $this->header; 62 while($node->next != null){ 63 if($node->data == $data){ 64 echo "found!"; 65 return; 66 } 67 $node = $node->next; 68 } 69 echo "not found!"; 70 } 71 72 public function getAll(){ 73 $node = $this->header; 74 while($node->next != null){ 75 echo $node->data; 76 $node = $node->next; 77 } 78 echo $node->data; 79 } 80 } 81 82 $list = new singleLinkList(); 83 $list->add("1"); 84 $list->add("2"); 85 $list->add("3"); 86 $list->add("4"); 87 $list->add("5"); 88 $list->add("6"); 89 echo "<pre>"; 90 // $list->getAll(); 91 92 // if($list->del("2")){ 93 // echo "success"; 94 // }else{ 95 // echo "false"; 96 // } 97 98 // if($list->update("3","7")){ 99 // var_dump($list); 100 // } 101 102 $list->find(7); 103 // $list->getAll();

?

?

3、雙向鏈表的數(shù)據(jù)結(jié)構(gòu)是怎樣？

<-pre data next->：data為數(shù)據(jù)，pre為指向前個(gè)節(jié)點(diǎn)的引用，next為指向后個(gè)節(jié)點(diǎn)的引用

class node{public $data;public $prev;public $next; } class doubleLinkList{public header;private size; } //操作函數(shù)getSize(),setHeader($v),__construct(),add($d) // delete($d),update($d),find($d),

?

?

4、循環(huán)鏈表的結(jié)構(gòu)結(jié)構(gòu)是怎樣？

和雙向鏈表相似：data域加前($prev)后($next)兩個(gè)指針：最后一個(gè)節(jié)點(diǎn)的next指針指向和第一個(gè)節(jié)點(diǎn)，第一個(gè)的prev指向了最后一個(gè)節(jié)點(diǎn)

?

5、約瑟夫環(huán)（求最后剩下的那個(gè)人）如何用循環(huán)鏈表來(lái)做，（n個(gè)小孩坐在一圈，每數(shù)到3就退出去，最后余下的是誰(shuí)）？

確定好Node節(jié)點(diǎn)的屬性和方法

確定構(gòu)造函數(shù)：創(chuàng)建鏈表

circleList的另外一個(gè)方法輸出最后剩下的那個(gè)人

<?php class Node{public $name;public $next;public function __construct($name,$next=null){$this->name = $name;$this->next = $next;}public function setNext(&$next){$this->next = $next;} }class circleList{public $head =null;public function __construct($str){$node = null;foreach (explode(" ", $str) as $key => $value) {if($node){$node->setNext(new Node($value));$node= $node->next;}else{$node = new Node($value);$this->head = $node;}}$node->setNext($this->head);// echo "<pre>";// var_dump($this->head); }public function findLastOne($n){$count = 1;$list = $this->head;while($list->next != $list){if($count%3==2){$list->next=$list->next->next;}else{$list=$list->next;}$count++;}return $list->name;} }$str = "圣夏彤 邴丹丹 臺(tái)浩邈 鮮依瑤 閃又青 威心遠(yuǎn) 佛樂(lè)正 尋仙韻 別光華 柳舒蘭 聞清婉 讓昕玨 出欣躍 慎詩(shī)丹 卿冬萱 拜若薇 黃夢(mèng)秋 浮婭玟 駱飛章 劍成化 平海榮 望凡霜 蔡雪萍 姓慧穎 秋訪夢(mèng) 須盈秀 邰宣朗 林安彤 謬祺然 能駿琛 湯香菱 查尋琴 乾問(wèn)凝 冒聽(tīng)筠 左詩(shī)蘭 市暄美 位水丹 裔翠芙 邗宏博 空永長(zhǎng) 進(jìn)南霜 司空新雪 穆樂(lè)蓉 緒野雪 告天瑞 仁桂帆 齊珠雨 姒以冬 禽夏菡 呼延蘭英 簡(jiǎn)小雨 建彤蕊 偶迎南 南夏嵐 枝傲菡 羅蔚星 年博簡(jiǎn) 夔代巧 戈曼蔓 赫麥冬 光美如 戲柔惠 恭千秋 森寄蕾 亓嫻淑 豆飛瑤 菅爾容 齋依云 荊紫杉 宦雪容 酒含景 占碧蓉 牽盼香 唐青雪 清映秋 瑞和璧 藍(lán)聽(tīng)春 牛新潔 沐妙思 胥雍恬 饒鴻光 丹樂(lè)然 抄曼吟 張廖智杰 府念云 昔德宇 堯平安 尹芳澤 勤清妍 哀清瑩 柴佩珍 夾谷昆琦 塔思琪 虞采萱 融水荷 招采萱 勢(shì)鴻志 次長(zhǎng)岳 費(fèi)莫懷芹 始修真";$list = new circleList($str); echo $list->findLastOne(3);

?

?

?

?

二、內(nèi)容在總結(jié)中

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Renyi-Fan/p/10873352.html

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的php数据结构课程---2、链表（php中 是如何实现单链表的（也就是php中如何实现对象引用的））...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。