单链表相关-天翼云

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

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

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

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

单链表相关

活动

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

单链表相关

单链表相关

建立单链表

前插法

后插法

任意位置插入

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

单链表查找元素(按值)

单链表的删除

单链表的销毁

相关文章

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

Java中的方法重写详解

面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集

这么多数组方法，你掌握了么？

驼峰命名规范的实际应用及其对代码可读性的影响

线程不推荐的方法与守护线程

什么是软件设计模式， 它们⽤于解决什么问题， 它们为什么有效

面向对象函数设计方法论

MFC Ribbon定制方法一则

线程函数和线程启动的几种不同形式

作者介绍

最新文章

Java中的方法重写详解

面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集

这么多数组方法，你掌握了么？

驼峰命名规范的实际应用及其对代码可读性的影响

线程不推荐的方法与守护线程

什么是软件设计模式， 它们⽤于解决什么问题， 它们为什么有效

热门文章

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

Lc27_移除元素

Lc面试题1710主要元素

React-React的写法

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

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

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

xml名称空间

基于“ViewHolder”技术提升Android ListView中Item View加载效率

设计模式_单例模式

ios开发之--系统控件显示中文

Thrift 资源清理代码剖析

详细分析Redis常用命令（图文）

面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之二分 + 哈希表 + 堆 + 优先队列合集

什么是软件设计模式，它们⽤于解决什么问题，它们为什么有效

面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之二分 + 哈希表 + 堆 + 优先队列合集

什么是软件设计模式，它们⽤于解决什么问题，它们为什么有效

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