单链表相关-天翼云

单链表相关

2024-10-14 06:56:05 阅读次数：31

链表不同于顺序表，顺序表底层采用数组作为存储容器，需要分配一块连续且完整的内存空间进行使用，而链表则不需要，它通过一个指针来连接各个分散的结点，形成了一个链状的结构，每个结点存放一个元素，以及一个指向下一个结点的指针，通过这样一个一个相连，最后形成了链表。它不需要申请连续的空间，只需要按照顺序连接即可，虽然物理上可能不相邻，但是在逻辑上依然是每个元素相邻存放的，这样的结构叫做链表（单链表）。

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

//结点
struct LNode{
//    数据域
    int data;
//    指针域
    struct LNode *next;
};



typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, LinkList;//LinkList为指向结构体LNode的指针

等价于
typedef struct LNode LNode;
typedef struct LNode LinkList;

建立单链表

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


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


bool InitList(LinkList* &L){
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if(!L){
        return false;
    } else{
        L->next = NULL;
        return true;
    }
}

int main(){
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    return 0;
}

前插法

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


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


bool InitList(LinkList* &L){
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if(!L){
        return false;
    } else{
        L->next = NULL;
        return true;
    }
}

bool FrontInsertList(LinkList* &L, LNode *node){
//    合法性校验
    if(!L || !node){
        return false;
    } else{
        node->next = L->next;
        L->next = node;
        return true;
    }
}

void DisplayList(LinkList* &L){
    if(!L){
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p){
        printf("%d,", p->data);
        p = p->next;
    }

}


int main(){
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
//    用前插法插入数据,我这里指定30个
    int num = 30;
    while (num > 0){
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        FrontInsertList(L, s);
        num--;
    }
//    输出链表
    DisplayList(L);
    return 0;
}

我这里是30到1的顺序，而结果是1到30说明确实是前插法

单链表相关

后插法

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


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


bool InitList(LinkList* &L){
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if(!L){
        return false;
    } else{
        L->next = NULL;
        return true;
    }
}


bool RearInserList(LinkList* &L, LNode *node){
    LinkList *last = NULL;
    if(!L || !node){
        return false;
    }
//    首先指向头结点
    last = L;
    while (last->next != NULL) {
        last = last->next;
    }
    node->next = NULL;
    last->next = node;
    return true;
}


void DisplayList(LinkList* &L){
    if(!L){
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p){
        printf("%d,", p->data);
        p = p->next;
    }

}


int main(){
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    //    后插法
    int num = 30;
    while (num > 0){
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        RearInserList(L, s);
        num--;
    }
//    输出链表
    DisplayList(L);



    return 0;
}

任意位置插入

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


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


bool InitList(LinkList *&L) {
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if (!L) {
        return false;
    } else {
        L->next = NULL;
        return true;
    }
}


bool RearInserList(LinkList *&L, LNode *node) {
    LinkList *last = NULL;
    if (!L || !node) {
        return false;
    }
//    首先指向头结点
    last = L;
    while (last->next != NULL) {
        last = last->next;
    }
    node->next = NULL;
    last->next = node;
    return true;
}

bool InsertLink(LinkList *&L, int pos, int value) {
    if (!L) {
        return false;
    }
    int j = 0;
    LinkList *p, *s;
//    p为当前节点
    p = L;
    while (p && j < pos - 1) {
        p = p->next;
        j++;
    }
    if (!p && j > pos - 1) {
        return false;
    }
//    生成新节点
    s = new LNode;
    s->next = p->next;
    p->next = s;
    s->data = value;
    return true;
}


void DisplayList(LinkList *&L) {
    if (!L) {
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p) {
        printf("%d,", p->data);
        p = p->next;
    }

}


int main() {
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    int num = 30;
    while (num > 0) {
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        RearInserList(L, s);
        num--;
    }
    //    任意位置的插入演示,第6个元素，插入555
    int pos = 6, value = 555;
    if(InsertLink(L, pos, value)){
        printf("成功!\n");
    } else{
        printf("失败\n");
    }
    DisplayList(L);
    return 0;
}

单链表相关

单链表获取元素（按索引）

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


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


bool InitList(LinkList *&L) {
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if (!L) {
        return false;
    } else {
        L->next = NULL;
        return true;
    }
}


bool RearInserList(LinkList *&L, LNode *node) {
    LinkList *last = NULL;
    if (!L || !node) {
        return false;
    }
//    首先指向头结点
    last = L;
    while (last->next != NULL) {
        last = last->next;
    }
    node->next = NULL;
    last->next = node;
    return true;
}


void DisplayList(LinkList *&L) {
    if (!L) {
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p) {
        printf("%d,", p->data);
        p = p->next;
    }

}


bool GetElem(LinkList* &L, int pos, int &value){
//    查找第pos个元素，其值为value
    int index = 1;
    LinkList *p;
//    链表为空，或者未存有元素
    if(!L || !L->next){
        return false;
    }
    p = L->next;
//    依次往后查询,p不为空，index=pos
    while (p && index < pos){
        p = p->next;
        index++;
    }
//    pos不合法为负或者大于length
    if(!p || index > pos){
        return false;
    }
    value = p->data;
    return true;
}


int main() {
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    int num = 30;
    while (num > 0) {
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        RearInserList(L, s);
        num--;
    }
    //    任意位置的插入演示,第6个元素，插入555
    int pos = 3, value = 0;
//    int pos = -3, value = 0;
    if(GetElem(L, pos, value))
    {
        printf("获取成功!,值为%d\n", value);
    } else{
        printf("获取失败\n");
    }
    DisplayList(L);
    return 0;
}

单链表相关

单链表查找元素(按值)

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


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


