• 2. 【单链表】的基本概念 + 单链表的代码实现

    文章目录

    单链表的基本概念

    ① 单链表：用 链式存储 实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。

    ② 特点：

    	优点：不要求大片连续空间，改变容量方便。
    缺点：不可随机存取，要耗费一定空间存放指针。

    • 1
    • 2

    ③ 两种实现方式：

    	【1】带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
	
	【2】不带头结点，麻烦。
	    对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑
	    对空表和非空表的处理需要用不同的代码逻辑。

    • 1
    • 2
    • 3
    • 4
    • 5


    单链表的实现

    1. 单链表的结构体

    在这里插入图片描述

    "LinkList"等价于"LNode * "前者强调这是链表，后者强调这是结点，合适的地方使用合适的名字，代码可读性更高

    2. 不带/带头结点的初始化和判断是否为空：InitList(LinkList &L)、Empty(LinkList L)

    不带头结点的单链表 ：

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

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL; //空表，暂时还没有任何结点
    return true;
}

void test(){
    LinkList L;  //声明一个指向单链表的头指针
    //初始化一个空表
    InitList(L);
    ...
}

//判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL)
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    带头结点的单链表 ：

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

// 初始化一个单链表（带头结点）
bool InitList(LinkList &L){      
    L = (LNode *)malloc(sizeof(LNode));  //分配一个头结点 
    if (L == NULL)        //内存不足，分配失败    
        return false;    
    L->next = NULL;       //头结点之后暂时还没有结点   
    return true;
}

void test(){     
    LinkList L;  //声明一个指向单链表的头指针 
    //初始化一个空表    
    InitList(L);     
    ...
}

