数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解

2024-09-09 836

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。

单链表理论知识详解

1.单链表的定义

线性表的链式存储.
优点:不要求大片连续空间,改变容量方便
缺点:不可随机存取,要耗费一定空间存放指针

typedef struct LNode{
   
    int data;
    struct LNode *next;
}LNode, *LinkList;

typedef 取别名
将struct LNode 取别名为别的，方便书写
比如我们要声明一个该结构体的时候
由原先的struct LNode a; 可以直接写为LNode a;
由原先的struct LNode *p; 可以直接写为LinkList a;

2.单链表的初始化

带头结点的初始化,头结点就是多一个结点,指向第一个存放数据的结点.
不带头结点,会使处理数据的逻辑更复杂,对==空表和非空表需要不同的代码逻辑==.
单链表的初始化本质:为头结点分配一个堆空间,将头结点指针域置为空,加上判断内存是否能分配

#include <stdio.h>
#include <stdlib.h>
//这是带有头结点的单链表初始化
void InitList() {
   
    LinkList L;//定义头指针变量 
    L=(LNode*)malloc(sizeof(LNode));//头指针指向分配的头结点内存空间 
    L->next=NULL;
    return true;
}
int main()
{
   
    InitList( );
}

3.单链表的插入和删除

3.1 单链表的插入

3.1.1 按位序插入

按位序插入,比如说有5个元素,插入到第三个元素的位置
注意在有头结点时,位序5,意味着是结点6
假如我们要插入的位序是3,意味着我们要寻找的是位序2,也就是结点3,当j=i-1时我们跳出循环,先操作,后j++,j代表当前结点值从0开始,也就是我们在j=3的时候应该跳出循环,所以先操作,后j++,就是j<i-1,j=i的时候就跳出循环

传入什么? 表+插入位置+插入的值
分为几步?
首先是非法操作的判断,是否合法.
第二步是,寻找要插入的位置,插入第几个位置,就找到他前一个位置即i-1,让此时的指针p落在该点处,即我们可以操作他的next域
第三步,先判断吐过p指向空,插入操作不合法,若合法,分配堆空间给一个新的结点s,s的数据域是传入值e,s的指针域指向原先的i(i-1的next域,即p当前的next域),然后将i-1的next域指向新的i

核心思想：先连后断

bool ListInsert(LinkList L,int i,int e)
{
   
    if(i<1)
        return false;
    LNode *p=L;  //为什么需要p指针,因为我们不能动表头指针
    int j=0;    //用来判断当前指针在第几个结点处,j=0,意思是在头结点处
    while(p!=NULL&&j<i-1) //P不能为空,为空咋插入啊,操作不合法,i=j的时候跳出循环
    {
   
        p=p->next; 
        j++; 
    }    //通过这个循环，我们就能找到A的指向B的next域，在他俩中间插入C
    if(p==NULL)
        return false;  //上个循环判断它是否为空，为空不执行，为空的具体操作写在了这，为空就结束
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true; 
}

3.1.2 在指定结点的前后插入

一.后插操作

分两步
判断操作是否合法(p指针是否为空+s是否能分配)
插入元素操作

InsertNextNode(LNode *p,int e)
{
   
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));    
    if(s==NULL)
        return false;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true; 
}

二.前插操作

前插操作我们这里不讨论从前遍历一遍,到最后的那种方法
而是考虑,用后插法再交换他们的数据域这种形式可以将时间复杂度降低到o(1)

bool InsertPriorNode(LNode *p,int e)
{
   
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));    
    if(s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true; 
}

4.单链表的删除

4.1 按位序删除

第一步与之前的查找的相同的,现查找位序-1的点
然后再进行删除操作

bool ListDelete(LinkList L,int i,int &e)
{
   
    if(i<1)
        return false;
    LNode *p=L;  //为什么需要p指针,因为我们不能动L头指针
    int j=0;  //用来判断当前指针在第几个结点处,j=0,意思是在头结点处
    while(p!=NULL&&j<i-1) //P不能为空,为空咋插入啊,操作不合法,i=j的时候跳出循环
    {
   
        p=p->next; 
        j++; 
    } 
    if(p==NULL) 
        return false;
    if(p->next==NULL) 
        return false;
    LNode *q=p->next;  //方便操作搞出了一个q,直接用p也行,就是写起来不直观
    e=q->data;
    p->next=q->next;
    free(q);
    return true; 
}

4.2 指定结点的删除

指定删除结点p,我们思考,给你结点p删除它,需要找到前一个结点,但是那样做太麻烦了,不如交换指定结点和后一个结点的数据域,再删除新的后继结点

bool DeleteNode(LNode *p)
{
   
    if(p==NULL)
        return false;
    LNode *q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
    return true;
}

5.单链表的查找

5.1 按位序查找

返回值是位序结点的指针

LNode * GetElem(LinkList L,int i)
{
   
    if(i<0)
        return NULL;
    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i)
    {
   
        p=p->next;
        j++;
    }
    return p;
 }

5.2 按值查找

LNode * LocateElem(LinkList L,int e)
{
   
    LNode *p=L->next; //从第一个结点处开始查值
    while(p!=NULL&&p->data!=e)
    {
   
        p=p->next;
    }
    return p; 
}

补充一个:求表的长度

int Length(LinkList L){
   
    int len=0;  //不包括头结点 
    LNode *p=L;
    while(p->next!=NULL)
    {
   
        p=p->next;
        len++;
    }
    return len;
}

