单链表相关-天翼云

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

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

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

//结点
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;
}

单链表相关

活动

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

单链表相关

单链表相关

建立单链表

前插法

后插法

任意位置插入

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

单链表查找元素(按值)

单链表的删除

单链表的销毁

相关文章

自动化测试——css元素定位

高效使用Java中的注解实现代码自动化处理

【算法】算法题-非自身以外数字的乘积

【数据结构与算法】之排序系列-有序数组的平方

链表元素分类（JAVA）

C++ 实现类似Python中format函数

如何识别和避免魔鬼数字在代码中的不良影响

Python学习笔记-列表与元组

Java中的面向对象设计原则与实践

jQuery的dom操作

作者介绍

最新文章

自动化测试——css元素定位

高效使用Java中的注解实现代码自动化处理

【算法】算法题-非自身以外数字的乘积

【数据结构与算法】之排序系列-有序数组的平方

链表元素分类（JAVA）

C++ 实现类似Python中format函数

热门文章

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

Lc27_移除元素

Lc面试题1710主要元素

React-React的写法

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

CE修改器入门：查找共享代码

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

【异常-Vue-HBuilder】写的vue的template里面的多个div只显示了一个

剑指offer之不修改数组找出重复的数字

C语言实现简易三子棋

利用eval()打造通用的checkbox全选、全部取消、反选函数升级版+3

Pytorch 学习（10）：Python Cython扩展（python pyx代码-----C 代码 ----python代码调用）

C++入门到精通——C++函数

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