数据结构与算法学习笔记(3):线性表Ⅰ

本系列笔记为跟着B站上王卓老师的教程学习所记录的笔记

2.1线性表的定义和特点
2.2案例引入
2.3线性的类型定义
2.4线性表的顺序表示和实现
2.5线性表的链式表示和实现
2.6顺序表和链表的比较
2.7线性表的应用
2.8案例分析与实现

一.线性表的定义和特点

1.定义

线性表是具有相同特性的数据元素的一个有限序列

• 由n(n≥0)个数据元素(结点)$a_1,a_2,...a_n$组成的有限序列
  • 元素个数n定义为表的长度
  • n=0时称为空表
  • 非空的线性表(n>0)记作:$(a_1,a_2,...a_n)$
  • 数据元素$a_i$只是一个抽象符号,不同情况下代表不同内容

2.特点

• 同一线性表中的元素必须具有相同特性，数据元素间的关系是线性关系

线性表的逻辑特征

在非空线性表中:

• 有且仅有一个开始结点$a_1$,它无直接前趋，仅有一个直接后继$a_2$
• 有且仅有一个终端结点$a_n$,它无直接后继，仅有一个直接前趋$a_{n-1}$
• 其余的内部结点$a_i(2⩽i⩽n-1)$都有且仅有一个直接前趋$a_{i-1}$和一个直接后继$a_{i+1}$

线性表是一种典型的线性结构

二.典型案例

1.一元多项式运算

实现两个多项式的加减乘运算
$$P_n(x)=p_0+p_{1}x+p_2{x}^2+...+p_n{x}^n$$

• 构造线性表$P=(p_0,p_1,p_2,...p_n)$

  ​ 每一项的指数i就是其系数$p_i$的序号

• 怎么表示存储系数呢？

  • 利用数组

    • 下标i为指数，p[i]为系数
    • 

  • 利用数组可实现多项式相加

    $R_n(x)=P_n(x)+Q_n(x)$

    线性表$R=(p_0+q_0,p_1+q_1,p_2+q_2,...,p_m+q_m,...,p_n+q_n)$

  • 这样开辟数组适用于所有情况吗？

    • 如果不是每一个指数的项都存在，那就会很浪费空间

    • 

    • 解决办法:

      • 
      • 由此引入👇下面的案例

2.稀疏多项式

• 

