链表

Suzhou
• 阅读 68

线性表的链式存储实现称为链表。 链表 每一个节点都需要一个结构体变量存储。 前一个节点的指针域指向下一个节点的数据域起始位置。 最后一个节点的指针域内存储的是NULL(即0)。 链表 ::: tip 为了简单,考研设计时,单链表都会包含头节点,业界不使用。 头指针L指向的空间称为头节点,认为是0号位置,a1称为第一个节点。考研时认为头节点的数据域为空。 列表为空表示a1-an不存在。 ::: 链表的初始化插入: 链表 如下图,插入时的新节点q需要使用malloc申请一个结构体大小的空间(sizeof(LNode)),再强转成结构体指针的类型链表 上图中,q->data为数据域,q->next为指针域。p->next为第一个节点a1的地址,保存在头节点p中。 链表的删除、查询: 链表 上图中的第一二行代码作用是确定p和q节点的位置,i为删除位置, ::: warning 每一个节点的空间都是malloc出来的,删除节点后必须free。 ::: 链表 上图中while循环中的p用来控制是否遍历到列表的尾部(最后一个元素的指针域是NULL) 链表 ::: tip while循环中的p!=NULL和p等价。 :::


头插法新建链表

头插法是每次新增节点时从头节点后的位置插入链表。 流程如下: 链表 头插法代码:

#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LNode
{
    Elemtype data;
    struct LNode* next;
}LNode,*LinkList;
//LNode*是结构体指针,等同于LinkList,写*LinkList只是为了方便认为是链表而非结构体节点指针

//void list_head_insert(LNode* &L)
//{
//    L = (LinkList)malloc(sizeof(LNode));  //申请头节点空间(头指针指向头节点)
//    //malloc开辟的空间默认是void类型,上述代码中LinkList可以换成LNode*
//    Elemtype x;  //读取的元素值放在第一个节点上(头节点是空的),需要再申请一个节点
//    L->next = NULL;
//    scanf("%d", &x);
//    //申请第一个节点空间
//    LNode* s = (LinkList)malloc(sizeof(LNode));
//    s->data = x;
//    s->next = NULL;  //头插法中第一个创建的节点会变为最后一个节点,需要将next设置成NULL
//    L->next = s;  //使得L的next(指针域)指向第一个节点
//    while (x!=9999)
//    {
//        scanf("%d", &x);
//        s = (LinkList)malloc(sizeof(LNode));  //s指向新开辟的节点
//        s->data = x;
//        s->next = L->next;  //新节点的next值为头节点L的next,即指向上一个创建的节点
//        L->next = s;  //头节点的next指向新建的节点
//    }
//}

//上述函数在插入节点时会插入最后一个作为结束标志的9999的数据,函数改进如下:
void list_head_insert(LNode*& L)
{
    L = (LinkList)malloc(sizeof(LNode));  //申请头节点空间(头指针指向头节点)
    //malloc开辟的空间默认是void类型,上述代码中LinkList可以换成LNode*
    Elemtype x;  //读取的元素值放在第一个节点上(头节点是空的),需要再申请一个节点
    L->next = NULL;  //循环中将L的next赋给第一次循环创建的节点的next,即链表最后一个节点
    scanf("%d", &x);  //供while循环判断是否结束
    //申请第一个节点空间
    LNode* s = (LinkList)malloc(sizeof(LNode));
    while (x != 9999)
    {
        s = (LinkList)malloc(sizeof(LNode));  //s指向新开辟的节点
        s->data = x;
        s->next = L->next;  //新节点的next值为头节点L的next,即指向上一个创建的节点
        L->next = s;  //头节点的next指向新建的节点(头插法新建的节点在头节点后面一个位置)
        scanf("%d", &x);
    }
}

void print_list(LinkList L)
{
    L = L->next;
    while (L != NULL)
    {
        printf("%3d", L->data);
        L = L->next;
    }
}
int main()
{
    LinkList L;  //等同于LNode* L
    list_head_insert(L);
    print_list(L);
    return 0;
}

尾插法新建链表

流程如下: 链表


链表的增删查改操作:

