线性表

线性表的定义：
线性表要求其中的数据元素必须是同类型的，但并没有规定必须是哪种类型。
它们可以是原子类型的，而对于复杂信息的存储，数据元素也可以是结构类型的。


线性表的特点：

• 同一性 —— 线性表必须是由同类数据元素组成。
• 有穷性 —— 数据元素的个数是有限的。
• 有序性 —— 相邻数据元素之间存在着序偶关系（有顺序）。

==》相同特性的有穷序列
线性表的逻辑结构：

1. 只有一个表头元素。
2. 只有一个表尾元素。
3. 表头元素没有前驱，表尾元素没有后继。
4. 除表头和表尾元素之外，其他元素只有一个直接前驱，也只有一个直接后继。

线性表（线性结构逻辑结构）+顺序存储和链式存储（两大物理结构）
==》

启示
线性表：零个或多个数据元素的有限序列。
这里需要强调几个关键的地方。

• 首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
• 然后，线性表强调是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

引言
今天我们要开始学习数据结构中最常用和最简单的一种结构，在介绍它之前先讲个例子。
我经常下午去幼儿园接送儿子，每次都能在门口看到老师带着小朋友们，一个拉着另一个的衣服，依次从教室出来。而且我发现很有规律的是，每次他们的次序都是一样。比如我儿子排在第5个，每次他都是在第5个，前面同样是那个小女孩，后面一直是那个小男孩。这点让我很奇怪，为什么一定要这样？
有一天我就问老师原因。她告诉我，为了保障小朋友的安全，避免漏掉小朋友，所以给他们安排了出门的次序，事先规定好了，谁在谁的前面，谁在谁的后面。这样养成习惯后，如果有谁没有到位，他前面和后面的小朋友就会主动报告老师，某人不在。即使以后如果要外出到公园或博物馆等情况下，老师也可以很快地清点人数，万一有人走丢，也能在最快时间知道，及时去寻找。
我一想，还真是这样。小朋友们始终按照次序排队做事，出意外的情况就可能会少很多。毕竟，遵守秩序是文明的标志，应该从娃娃抓起。而且，真要有人丢失，小孩子反而是最认真负责的监督员。
再看看门外的这帮家长们，都挤在大门口，哪个分得清他们谁是谁呀。与小孩子们的井然有序形成了鲜明的对比。哎，有时大人的所作所为，其实还不如孩子。
这种排好队的组织方式，其实就是今天我们要介绍的数据结构：线性表。

所以，线性表的抽象数据类型定义如下：

ADT 线性表(List)
Data
线性表的数据对象集合为{a 1 , a 2 , ......, a n }，每个元素的类型均为DataType。
其中，除第一个元素a 1 外，每一个元素有且只有一个直接前驱元素，
除了最后一个元素a n 外，每一个元素有且只有一个直接后继元素。
数据元素之间的关系是一对一的关系。

Operation
InitList(*L):          初始化操作，建立一个空的线性表L。
ListEmpty(L):          若线性表为空，返回true，否则返回false。
ClearList(*L):         将线性表清空。
GetElem(L, i, *e):     将线性表L中的第i个位置元素值返回给e。
LocateElem(L, e):      在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；

仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。

/* 将所有的在线性表Lb中但不在La中的数据元素插入到La中 */
void unionL(List *La, List Lb)
{
    int La_len, Lb_len, i;
    /* 声明与La和Lb相同的数据元素e */
    ElemType e;                             
    /* 求线性表的长度 */
    La_len = ListLength(*La);               
    Lb_len = ListLength(Lb);
    for (i = 1; i <= Lb_len; i++)
    {
        /* 取Lb中第i个数据元素赋给e */
        GetElem(Lb, i, &e);                 
        /* La中不存在和e相同数据元素 */    
        if (!LocateElem(*La, e))            
            /* 插入 */
            ListInsert(La, ++La_len, e);    
    }
}

注意一个很容易混淆的地方：
当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。
如果需要被改动，则需要传递指向这个参数的指针，如果不用被改动，可以直接传递这个参数。

线性表（linear list）：
是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

[

](https://blog.csdn.net/m0_59139260/article/details/121255554)