1.1 定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。

同一线性表中的元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在着序偶（ordered pair）关系。

1.2 逻辑结构

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。

 

1.2.1 特性

1. 存在唯一一个表头元素（第一个元素）；
2. 存在唯一一个表尾元素（最后一个元素）；
3. 除了表头元素外，每个数据元素有且仅有一个前驱；除了表尾元素外，每个数据元素有且仅有一个后继。

1.2.2 基本操作

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

ADT List{

InitList(&L)
    操作结果：构造一个空的线性表L。
DestroyList(&L)
    初始条件：线性表L已存在。
    操作结果：销毁线性表L。
ClearList(&L)
    初始条件：线性表L已存在。
    操作结果：将L重置为空表。
ListEmpty(L)
    初始条件：线性表L已存在。
    操作结果：若L为空表，则返回true，否则返回false。
ListLength(L)
    初始条件：线性表L已存在。
    操作结果：返回L中数据元素个数。
GetElem(L, i, &e)
    初始条件：线性表L已存在，1<=i<=L.length。
    操作结果：用e返回L中第i个数据元素的值。
LocateElem(L, e, compare())
    初始条件：线性表L已存在，compare()是数据元素判定函数。
    操作结果：返回L藏第1个与e满足关系compare()的数据元素的位序。若这样的元素不存在，则返回值为0。
PriorElem(L, cur_e, &pre_e)
    初始条件：线性表L已存在。
    操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem(L, cur_e, &next_e)
    初始条件：线性表L已存在。
    操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
ListInsert(&L, i, e)
    初始条件：线性表L已存在，1<=i<=L.length+1。
    操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加一。
ListDelete(&L, i, &e)
    初始条件：线性表L已存在且非空，1<=i<=L.length。
    操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一。
ListTraverse(L, visit())
    初始条件：线性表L已存在。
    操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADT List

1.3 顺序表

1.3.1 创建和销毁

①静态分配内存

//static allocation
typedef struct{
    ElemType data[LIST_MAX_SIZE];
    int length;
}SqList;

bool InitList(SqList &L){
    //for(int i=0; i 
结构体有两个成员变量：
 
最大长度为LIST_MAX_SIZE（宏定义，见文末完整代码）的自定义类型静态数组data。
指示当前顺序表长度的整型变量length。
InitList：
 
函数为bool类型变量，用于指示函数运行是否成功。
将顺序表当前长度length设为0。
        关于注释中，给每个数据元素赋初始值，关注到以下问题：
 
        (1)官方教材中，并无静态分配的参考代码。
 
        (2)辅助教材中，静态分配赋初始值，动态分配无这一动作。
 
        (3)在对线性表的任何操作中，都会受到L.length的限制，即不会访问到没有数据的地方。
 
        (4)在L.length的限制下，只要在长度内，就必然有数据，不可能访问到内存中的脏数据。
 
        所以，个人认为赋初始值的操作没有必要，即使有，也不应该像辅助教材中那样写，若非数值型变量，仅仅用等于号赋值是不够的（函数赋值或重载等于号）。后续在清空线性表操作中，也有类似问题。仁者见仁智者见智，欢迎讨论。
 
②动态分配内存
 
//dynamic allocation
typedef struct{
    ElemType *data;
    int length;
    int listsize;
}SqList;

bool InitList(SqList &L){
    L.data = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.data) return false;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return true;
}

bool DestroyList(SqList &L){
    free(L.data);
    return true;
}
 
结构体有三个成员变量：
 
指向动态分配返回首地址的指针data。
指示当前顺序表长度的整型变量length。
指示当前顺序表最大长度的整型变量listsize，类似静态的LIST_MAX_SIZE，只是这个变量会随着需求不断变大。
InitList（创建、初始化）：
 
void *malloc(unsigned int size)，所以返回的指针需要强转。
若内存分配失败（没有那么长的连续内存），则返回NULL，!L.data为true。
将顺序表当前长度length设为0。
将当前顺序表最大长度listsize设为LIST_INIT_SIZE（宏定义，见文末完整代码），指定顺序表初始的最大长度，在1.3.2的ListIncrease函数中有更详细的调用。
DestroyList（销毁）：
 
 
动态分配需要销毁的详细原因见注中红色部分，当静态内存（数组）不用时，编译器会自动收回空间；但使用malloc分配的动态内存必须要手动free。
 
 
free只需连续动态内存的首地址。
 
*注：关于为什么叫做动态和静态，以及各自的优缺点，这里引用一篇文章
 
 
 
静态内存的分配是在程序开始编译时完成的，不占用CPU资源而动态内存的分配是在程序运行时完成的；动态内存的分配与释放都是占用CPU资源的。
静态内存是在栈上分配的；动态内存是在堆上分配的。
动态内存分配需要指针和引用数据类型的支持；静态内存不需要。
静态内存分配是在编译前就已经确定了内存块的大小，属于按计划分配内存而动态内存区；动态分配是在程序运行过程中，根据需要随时分配的，属于按需分配。
静态内存的控制权是交给编译器的；而动态内存的控制权是由程序员决定的。
 
动态内存和静态内存 - 知乎动态内存与静态内存是两种不同的分配内存的方式，那么它们在分配方式上存在什么样的区别呢? (1)静态内存的分配是在程序开始编译时完成的，不占用CPU资源而动态内存的分配是在程序运行时完成的，动态内存的分配与释…https://zhuanlan.zhihu.com/p/54776045
 
 
1.3.2 插入和删除 
这里还得扯一下静态分配和动态分配
 
在插入一个元素时，线性表的长度会加一，自然就可能超出最大长度的限制。
 
而此时，静态分配唯一能采取的办法是，①重新定义一个更长的数组，②将原有数组的所有元素拷贝到新数组中，③把新元素插入新数组。
 
对于动态分配来说，处理方法不唯一，比如可以通过malloc函数，重新找一块更大的连续空间，执行和静态分配同样的动作。另外，个人认为比较方便的一点是，可以通过realloc函数直接操作。
 
*注：realloc函数的原理
 
 
 
ElemType *q =（ElemType *)realloc(p, ...)
 
 
realloc() 扩展内存时，如果当前连续内存块足够 realloc 的话，只是将p所指向的空间扩大，并返回p的指针地址。 这个时候 q 和 p 指向的地址是一样的。
如果当前连续内存块不够长度，再找一个足够长的地方，分配一块新的内存q，并将 p指向的内容拷贝到 q，返回 q。并将p所指向的内存空间删除。
 
