‍♂️ 个人主页: @计算机魔术师
‍ 作者简介：CSDN内容合伙人，全栈领域优质创作者。

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

文章目录

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

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

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

方法一 – 顺序存储结构

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

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


这样我们就可以只存储存在的多项式，减少了大量空间的浪费，那么难点来了，怎么进行加减操作呢？ 要求是按指数大小有序存储
我们按照次方排序，不相同时往下放，相同时系数相加即可，

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


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

二、什么是线性表

2.1 抽象类型描述

（描述分为 数据对象集和操作集`）

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

3.3 主要操作的实现

初始化与查找

插入（首先需要全部元素往后挪）

删除操作

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


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

4.3 主要操作的实现

实现方法是遍历链表长

查找 （在链表中查找值比数组麻烦，也需要便利链表）

插入


删除操作

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

五、 广义表

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

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

六、多重链表

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

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

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

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

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