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

【考研复习】24王道数据结构课后习题代码｜2.3线性表的链式表示

9月前 作者：Lydia.na 分类：Toy博客 阅读(46) 违法举报

这篇具有很好参考价值的文章主要介绍了【考研复习】24王道数据结构课后习题代码｜2.3线性表的链式表示。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

总结

  • 删除结点：1、2、4
  • 就地逆置：5、
  • 合并链表
  • 分解链表：10、11、
  • 去除重复元素：12、
  • 并集：14、15
  • 循环链表：17、18、19、20
  • 头插法、尾插法重点基础必掌握。
  • 判断是否有环：21

01 递归删除结点

用函数递归调用删除结点。

void deletex(linklist &L,int x){
    if(L==NULL) return;
    lnode *p;
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);
        deletex(L,x);
    }
    else deletex(L->next,x);
}

02 删除结点

注意删除结点的时候可能断链。

void deletex2(linklist &L,int x){
    lnode *p=L->next,*pre=L,*q;
    while(p){
        if(p->data==x){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}

03 反向输出

利用函数调用的特性反向输出。

void r_print(linklist L){
    if(L!=NULL)
    {
        r_print(L->next);
        cout<<(L->data)<<" ";
    }
    else return;
}
void r_ignore_node(linklist L){
    if(L->next!=NULL){
        r_print(L->next);
    }
}

04 删除最小值

  1. 设置保留最小值的指针和其前驱
  2. 每次更新最小值
void delete_min(linklist L){
    lnode *p=L->next,*pre=L;
    lnode *minp=p,*minpre=pre;
    while(p){
        if(p->data<minp->data){
            minp=p;
            minpre=pre;
        }else{
            p=p->next;
            pre=pre->next;
        }
    }
    minpre->next=minp->next; //删除最小值结点
    free(minp);
}

05 逆置

很重要的基础：头插法

void head(linklist &L){
    lnode *p=L->next,*r;
    L->next=NULL;
    while(p){
        r=p->next;      //记录下一结点
        p->next=L->next;
        L->next=p;
        p=r;
    }
}

06 链表递增排序

使用插入排序的思想，将头置空之后，扫描最小元素，然后使用尾插法插入头中。

void insert_sort(linklist &L){
    lnode *p=L->next,*r=p->next,*pre;
    p->next=NULL;
    p=r;
    while(p){
        r=p->next;
        pre=L;
        while(pre->next!=NULL&&pre->next->data<p->data){
            pre=pre->next;
        }
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
}

07 删除区间值

见2题的删除代码，改下if语句即可。

void delete_x_m_n(linklist &L,int m, int n){
    lnode *p=L->next,*pre=L,*q;
    while(p){
        if(p->data<n&&p->data>m){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}

08 找公共结点

linklist find_same_dot(linklist L1,linklist L2){
    linklist longlist, shortlist;
    int dist=0;
    int len1=length(L1),len2=length(L2);
    if(len1>len2){
        longlist=L1;
        shortlist=L2;
        dist=len1-len2;
    }else{
        longlist=L2;
        shortlist=L1;
        dist=len2-len1;
    }
    while(dist--) longlist=longlist->next;
    while(longlist){
        if(longlist->data==shortlist->data&&longlist->next->data==shortlist->next->data)
            return longlist;
        else{
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
    }
    return NULL;
}

09 增序输出链表

见6题

void min_output(linklist L){
    while(L->next){
        lnode *pre=L,*p=L->next;
        lnode *minpre=pre, *minp=p;
        while(p){
            if(p->data<minp->data){
                minp=p;
                minpre=pre;
            }
            p=p->next;
            pre=pre->next;
        }
        cout<<minp->data<<" ";
        minpre->next=minp->next;
        free(minp);
    }
}

10 拆分链表–尾插

第一种方法是在A中直接删除。

linklist split_1_1(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B,*q;
    while(p){
        //向后移一个
        ra=p;
        p=p->next;
        //从A中删除结点
        q=p;
        ra->next=p->next;
        p=p->next;
        //利用尾插法将结点插入B中
        rb->next=q;
        rb=rb->next;
    }
    ra->next=NULL;
    rb->next=NULL;
    return B;
}

第二种方法是把A的头拿下来，再选最小的排在A后。=尾插==

linklist split_1_2(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B;
    //把表头摘下来
    A->next=NULL;
    while(p){
        //结点给A
        ra->next=p;
        ra=ra->next;
        p=p->next;
        //结点给B
        rb->next=p;
        rb=rb->next;
        p=p->next;
    }
    ra->next=NULL;
    rb->next=NULL;
    return B;
}

11 拆分链表–头插

第一种方法同上

linklist split_1_1(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B,*q;
    while(p){
        //向后移一个
        ra=p;
        p=p->next;
        //从A中删除结点
        q=p;
        ra->next=p->next;
        p=p->next;
        //利用头插法将结点插入B中
        q=p->next;
        p->next=rb->next;
        rb->next=p;
        p=q;
    }
    ra->next=NULL;
    return B;
}

第二种方法同上

linklist split_2_1(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B,*q;
    //把表头摘下来
    A->next=NULL;
    while(p){
        //结点给A
        ra->next=p;
        ra=ra->next;
        p=p->next;
        //结点给B
        if(p){
            q=p->next;
            p->next=rb->next;
            rb->next=p;
            p=q;
        }
    }
    ra->next=NULL;
    //b是头插法所以最后指向是为NULL
    return B;
}

12 删除相同元素

简单代码，只不过要注意的p是要删除结点的前一个结点，判断的时候别判断错了。

void del_same(linklist &L){
    lnode *p=L->next,*q;
    if(p==NULL) return;
    while(p->next){
        q=p->next;
        if(p->data==q->data){
            p->next=q->next;
            free(q);
        }else{
            p=p->next;
        }
    }
}

13 合并链表

void merge(linklist &L1,linklist &L2)
{
    lnode *p1=L1->next,*p2=L2->next,*r;
    L1->next=NULL;
    while(p1&&p2)
    {
        if(p1->data<=p2->data)
        {
            r=p1->next;
            p1->next=L1->next;
            L1->next=p1;
            p1=r;
        }
        else
        {
            r=p2->next;
            p2->next=L1->next;
            L1->next=p2;
            p2=r;
        }
    }
    if(p1) p2=p1;
    while(p2)
    {
        r=p2->next;
        p2->next=L1->next;
        L1->next=p2;
        p2=r;
    }
    free(L2);
}

14 生成含有公共元素的链表C

  1. 两个链表分别遍历，比较值头插入C中
linklist merge_same(linklist &A,linklist &B){
    lnode *p=A->next,*q=B->next;
    lnode *r,*s;
    linklist C = (linklist)malloc(sizeof(lnode));
    r=C;
    while(p&&q){
        if(p->data<q->data){
            p=p->next;
        }
        else if(p->data>q->data){
            q=q->next;
        }else{
            s=(lnode *)malloc(sizeof(lnode *));
            s->data=p->data;
            r->next=s;
            r=r->next;
            p=p->next;
            q=q->next;
        }
    }
    r->next=NULL;
    return C;
}

15 求并集

  1. 值不相同时分别删除A和B中的值
  2. 相同时删除B中的值
  3. 基础就是删除代码
void intersection(linklist &A,linklist &B){
    lnode *p=A->next,*q=B->next;
    lnode *r=A,*temp;
    while(p&&q){
        if(p->data<q->data){
            temp=p;
            p=p->next;
            free(temp);
        }else if(p->data>q->data){
            temp=q;
            q=q->next;
            free(temp);
        }else{
            //相等的时候保留A中相同元素
            r->next=p;
            r=r->next;
            p=p->next;
            //删除B中相同的元素
            temp=q;
            q=q->next;
            free(temp);
        }
    }
    while(p){
        temp=p;
        p=p->next;
        free(temp);
    }
    while(q){
        temp=q;
        q=q->next;
        free(temp);
    }
    r->next=NULL;
}

16 判断子序列

朴素kmp，也有所说bf的

bool simple_kmp(linklist &A,linklist &B){
    lnode *p=A->next,*q=B->next,*r=A->next;
    while(p&&q){
        if(p->data!=q->data){
            r=r->next;
            p=r;
            q=A->next;
        }else{
            p=p->next;
            q=q->next;
        }
    }
    if(q) return false;
    else return true;
}

17 判断循环链表是否对称

循环链表就方便了，能找前驱和后继，两个指针同时移动判断值即可。

bool symmetry(linklist L)
{
    lnode *p=L->next,*q=L->prior;
    while(p!=q&&q->next!=p)
    {
        if(p->data==q->data)
        {
            p=p->next;
            q=q->prior;
        }
        else return false;
    }
    return true;
}

18 两个循环链表链接

注意头尾即可

void add(linklist &h1,linklist &h2)
{
    lnode *p=h1->next,*q=h2->next;
    while(p->next!=h1)
    {
        p=p->next;
    }
    while(q->next!=h2){
        q=q->next;
    }
    p->next=h2->next;//初始化的链表带头结点，若不带h2即可
    q->next=h1;
}

19 找最小结点并删除

  1. 遍历链表每次输出最小结点然后删除即可
    相同代码见9题 
void find_min(linklist &L){
    while(L->next!=L){
        lnode *pre=L,*p=L->next;
        lnode *minpre=pre, *minp=p;
        while(p!=L){
            if(p->data<minp->data){
                minp=p;
                minpre=pre;
            }
            p=p->next;
            pre=pre->next;
        }
        cout<<minp->data<<" ";
        minpre->next=minp->next;
        free(minp);
    }
    free(L);
}

21 判断单链表是否有环

  1. 两步走总能相遇，按照这个作为遇到的条件找相遇点和入环结点。
    25题也是两步走。 
lnode* findd(lnode *L)
{
    lnode *f=L,*s=L;
    while(s!=NULL&&f->next!=NULL)
    {
        s=s->next;
        f=f->next->next;
        if(s->data==f->data) break; //可以直接设置指针，但是我初始化的有单链表为int a[15]={1,2,3,4,5,6,7,8,9,4,5,6,7,8,9};故用这种方法
    }
    if(s==NULL||f->next==NULL) return NULL;
    lnode *p=L,*q=s;
    while(p->data!=q->data)
    {
        p=p->next;
        q=q->next;
    }
    return p;
}

22 【2009真题】找倒数第k个元素

  1. 相当于用长度为k的尺子比着找，最右端到尾部的时候，最左端就是倒数第k个元素。
int findk(linklist &L, int k){
    lnode *p=L,*q=L;
    int count=0;
    while(p){
        if(count<k) count++;
        else q=q->next;
        p=p->next;
    }
    if(count<k) return 0;
    else cout<<"kth to last position: "<<q->data;
    return 1;
}

23 【2012真题】相同后缀找起始位置

  1. 把尾部排齐：两个指针遍历链表，长度相同时找到相同时尾部对齐了
  2. 排齐之后遍历两个链表找第一个不相同的位置，该位置的下一个位置就是相同后缀的位置
typedef struct lnode{
    int data;
    struct lnode *next;
}lnode,*linklist;
lnode * find_addr(linklist str1, linklist str2){
    lnode *p,*q;
    int m=length(str1);
    int n=length(str1);
    for(p=str1;m>n;m--) p=p->next;
    for(q=str2;m<n;n--) q=q->next;
    while (p->next!=NULL&&q->next!=NULL)
    {
        p=p->next;
        q=q->next;
    }
    return p->next;
}

24 【2015真题】删除绝对值相同

要求时间复杂度尽可能高➡️空间换时间文章来源地址https://www.toymoban.com/news/detail-635119.html

  1. 数组存查找状态：0表示绝对值未找到，1表示找到，第二次找到的同时删除该结点
  2. 注意动态分配数组的使用（静态数组试了试内存超出，不知道是不是这个问题）
void same(linklist &L,int n)
{
    lnode *p=L;
    int *q;
    q=(int *)malloc(sizeof(int)*(n+1));
    for(int i=0;i<n+1;i++) *(q+i)=0;
    int s;
    lnode *f;
    while(p->next!=NULL)
    {
        s=abs(p->next->data);
        if(*(q+s)==0) 
        {
            *(q+s)=1;
            p=p->next;
        }
        else
        {
            f=p->next;
            p->next=f->next;
            free(f);
        }
    }
    free(q);
}

25 【2019真题】重新排列链表

  1. 两步走找中间结点
  2. 逆置后边链表：使用头插法
  3. 看成两个链表进行插入
    21也是两步走 
void change(linklist &L){
    lnode *p,*q,*r,*s;
    p=q=L;
    while (q->next)
    {
        p=p->next;
        q=q->next;
        if(q->next) q=q->next;
    }
    q=p->next;  //p现在在中间结点
    p->next=NULL;  //把后半段摘下来，逆置之后分别遍历两个链表插入指定位置
    while (q)  //头插法实现原地逆置
    {
        r=q->next;  //暂存后继结点
        q->next=p->next;  //将q结点放在头结点p之后
        p->next=q;
        q=r;
    }
    s=L->next;  //插入点
    q=p->next;  //后半段数据点
    p->next=NULL;  
    while(q){
        r=q->next;
        q->next=s->next;
        s->next=q;
        s=q->next;
        q=r;
    }
}

到了这里，关于【考研复习】24王道数据结构课后习题代码｜2.3线性表的链式表示的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

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

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

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

    2024年02月13日
    浏览(49)
  • 王道考研数据结构——链表

    王道考研数据结构——链表

    找到头节点就相当于找到了整个链表 Linklist Lnode*是一个东西 大部分使用的带头结点，比较方便！带头结点只维护指针域，不维护数据域 找前驱节点+插入节点(可以单独封装成一个函数)  如果不带头节点的话，那么插入和删除头节点的话都需要特殊处理，即重新修改头指针的

    2024年02月16日
    浏览(59)
  • 【王道考研】王道数据结构与算法详细笔记（全）

    【王道考研】王道数据结构与算法详细笔记（全）

    目录 第一章 数据结构绪论  1.1 数据结构的基本概念 1.2 数据结构的三要素 1.2.1. 数据的逻辑结构 1.2.2. 数据的存储结构（物理结构） 1.2.3. 数据的运算 1.2.4. 数据类型和抽线数据类型 1.3 算法的基本概念 1.4 算法的时间复杂度 1.5 算法的空间复杂度 第二章 线性表 2.1 线性表的定

    2024年02月08日
    浏览(52)

  • 王道考研数据结构--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.完整代码 日期：2023.6.21 书籍：2024年数据

    2024年02月09日
    浏览(115)
  • 数据结构笔记（王道考研） 第一章：绪论

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

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

    2024年02月14日
    浏览(49)
  • 王道考研数据结构--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日
    浏览(47)
  • 【数据结构】| 王道考研——树的前世今生

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

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

    2024年02月15日
    浏览(49)
  • 【2023王道数据结构】王道数据结构课后代码题汇总答案C、C++代码实现完整版大全（可直接运行）

    【2023王道数据结构】王道数据结构课后代码题汇总答案C、C++代码实现完整版大全（可直接运行）

    本文章为 2023王道数据结构专栏 导航贴，正在积极更新中！ 本专栏文章将王道一些 课后算法设计题目 的全部实现（答案解析全部都是伪码或者函数的部分实现，不可调试运行）， 同时包含各个章节的经典算法数据结构的实现以及一些经典的算法 本专栏使用人群：复习数据

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

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

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

    2023年04月08日
    浏览(45)
  • 王道考研数据结构第五章知识点

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

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

    2024年02月15日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包