数据结构算法 - 线性表的实现

数组是线性表数据结构中顺序存储的具体实现。用一组连续的内存空间，存储相同类型的数据

链表是线性表数据结构中链式存储的具体实现。用节点的指针把各个节点串联在一起

数组的基本操作

• 在指定位置插入元素
• 删除指定元素
• 查找值等于给定值的元素
• 查找数组小标为 index 的元素

根据线性表顺序存储的数据结构特征，我们可以知道，数组的插入、删除时间复杂度为O(n)，因为涉及到数据的搬移操作；数组的根据下标访问元素的时间复杂度为O(1)，这是连续的内存空间带来的优势，根据寻址公式我们可以很容易的找到指定下标的内存地址

数组的代码实现 (PHP)

classMyArray{// 数组大小private$size;// 当前数组长度private$len;// 数组的数据private$data;/** * 初始化数组 */publicfunction__construct($size=0){if($size<=0)thrownewException('Invalid Array size');$this->size=$size;$this->len=0;$this->data=array();}/** * 判断数组是否已满 */privatefunctionfull(){if($this->size==$this->len)returntrue;returnfalse;}/** * 索引是否超出范围 */privatefunctionoutOfRange($index){if($index<0||$index>=$this->len)returntrue;returnfalse;}/** * 根据索引访问数据元素 */publicfunctionfind($index){if(true===$this->outOfRange($index)){thrownewException('Index out of range');}return$this->data[$index];}/** * 在指定索引 index 处插入数据 data */publicfunctioninsert($index,$data){if(true===$this->full()){thrownewException('Array is full');}for($i=$this->len-1;$i>=$index;$i--){$this->data[$i]=$this->data[$i-1];}$this->data[$index]=$data;$this->len++;return$index;}/** * 删除指定索引的值 */publicfunctiondelete($index){if(true===$this->outOfRange($index)){thrownewException('Index out of range');}$data=$this->data[$index];for($i=$index;$i<$this->len-1;$i++){$this->data[$i]=$this->data[$i+1];}// unset 掉移动元素后最后的重复元素unset($this->data[$this->len-1]);$this->len--;return$data;}}

链表的基本操作

• 初始化链表
• 插入一个节点
• 删除指定节点
• 查询值等于给定值的节点

链表的代码实现 (PHP)

classLinkedListNode{// 节点的数据public$data;// 节点的指针public$next;publicfunction__construct($data=null){$this->data=$data;$this->next=null;}}classLinkedList{/** * 哨兵，头节点 * @var LinkedListNode */public$head;// 链表的长度public$len;/** * 初始化链表 */publicfunction__construct(LinkedListNode$head){$this->head=$head;$this->len=0;}/** * 插入节点，默认头插法 (头节点后插入) */publicfunctioninsert($value){try{$this->insertAfterNode($this->head,$value)}catch(Exception$e){thrownewException($e);}returntrue;}/** * 查询值等于给定值的节点 */publicfunctiongetNodeByValue($value){$curNode=$this->head;while(null!==$curNode){if($value==$curNode->data){return$curNode;}$curNode=$curNode->next;}returnnull;}/** * 查询链表的第 index 个节点 */publicfunctiongetNodeByIndex($index){if($index<=0||$index>$this->len){thrownewException('Index out of range');}$curNode=$this->head;for($i=0;$i<=$index;$i++){$curNode=$curNode->next;}return$curNode;}publicfunctiondelete(LinkedListNode$node){if(null===$node){thrownewException('Invalid node');}$preNode=$this->getPreNode($node);$preNode->next=$node->next;unset($node);$this->len--;returntrue;}privatefunctiongetPreNode(LinkedListNode$node){if(null===$node){thrownewException('Invalid node');}$curNode=$this->head;$preNode=$this->head;while(null!=$curNode&&$curNode!=$node){$preNode=$curNode;$curNode=$curNode->next;}return$preNode;}/** * 指定节点后插入元素 */privatefunctioninsertAfterNode(LinkedListNode$node,$value){if(null===$node)thrownewException('Node is null');$newNode=newLinkedListNode($value);$newNode->next=$node->next;$node->next=$newNode;$this->len++;returntrue;}}