单链表的增删改查

一、带头结点

1️⃣创建

本文代码创建部分使用的是带头结点的尾插法，若想要使用其他的方法，可查看单链表之头插法和尾插法

❗❗ 重点一：以尾插法实现单链表的创建

  1. 动图解析
    请添加图片描述
  2. 图解
    在这里插入图片描述
  3. 代码
    LinkList TailInster(LinkList &L,int n){
	int x=1;
	L= (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	while(x!=n){
   		s=(LNode*) malloc(sizeof(LNode));
   		s->data=x;
  	 	r->next=s;
   		r=s;
   		x++;
	}
	r->next=NULL;
	return L;
}

2️⃣查——查找某个结点

  1. 查找分为两种方式：
    💡按序号查找
    💡按值查找
  2. 基本思想
    单链表是的元素是离散的分布在存储空间，所以不能直接找到表中某个特定的结点，查找时，需要从表头开始遍历

在这里插入图片描述

❗❗ 重点二：按序号查找结点（例子：找序号为2的结点）

  1. 图解
    在这里插入图片描述
  2. 代码解析
    • 💡j的作用 ：结束while循环，返回对应结点，j表示目前指针p位于第几个结点的位置，用j==i来结束while循环（j==0表示，p指向头结点）
      在这里插入图片描述
    • 💡p==Null的情况：不存在该结点，指针p遍历到了链尾，也没有找到对应的序号。
      在这里插入图片描述
  3. 代码
    /*查找——按序*/
LNode* GetElem(LinkList L,int i){       //i——序号
	if (i<1) return NULL;
	LNode *p;                          
	int j=0;                            
	p=L;
	while(p!=NULL&&j<i){
    	p=p->next;
    	j++;
	}
	return p;
}

❗❗ 重点三：按值查找结点

图解和解析参考重点二，
与按值查找相比，只是在循环条件中将j<i改成了p->data!=e

  1. 代码
    /*查找——按值*/
int LocateElem(LinkList L,ElemType e){
	int i=0;
   	LNode *p=L->next;
	while (p!=NULL&&p->data!=e){
 		p=p->next;
 		i++;
	}
	if (i!=0)i++;
	return i;
}

2.部分代码解析

  • i的初值为什么设置成0❓
    i的作用主要是记录结点的位置，当i==0时，就代表该结点不存在。

3️⃣增——插入结点

插入结点的原理类似于头插法

  1. 基本思想
    找到要插入的位置的前一个位置（i-1），插入结点
  2. 图解(4 5 顺序不可以调换呦)
    在这里插入图片描述
  3. 代码
       /*增加--插入*/
   bool ListInster(LinkList &L,int i,ElemType e){
   	LNode *p= GetElem(L,i-1);		//找到i结点的前一个结点
   	if (p==NULL)return false;
   	LNode *s=(LNode*) malloc(sizeof(LNode));
   	s->data=e;
   	s->next=p->next;
   	p->next=s;
   	return true;
   }

4️⃣删——删除结点

删除时，也要找到被删除位置的前一个结点。

  1. 图解
    在这里插入图片描述
  2. 代码
    /*删除*/
bool ListDelete(LinkList &L,int i,ElemType &e){
 	LNode *p= GetElem(L,i-1);
	if (p==NULL)return false;
	LNode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
}
  • 💡e的作用：用来记录被删除的结点的值域

5️⃣改——修改结点

只要找到要修改结点的结点，将其值换成要修改的值就可以啦

/*修改*/
bool UpgreatList(LinkList &L,int i,ElemType e){
    LNode *p= GetElem(L,i);
    if (p==NULL)return false;
    p->data=e;
    return true;
}

6️⃣求表长

求表长的本质也是一种遍历

  • 💡s的作用：通过s从表头遍历到表尾(s==null)，获得表长
  • 💡x的作用：记录表长
/*求表长*/
int Length(LinkList L){
    int x=0;
    LNode *s=L->next;//指向首元结点，以免将头结点算在表长中
    while (s!=NULL){
        x++;
        s=s->next;
    }
    return x;
}

7️⃣完整代码

#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;
typedef struct LNode{
    ElemType data;           //数据域
    struct LNode *next;      //指针域
}LNode,*LinkList;

/*尾插*/
LinkList CreateTail(LinkList &L,int n){
    int x=1;
    L= (LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    while(x<=n){
        s=(LNode*) malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        x++;
    }
    r->next=NULL;
    return L;
}

/*查找——按序*/
LNode* GetElem(LinkList L,int i){       //i——序号
    if (i<1) return NULL;
    LNode *p;                           //指针p当前扫描到的结点
    int j=0;                            //当前p指向的是第几个结点，0表示头结点
    p=L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

/*查找——按值*/
int LocateElem(LinkList L,ElemType e){
    int i=0;
    LNode *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
        i++;
    }
    if (i!=0)i++;
    return i;
}

/*增加--插入*/
bool ListInster(LinkList &L,int i,ElemType e){
    LNode *p= GetElem(L,i-1);
    if (p==NULL)return false;
    LNode *s=(LNode*) malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

/*修改*/
bool UpgreatList(LinkList &L,int i,ElemType e){
    LNode *p= GetElem(L,i);
    if (p==NULL)return false;
    p->data=e;
    return true;
}

/*删除*/
bool ListDelete(LinkList &L,int i,ElemType &e){
    LNode *p= GetElem(L,i-1);
    if (p==NULL)return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

/*求表长*/
int Length(LinkList L){
    int x=0;
    LNode *s=L->next;
    while (s!=NULL){
        x++;
        s=s->next;
    }
    return x;
}

/*便利*/
void PrintList(LinkList L){
    LNode *s;
    s=L->next;
    while (s!=NULL) {
        printf("%d  ",s->data);
        s=s->next;
    }
}
int main(){
    LinkList L;
    printf("建立：");
    CreateTail(L,10);
    printf("\n建立后的链表：");
    PrintList(L);

    //求表长
    printf("\n\n求表长：");
    printf("\n表长为：%d",Length(L));

    //查找
    printf("\n\n求查询：");
    LNode *p=GetElem(L,3);
    if (p==NULL)printf("所找位置不存在！！");
    else printf("\n第三个位置的元素是：%d",p->data);
    printf("\n元素为5的结点在第%d个位置", LocateElem(L,5));

    //插入
    printf("\n\n插入：");
    if(ListInster(L,5,11)){
        printf("\n插入成功后的链表为：");
        PrintList(L);
    }else{
        printf("\n插入失败");
    }

    //修改
    printf("\n\n修改：");
    if(UpgreatList(L,5,5)){
        printf("\n修改成功后的链表为：");
        PrintList(L);
    }else{
        printf("\n修改失败");
    }

    //删除
    printf("\n\n删除：");
    ElemType  e;
    if(ListDelete(L,5,e)){
        printf("\n修改成功后的链表为：");
        PrintList(L);
        printf("\n删除的值为：%d",e);
    }else{
        printf("\n修改失败");
    }

}

运行结果

在这里插入图片描述

二、不带头结点

在这里插入图片描述
只要注意在新建结点(例：s)时，s的指向是L(无头结点)还是L->next(有头结点)，其他可以参照带头结点的图。

代码

#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;
typedef struct LNode{
    ElemType data;           //数据域
    struct LNode *next;      //指针域
}LNode,*LinkList;

/*尾插*/
LinkList CreateTail(LinkList &L,int n){
    int x=1;
    L= (LinkList)malloc(sizeof(LNode));
    L->data=x++;
    LNode *s,*r=L;
    while(x<=n){
        s=(LNode*) malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        x++;
    }
    r->next=NULL;
    return L;
}

/*查找——按序*/
LNode* GetElem(LinkList L,int i){       //i——序号
    if (i<1) return NULL;
    LNode *p;                           //指针p当前扫描到的结点
    int j=1;                            //当前p指向的是第几个结点，0表示头结点
    p=L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

/*查找——按值*/
int LocateElem(LinkList L,ElemType e){
    int i=0;
    LNode *p=L;
    while (p!=NULL&&p->data!=e){
        p=p->next;
        i++;
    }
    if (i!=0)i++;
    return i;
}

/*增加--插入*/
bool ListInster(LinkList &L,int i,ElemType e){
    LNode *p= GetElem(L,i-1);
    if (p==NULL)return false;
    LNode *s=(LNode*) malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

/*修改*/
bool UpgreatList(LinkList &L,int i,ElemType e){
    LNode *p= GetElem(L,i-1);
    if (p==NULL)return false;
    p->next->data=e;
    return true;
}

/*删除*/
bool ListDelete(LinkList &L,int i,ElemType &e){
    LNode *p= GetElem(L,i-1);
    if (p==NULL)return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

/*求表长*/
int Length(LinkList L){
    int x=0;
    LNode *s=L;
    while (s!=NULL){
        x++;
        s=s->next;
    }
    return x;
}

/*便利*/
void PrintList(LinkList L){
    LNode *s;
    s=L;
    while (s!=NULL) {
        printf("%d  ",s->data);
        s=s->next;
    }
}
int main(){
    LinkList L;
    CreateTail(L,10);
    printf("建立后的链表：");
    PrintList(L);

    //求表长
    printf("\n表长为：%d",Length(L));

    //查找
    printf("\n第三个位置的元素是：%d",GetElem(L,3)->data);
    printf("\n元素为5的结点在第%d个位置", LocateElem(L,5));

    //插入
    if(ListInster(L,5,11)){
        printf("\n插入成功后的链表为：");
        PrintList(L);
    }else{
        printf("\n插入失败");
    }

    //修改
    if(UpgreatList(L,5,5)){
        printf("\n修改成功后的链表为：");
        PrintList(L);
    }else{
        printf("\n修改失败");
    }

    //删除
    ElemType  e;
    if(ListDelete(L,5,e)){
        printf("\n修改成功后的链表为：");
        PrintList(L);
        printf("\n删除的值为：%d",e);
    }else{
        printf("\n修改失败");
    }

}

运行截图

在这里插入图片描述

# 链表 # 数据结构 # c语言
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

开源成为金融领域创新发展的新动力引擎

开源成为金融领域创新发展的新动力引擎

avatar 开放原子开发者工作坊

开源成为推动城市数字化转型的核心动力

城市，不仅是人们工作与生活的基本载体，更是承载着亿万人民的希望与梦想。近年来，我国智慧城市建设如火如荼，开源技术的深度融合为其发展注入了新的活力。在民生、环保、公共安全、城市服务等多个领域，开源技术的应用不仅为民众带来了切实的便捷，而且促进了政府决策的科学化，显著提升了城市综合治理能力。

avatar 开放原子开发者工作坊

OpenLoong项目通过技术监督委员会（TOC）评审

OpenLoong项目通过技术监督委员会（TOC）评审

avatar 开放原子开发者工作坊