bool InitList(LinkList *&L) {
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if (!L) {
        return false;
    } else {
        L->next = NULL;
        return true;
    }
}


bool RearInserList(LinkList *&L, LNode *node) {
    LinkList *last = NULL;
    if (!L || !node) {
        return false;
    }
//    首先指向头结点
    last = L;
    while (last->next != NULL) {
        last = last->next;
    }
    node->next = NULL;
    last->next = node;
    return true;
}


void DisplayList(LinkList *&L) {
    if (!L) {
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p) {
        printf("%d,", p->data);
        p = p->next;
    }

}

//按值查找
bool FindElem(LinkList* &L, int value, int &index){
    LinkList *p;
    index = 1;
    p = L->next;
    if(!L || !L->next){
        index = -1;
        return false;
    }
    while (p && p->data != value){
        p = p->next;
        index++;
    }
//    节点不存在
    if(!p){
        index = -1;
        return false;
    }
    return true;
}


int main() {
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    int num = 30;
    while (num > 0) {
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        RearInserList(L, s);
        num--;
    }
    int index;
    int value = 18;
    if(FindElem(L, value, index)){
        printf("%d存在,位置是%d\n", value, index);
    } else{
        printf("%d不存在\n", value);
    }
    DisplayList(L);
    return 0;
}

单链表相关

单链表的删除

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


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


bool InitList(LinkList *&L) {
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if (!L) {
        return false;
    } else {
        L->next = NULL;
        return true;
    }
}


bool RearInserList(LinkList *&L, LNode *node) {
    LinkList *last = NULL;
    if (!L || !node) {
        return false;
    }
//    首先指向头结点
    last = L;
    while (last->next != NULL) {
        last = last->next;
    }
    node->next = NULL;
    last->next = node;
    return true;
}


void DisplayList(LinkList *&L) {
    if (!L) {
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p) {
        printf("%d,", p->data);
        p = p->next;
    }

}

//删除
bool DeleteList(LinkList* &L, int pos){
    LinkList *p, *q;
    int index = 0;
    p = L;
    if(!L || !L->next){
        return false;
    }
    while (p->next != NULL && index < pos - 1){
        p = p->next;
        index++;
    }
//    p是要删除的前一个节点
    if(!p->next || index > pos - 1){
        return false;
    }
//    把删除的节点存起来
    q = p->next;
    p->next = q->next;
//    释放
    delete q;

    return true;
}


int main() {
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    int num = 30;
    while (num > 0) {
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        RearInserList(L, s);
        num--;
    }
    int pos = 5;
    if(DeletList(L, pos)){
        printf("第%d个元素删除成功!\n", pos);
    } else{
        printf("第%d个元素删除失败\n", pos);
    }
    DisplayList(L);
    return 0;
}

单链表相关

单链表的销毁

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


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


bool InitList(LinkList *&L) {
//    生成新结点作为头结点，用头指针L 指向头结点
    L = new LNode;
//    生成节点失败
    if (!L) {
        return false;
    } else {
        L->next = NULL;
        return true;
    }
}


bool RearInserList(LinkList *&L, LNode *node) {
    LinkList *last = NULL;
    if (!L || !node) {
        return false;
    }
//    首先指向头结点
    last = L;
    while (last->next != NULL) {
        last = last->next;
    }
    node->next = NULL;
    last->next = node;
    return true;
}


void DisplayList(LinkList *&L) {
    if (!L) {
        printf("链表为空!\n");
        return;
    }
    LNode *p = NULL;
    p = L->next;
    while (p) {
        printf("%d,", p->data);
        p = p->next;
    }
}

//删除
void DestroyList(LinkList* &L){
    LinkList *p;
    p = L;
    while (p){
        L = L->next;
        delete p;
        p = L;
    }
}


int main() {
    LinkList *L = NULL;
//    初始化一个链表
    InitList(L);
    int num = 30;
    while (num > 0) {
//        生成新节点
        LNode *s = new LNode;
        s->data = num;
        RearInserList(L, s);
        num--;
    }
    DestroyList(L);
    DisplayList(L);
    return 0;
}

单链表相关

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

单链表相关

单链表相关

建立单链表

前插法

后插法

任意位置插入

单链表获取元素（按索引）

单链表查找元素(按值)

单链表的删除

单链表的销毁

相关文章

【Canvas技法】辐射式多道光影的实现

复杂度的OJ练习

Redis Set集合

计算机小白的成长历程——数组（1）

【数据结构】详细介绍串的简单模式匹配——朴素模式匹配算法

webpack5基础--13_生产模式介绍

30天拿下Rust之高级类型

30天拿下Rust之向量

C++ 11新特性之tuple

30天拿下Rust之模式与模式匹配

作者介绍

最新文章

【Canvas技法】辐射式多道光影的实现

复杂度的OJ练习

Redis Set集合

【数据结构】详细介绍串的简单模式匹配——朴素模式匹配算法

webpack5基础--13_生产模式介绍

30天拿下Rust之高级类型

热门文章

python学习（6）——列表元素的添加、删除、修改及排序

Lc27_移除元素

Lc面试题1710主要元素

React-React的写法

XML简介

一文读懂css【css3】绝对（absolute）定位和相对（relative）定位 相对定位是相对谁定位的 绝对定位又是根据谁绝对定位的 子绝父相 包含块

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

Linux源码阅读笔记13-进程通信组件中

最高频率的 ID

动态圣诞树html网页完整代码

基于Opencv4.2的车牌识别(C++语言版本)

C++从入门到精通——文件和流

Github在线解决代码冲突（图文并茂）

一文读懂css【css3】绝对（absolute）定位和相对（relative）定位相对定位是相对谁定位的绝对定位又是根据谁绝对定位的子绝父相包含块