//判断单链表是否为空
bool Empty(LinkList L){  
    if (L->next == NULL) 
        return true;     
    else             
        return false;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29


    3. 求表的长度【头结点不算】：Length(LinkList L)

    // 计算单链表的长度
int Length(LinkList L){      
    int len=0;       //统计表长  
    LNode *p = L;
    while(p->next != NULL){ 
        p = p->next;      
        len++;       
    }      
    return len;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    时间复杂度： O(n)


    4. 单链表的查找

    在这里插入图片描述

    4.1 按位查找 ：GetElem(LinkList L, int i)

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

// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){   
    if(i<0)            
        return NULL;   
    LNode *p;     
    int j=0;     
    p = L;      
    while(p!=NULL && j<i){   
        p = p->next;     
        j++;      
    }        
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    在这里插入图片描述
    时间复杂度：

    • 最好时间复杂度： O(1)
    • 最坏时间复杂度： O(n)
    • 平均时间复杂度： O(n)

    4.2 按值查找 ：LocateElem(LinkList L , ElemType e)

    // 查找数据域为e的结点指针，否则返回NULL
LNode * LocateElem(LinkList L, ElemType e){           
    LNode *P = L->next;     
    // 从第一个结点开始查找数据域为e的结点  
    while(p!=NULL && p->data != e){   
        p = p->next;     
    }     
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述
    时间复杂度：

    • 最好时间复杂度： O(1)
    • 最坏时间复杂度： O(n)
    • 平均时间复杂度： O(n)


    单链表的实现-简单操作
    ppt 0星 超过10%的资源 401KB
    下载

    5. 单链表的插入

    在这里插入图片描述

    5.1 指定结点的后插操作：InsertNextNode(LNode *p, ElemType e)

    在这里插入图片描述

    5.2 指定结点的前插操作：InsertPriorNode(LNode *p, ElemType e)

    思路1：如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对q进行后插操作；

    bool InsertPriorNode (LinkList L, LNode *p, ElemType e)

    • 1

    思路2：如果不传入头指针，在指定结点p后插入一个结点s，并交换两个结点所保存的数据，从而变相实现指定结点的前插操作

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

// 在结点p前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){  
    if(p==NULL)      
        return false;  
    LNode *s = (LNode *)malloc(sizeof(LNode));  
    // 内存不足分配失败       
    if(s==NULL)       
        return false;    
    // 将s插入结点p之后    
    s->next = p->next;   
    p->next = s;       
    // 交换两个结点中的数据  
    s->data = p->data;   
    p->data = e;       
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    5.3 按位序插入：ListInsert(LinkList &L, int i, ElemType e)

    在这里插入图片描述

    ① 带头结点

    在这里插入图片描述
    把前面的函数用上：
    在这里插入图片描述

    ② 不带头结点

    在这里插入图片描述


    6. 单链表的删除

    6.1 按位序删除 ：ListDelete(LinkList &L, int i, ElemType &e)

    单链表的C++实现。。
    text/x-c 0星 超过10%的资源 6KB
    下载

    思路：如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对p进行删除操作

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

// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList &L, int i, ElemType &e){      
    if(i<1)             
        return false;     
    LNode *p;       //指针p指向当前扫描到的结点     
    int j=0;        //当前p指向的是第几个结点    
    p = L;         
    //循环找到第i-1个结点     
    while(p!=NULL && j<i-1){   
        //如果i>lengh，p和p的后继结点会等于NULL        
        p = p->next;            
        j++;      
    }       
    if(p==NULL)       
        return false;    
    if(p->next == NULL)        
        return false;    	   
    //令q暂时保存被删除的结点   
    LNode *q = p->next;    
    e = q->data;     
    p->next = q->next;      
    free(q)     
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    时间复杂度：

    • 最好时间复杂度： O(1)
    • 最坏时间复杂度： O(n)
    • 平均时间复杂度： O(n)

    6.2 删除指定结点 ：DeleteNode(LNode *p)

    思路：
    如果不传入头指针，可以把指定结点p的后继结点q删除，
    并使结点p保存结点q存储的数据，从而变相实现删除指定结点的操作。
    但是 如果指定结点p没有后继结点，这么做会报错

    在这里插入图片描述

    // 删除指定结点p
bool DeleteNode(LNode *p){   
    if(p==NULL)           
        return false;     
    LNode *q = p->next; // 令q指向p的后继结点  
    // 如果p是最后一个结点，则q指向NULL，继续执行就会报错  
    p->data = q->data;  
    p->next = q->next;   
    free(q);    
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    时间复杂度： O(1)


    7. 单链表的建立

    7.1 尾插法建立单链表 ：List_TailInsert(LinkList &L)

    // 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){   
    int x;			//设ElemType为整型int  
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)     
    LNode *s, *r = L;                        //r为表尾指针    
    scanf("%d", &x);                         //输入要插入的结点的值   
    while(x!=9999){                          //输入9999表示结束     
        s = (LNode *)malloc(sizeof(LNode));    
        s->data = x;           
        r->next = s;           
        r = s;                               //r指针指向新的表尾结点     
        scanf("%d", &x);       
    }    
    r->next = NULL;                          //尾结点指针置空      
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    时间复杂度： O(n)

    7.2 头插法建立单链表 ：List_HeadInsert(LinkList &L)

    LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表   
    LNode *s;      
    int x;     
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点   
    L->next = NULL;                          //初始为空链表,这步很关键  
    scanf("%d", &x);                         //输入要插入的结点的值  
    while(x!=9999){                          //输入9999表结束     
        s = (LNode *)malloc(sizeof(LNode)); 
        s->data = x;          
        s->next = L->next;      
        L->next = s;          
        //将新结点插入表中，L为头指针   
        scanf("%d", &x);       
    }     
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    时间复杂度： O(n)

    7.3 重难点：头插法实现链表的逆置 ——Inverse(LNode *L)

    // 将链表L中的数据逆置并返回
LNode *Inverse(LinkList L){	
    LNode *p, *r;	  
    p = L->next;     //p指针指向第一个结点	  
    L->next = NULL;  //断链   
    // 依次判断p结点中的数据并采用头插法插到L链表中	
    while (p != NULL){		   
      r=p->next;
      p->next=L->next;
      L->next=p;
      p=r;      
    }	   
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    在这里插入图片描述
    具体解释详见：单链表逆置图解

  • 相关阅读:
    国内最牛的Java面试八股文合集，不接受反驳 我这该死的魅力
    六石管理学：水平不高，照抄就好
    【Java入门每日一练】使用DFS深度优先遍历文件夹
    MySql学习笔记05——DML
    Python新特性
    python手柄pygame joystick文档
    VSCode中使用github
    JVS私有化部署启动失败处理方案
    AD知识总结
    Hadoop入门（四）：SSH免密登录 配置
  • 原文地址：https://blog.csdn.net/weixin_42214698/article/details/126155237