6. 单链表的建立(带头结点的建立)

单链表的建立包括了头结点的建立(初始化)

6.1 尾插法建立单链表

- 在尾插法中,LNode *s,*r=L;这个写法,其实是为了简化代码,实际上*s不需要赋值,
- 因为在接下来的代码中会给结点s分配堆空间,结点s的位置就会变成随机的,
- 实际上,我们只需要让r=L就行,声明一个s即可

声明输入值x,分配头结点,声明s和r指针
循环分配s结点再把它加入链表,再循环的输入x值
链表尾指针置空

LinkList List_Tailnsert(LinkList &L)
{
   
    int x;
    L=(LinkList)malloc(sizeof(LNode)); //初始化头结点
    LNode *s,*r=L;                     //定义上表尾指针和待随机分配的结点指针
    scanf("%d",&x);
    while(x!=9999) //输出9999表示结束
    {
   
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
     }
     r->next=NULL;
     return L; 
}

6.2 头插法建立单链表

头插法相比于尾插法,我们要把头指针置空,因为分配的头指针很可能指向神秘的空间有脏数据

LinkList List_Headlnsert(LinkList L)
{
   
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL; //初始链表头指针指向NULL
    LNode *s;
    scanf("%d",&x);
    while(x!=9999) //输出9999表示结束
    {
   
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
     }
     return L; 
}

本文完整代码

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
   
    int data;
    struct LNode *next;
}LNode ,*LinkList;

void InitList() {
   
    LinkList L;//定义头指针变量 
    L=(LNode*)malloc(sizeof(LNode));//头指针指向分配的头结点内存空间 
    L->next=NULL;
    return true;
}
bool ListInsert(LinkList L,int i,int e)
{
   
    if(i<1)
        return false;
    LNode *p=L;  //为什么需要p指针,因为我们不能动L头指针
    int j=0;  //用来判断当前指针在第几个结点处,j=0,意思是在头结点处
    while(p!=NULL&&j<i-1) //P不能为空,为空咋插入啊,操作不合法,i=j的时候跳出循环
    {
   
        p=p->next; 
        j++; 
    } 
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true; 
}

InsertNextNode(LNode *p,int e)
{
   
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));    
    if(s==NULL)
        return false;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true; 
}
bool InsertPriorNode(LNode *p,int e)
{
   
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));    
    if(s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true; 
}

bool ListDelete(LinkList L,int i,int &e)
{
   
    if(i<1)
        return false;
    LNode *p=L;  //为什么需要p指针,因为我们不能动L头指针
    int j=0;  //用来判断当前指针在第几个结点处,j=0,意思是在头结点处
    while(p!=NULL&&j<i-1) //P不能为空,为空咋插入啊,操作不合法,i=j的时候跳出循环
    {
   
        p=p->next; 
        j++; 
    } 
    if(p==NULL) 
        return false;
    if(p->next==NULL) 
        return false;
    LNode *q=p->next;  //方便操作搞出了一个q,直接用p也行,就是写起来不直观
    e=q->data;
    p->next=q->next;
    free(q);
    return true; 
}

bool DeleteNode(LNode *p)
{
   
    if(p==NULL)
        return false;
    LNode *q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
    return true;
}

LNode * GetElem(LinkList L,int i)
{
   
    if(i<0)
        return NULL;
    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i)
    {
   
        p=p->next;
        j++;
    }
    return p;
} 
LNode * LocateElem(LinkList L,int e)
{
   
    LNode *p=L->next; //从第一个结点处开始查值
    while(p!=NULL&&p->data!=e)
    {
   
        p=p->next;
    }
    return p; 
}

int Length(LinkList L){
   
    int len=0;  //不包括头结点 
    LNode *p=L;
    while(p->next!=NULL)
    {
   
        p=p->next;
        len++;
    }
    return len;
}
LinkList List_Tailnsert(LinkList L)
{
   
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%d",&x);
    while(x!=9999) //输出9999表示结束
    {
   
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
     }
     r->next=NULL;
     return L; 
}

LinkList List_Headlnsert(LinkList L)
{
   
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s;
    scanf("%d",&x);
    while(x!=9999) //输出9999表示结束
    {
   
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
     }
     return L; 
}

int main()
{
   
    InitList();
    int e=-1;
}

数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解

单链表理论知识详解

1.单链表的定义

2.单链表的初始化

3.单链表的插入和删除

3.1 单链表的插入

3.1.1 按位序插入

3.1.2 在指定结点的前后插入

一.后插操作

二.前插操作

4.单链表的删除

4.1 按位序删除

4.2 指定结点的删除

5.单链表的查找

5.1 按位序查找

5.2 按值查找

补充一个:求表的长度

6. 单链表的建立(带头结点的建立)

6.1 尾插法建立单链表

6.2 头插法建立单链表

本文完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解

单链表理论知识详解

1.单链表的定义

2.单链表的初始化

3.单链表的插入和删除

3.1 单链表的插入

3.1.1 按位序插入

3.1.2 在指定结点的前后插入

一.后插操作

二.前插操作

4.单链表的删除

4.1 按位序删除

4.2 指定结点的删除

5.单链表的查找

5.1 按位序查找

5.2 按值查找

补充一个:求表的长度

6. 单链表的建立(带头结点的建立)

6.1 尾插法建立单链表

6.2 头插法建立单链表

本文完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景