c函数之realloc工作原理及其正确用法_archerLea的博客-CSDN博客_realloc原理直接给例子，围绕例子来谈：https://blog.csdn.net/deggfg/article/details/23515319
 
 
后续内容将不再讨论静态分配方式
 
bool ListIncrease(SqList &L){
    L.listsize += LIST_INCREMENT;
    ElemType *newbase = (ElemType *)realloc(L.data, L.listsize*sizeof(ElemType));
    if(!newbase) return false;
    L.data = newbase;
    return true;
}

bool ListInsert(SqList &L, int i, ElemType e){
    if(i<1||i>L.length+1)return false;
    if(L.length>=L.listsize){
        if(!ListIncrease(L)) return false;
    }

    //normal
    for(int j=L.length-1; j>=i-1; j--) L.data[j+1] = L.data[j];
    L.data[i-1] = e;

    L.length++;
    return true;
}

bool ListDelete(SqList &L, int i, ElemType &e){
    if(i<1||i>L.length)return false; //not empty

    //normal
    e = L.data[i-1];
    for(int j=i; j<=L.length-1; j++) L.data[j-1] = L.data[j];

    L.length--;
    return true;
}
 
 ListIncrease（扩容）：
 
顺序表的最大长度在原有基础上增加一个LIST_INCREMENT（宏定义，见文末完整代码）。
用的是realloc函数，返回值和malloc一样，都需要进行强转。
realloc函数有两个参数，第一个是原先malloc返回的首地址，第二个是需要的长度。
因为realloc的结果可以指向一块新的内存区，所以需要对data进行重新赋值。
ListInsert（插入）：
 
i代表位序，位序和数组下标不是同一个概念，我们一般说“数组的第i个元素”，其中的i代表位序，对应的数组下标应为[i-1]。
插入的时候，位序的范围是从1到L.length+1，1就是第1个位置，第L.length+1个是最后一个元素后面的位置（不是最后一个元素，最后一个元素的位序是L.length）。
如果数据个数等于（书上写的大于等于）最大长度，那么需要调用ListIncrease扩容。
新来的数据元素会插入在第i个位置上（对应下标[i-1]）。
从第i个变量开始，后面的每个元素依次后移，共L.length-i+1个元素，这个操作是从后向前进行的。
添加完了之后顺序表长度再加一。
ListDelete（删除）：
 
