定义和概念

定义

线性表是零个或多个数据元素的有限序列。

概念

直接前驱元素

a2是a3的直接前驱元素，是对于后者来说的

直接后继元素

a3是a2的直接后继元素，是对于前者来说的‘

线性表的长度

线性表中元素的个数是线性表的长度

空表

没有元素，n=0

位序

元素在线性表中的位置，例如Ai是线性表中的第i个元素，i是A元素的位序

线性表的抽象数据类型

线性表的定义

除a1外其他元素都有且只有一个直接前驱元素，除an外都有一个后继元素，元素与元素是一一对应的关系。

定义方法一：固态定义

通过编译器提前定义好数组、链表等，个数有限，且不能在使用过程中增加

#define MAXLIST 100
void initList(){
    int list[MAXLIST];//长度为100的数组
}

定义方法二：动态定义

通过动态内存分配的方法来分配空间，例如链表和栈

#include <malloc.h>
void initList(){
    int *p = NULL;
    p = (int*)malloc(sizeof(int) * 100);//100个int大小的内存空间
}

定义方法三：混合定义

通过固态定义长度、动态定义大小的方法或是反过来来定义特殊情况下需要的线性表

#include<malloc.h>
#define MAXLIST 100
void initList(){
    int *parr[100];
    for(int i = 0;i < 100; i++){
        parr[i]=(int *)malloc(sizeof(int)*100);
    }
}//定义一百个指针数组，每个指针数组都存储着大小为100的动态内存空间
//不支持指针的语言传引用

线性表的基本操作

初始化操作

建立一个空表并清空
InitList

参数列表

1. 传递一个接收表的头指针（返回值可省略）

2. 若是动态表，传入一个表的长度或大小

   返回值

3. 返回接收表的头指针（参数可省略）

4. 返回是否成功分配空间（布尔值）

   实现思路

   通过循环来分配空间，将头指针传回

判断空操作

空则返回真，有元素则返回假
ListIsEmpty

参数列表

1. 传入一个表头地址
2. 传入一个接收指针（返回值可忽略）

   返回值

   是否为空的布尔值

   实现思路

   第一个元素是否存在，表示栈顶的变量是否为空（或标识），是否为默认值、是否为有效值。

清空表操作

将传入的表清空

参数列表

1. 传入表头

   返回值

   传出成功状态

   实现方式

   将值或指针清空或置空，如果是数组则传入默认值，如果是链表就解构链表，如果是栈就把栈顶变量恢复默认

删除表操作

删除整个表

参数列表

1. 传入表头

   返回值

   是否成功

   实现方式

   通过空间释放、链接析构、指针置空等方式解构一个表，或是栈顶栈底恢复默认值。

遍历表操作

遍历表中所有元素

参数列表

1. 头指针

   返回值

   是否遍历成功

   实现方法

   通过循环来遍历所有元素。

返回个数操作

返回表有多少个元素

参数列表

1. 传入表头

2. 接收个数的指针

   返回值

3. 接收个数

4. 是否成功

   实现方式

   如果有计数则通过计数判断，没有则通过标记头元素的地址，然后计算第一个元素的大小，开始遍历直至地址重合。或是直接计算空间大小除以子空间大小。

   获取元素操作

   获取某个特定元素

   参数列表

5. 表地址

6. 元素位置

7. 接收元素的指针

   返回值

8. 是否成功获取

9. 获取的值

10. 获取的地址

    实现方式

    通过遍历对比的方法循环找到值，如果有两个则返回不成功

    查找判断操作

    查找某个元素或判断是否存在

    参数列表

11. 接收查找元素或指针

12. 接收成功标志

    返回值

13. 返回是否存在

14. 返回是否成功

    实现方式

    通过遍历判断是否存在，如果存在多个则返回假，或传回包含多个元素的地址指针数组

插入元素操作

在某个值或末尾插入一个元素

参数列表

1. 表头指针
2. 插入的地点
3. 接收成功值

   返回值

   是否成功

   实现方法

   从后到前依次向后，若超出最大范围则报错或新建一个空间，然后插入。

删除元素操作

删除某个元素

参数列表

1. 表头指针
2. 删除的元素值或指针

3. 接收是否删除成功

   返回值

4. 是否删除成功

   实现方法

   删除元素后把后继依次前移，前移完成后销毁最后一个空间或指针置空或栈顶向后移。

   线性表的复杂操作

   线性表的链接

   将两个表链接到一起，例如通过指针链接、链接节点的内存空间。链接地址储存在哑结点。

   线性表的对比

   排序后对比，映射对比，大小量对比，或生成映射表。

   线性表的排序

   通过排序算法，或者多个排序算法，在不同情况下使用，或自动选择使用的场景。

   线性表的循环

   将尾元素指向第一个元素，形成闭环或是通过指针将头节点顶住。