20230303 2.1. 线性表及其实现

标签：结点 20230303 线性表元素 List private 链表 2.1

如何表示多项式?

\[f(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n \]

方法1：顺序存储结构直接表示

\(a[i]\) ：项 \(x^i\) 的系数 \(a_i\)

例如：

\[f (x) =4x^5-3x^2+1 \]

下标i	0	1	2	3	4	5
a[i]	1	0	-3	0	0	4

问题：

浪费空间，例如 \(x+3x^{2000}\)

方法2：顺序存储结构表示非零项

每个非零项 \(a_ix^i\) 涉及两个信息：系数 \(a_i\) 和指数 i 可以将一个多项式看成是一个 ( \(a_i\) , i ) 二元组的集合。

下标i	0	1	2
系数 \(a^i\)	4	-3	1
指数i	5	2	0

按指数大小有序存储！

方法3：链表结构存储非零项

链表中每个结点存储多项式中的一个非零项，包括 系数和指数两个数据域 以及 一个指针域

coef	expon	link

@Data
public class Polynomial {
    /**
     * 系数
     */
    private int coef;

    /**
     * 指数
     */
    private int expon;


    private Polynomial link;
}

线性表

线性表(Linear List) ：由 同类型数据元素 构成 有序序列 的线性结构

表中元素个数称为线性表的长度
线性表没有元素时，称为空表
表起始位置称表头，表结束位置称表尾

抽象数据类型描述

类型名称：线性表（List）

数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1 , a2 , ,an )

操作集：线性表L ∈ List，整数i表示位置，元素X ∈ ElementType，

线性表基本操作主要有：

List MakeEmpty() ：初始化一个空线性表L；
ElementType FindKth( int K, List L ) ：根据位序K，返回相应元素；
int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；
void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；
void Delete( int i, List L )：删除指定位序i的元素；
int Length( List L )：返回线性表L的长度n。

顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

下标i	0	1	...	i-1	i	...	n-1 (Last)	...	MAXSIZE-1
Data	\(a_1\)	\(a_2\)	...	\(a_i\)	\(a_{i+1}\)	...	\(a_n\)	...	-

public class List {
    private Object[] data;
    private int maxSize;
    private int last;
}

参考 java.util.ArrayList

链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

@Data
public class LNode {
    private Object data;
    private LNode next;
}

广义表

给定二元多项式：

\[P(x,y)=9x^{12}y^2+4x^{12}+15x^8y^3-x^8y+3x^2 \]

【分析】可以将上述二元多项式看成关于x 的一元多项式

\[P(x,y)=(9y^2+4)x^{12}+(15y^3-y)x^8+3x^2 \]

所以，上述二元多项式可以用“复杂”链表表示为：

广义表(Generalized List)

广义表是线性表的推广
对于线性表而言， n个元素都是基本的单元素；
广义表中，这些元素不仅可以是单元素也可以是另一个广义表。

@Data
public class GNode {
    /**
     * 标志域：0表示结点是单元素，1表示结点是广义表
     */
    private int tag;

    /**
     * 指向后继结点
     */
    private GNode next;

    @Data
    public static class URegion {
        Object data;
        GNode sub;
    }

}

多重链表

多重链表：链表中的节点可能同时隶属于多个链

多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表。

多重链表有广泛的用途：

基本上如树、图这样相对
复杂的数据结构都可以采用多重链表方式实现存储。

例题

十字链表

矩阵可以用二维数组表示，但二维数组表示有两个缺陷：

一是数组的大小需要事先确定，
对于“稀疏矩阵 ”，将造成大量的存储空间浪费。

【分析】采用一种典型的多重链表—— 十字链表 来存储稀疏矩阵

只存储矩阵非0元素项
- 结点的数据域：行坐标Row、列坐标Col、数值Value
每个结点通过两个指针域，把同行、同列串起来;
- 行指针（或称为向右指针）Right
- 列指针（或称为向下指针）Down

用一个标识域Tag来区分头结点和非0元素结点：
头节点的标识值为“Head”，矩阵非0元素结点的标识值为“Term”。

多项式加法运算

\[P1=3x^5+4x^4-x^3+2x-1 \newline P2=2x^4+x^3-7x^2+x \newline P=3x^5+6x^4-7x^2+3x-1 \]

采用不带头结点的单向链表，按照指数递减的顺序排列各项

Java 关联

java.util.ArrayList
java.util.LinkedList

java.util.List 方法

add, addAll
clear
contains, containsAll
equals
forEach
get
indexOf, lastIndexOf
isEmpty
iterator,listIterator, spliterator
stream, parallelStream
remove, removeAll, removeIf
replaceAll
retainAll
set
size
sort
subList
toArray

标签：结点,20230303,线性表,元素,List,private,链表,2.1
From： https://www.cnblogs.com/huangwenjie/p/17490484.html