C语言——链表的插入(头、尾、有序插入)

曾经终败给现在 2023-01-18 11:26 65阅读 0赞

## **1、头部插入** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzM5MTk1Nw_size_16_color_FFFFFF_t_70]

//在链表的头部之前 插入
    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;
    		//return head;
    	}
    	else//链表存在（头部之前插入）
    	{ 
    		//1、让pi 指向就的头
    		pi->next = head;
    
    		//2、head指向新的头节点
    		head = pi;
    
    		//return head;
    	}
    
    	return head;
    }

## **2、尾部插入** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzM5MTk1Nw_size_16_color_FFFFFF_t_70 1]

//链表的尾部插入
    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、将节点插入到链表的尾部
    	if(head == NULL)//链表不存在
    	{ 
    		head = pi;
    		return head;
    	}
    	else//链表存在
    	{ 
    		//a、寻找链表的尾节点
    		STU *pb = head;
    		while(pb->next != NULL)//如果不是尾节点
    			pb = pb->next;//pb就指向下一个节点
    
    		//b、用尾结点 pb 链接上 插入的节点pi
    		pb->next = pi;
    		return head;
    	}
    
    	return head;
    }

## **3、有序插入(从小->大)：** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzM5MTk1Nw_size_16_color_FFFFFF_t_70 2]

//链表的有序插入 以num的顺序为准（小--->大）
    STU* insert_link(STU *head, STU tmp)
    { 
    	//1、给待插入的节点pi 申请 堆区空间
    	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;
    		return head;
    	}
    	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)//头部 中部插入
    		{ 
    			if(pb == head)//头部之前插入
    			{ 
    				pi->next = head;
    				head = pi;
    				return head;
    			}
    			else//中部插入
    			{ 
    				pf->next = pi;
    				pi->next = pb;
    				return head;
    			}
    		}
    		else//尾部插入
    		{ 
    			pb->next = pi;
    			return head;
    		}
    	}
    	return head;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzM5MTk1Nw_size_16_color_FFFFFF_t_70]: /images/20221021/756478144e624d5aa271b1c9a7ab6973.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzM5MTk1Nw_size_16_color_FFFFFF_t_70 1]: /images/20221021/60fa300ac7914f66b47f6aa2f2ff74c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzM5MTk1Nw_size_16_color_FFFFFF_t_70 2]: /images/20221021/14e3834bf333435b89eb3f03619824b7.png