【C】链表_有序插入

<div class="inner-content" >
<p class="inser-title">【C】链表_尾部插入</p>
<div class="inster-summary text-muted">
尾部插入继续上一篇文章的后续我们修改link里边的insert_link函数，应为这就是插入函数嘛。。直接改寻找尾...
</div>
</div>
</a>

</div>

</div>

> 继续上一篇文章的后续

**意义：**有序插入是按照结构体中的某个成员的顺序来决定链表的顺序。（如我们可以按照成绩从高到低来决定顺序）

* 插入前需要保证链表已经有序
* 寻找pi插入点

```c
STU *pb = head;//pb寻找插入点
STU *pf = head;//保存pb移动前的位置
while(pb->num < pi->num&&pb->next!=NULL)
{
  pf=pb;
  pb=pb->next;
}
```

* 判断插入点的位置（头部、中部、尾部）

1. 头部插入(pb==head):

```C
   if(pb==head)//直接更新链表头
   {
   pi->next=head;
   head=pi;
   }
   ```
2. 中部插入（pb->num > pi->num）:

```C
   if(pb->num > pi->num)
   {
     pf->next=pi;
     pi-next=pb;
   }
   ```
3. 尾部插入（pi->num > pbnum&&pb->next==NULL）

```c
   if(pb->num < pi->num&&pb->next!=NULL)
   {
    pb-next=pi;
   }
   ```

![](https://blog.fivk.cn/usr/uploads/2021/01/1347695641.jpg)

---

```C
//链表的有序插入 以num降序排列
STU* insert_link(STU* head, STU tmp) {
	//老规矩1、给带插入的节点申请堆区空间
	STU* pi = (STU*)calloc(1, sizeof(STU));
	if (pi == NULL) {
		perror("calloc");
		//打印错误信息
		return head;
	}
	//2、给申请的结构空间节点赋值（将tmp的内容 赋值给 *pi）
	*pi = tmp;
	pi->next = NULL;

//3、将申请的结构空间节点插入（链表节点pi的插入）
	if (head == NULL)
	{
		//链表不存在
		head = pi;
	}
	else{
		//链表存在
		//a、寻找插入点
		STU* pb = head, * pf = head;
		while (pb->num < pi->num && pb->next != NULL)
		{
			pf = pb;
			pb = pb->next;
		}
		//b、插入点的判断
		if (pb->num >= pi->num)
		{
			//头部 or 中部插入
			if (pb == head)
			{
				//头部插入
				pi->next = head;
				head = pi;
			}
			else {
				//中部插入
				pf->next = pi;
				pi->next = pb;
			}
		}
		else {
			//尾部插入
			pb->next = pi;
		}

}
	return head;
}
```

* 还是老样子修改link.c里面的函数
* 有序插入的难点在于判断

![打印结果](https://blog.fivk.cn/usr/uploads/2021/01/1729677935.png)

最后修改：2021 年 03 月 14 日