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

在这里插入图片描述

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

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

文章目录

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

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

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

在这里插入图片描述

在这里插入图片描述

方法一 - 顺序存储结构

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

二、什么是线性表

在这里插入图片描述

2.1 抽象类型描述

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

在这里插入图片描述

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

在这里插入图片描述

3.3 主要操作的实现

初始化与查找

在这里插入图片描述

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

在这里插入图片描述

在这里插入图片描述

删除操作

在这里插入图片描述

在这里插入图片描述

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

在这里插入图片描述

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

4.3 主要操作的实现

实现方法是遍历链表长

在这里插入图片描述

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

在这里插入图片描述

插入

在这里插入图片描述

在这里插入图片描述

删除操作

在这里插入图片描述

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

五、 广义表

为了表示二元多项式，我们可以将二元多项式看作只关于

得一元多项式，如下（每个链表钟第一个地址代表着参数，第二个值代表x的幂

在这里插入图片描述

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

在这里插入图片描述

六、多重链表

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述