数据结构算法 - 线性表的实现-北京尧图网络

数组是线性表数据结构中顺序存储的具体实现。用一组连续的内存空间存储相同类型的数据链表是线性表数据结构中链式存储的具体实现。用节点的指针把各个节点串联在一起数组的基本操作在指定位置插入元素删除指定元素查找值等于给定值的元素查找数组小标为 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;}}

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

相关推荐

VMware虚拟机导致宿主机蓝屏：从原理到排查的完整指南

物联网硬件安全：SE050芯片与PIC32MX795F512L集成方案

Zenmap图形化Nmap工具：从安装配置到实战扫描技巧全解析

更多资讯

Thunderstore MOD一键安装指南：BepInEx框架与r2modman管理器实操

光电二极管检测电路设计：跨阻放大与暗电流噪声优化

独立开发者素材基建手册：合法、即用、可复用的免费游戏资源工作流

学生选课成绩分析系统实战：Flask+Vue+ECharts前后端分离开发

Safari 最近标签切换器：MRU 排序与模糊搜索实现

江苏智能电网规划：从docx到系统参数的全链路拆解

今日更新

校园网认证计费模式详解：AAA与代拨架构、原理及排障

Spring Boot+Vue垃圾分类毕设：分层、权限与排错实战

把 Cline 的 Base URL 改到 TaoToken 之后，DeepSeek 仍能修调试配置

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？