1，线性表的定义

线性表是具有相同特性的数据元素的一个有限序列，该序列中所含元素的个数叫做线性表的长度，用n表示，n>=0。当n=0时，表示线性表是一个空表，即表中不包括任何元素。第一个元素叫表头元素，最后一个元素叫表尾元素。
线性表：零个或多个数据元素的有限序列。

线性表、包括顺序表和链表
顺序表（其实就是数组）里面元素的地址是连续的，
链表里面节点的地址不是连续的，是通过指针连起来的。

---

2，线性表的抽象数据类型

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

InitList(L):初始化操作，建立一个空的线性表。
ListEmpty(L):若线性表为空，返回true，否则返回false。
ClearList(L):线性表清空。
GetElem(L,i,e):将线性表L中第i个位置元素返回给e。
LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功,返回该元素在表中的序列号；否则，返回0表示失败。
ListInsert(L,i,e):在线性表的第i个位置插入元素e。
ListDelete(L,i,e):删除线性表L中的第i个元素，并用e返回其值
ListLength(L):返回线性表L的元素个数。
PrintList(L):打印线性表

---

3，线性表的顺序存储结构

3.1. 顺序存储定义

顺序表，一般使用数组实现，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定连续的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中，数组大小有两种方式指定，一是静态分配，二是动态扩展。

顺序表相关的操作跟数组有关，一般都是移动数组元素。

3.2.代码实现

#include<iostream>
using namespace std;

const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
    SeqList(){length=0;}            //无参数构造方法
    SeqList(DataType a[],int n);    //有参数构造方法
    ~SeqList(){}                    //析构函数
    int Length(){return length;}    //线性表长度
    DataType Get(int i);            //按位查找
    int Locate(DataType x);         //按值查找
    void Insert(int i,DataType x);  //插入
    DataType Delete(int i);         //删除
    void PrintList();               //遍历
private:
    DataType data[MaxSize];         //顺序表使用数组实现
    int length;                     //存储顺序表的长度
};
template <class DataType>
SeqList<DataType>::SeqList(DataType a[],int n)
{
    if(n>MaxSize) throw "wrong parameter";
    for(int i=0;i<n;i++)
        data[i]=a[i];
    length=n;
}

template <class DataType>
DataType SeqList<DataType>::Get(int i)
{
    if(i<1 && i>length) throw "wrong Location";
    else return data[i-1];
}

template <class DataType>
int SeqList<DataType>::Locate(DataType x)
{
    for(int i=0;i<length;i++)
        if(data[i]==x) return i+1;
    return 0;
}

template <class DataType>
void SeqList<DataType>::Insert(int i,DataType x)
{
    if(length>=MaxSize) throw "Overflow";
    if(i<1 || i>length+1) throw "Location";
    for(int j=length;j>=i;j--)
        data[j]=data[j-1];
    data[i-1]=x;
    length++;
}

template <class DataType>
DataType SeqList<DataType>::Delete(int i)
{
    int x;
    if(length==0) throw "Underflow";
    if(i<1 || i>length) throw "Location";
    x = data[i-1];
    for(int j=i;j<length;j++)
        data[j-1] = data[j];
    length--;
    return x;
}

template <class DataType>
void SeqList<DataType>::PrintList()
{
    for(int i=0;i<length;i++)
        cout<<data[i]<<endl;
}

int main()
{
    SeqList<int> p;
    p.Insert(1,5);
    p.Insert(2,9);
    p.PrintList();
    p.Insert(2,3);
    cout<<p.Length()<<endl;
    p.PrintList();
    cout<<p.Get(3)<<endl;
    p.Delete(2);
    p.PrintList();
    return 0;
}

3.3.3. 顺序存储的优缺点
优点：

• 随机访问特性，查找O(1)时间，存储密度高；
• 逻辑上相邻的元素，物理上也相邻；
• 无须为表中元素之间的逻辑关系而增加额外的存储空间；

缺点：

• 插入和删除需移动大量元素；
• 当线性表长度变化较大时，难以确定存储空间的容量；
• 造成存储空间的“碎片”

---

4，线性表的链式存储结构

4.1. 链式存储定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些元素可以存在内存未被占用的任意位置。
链表可以理解为一群小朋友排队，每个只需记住自己后面那个小朋友的名字就好了，站最后面的小朋友不需要记名字

4.2.代码实现

#include<iostream>
using namespace std;

template<class DataType>
struct Node
{
    DataType data;
    Node<DataType> *next;
};

template<class DataType>
class LinkList
{
public:
    LinkList();    //无参数构造
    LinkList(DataType a[], int n);  //有参数构造
    ~LinkList();             //析构函数
    int Length();            
    DataType Get(int i);      //按位查找
    int Locate(DataType x);   //按值查找
    void Insert(int i, DataType x);  //插入
    DataType Delete(int i);     //删除
    void PrintList();    //遍历输出              
private:
    Node<DataType> *first;          
};

template<class DataType>
LinkList<DataType>::LinkList()
{
    first = new Node<DataType>;
    first->next = NULL;
}

template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
    first = new Node<DataType>;
    first->next = NULL;
    for (int i = 0; i < n; i++)
    {
        Node<DataType> *s = new Node<DataType>;
        s->data = a[i];
        s->next = first->next;
        first->next = s;
    }
}

template<class DataType>
LinkList<DataType>::~LinkList()
{
    while (first != NULL)
    {
        Node<DataType>* q = first;
        first = first->next;
        delete q;
    }
}

template<class DataType>
int LinkList<DataType>::Length()
{
    Node<DataType>* p = first->next;
    int count = 0;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

template<class DataType>
DataType LinkList<DataType>::Get(int i)
{
    Node<DataType>* p = first->next;
    int count = 1;
    while (p != NULL && count<i)
    {
        p = p->next;
        count++;
    }
    if (p == NULL) throw "Location";
    else return p->data;
}

template<class DataType>
int LinkList<DataType>::Locate(DataType x)
{
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL)
    {
        if (p->data == x) return count;
        p = p->next;
        count++;
    }
    return 0;
}

template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count<i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL) throw "Location";
    else {
        Node<DataType> *s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

template<class DataType>
DataType LinkList<DataType>::Delete(int i)
{
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count<i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL) throw "Location";
    else {
        Node<DataType> *q = p->next;
        int x = q->data;
        p->next = q->next;
        return x;
    }
}

template<class DataType>
void LinkList<DataType>::PrintList()
{
    Node<DataType> *p = first->next;
    while (p != NULL)
    {
        cout << p->data << endl;
        p = p->next;
    }
}

int main()
{
    LinkList<int> p;
    p.Insert(1, 6);
    p.Insert(2, 9);
    p.PrintList();
    p.Insert(2, 3);
    p.PrintList();
    cout << p.Get(2) << endl;
    cout << p.Locate(9) << endl;
    cout << p.Length() << endl;
    p.Delete(1);
    p.PrintList();
    return 0;
}

4.3.链式存储的优缺点

优点：

• 插入、删除不需移动其他元素，只需改变指针.
• 链表各个节点在内存中空间不要求连续，空间利用率高

缺点：

• 查找需要遍历操作，比较麻烦

参考文章