钛节点

数据结构之线性表（顺序存储表）

发表@2018-09-13 09:15:21

更新@2023-01-21 22:47:40

为啥突然不写排序了，不是听说还有好几种别的排序办法吗？主要是剩下几种算法是和一些数据结构挂钩的，不明白这些数据结构是很难搞明白这些排序算法的。

第一篇线性表是一个比较简单的概念，大概意思就是“ 零个或多个数据元素的有限序列 ”，值得注意的是这些数据是有先后顺序的，并不是一坨乱而无序的数字。

举个简单的例子吧，准备开始练球了，达叔让大师兄、二师兄、三师兄、五师弟、六师弟拍成一队，然后大师兄发球给二师兄，二师兄转球给三师兄，三师兄转球给你，你转球给五师弟，五师弟转球给六师弟，到了六师弟这里就算一轮练习完成，我们说这种前后有顺序的队列可以称作线性表，在这个队伍中，如果球到从大师兄脚下到五师弟这里，就必须严格按照大师兄 -> 二师兄 -> 三师兄 -> 我 -> 五师弟这样的顺序来传球，不能出现大师兄直接传球给五师弟等现象。

![](https://ti-node.com/static/upload/6401618099149209600)

在练习了一段时间后，达叔让大家到球场上和著名业余球队踢了以切磋为主的“ 友谊第一，比赛第二 ”的球赛，这个球赛中，少林队传球就不能讲究顺序了，而是任意一个球员都可以向其他任意队友传球。这种情况下，就不能满足线性表的一些定义和概念了。

![](https://ti-node.com/static/upload/6401621180733718528)

线性表有两种存储方式：
- 顺序存储方式，顺序存储的方式就是在内存中开辟一块儿地址连续的存储空间用来容纳数据。举个例子，就像观众在排队买 少林队 VS 豆腐金刚队 的门票，由于赛况激烈所以采取抢购策略，来了十个抢票的人，这个时候保安就得腾出一块儿能容纳下十个人地儿来。如果突然一个美女要插队买票，这事儿就比较麻烦了。既然是插队，也就说肯定不是在队尾了，假如美女靠美色插队到了第五个人前面，那么后面的人就要统统往后退一个位置了，一下要六个人往后后退一步。
- 链式存储方式，对于上述顺序存储的问题，该如何解决呢？还是少林队 VS 金刚豆腐队的事儿，官方这次学聪明了，这次官方让大家通过网络预约号码，号码上同时还有下一个人的人名。这下好了，门口的空间可以好好利用了，大家可以随意占了没有必要一定要排队。观众强雄在买完票后，他会喊下一个观众酱爆，至于酱爆在什么地方就不一定了，他不一定非要站在强雄后面。这种方式的好处就是，每个人都可以占据在自己想在的地方，门口的空间利用率会更好更高。这个时候，如果再有美女来插队，那也变得简单的很了。比如她插队到酱爆前面，就只需要把强雄票上的下一个人的人名换成美女，然后美女票上下一个人的人名换成酱爆就可以了。

![](https://ti-node.com/static/upload/6401653572303323137)

现在我们先抽象一下顺序存储线性表的几个重要操作：
- 添加元素
- 删除元素
- 查看元素数量
- 获取某个位置上的数据
- 根据数据获取数据位置
- 更改某个位置上的数据
- 清空线性表

其实，在php中，数组就可以用来当作顺序存储表，大家想想是不是？然而，作为一个有尺度有态度的php文化传播圣地，不弄点儿高端的实在是对不起自己的。来吧，动手吧。
```php
<?php
class Linear{
  protected $item = [];
  /*
    * @desc : 向某个位置添加一个元素
	* @param : index
	* @param : item
    */
  public function add_item( $index, $item ){
    $length = $this->get_length();
	if( $index < 0 || $index > $length ){
	  return false;
	}
	// 将数字统统往后移动一个位置
	for( $i = $length; $i > $index; $i-- ){
	  $this->item[ $i ] = $this->item[ $i - 1 ];
	}
    $this->item[ $index ] = $item;
	return true;
  }
  /*
    * @desc : 删除某个位置的元素
	* @param : index
    */  
  public function delete_item( $index ){
    $length = $this->get_length();
	if( $index < 0 || $index > $length - 1 ){
	  return false;
	}
	$value = $this->item[ $index ];
	// 将数字统统往前移动一个位置
	for( $i = $index; $i < $length - 1; $i++ ){
	  $this->item[ $i ] = $this->item[ $i + 1 ];
	}
	unset( $this->item[ $length - 1 ] );
	return $value;
  }
  /*
    * @desc : 获取长度
	* @param : index
    */  
  public function get_length(){
    return count( $this->item );
  }
  /*
    * @desc : 根据位置获取元素
	* @param : index
    */  
  public function get_item_by_index( $index ){
    $length = $this->get_length();
	if( $index < 0 || $index >= $length ){
	  return null;
	}
	return $this->item[ $index ];
  }
  /*
    * @desc : 根据元素获取位置
	* @param : item
    */  
  public function get_index_by_item( $item ){
    // 这个没什么好办法，只能是通过遍历所有数据来做了
	$length = $this->get_length();
	$index = null;
	for( $i = 0; $i < $length; $i++ ){
	  if( $item == $this->item[ $i ] ){
	    $index = $i;
	  }
	}
	return $index;
  }
  /*
    * @desc : 更新某个位置上的元素
	* @param : index
	* @param : item
    */
  public function update_item_by_index( $index, $item ){
    $length = $this->get_length;
	if( $index < 0 || $index >= $length ){
	  return false;
	}
	$this->item[ $index ] = $item;
  }
  /*
    * @desc : 获取线性表中所有元素
    */
  public function get_all_item(){
    // 你以为要用print_r或者var_dump，然而，为了装逼，并不能，我们要遍历，遍历，遍历！
	$length = $this->get_length();
	for( $i = 0; $i < $length; $i++ ){
	  echo $this->item[ $i ].' ';
	}
    echo PHP_EOL;
  }
  /*
    * @desc : 清空一个线性表
    */  
  public function truncate(){
    $this->item = null;
  }
}

$line = new Linear();
// 连续添加5个元素
$line->add_item( 0, 12 );
$line->add_item( 1, 2 );
$line->add_item( 2, 5 );
$line->add_item( 3, 6 );
$line->add_item( 4, 1 );
// 获取所有元素
$line->get_all_item();
// 向位置2上插入一个新的元素8
$line->add_item( 2, 8 );
// 获取所有元素
$line->get_all_item();
// 获取3位置上的元素
echo $line->get_item_by_index( 3 ).PHP_EOL;
// 获取元素5的位置
echo $line->get_index_by_item( 5 ).PHP_EOL;
// 删除位置3上的元素
$line->delete_item( 3 );
// 获取所有元素
$line->get_all_item();
// 获取表的长度
echo '表的长度：'.$line->get_length().PHP_EOL;
```

懒的人分为好几种：
- 看了看文章，记住了些许理论原理，觉得了然于胸的
- 看了看文章直接复制粘贴代码运行了一下的
- 看了看文章，自己用php array函数走了一遍的
- 看了看文章，自己对着上述代码敲了一遍的
- 看了看文章，理解了原理，看了一眼代码，自己憋代码，实在憋不出的再回来看代码

### 哈哈哈哈哈哈哈，实际上我的代码有好几处错的，懒的人早晚栽坑

------