//输入9999表示输入结束
#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LNode
{
    Elemtype data;
    struct LNode* next;
}LNode, * Linklist;
//尾插法插入
void list_tail_insert(Linklist& L)
{
    L = (LNode*)malloc(sizeof(LNode));  //头节点
    L->next = NULL;
    LNode* s, * r = L;  //r->next=NULL;
    Elemtype x;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode*)malloc(sizeof(LNode));
        r->next = s;
        s->data = x;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
}
//节点查找
LNode* value_find(LNode* L,Elemtype x)
{
    Elemtype a = 0;
    if (x < 0)
    {
        return NULL;
    }
    while (L && a < x)
    {
        L = L->next;
        a++;
    }
    /*printf("%d\n", L->data);*/
    return L;
}
//值插入
bool value_insert(LNode* L, Elemtype x, Elemtype y)  //在某位置上插入节点
{
    Elemtype i = 0;
    LNode* s = value_find(L, x - 1);  //找到要插入位置的前一个节点
    if (s == NULL)
    {
        return false;
    }
    LNode* q = (LNode*)malloc(sizeof(LNode));  //新节点
    q->data = y;
    q->next = s->next;
    s->next = q;
    return true;
}
//删除节点
bool Dele_list(LNode* L, Elemtype x)
{
    //1.调用位置查找函数
    LNode* p = value_find(L, x - 1);  //要删除节点的前一个节点
    if (p == NULL)
    {
        return false;
    }
    LNode* q = p->next;  //要删除的节点
    p->next = q->next;
    free(q);
    return true;
    //2.直接遍历查找
    //Elemtype i = 0;
    //while (L && i < x - 1)
    //{
    //    L = L->next;
    //    i++;
    //}
    //LNode* s = L;
    //L = L->next;
    //s->next = L->next;
    //free(L);
    //return true;
}
//打印节点
void Print_list(LNode* L)
{
    L = L->next;
    while (L)
    {
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

int main()
{
    LNode* L;
    list_tail_insert(L);
    LNode* search = value_find(L, 2);
    if (search != NULL)
    {
        printf("%d\n", search->data);
    }
    int ret = 0;
    ret = value_insert(L, 2, 99);
    if (ret)
    {
        Print_list(L);
    }
    else
    {
        printf("false\n");
    }
    ret = Dele_list(L, 4);
    if (ret)
    {
        Print_list(L);
    }
    return 0;
}
点赞
收藏
评论区
推荐文章
22 22
1年前
【数据结构之链表】看完这篇文章我终于搞懂链表了
一览:本文从零介绍链式存储结构的线性表——单链表。包括以下内容:什么是链式存储存储结构?单链表的结构辨析头结点、头指针等易混淆概念基本的增删改查操作(不带头结点和带头结点)单链表与顺序表的对比线性表的链式存储结构在一文中我们介绍了一种“用曲线连接”的线性表,“曲线”是一种形象化的语言,实际上并不会存在所谓“曲线”的这种东西。所谓“曲线连
22 22
1年前
【数据结构之链表】详细图文教你花样玩链表
【系列文章推荐阅读】0.提要钩玄文章已经介绍了链式存储结构,介绍了链式存储结构的最基本(简单)实现——单向链表。单向链表,顾名思义,它是单向的。因为单链表的每个结点只有一个数据域和一个指针域,而该指针域只存储了下一个结点的地址,所以我们只能通过某结点找到其直接后继结点,却不能通过某节点找到其直接前驱结点。此外,由于单链表到尾结点(链表的最后一
易娃 易娃
1年前
Go VS Java:一位资深程序员对两种语言的解读
导读:对于软件开发的编程语言,其实没有万能灵药。本文作者详细介绍了他使用Java和Go这两种编程语言,一个是传统语言,一个是新兴语言的工作方式。image(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/0f0509de2420894d6c75e8678081e0cd.png)
Stella981 Stella981
1年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Easter79 Easter79
1年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
1年前
D1
1\.数据结构  1.1线性结构  (1)最常用的数据结构,特点是数据元素之间存在一对一的线性关系  (2)有两种不同的存储结构,即顺序存储结构和链式存储结构    顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Suzhou Suzhou
1星期前
线性表
线性表的顺序存储实现(数组形式)称为顺序表。线性表顺序表示原理解析这里描述的线性表是逻辑结构的,独立于存储结构。线性表的顺序表示简称顺序表。顺序表实现线性表的方式是使用数组。线性表第一个元素的数组下标是0。另外一种实现顺序表的方法:使用数组方式比动态分配更
Suzhou Suzhou
1个月前
查找算法
顺序查找顺序查找又称为线性查找,对线性表和链表都适用。线性表可以通过数组下标递增来顺序扫描每个元素,链表可以通过next指针依次扫描每一个元素。:::tip指针实现顺序表时,顺序表中是指针时,在定义顺序表的结构体后,需要对顺序表初始化,初始化时为指针申请堆
Suzhou Suzhou
1个月前
C语言易错内容汇总
!image(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/3dc55e061bdab8d2c66dcdf6d51bf99f.png)
Suzhou
Suzhou
Lv1
这个网站设计堪称垃圾。CTRL+S过后的东西,重启电脑只能保存5行。多按几次CTRL+S还提示频繁保存不了。吐了。
17
文章
2
粉丝
3
获赞