1. Toy模板网首页
  2. > Toy博客

王道考研数据结构--2.单链表

7月前 作者：西柚小萌新 分类：Toy博客 阅读(79) 违法举报

这篇具有很好参考价值的文章主要介绍了王道考研数据结构--2.单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

1.前言

2.难点

2.1c和c++的引用转换

2.2引入头结点的好处

2.3头插法和尾插法

3.代码段

3.1C语言自定义bool操作

3.2单链表结构体定义

3.3创建新节点

3.4头插法和尾插法

3.5查找

3.6按位序插入

3.7后插和前插

3.8删除

3.9求表长

3.10遍历输出单链表

4.完整代码

1.前言

日期：2023.6.21

书籍：2024年数据结构考研复习指导（王道考研系列）

内容：单链表的实现，结构体定义，初始化，创建新结点，头插和尾插，查询，按位序插入，删除指定节点，输出单链表

2.难点

2.1c和c++的引用转换

符号"&"，表示c++中的引用调用，在c语言中可以用指针达到一样的效果

2.2引入头结点的好处

  1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
  2. 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空）因此空表和非空表的处理也就得到了统一。所以,没事儿写代码就把头指针带着吧

2.3头插法和尾插法

采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。

若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加个尾指针r,使其始终指向当前链表的尾结点. 

3.代码段

3.1C语言自定义bool操作

//C语言自定义bool操作
#define bool char
#define false 0
#define true 1

3.2单链表结构体定义

typedef int ElemType;

/*单链表结构体定义*/
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
}LNode,*LinkList;

LinkList L; //声明一个指向单链表第一个结点的指针,这种方法代码可读性更强，强调单链表

等价于：

LNode *L; //声明一个指向单链表第一个结点的指针,但这种方法可读性不强, 无法第一时间看出L是指向整个链表的头指针,还是仅仅是个新的结点。强调的是一个节点。文章来源地址https://www.toymoban.com/news/detail-494196.html

3.3创建新节点

//3.创建新节点函数
LNode* creatNote(int data){//通过传参为节点数据
    //[1]为新节点申请空间
    LNode* newNode=(LNode*)malloc(sizeof(LNode));
    //[2]如果内存满了,则分配失败,返回0
    if(newNode==NULL){
        printf("内存出现错误，节点分配失败！");
        return NULL;
    }
    //[3]为新节点的数据域和指针域分别赋值
    newNode->data=data;
    newNode->next=NULL;
    return newNode;
}

3.4头插法和尾插法

//4.1.头插法
bool ListHeadInsert(LinkList L,ElemType data){
    LNode* newNode=creatNote(data);
    newNode->next=L->next;
    L->next=newNode;
    return true;

}

//4.2.尾插法
bool ListTailInsert(LinkList L,ElemType data){
    LNode* newNode = creatNote(data);

    LNode* p = L->next;
    //[3]遍历链表,找到最后的元素,用工具指针指向它
    while (p->next != NULL){
        p = p->next;
    }//此时的p节点就是最后一个节点
    newNode->next = NULL;
    p->next = newNode;
}

3.5查找

//5.1按序号查找结点
LNode* GetElem(LinkList L,int i){
    int count;
    //[1]设置一个变量计数
    //[2]设置待返回的结点p,开始指向第一个结点
    LNode *p = L->next;
    //[3]检查参数
    if(i == 0) {p = L; return p;}
    if(i < 1) { return NULL;}

    //[4]开始循环
    while (p != NULL && count < i){
        p = p->next;
        count++;
    }
    return p;
}

//5.2按值查找节点
LNode* LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}

3.6按位序插入

//6.按位序插入
bool ListInsert(LinkList L,int i,ElemType data){
    //创建data节点
    LNode* newNode=creatNote(data);
    LNode* Node=GetElem(L,i-1);//找到i-1节点，然后后插操作
    newNode->next=Node->next;
    Node->next=newNode;
    return true;
}

3.7后插和前插

//7.1.后插节点操作
bool LocateTailInsert(LinkList L,int i,ElemType e){
    //[1]生成指向目标节点的指针p
    LNode* p = GetElem(L,i-1);
    //[2]生成新节点s
    LNode* s = creatNote(e);
    //[3]插入
    s->next = p->next;
    p->next = s;
}

//7.2.前插节点操作
bool LocateHeadInsert(LinkList L,int i,ElemType e){
    //[1]生成指向目标节点的指针p
    LNode* p = GetElem(L,i);
    //[2]生成新节点s
    LNode* s = creatNote(e);
    //[3]插入
    ElemType temp = p->data;
    s->next = p->next;
    p->next = s;
    p->data = s->data;
    s->data = temp;
}

3.8删除

//8.删除指定节点
bool ElemDelete(LinkList L,int i){
    //[1]定位
    LNode *p = GetElem(L,i-1);
    LNode *q = p->next;
    //[2]删除
    p->next = q->next;
    //[3]释放被删除节点
    free(q);
}
bool LocateElemDelete(LinkList L,int i)
{
    //[1]定位
    LNode *p = GetElem(L,i);
    LNode *q = p->next;
    //[2]复制数据
    p->data = q->data;
    p->next = q->next;
    //[3]释放结点
    free(q);
}

