线性表

学习内容来自数据结构详解——线性表（C++实现）

线性表（List）:零个或多个数据元素的有限序列。
顺序表（数组）：元素地址单元连续。
链表：结点地址不连续，由指针指向下个元素地址。

一、线性表的抽象数据类型

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):打印线性表

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的。
对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

二、顺序储存结构

定义：用一段连续地址单元依次储存
结构：
顺序表模板类代码：

//顺序存储
const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
    SeqList() { length = 0; } //无参数构造
    SeqList(DataType[], 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;
};

顺序表描述需要三个属性：

• 储存空间的起始位置：数组data
• 线性表最大储存容量：数组长度MaxSize
• 线性表当前长度：length

有参数构造：

创建一个长度为n的顺序表，需要将给定的数组元素作为线性表的数据元素传入顺序表中，并将传入的元素个数作为顺序表的长度。

template <class DataType>
SeqList<DataType>::SeqList(DataType a[],int n) 
{
    if (n > MaxSize) throw"wrong parameter";
    for (int i = 0; i < MaxSize; i++)
        data[i] = a[i];
    length = n;
}

按位查找

时间复杂度O(1).

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

按值查找

对顺序表元素依次比较，返回下标+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  "overSize";
    if (i<1 || i>length + 1) throw "eror Location";
    
    for (int j=length; j > i-1; j--)
    {
        data[j] = data[j-1];
    }
    data[i - 1] = x;
    length++;
}

删除

• 注意元素移动方向，移动元素前需取出被删元素。

• 表为空，则发生下溢；位置不合理异常，引发位置

  
  

template<class DataType>
DataType SeqList<DataType>::Delete(int i)
{
    if (i<1 || i>length + 1) throw "eror Location";
    DataType 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++)
        std::cout << data[i] << std::endl;
}

顺序储存的优缺点

优点：

• 随机访问特性，查找时间O(1),存储密度高
• 无须为逻辑关系增加额外储存空间
  缺点：
• 插入、删除需移动大量数据元素
• 线性表长度变化大，难以确定储存空间
• 造成储存空间“碎片化”

三、链式储存

1.链式储存定义

链表的定义是递归的，它或者为空null，或者指向另一个节点node的引用，这个节点含有下一个节点或链表的引用，线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。

2.链式储存实现方式

储存方法

//链表
template<class DataType>
struct Node  //结构体模板
{
    DataType data; //储存数据
    Node<DataType> *next; //储存下一节点地址（传递自定义类型参数DataType）
};

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

结构
单链表模板类代码：

template<class DataType>
class LinkList 
{
public:
    LinkList();
    LinkList(DataType [],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>; //new头指针指向的头地址
    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(DataType a[], int n)
{
    first = new Node<DataType>;
    Node<DataType> *r = first;
    for (int i = 0; i < n; i++)
    {
        Node<DataType> *s = new Node<DataType>;
        s->data = a[i];
        r->next = s;
        r = s; 
    }
    r->next = NULL; //终端结点指针域置空
}

析构函数

单链表中结点通过new申请，需通过析构中的delete进行释放。

template<class DataType>
LinkList<DataType>::~LinkList()
{
    while (first != NULL) //头地址不为空，链表有值
    {
        Node<DataType> *q = first;
        first = first->next;
        delete q;
    }
}

计算长度

将单链表扫描一遍,，时间复杂度为O(n)

//时间复杂度O(n)
template<class DataType>
int LinkList<DataType>::Length()
{
    Node<DataType> *p = first->next;
    int count = 0;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

按位查找

单链表中即使知道节点位置也不能直接访问，需要从头指针开始逐个节点向下搜索，平均时间性能为O(n)，单链表是顺序存取结构

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 "no data"; //未找到
    else return p->data; 
}

按值查找

单链表中按值查找与顺序表中的实现方法类似，对链表中的元素依次进行比较，平均时间性能为O(n).

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;//no found
}

插入

单链表在插入过程中需要注意分析在表头、表中间、表尾的三种情况，由于单链表带头结点，这三种情况的操作语句一致，不用特殊处理，时间复杂度为O(n).

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;
    }
}

删除

删除操作时需要注意表尾的特殊情况，此时虽然被删结点不存在，但其前驱结点却存在。因此仅当被删结点的前驱结点存在且不是终端节点时，才能确定被删节点存在，时间复杂度为O(n)

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;
        p->next = q->next;
        return q->data;
    }
}

遍历

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

链式储存优缺点

优点：

• 插入、删除无需移动其他元素，只用改变指针
• 链表各结点内存空间无需连续，利用率高

缺点：

• 查找需遍历

四、其他类型链表

循环链表

• 特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。（通常为了使空表和非空表的处理一致，通常也附加一个头结点）

• 通常以判断指针是否等于某一指定指针来判定是否扫描了整个循环链表。

  
  

双链表

循环链表虽然可以从任意结点出发扫描其他结点，但是如果要查找其前驱结点，则需遍历整个循环链表。为了快速确定任意结点的前驱结点，可以再每个节点中再设置一个指向前驱结点的指针域，这样就形成了双链表。

储存方法：

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

结点p的地址既存储在其前驱结点的后继指针域内，又存储在它后继结点的前驱指针域中
需要注意：

• 循环双链表中求表长、按位查找、按值查找、遍历等操作的实现与单链表基本相同。
• 插入操作需要修改4个指针，并且要注意修改的相对顺序。

静态链表

静态链表是用数组来表示单链表，用数组元素的下标来模拟单链表的指针.
静态链表储存储存：

const int MaxSize = 100;
template<class DataType>
struct Node{
    DataType data;
    int next;
}SList[MaxSize];

静态链表虽然是用数组来存储线性表的元素，但在插入和删除操作时，只需要修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点，但是它并没有解决连续存储分配带来的表长难以确定的问题