• 稀疏多项式

  $P_n(x)=p_1{x}^{e_1}+p_2{x}^{e_2}+...+p_n{x}^{e_n}$

  线性表$P=((p_1,e_1),(p_2,e_2),...,(p_n,e_n)$

• 上面的$A(x)$线性表可表示为 A = ( ( 7 , 0 ) , ( 3 , 1 ) , ( 9 , 8 ) , ( 5

  数据结构与算法学习笔记线性表ⅱ(代码片段)

  数据结构与算法学习笔记(4)线性表Ⅱ文章目录数据结构与算法学习笔记(4)线性表Ⅱ一.线性表的链式表示和实现1.链式存储结构情境引入2.链式存储相关术语结点链表单链表、双链表、循环链表头指针、头结点和首元结点单链表的... 查看详情

  b站学习数据结构笔记=====＞稀疏数组(代码片段)

  学习来源–>传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）程序==数据结构+算法数据结构包括线性结构与非线性的结构线性结构:特点;数据元素之间存在着一对一的线性关系;但是;线性结构又... 查看详情

  数据结构与算法全套数据结构笔记持续更新

  目录【数据结构与算法】线性表的重要基本操作与代码实现【C语言版】【数据结构与算法】线性表的链式表示和实现，超详细【C语言版】【数据结构与算法】Leetcode2：两数相加【链表学习】【数据结构与算法】栈与队列... 查看详情

  数据结构与算法全套数据结构笔记持续更新

  目录【数据结构与算法】线性表的重要基本操作与代码实现【C语言版】【数据结构与算法】线性表的链式表示和实现，超详细【C语言版】【数据结构与算法】Leetcode2：两数相加【链表学习】【数据结构与算法】栈与队列... 查看详情

  数据结构与算法学习笔记查找(代码片段)

  数据结构与算法学习笔记(9)查找文章目录数据结构与算法学习笔记(9)查找一.查找的基本概念二.线性表的查找1.顺序查找应用范围算法基本形式改进算法特点2.折半查找(二分查找)非递归算法递归算法算法分析判定树优缺点3.分块... 查看详情

  《数据结构与算法》---（哔哩哔哩-王卓老师笔记）---线性表类型定义

  抽象数据类型线性表的定义如下定义一个list的类型基本操作（一）InitList（&L）构造一个空的线性表LDestroyList（&L）销毁线性表2.1.初始条件：线性表L已经存在2.2.操作结果：销毁线性表L2.3.就是... 查看详情

  尚硅谷算法与数据结构学习笔记02--单链表(代码片段)

  1、链表(LinkedList)介绍1.1、内存结构内存上来看：链表存储空间不连续（不像数组）1.2、逻辑结构逻辑上来看：链表属于线性结构1.3、链表特点链表是以节点的方式来存储，是链式存储data域存放数据，next域... 查看详情

  数据结构与算法学习笔记:数据结构基本概念(代码片段)

  数据结构与算法基础学习笔记(1):数据结构基本概念​本系列笔记为跟着B站上王卓老师的教程学习所记录的笔记文章目录数据结构与算法基础学习笔记(1):数据结构基本概念一.基本概念和术语1.数据2.数据元素3.数据项4.数据对象5.... 查看详情

  数据结构与算法-线性表

  近期在学习数据结构，反反复复已经看过几遍了，也做了一些练习题，但总感觉不记录一下，思路就不是很清晰，所以，从今天开始总结这段时间对数据结构的学习。 无论学习什么，基础知识都是最总要的，数据结构也不例... 查看详情

  数据结构学习笔记（特殊的线性表：栈与队列）

  　　　　　　　　　　　　　　　　　　　　　　　　　　　　栈与队列栈是限定仅在表尾（栈顶）进行插入和删除操作的线性表（后进先出）。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表（先进先出... 查看详情

  数据结构与算法学习笔记图(代码片段)

  数据结构与算法学习笔记(8)图复习文章目录数据结构与算法学习笔记(8)图一.图的定义和基本术语二.图的类型定义三.图的存储结构1.邻接矩阵无向图的邻接矩阵有向图的邻接矩阵网(有权图)邻接矩阵的存储表示创建邻接矩阵(以无... 查看详情

  数据结构与算法学习笔记串,数组和广义表(代码片段)

  数据结构与算法学习笔记(6)串、数组和广义表截图、笔记来自:王卓数据结构与算法文章目录数据结构与算法学习笔记(6)串、数组和广义表一.串1.串的定义2.串的类型定义、存储结构及其运算串的类型定义串的存储串的顺序存储结... 查看详情

  计算机软考笔记之《数据结构与算法》

  ...结构4、常用算法(1)算法概述①算法的基本概念②算法与数据结构③算法的描述 查看详情

  学习数据结构笔记---查找算法(线性查找,二分查找,插值查找,斐波那契查找)(代码片段)

  B站学习传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）ml1.顺序/线性查找算法(SequentialSearch)2.二分查找算法3.插值查找4.斐波那契查找1.顺序/线性查找算法(SequentialSearch)线性查找的话,比较简单,直接遍历数... 查看详情

  数据结构与算法学习

  数据结构是系统的骨肉，算法是系统的灵魂；没有算法，系统就是一具死尸；没有数据，算法就是孤魂野鬼；数据结构的基本概念：1、集合2、线性表3、树、4、图近几天主要学习的是线性表的内容：单链表，循环链表的基本概... 查看详情

  python学习笔记--数据结构与算法哈希表implementationofahashtable

  Python内建的字典就是用hashtable实现的。这里我们只是通过实现自己的hashtable来加深对hashtable和hashfunctions的理解。【概念1：Mapping（映射）】　　字典通过键(Key)来索引。一个key对应一个存储的value。任意不可变的数据类型均可作... 查看详情

  数据结构与算法学习(介绍)

  数据结构与算法介绍数据结构与算法的重要性算法是程序的灵魂，优秀的程序可以在海量数据计算时，任然保持高速运算框架和缓存技术的核心时算法高薪数据结构与算法的关系数据(data)结构(Structure)是一门研究组织数据方式的... 查看详情

  郑捷《机器学习算法原理与编程实践》学习笔记（第七章预测技术与哲学）7.1线性系统的预测

   7.1.1回归与现代预测 7.1.2最小二乘法 7.1.3代码实现（1）导入数据defloadDataSet(self,filename):#加载数据集X=[];Y=[]fr=open(filename)forlineinfr.readlines():curLine=line.strip().split(‘ ‘)X.append(float(curLine[0]) 查看详情