3.9求表长

//9.表长
int ListLength(LinkList L){
    int count = 0;
    while (L->next != NULL){
        L = L->next;
        count++;
    }
    return count;    
}

3.10遍历输出单链表

//遍历输出单链表

void Listprint(LinkList L){
    LNode* p = L->next;
    while (p != NULL){
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
}

4.完整代码

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

//C语言自定义bool操作
#define bool char
#define false 0
#define true 1

//1.单链表结构体定义
typedef int ElemType;
typedef struct LNode{  //定义单链表结点类型
    ElemType data;     //每个结点存放一个数据元素
    struct LNode *next;//指针指向下一节点
   
}LNode,*LinkList;      


//2.链表的初始化
LinkList ListInit(){
    //申请一块LinkList类型的存储空间给L
    LinkList L=(LNode*)malloc(sizeof(LinkList));//
    //设置L的指针域为空
    L->next=NULL;
    return L;
}

//3.创建新节点函数
LNode* creatNote(int data){//通过传参为节点数据
    //[1]为新节点申请空间
    LNode* newNode=(LNode*)malloc(sizeof(LNode));
    //[2]如果内存满了,则分配失败,返回0
    if(newNode==NULL){
        printf("内存出现错误，节点分配失败！");
        return NULL;
    }
    //[3]为新节点的数据域和指针域分别赋值
    newNode->data=data;
    newNode->next=NULL;
    return newNode;
}

//4.1.头插法
bool ListHeadInsert(LinkList L,ElemType data){
    LNode* newNode=creatNote(data);
    newNode->next=L->next;
    L->next=newNode;
    return true;

}

//4.2.尾插法
bool ListTailInsert(LinkList L,ElemType data){
    LNode* newNode = creatNote(data);

    LNode* p = L->next;
    //[3]遍历链表,找到最后的元素,用工具指针指向它
    while (p->next != NULL){
        p = p->next;
    }//此时的p节点就是最后一个节点
    newNode->next = NULL;
    p->next = newNode;
}

//5.1按序号查找结点
LNode* GetElem(LinkList L,int i){
    int count;
    //[1]设置一个变量计数
    //[2]设置待返回的结点p,开始指向第一个结点
    LNode *p = L->next;
    //[3]检查参数
    if(i == 0) {p = L; return p;}
    if(i < 1) { return NULL;}

    //[4]开始循环
    while (p != NULL && count < i){
        p = p->next;
        count++;
    }
    return p;
}

//5.2按值查找节点
LNode* LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}

//6.按位序插入
bool ListInsert(LinkList L,int i,ElemType data){
    //创建data节点
    LNode* newNode=creatNote(data);
    LNode* Node=GetElem(L,i-1);//找到i-1节点，然后后插操作
    newNode->next=Node->next;
    Node->next=newNode;
    return true;
}

//7.1.后插节点操作
bool LocateTailInsert(LinkList L,int i,ElemType e){
    //[1]生成指向目标节点的指针p
    LNode* p = GetElem(L,i-1);
    //[2]生成新节点s
    LNode* s = creatNote(e);
    //[3]插入
    s->next = p->next;
    p->next = s;
}

//7.2.前插节点操作
bool LocateHeadInsert(LinkList L,int i,ElemType e){
    //[1]生成指向目标节点的指针p
    LNode* p = GetElem(L,i);
    //[2]生成新节点s
    LNode* s = creatNote(e);
    //[3]插入
    ElemType temp = p->data;
    s->next = p->next;
    p->next = s;
    p->data = s->data;
    s->data = temp;
}

//8.删除指定节点
bool ElemDelete(LinkList L,int i){
    //[1]定位
    LNode *p = GetElem(L,i-1);
    LNode *q = p->next;
    //[2]删除
    p->next = q->next;
    //[3]释放被删除节点
    free(q);
}
bool LocateElemDelete(LinkList L,int i)
{
    //[1]定位
    LNode *p = GetElem(L,i);
    LNode *q = p->next;
    //[2]复制数据
    p->data = q->data;
    p->next = q->next;
    //[3]释放结点
    free(q);
}


//9.表长
int ListLength(LinkList L){
    int count = 0;
    while (L->next != NULL){
        L = L->next;
        count++;
    }
    return count;    
}

//遍历输出单链表

