当前位置: 首页 > biancheng >正文

有序单链表的插入

 相比有序表,我们单链表插入就方便多了,起码有一点,我们有指针指引 ,就不用再把传入位置腾出来了 , 方便了插入

但是,我们要把新节点插入到有序单链表 , 必不可少的一步是从头指针遍历 ,找到一个区间 , 左端点比插入节点小 , 右端点比插入结点大, 然后把新元素插入到这之间就可以了.如下图:

 

所以我们首先要找到这个区间, 然后 让 左端点的节点的后继指针指向 e , e的后继指针指向右端点就可以了

设 指针 pre 指向如图 4 , pre->next 就指向了如图 7,  指针 *p 指向 新 节点 e

然后把         让新节点p 的后继指针指向  pre->next  (7)  

                       p->next=pre->next;


4 的后继指针 指向 新节点 p 

                pre->next = p;

这样就完成了

所以主要的问题是找到这个区间 ,然后让pre 指向区间的左端点 就行了

当 pre 指向的节点的下一个节点比 新节点数值大 , 就跳出遍历,并且还要有下一个节点,没有的话,我们直接把新节点插入到尾结点就可以了

while(pre->next->data < e && pre ->next !=NULL)

{

        pre = pre ->next;                //不符合,就继续遍历

}


跳出遍历的时候 , pre->next->data 大于等于新节点 ,那么 pre 指向的就是区间的左端点,pre->next指向的就是区间的右端点 ,按照上面的插入方法插入就可以了

完整代码如下:

void ListInsert(LinkList *&L, ElemType e)
{
	LinkList *pre = L, *p;
	while(pre ->next != NULL && pre->next-data < e )
	{
		pre = pre -> next;		//找到合适的插入位置
	}
	p = (LinkList *)malloc(malloc(LinkList));  //构建新节点
	p->data = e;			//新节点赋值
	p ->next = pre->next;	//链表的插入
	pre ->next = p;			//顺序不可颠倒
}

相关文章:

  • switch循环语句
  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)