当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/8 1:38:44

在这里插入图片描述

🤵‍♂️ 个人主页: @计算机魔术师
👨‍💻 作者简介：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
在这里插入图片描述

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

相关文章：

  • vmware虚拟机中的archlinux无法播放声间的解决办法
  • 深度学习常用的backbone有哪些
  • 君正X2000/X1600主控CPU方案有哪些场景？行业迈向人机交互智能时代来啦！
  • c++类和对象万字详解
  • Less预处理——初识Less
  • 在低浓度下修饰生物分子的Pyrimidine-Tetrazine-PEG1-Alkyne 四嗪试剂
  • 【web前端开发】前端生日礼物--主页面篇
  • Linux 驱动开发 五十六：Buildroot 笔记
  • 移动端JDtoolbar
  • 公众号题库搜题对接(免费接口)
  • 傻妞机器人对接TG【无需QQ】
  • Mysql基础 (二)
  • winform服务站药品管理系统VS开发sqlserver数据库cs结构c#编程源码网页
  • java计算机毕业设计小区车辆管理系统源程序+mysql+系统+lw文档+远程调试
  • A公司与B公司xx项目互通测试解决方案模板
  • [译] 怎样写一个基础的编译器
  • 10个最佳ES6特性 ES7与ES8的特性
  • Android开源项目规范总结
  • Angular4 模板式表单用法以及验证
  • avalon2.2的VM生成过程
  • Bytom交易说明（账户管理模式）
  • ECMAScript入门（七）--Module语法
  • Fundebug计费标准解释：事件数是如何定义的？
  • Hibernate【inverse和cascade属性】知识要点
  • MYSQL 的 IF 函数
  • Python语法速览与机器学习开发环境搭建
  • text-decoration与color属性
  • 持续集成与持续部署宝典Part 2：创建持续集成流水线
  • 基于组件的设计工作流与界面抽象
  • 简析gRPC client 连接管理
  • 罗辑思维在全链路压测方面的实践和工作笔记
  • 名企6年Java程序员的工作总结，写给在迷茫中的你！
  • 前端面试之闭包
  • 深入 Nginx 之配置篇
  • 通过来模仿稀土掘金个人页面的布局来学习使用CoordinatorLayout
  • Unity3D - 异步加载游戏场景与异步加载游戏资源进度条 ...
  • 不要一棍子打翻所有黑盒模型，其实可以让它们发挥作用 ...
  • ​卜东波研究员：高观点下的少儿计算思维
  • #Z0458. 树的中心2
  • %3cli%3e连接html页面,html+canvas实现屏幕截取
  • (iPhone/iPad开发)在UIWebView中自定义菜单栏
  • （Note）C++中的继承方式
  • （多级缓存）缓存同步
  • （附源码）springboot 基于HTML5的个人网页的网站设计与实现 毕业设计 031623
  • （附源码）ssm航空客运订票系统 毕业设计 141612
  • (转)拼包函数及网络封包的异常处理(含代码)
  • .FileZilla的使用和主动模式被动模式介绍
  • .NET Compact Framework 3.5 支持 WCF 的子集
  • .net core webapi 大文件上传到wwwroot文件夹
  • .net遍历html中全部的中文,ASP.NET中遍历页面的所有button控件
  • .net反编译的九款神器
  • /dev/sda2 is mounted; will not make a filesystem here!
  • @Autowired注解的实现原理
  • [C# 开发技巧]实现属于自己的截图工具
  • [C++基础]-入门知识