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

数组是线性表数据结构中顺序存储的具体实现。用一组连续的内存空间存储相同类型的数据链表是线性表数据结构中链式存储的具体实现。用节点的指针把各个节点串联在一起数组的基本操作在指定位置插入元素删除指定元素查找值等于给定值的元素查找数组小标为 index 的元素根据线性表顺序存储的数据结构特征我们可以知道数组的插入、删除时间复杂度为O(n)因为涉及到数据的搬移操作数组的根据下标访问元素的时间复杂度为O(1)这是连续的内存空间带来的优势根据寻址公式我们可以很容易的找到指定下标的内存地址数组的代码实现 (PHP)classMyArray{// 数组大小private$size;// 当前数组长度private$len;// 数组的数据private$data;/** * 初始化数组 */publicfunction__construct($size0){if($size0)thrownewException(Invalid Array size);$this-size$size;$this-len0;$this-dataarray();}/** * 判断数组是否已满 */privatefunctionfull(){if($this-size$this-len)returntrue;returnfalse;}/** * 索引是否超出范围 */privatefunctionoutOfRange($index){if($index0||$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[$i1];}// unset 掉移动元素后最后的重复元素unset($this-data[$this-len-1]);$this-len--;return$data;}}链表的基本操作初始化链表插入一个节点删除指定节点查询值等于给定值的节点链表的代码实现 (PHP)classLinkedListNode{// 节点的数据public$data;// 节点的指针public$next;publicfunction__construct($datanull){$this-data$data;$this-nextnull;}}classLinkedList{/** * 哨兵头节点 * var LinkedListNode */public$head;// 链表的长度public$len;/** * 初始化链表 */publicfunction__construct(LinkedListNode$head){$this-head$head;$this-len0;}/** * 插入节点默认头插法 (头节点后插入) */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($index0||$index$this-len){thrownewException(Index out of range);}$curNode$this-head;for($i0;$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);$newNodenewLinkedListNode($value);$newNode-next$node-next;$node-next$newNode;$this-len;returntrue;}}