void Listprint(LinkList L){
    LNode* p = L->next;
    while (p != NULL){
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
}

int main(){
    //[1]定义一个链表
    LinkList L = NULL;
    // printf("%d",L->next);//可以尝试,此时L->next无法输出
    //[2]将链表初始化
    L = ListInit();
    ListHeadInsert(L,1);
    ListHeadInsert(L,2);
    ListHeadInsert(L,3);
    ListHeadInsert(L,4);
    ListHeadInsert(L,5);
    ListTailInsert(L,6);
    ListTailInsert(L,7);
    ListTailInsert(L,8);
    ListTailInsert(L,9);
    ListTailInsert(L,10);
    ListInsert(L,3,666);
    ListInsert(L,1,88888);
    LocateTailInsert(L,8,6969);
    LocateHeadInsert(L,2,3333);
    ElemDelete(L,3);
    LocateElemDelete(L,5);
    Listprint(L);
    printf("链表长度为:%d\n",ListLength(L));
    return 0;
}

到了这里，关于王道考研数据结构--2.单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构笔记（王道考研） 第一章：绪论

    数据结构笔记（王道考研） 第一章：绪论

    大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记，该课属于付费课程（不过盗版网盘资源也不难找。。。）。后续又根据23年考研的大纲对内容做了一些调整，将二叉排序树和平衡二叉树的内容挪到了查找一章，并增加了并查集、平衡二叉树的删除、红黑树的内

    2024年02月14日
    浏览(32)
  • 【数据结构】| 王道考研——树的前世今生

    【数据结构】| 王道考研——树的前世今生

    根据王道考研数据结构总结出的知识点，以下是文章整体大纲： 1.1 概念 树是n个结点的有限集合，n = 0时称为空树，这是一种特殊情况。任意一棵非空树中应满足： 有且仅有一个特定的称为根的节点 当n1时，其余结点可分为m个互不相交的有限集合T1、T2、T3……Tm；每个集合又

    2024年02月15日
    浏览(31)
  • 王道考研数据结构--4.2循环队列

    王道考研数据结构--4.2循环队列

    目录 前言  1.循环队列的定义 2.循环队列的结构 3.循环队列的操作 3.1定义循环队列 3.2初始化 3.3入队 3.4出队 3.5遍历，求表长 3.6清空销毁 4.完整代码 日期：2023.7.25 书籍：2024年数据结构考研复习指导（王道考研系列） 内容：实现顺序队列的基本实现，主要功能如下： 1.循环队

    2024年02月15日
    浏览(36)
  • 一篇学完：王道考研408数据结构（全）

    一篇学完：王道考研408数据结构（全）

    PDF版本附在  lengyueling.cn 对应 文章结尾，欢迎下载访问交流 数据结构在学什么 如何用程序代码把现实世界的问题信息化 如何用计算机高效地处理这些信息从而创造价值 数据结构的基本概念 什么是数据： 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到

    2023年04月08日
    浏览(33)
  • 【数据结构】24王道考研笔记——栈、队列和数组

    【数据结构】24王道考研笔记——栈、队列和数组

    基本概念 栈是 只允许在一端进行插入或删除操作 的线性表。 栈顶：线性表允许进行插入删除的那一端 栈底：固定的，不允许进行插入删除的那一端 空栈：不含任何元素的空表 特点： 先进后出 基本操作： 常考题型： [外链图片转存失败,源站可能有防盗链机制,建议将图片

    2024年02月09日
    浏览(58)
  • 王道考研数据结构第五章知识点

    王道考研数据结构第五章知识点

    5.1.1 树的定义和基本术语   祖先节点：(对于你来说),父亲和爷爷都是祖先节点 子孙节点：对于父亲来说，父亲下面所有的节点都叫子孙节点 双亲节点(父节点)：一个节点的直接前驱就是它的父节点  兄弟节点：例如二叔，三叔都是父亲的兄弟节点 堂兄弟节点：对于你来说，

    2024年02月15日
    浏览(35)
  • 【数据结构】24王道考研笔记——树与二叉树

    【数据结构】24王道考研笔记——树与二叉树

    树是n个结点的有限集合，n=0时，称为空树。非空树满足： 除了根节点外，任何一个结点都有且仅有一个前驱 结点的层次（深度）：从上往下数 结点的高度：从下往上数 树的高度（深度）：总共有多少层 结点的度：有几个孩子（分支） 树的度：各节点的度的最大值 森林：

    2024年02月13日
    浏览(40)

  • 【数据结构】【王道】【数据结构实现】文章目录

    持续更新中。。。 数据结构 链接 顺序表实现及基本操作（可直接运行） 文章链接 无头结点单链表的实现及基本操作（可直接运行） 文章链接 带头结点单链表的实现及基本操作（可直接运行） 文章链接 双链表的实现及基本操作（可直接运行） 文章链接 循环链表的实现及

    2023年04月08日
    浏览(79)

  • 王道计算机考研 数据结构C语言复现-第六章-队列

     这篇文章收录了王道考研课程中涉及的数据结构的所有代码。此外，本博客可能会添加一些额外的代码（不仅限于王道考研），因为408考试中会频繁考察一些冷门的知识点，所以这篇博客会涵盖所有相关的代码。这也是我数据结构的第一轮复习，希望能与大家共同进步。由

    2024年01月21日
    浏览(31)
  • 【考研复习】24王道数据结构课后习题代码｜第3章栈与队列

    【考研复习】24王道数据结构课后习题代码｜第3章栈与队列

    伪代码

    2024年02月13日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包