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

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

更多资讯

SystemVerilog双向开关tran与tranif1选型指南：从仿真异常到建模实践

Agentic工作负载的云原生调度与编排：从Kubernetes到运行时实践

ax：云原生Agent调度底座设计与gRPC实践

Jev AI决策系统架构设计：从概念到生产的工程实践

第一次把 Godot 游戏发布到三大桌面平台：从导出到签名的完整实操路径

agent-native架构实战：从AI增强到原生智能体系统的设计原则与落地

今日更新

济南做网站多少钱：3个案例拆解，防黑源码下载全攻略

婚恋网站实战案例：避开3个高价坑，省钱50%还能跑赢流量

制作网页比较方便的软件怎么选?一文搞懂避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

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

分布式服务的决策记录

创业产品的首版范围

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