删除的时候，位序的范围是从1到L.length，比插入的时候少一个，插入可以插在最后一个空位上，删除不可以，最多也只能删除到最后一个（位序为L.length）。
先回传变量，再删除。
从第i+1个变量开始，后面的每个元素依次前移，共L.length-(i+1)+1=L.length-i个元素，这个操作是从前向后进行的。
删除完了之后顺序表长度再减一。
注意到官方教材中，除了位序的限制外，还应要求顺序表非空。i>L.length其实隐含了这一条件，当顺序表为空表时，L.length==0，位序i>=1>L.length，会直接返回false。
 
 
 
注意到前文代码中有个//normal，既然有normal，就有不normal。
 
指针写法参考官方教材代码；
 
普通写法参考辅助教材代码。
 
bool ListInsert(SqList &L, int i, ElemType e){
    if(i<1||i>L.length+1)return false;
    if(L.length>=L.listsize){
        if(!ListIncrease(L)) return false;
    }

    //pointer
    ElemType *q = &(L.data[i-1]);
    for(ElemType *p=&(L.data[L.length-1]); p>=q; p--) *(p+1) = *p;
    *q = e;

    L.length++;
    return true;
}

bool ListDelete(SqList &L, int i, ElemType &e){
    if(i<1||i>L.length)return false; //not empty

    //pointer v1
    ElemType *p = &(L.data[i-1]);
    e = *p;
    ElemType *q = L.data+L.length-1;
    for(p++; p<=q; p++) *(p-1) = *p;
    
    L.length--;
    return true;
}
 
1.3.3 查找 
①按位查找（随机存取特性）
 
bool GetElem(SqList L, int i, ElemType &e){
    if(i<1||i>L.length) return false;
    e = L.data[i-1];
    return true;
}
 
 GetElem（按位查找）：
 
边界条件，只能按位序查找到第1个到第L.length个这个范围内的元素。
下标等于位序减一。
 
 
假设线性表的每个元素需要占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置…一般来说，线性表的第i个数据元素ai的存储位置为
 
 
LOC(ai) = LOC(a1) + (i-1)*l
 
 
式中LOC(a1)是线性表第一个数据元素a1的存储位置，通常称作线性表的起始位置或基地址…通常称这种存储结构的顺线性表为顺序表…每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素再线性表中的位序成正比的常数。由此，只要确定了存储线性表的起始位置，线性表中任意数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
 
 
 
②按值查找
 
bool compare(ElemType a, ElemType b);

int LocateElem(SqList L, ElemType e, bool (* compare)(ElemType, ElemType)){
    for(int j=0; j 
LocateElem（按值查找）：
 
这里采用了官方教材的写法，会给函数传递一个函数指针，这里我自己也一知半解，无法形成什么系统性的语言。
个人认为，针对不同的数据类型，compare的写法可易可难，但LocateElem的写法无需改变。
个人认为，可以定义不同的compare函数，针对不同的使用场景，调用LocateElem的时候传入不同的compare函数。
同样的传入指针的操作可在1.3.4的ListTraverse函数中找到。
函数返回的是位序，但是函数中的j是下标，所以返回时需要加一。
1.3.4 补充   
bool ClearList(SqList &L){
    //for(int j=0; j 
ClearList（置空） ：
 
是否需要将元素置为初始值仍存疑。
必须将长度修改为0。
bool ListEmpty(SqList L){
    return L.length==0?true:false;
}

int ListLength(SqList L){
    return L.length;
}
 
ListEmpty（判空）：若L为空表，则返回true，否则返回false。
 
ListLength（判长）：返回L中数据元素个数。
 
bool PriorElem(SqList L, ElemType cur_e, ElemType &pre_e){
    int i = LocateElem(L, cur_e, compare);
    if(!i||i==1) return false;
    pre_e = L.data[i-2];
    return true;
}

bool NextElem(SqList L, ElemType cur_e, ElemType &next_e){
    int i = LocateElem(L, cur_e, compare);
    if(!i||i==L.length) return false;
    next_e = L.data[i];
    return true;
}
 
 PriorElem（前驱）：若cur_e在L中且不是第一个元素，用pre_e返回cur_e的前驱。注意第i个元素的前驱的下标为[i-2]。
 
NextElem（后继）：若cur_e在L中且不是最后一个元素，用next_e返回cue_e的后继。注意第i个元素的后继的下标为[i]。
 
bool visit(ElemType e);

bool ListTraverse(SqList L, bool (*visit)(ElemType)){
    for(int i=0; i 
ListTraverse（遍历）：对L的每个元素都调用visit函数。 对此处的函数指针，我的理解和前文的按值查找一样。
 
*注：完整代码请见文末。
 
1.4 链表 
1.5 对比