【数据结构】单链表的插入和删除

我不是女神ヾ 2023-02-20 13:32 40阅读 0赞

### 单链表、循环链表的插入和删除 ###

*  单链表的插入
 *   *  在不带头结点的单链表中插入
     *   *  在表首插入无前驱结点
         *  其他位置插入有前驱结点
     *  在带头结点的单链表中插入
     *  插入部分代码实现
 *  单链表的删除
 *   *  在不带头结点的单链表中删除
     *   *  删除首元结点
         *  删除其他位置元素
     *  在带头结点的单链表中删除
     *  删除部分代码实现

# 单链表的插入 #

## 在不带头结点的单链表中插入 ##

### 在表首插入无前驱结点 ###

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

### 其他位置插入有前驱结点 ###

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

## 在带头结点的单链表中插入 ##

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

## 插入部分代码实现 ##

status  ListInsert( LinkList &L, int i, ElemType e){
        
    //在带头结点的单链表L中第i个位置之前插入元素e，1≤ i≤表长+1
    	p=L; j=0;
    	while( p&&j<i-1 ) {
         p=p->next; j++; } 	//顺指针找第i-1个结点
    	if( !p || j>i-1 )	return ERROR; 		//i大于表长加1或i小于1
    	s=new LNode; 	//生成新结点
    	s->data=e;
    	s->next=p->next; 	//插入L中
    	p->next=s;
    	return OK;
    } //ListInsert

# 单链表的删除 #

## 在不带头结点的单链表中删除 ##

### 删除首元结点 ###

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

### 删除其他位置元素 ###

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

## 在带头结点的单链表中删除 ##

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

## 删除部分代码实现 ##

status  ListDelete(LinkList &L, int i, ElemType &e) {
        
    //在带头结点的单链表L中，删除第i个元素，并用e返回其值
    	p=L;     j=0;
    	while( p->next && j<i-1 ) {
        p=p->next; j++;} //顺指针找第i-1个结点
    	if( !(p->next) || j>i-1 ) return ERROR; 	//i小于1或i大于表长
    	q=p->next; 	//q指向第i个结点
    	p->next=q->next; 
    	e=q->data;
    	free(q);  	//释放所删结点的空间
    	return OK;
    } //ListDelete

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627155450941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200627160230407.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200627160518404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200627161058877.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200627161413840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200627161557588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70