集合——PHP实现
集合：由一個(gè)或多個(gè)確定的元素所構(gòu)成的整體叫做集合。是數(shù)學(xué)中的的常用概念。
集合中的元素有三個(gè)特征：
1.確定性（集合中的元素必須是確定的）
2.互異性（集合中的元素互不相同。例如：集合A={1，a}，則a不能等于1）
3.無序性（集合中的元素沒有先后之分），如集合{3,4,5}和{3,5,4}算作同一個(gè)集合。
針對(duì)集合這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，實(shí)現(xiàn)如下：
1 <?php 2 class Collection{ 3 protected $_members=array(); 4 protected $_itemHasType; //標(biāo)志是否指定元素的類型 5 protected $_itemType; //集合中的元素類型 6 7 public function __construct($items = [], $itemHasType = false, $itemType = NULL){ 8 $this->_itemHasType = $itemHasType; 9 $this->_itemType = $itemType; 10 $tmp = $this->getArrayableItems($items); 11 if($this->_itemHasType){ 12 foreach($tmp as $val){ 13 if($val instanceof $this->_itemType){ 14 $this->_members[] = $val; 15 } 16 } 17 }else{ 18 $this->_members = $tmp; 19 } 20 } 21 22 public function addItem($obj){ 23 if($this->_itemHasType){ 24 if(!($obj instanceof $this->_itemType)) 25 throw new Exception("The added obj is not the type of \"$this->_itemType\"!"); 26 } 27 if($this->exists($obj)){ 28 throw new Exception("Obj is already exists!"); 29 }else{ 30 $this->_members[] = $obj; 31 } 32 } 33 34 public function removeItem($obj){ 35 if(false != ($key = array_search($obj, $this->_members))){ 36 unset($this->_members[$key]); 37 }else{ 38 throw new Exception("Obj is not exists!"); 39 } 40 } 41 42 public function all(){ 43 return $this->_members; 44 } 45 46 public function length(){ 47 return sizeof($this->_members); 48 } 49 50 public function exists($obj){ 51 return in_array($obj, $this->_members); 52 } 53 54 protected function getArrayableItems($items) 55 { 56 if (is_array($items)) { 57 return array_values(array_unique($items, SORT_REGULAR)); 58 } elseif ($items instanceof self) { 59 return $items->all(); 60 } 61 return (array) $items; 62 } 63 }?
該集合類包含如下屬性：
該集合類包含了如下方法：
構(gòu)造方法。其中在通過array_unique方法去除$items數(shù)組中的重復(fù)項(xiàng)（注意：該方法默認(rèn)采用字符串方式比較數(shù)組元素，需要設(shè)置為SORT_REGULAR按照通常的方法比較，這樣才能）
對(duì)構(gòu)造方法中輸入的用于初始化的集合元素進(jìn)行去重、去鍵值預(yù)處理，或?qū)⒁粋€(gè)已有的Collection對(duì)象中的元素提取出來。需要指出的是：array_unique()方法默認(rèn)采用字符串方式比較數(shù)組元素，需要設(shè)置為SORT_REGULAR按照通常的方法比較，這樣才能實(shí)現(xiàn)對(duì)對(duì)象的比較。另外，去鍵值操作是將鍵值統(tǒng)一為1、2、3...的數(shù)字，這樣實(shí)現(xiàn)array與集合概念的一致，并且避免了在后續(xù)查找集合元素時(shí)，key值可能影響in_array()方法、array_search()在loose模式下的查找判斷（鍵值對(duì)這兩個(gè)方法造成的影響可以參考：http://php.net/manual/zh/function.in-array.php#106319），雖然strict模式可以避免key值對(duì)in_array()、array_search()方法的影響，但是在strict模式又引發(fā)了in_array()、array_search()方法不能對(duì)數(shù)組中保存的對(duì)象的按值比較，只有當(dāng)是要查找的對(duì)象與數(shù)組中保存的對(duì)象保存的是相同的object identifier時(shí)，in_array()才會(huì)返回true，array_search()才會(huì)返回對(duì)應(yīng)的key值。
添加元素方法。
移除指定元素方法。
獲取集合中所有元素，并保存在數(shù)組中。
獲取集合的長(zhǎng)度，即集合中元素的個(gè)數(shù)。
判斷集合中是否存在指定元素。
集合的應(yīng)用實(shí)例：
網(wǎng)易筆試題：已知輸入w、x、y、z，有 0<w<=p<=x, 0<y<=q<=z，且其中w、x、y、z、p、q均為正整數(shù)。將p/q加入集合中，集合中一共有多少元素。
1 <?php 2 class Collection{ 3 protected $_members=array(); 4 protected $_itemHasType; //標(biāo)志是否指定元素的類型 5 protected $_itemType; //集合中的元素類型 6 7 public function __construct($items = [], $itemHasType = false, $itemType = NULL){ 8 $this->_itemHasType = $itemHasType; 9 $this->_itemType = $itemType; 10 $tmp = $this->getArrayableItems($items); 11 if($this->_itemHasType){ 12 foreach($tmp as $val){ 13 if($val instanceof $this->_itemType){ 14 $this->_members[] = $val; 15 } 16 } 17 }else{ 18 $this->_members = $tmp; 19 } 20 } 21 22 public function addItem($obj){ 23 if($this->_itemHasType){ 24 if(!($obj instanceof $this->_itemType)) 25 throw new Exception("The added obj is not the type of \"$this->_itemType\"!"); 26 } 27 if($this->exists($obj)){ 28 //throw new Exception("Obj is already exists!"); 29 }else{ 30 $this->_members[] = $obj; 31 } 32 } 33 34 public function removeItem($obj){ 35 if(false != ($key = array_search($obj, $this->_members))){ 36 unset($this->_members[$key]); 37 }else{ 38 throw new Exception("Obj is not exists!"); 39 } 40 } 41 42 public function all(){ 43 return $this->_members; 44 } 45 46 public function length(){ 47 return sizeof($this->_members); 48 } 49 50 public function exists($obj){ 51 return in_array($obj, $this->_members); 52 } 53 54 protected function getArrayableItems($items) 55 { 56 if (is_array($items)) { 57 return array_values(array_unique($items, SORT_REGULAR)); 58 } elseif ($items instanceof self) { 59 return $items->all(); 60 } 61 return (array) $items; 62 } 63 } 64 65 class Num{ 66 private $numerator; //分子 67 private $denominator; //分母 68 public function __construct($numerator,$denominator){ 69 list($this->numerator, $this->denominator) = $this->simply($numerator, $denominator); 70 } 71 private function simply($numerator,$denominator){ 72 $num = $this->gcd($numerator, $denominator); 73 return array($numerator/$num, $denominator/$num); 74 } 75 76 //獲取兩個(gè)數(shù)的最大公約數(shù)greatest common divisor 77 //輾轉(zhuǎn)相除法。另外還可以采用更相損減法 78 private function gcd($num1,$num2){ 79 if($num1 < $num2) $this->gcd($num2, $num1); 80 while($num2 != 0){ 81 $tmp = $num1%$num2; 82 $num1 = $num2; 83 $num2 = $tmp; 84 } 85 return $num1; 86 } 87 } 88 89 function getInput(){ 90 return list($w, $x, $y, $z) = explode(' ', trim(fgets(STDIN))); 91 } 92 93 function main(){ 94 list($w, $x,$y,$z) = getInput(); 95 $w = (int)$w; 96 $x = (int)$x; 97 $y = (int)$y; 98 $z = (int)$z; 99 $numSet = new Collection([], true, 'Num'); 100 for($i=$w; $i<=$x; $i++){ 101 for($j=$y; $j<=$z; $j++){ 102 $numSet->addItem(new Num($i,$j)); 103 } 104 } 105 echo $numSet->length(); 106 } 107 main(); View Code?
轉(zhuǎn)載于:https://www.cnblogs.com/jade640/p/6634614.html
總結(jié)
- 上一篇： The 15th UESTC Progr
- 下一篇： 51nod 1090 1267 【二