小工具知识网

当前位置: 首页 > 行业知识 > 【数据结构 | 入门】线性表与链表 (问题引入&实现&算法优化)

行业知识

【数据结构 | 入门】线性表与链表 (问题引入&实现&算法优化)

2026-11-16 14:18:31 来源:互联网转载

‍♂️ 个人主页: @计算机魔术师

‍ 作者简介:CSDN内容合伙人,全栈领域优质创作者。

本文是浙大数据结构学习笔记专栏

文章目录

  • 一、问题引入 - 如何用编程表达多项式
    • 方法一 - 顺序存储结构
    • 方法二- 顺序存储结构表示非零项
    • 方法三 - 链表结构存储非零项
    • 二、什么是线性表
      • 2.1 抽象类型描述
      • 三、 线性表的顺序存储实现
        • 3.3 主要操作的实现
        • 四、 线性表的链式存储实现
          • 4.3 主要操作的实现
          • 五、 广义表
          • 六、多重链表

            一、问题引入 - 如何用编程表达多项式

            这里我们引入一个问题,最常见的多项式,我们如何使用编程将多项式表示出来呢?

            方法一 - 顺序存储结构

            我们可以使用数组来表示,但是会随着一个问题,如下图底部所表示的多项式,我们需要多大的数组来表示呢?显然需要使用2001个数组来表示,缺只有两项多项式,会有非常大一部分为0,会很浪费空间

            方法二- 顺序存储结构表示非零项

            这样我们就可以只存储存在的多项式,减少了大量空间的浪费,那么难点来了,怎么进行加减操作呢? 要求是按指数大小有序存储

            我们按照次方排序,不相同时往下放,相同时系数相加即可,

            方法三 - 链表结构存储非零项

            我们还可以使用链表来实现,加减也是和上面的方法一样

            二、什么是线性表

            2.1 抽象类型描述

            (描述分为 数据对象集和操作集`)

            三、 线性表的顺序存储实现

            3.3 主要操作的实现

            初始化与查找

            插入(首先需要全部元素往后挪)

            删除操作

            四、 线性表的链式存储实现

            其中问题在于我们只知道一个链表头,那我们如何知道该线性表的长度为多少?,

            4.3 主要操作的实现

            实现方法是遍历链表长

            查找 (在链表中查找值比数组麻烦,也需要便利链表)

            插入

            删除操作

            需要注意的是删除第一个结点的操作,由于第一个结点没有上一个结点(头节点不算)所以将后面的结点往前挪,如果不是第一个节点,则将结点指针指向往后指向一位

            五、 广义表

            为了表示二元多项式,我们可以将二元多项式看作只关于 x x x得一元多项式,如下(每个链表钟第一个地址代表着参数,第二个值代表x的幂

            我们使用 c语言所提供的联合实现

            六、多重链表

            广义表其实就是特殊的多重链表

            我们看一个矩阵的例子(和之前存贮多项式一样,用数组存储面对非常多的系数为0时,非常浪费空间)

            我们抓住关键信息,构造结点,其中如下,左上角的Term为入口点,两个指针指向行头结点和列头结点,

            我们便可通过联合将非0元素与0元素合并为一个tag

              ✨谢谢你的阅读,您的点赞和收藏就是我创造的最大动力!✨

上一篇:揭秘友情链接添加秘籍,助力社交圈更紧密!

下一篇:怎么获取微信服务器?