单链表的指定结点的 插入 （前插和后插）操作

文章目录指定结点的 后插 操作代码指定结点的 前插 操作代码解释 前插与后插物理结构与逻辑结构物理结构存储结构逻辑结构逻辑关系指定结点的 后插 操作代码#includestdio.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;// 后插操作在 p 结点之后插入元素 eboolInsertNextNode(LNode*p,inte){if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)//内存分配失败returnfalse;s-datae;s-nextp-next;p-nexts;returntrue;}// 在 第 i 个位置插入元素 e (带头结点)boolListInsert(LinkListL,inti,inte){if(i1)returnfalse;LNode*p;intj0;pL;// p 初始指向头结点第 0号结点while(p!NULLji-1){pp-next;j;}if(pNULL)// i过大找不到前驱returnfalse;returnInsertNextNode(p,e);}// 配套初始化boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));if(LNULL)returnfalse;L-nextNULL;returntrue;}指定结点的 前插 操作代码数据交换法//前插操作: 在p结点【逻辑上】之前插入元素 eboolInsertPriorNode(LNode*p,inte){if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;s-nextp-next;p-nexts;//新结点 s 连到 p 之后s-datap-data;//p原有数据复制到sp-datae;//p存放新元素ereturntrue;}// 这段代码在物理上执行的是“后插”在 p 的后面挂新节点// 但通过“交换数据”的障眼法在逻辑上实现了“前插”让新元素出现在 p 的前面。// 它的时间复杂度是 O(1)远优于“找前驱再插入”的 O(n) 方法。这段代码在不使用找前驱的方式下对数据进行前插操作。解释 前插与后插单链表插入找前驱i-1改前驱的next改前驱的next就是后插这个后插在逻辑上就是目标位序的前插。即为 次序 i 的前插为次序 i-1 的后插。物理结构与逻辑结构物理结构存储结构指数据在计算机内存里真实存放的方式、内存地址分布、结点实际位置、指针连接方式。常见类型顺序存储连续整块内存数组链式存储离散内存靠指针 next 连接索引存储、散列存储关键词内存布局、地址、指针连接、结点真实位置、数组 / 链表存储形式问内存 / 指针布局 / 真实结点位置 物理层面逻辑结构逻辑关系指数据元素之间的抽象关系和内存怎么存无关、和地址无关只看遍历顺序 / 前后从属关系。描述谁是前驱、谁是后继、层级关系、图的连接关系线性一对一链表、顺序表树形一对多图状多对多集合无关联关键词前驱、后继、遍历顺序、前后顺序、算法功能、语义问顺序 / 遍历 / 算法功能 逻辑层面