Chapter2 线性表

线性结构简介

线性表：操作不限表
栈：时间有序表，先进后出表
队列：时间有序表，先进先出表

线性表定义

线性表是N个具有相同特征的节点 $A_0,A_1,\cdots,A_{N-1}$ 构成的有穷有序序列

线性表的基本操作

创建 create()
清除 clear()
求线性表的长度 length()
删除 remove(i)
搜索 search(x)
访问 visit(i)
遍历 traverse()

线性表的抽象类

抽象类：如果一个类中至少有一个纯虚函数，则该类为抽象类
Tips. 一些好习惯：

不需修改的形参尽量使用const &（尽量使用引用传参）
不会进行修改的引用，请加const
类的成员函数如果不对类本身的成员变量进行修改，请将声明为类的const成员函数（原因：常对象不能调用非const成员函数，可以调用const成员函数）

template <class elemType>
class list
{ public:
     virtual void clear() = 0;
     virtual int length() const = 0;
     virtual void insert(int i, const elemType &x) = 0;
     virtual void remove(int i) = 0; 
     virtual int search(const elemType &x) const = 0 ;
     virtual elemType visit(int i) const = 0;
     virtual void traverse() const = 0
     virtual ~list() {};
};//抽象类无构造函数

线性表顺序实现

顺序表的存储实现

利用数组，进行顺序存放，数据连续分布
需要预先申请一块比存储的数据稍大的内存空间（new一个数组）
使用一个指针（elemType * data）存储数据的起始位置，因为数组的大小需要动态修改
需要两个额外的量存储目前申请的内存空间数组项数int maxSize和当前存储的数据项数int currentLength

顺序表类的定义

template <class elemType>
class seqList: public list<elemType>
{ private:
    elemType *data;
    int currentLength;
    int maxSize;
    void doubleSpace();
    
  public:
    seqList(int initSize = 10);
    ~seqList()  {delete [] data;}
    void clear()  {currentLength = 0;}
    int length() const  {return currentLength;}
    void insert(int i, const elemType &x);
    void remove(int i); 
    int search(const elemType &x) const ;
    elemType visit(int i) const;
    void traverse() const ;

};

构造函数

template <class elemType>
seqList<elemType>::seqList(int initSize)
{
	data = new elemType[initSize];
	maxSize = initSize;
	currentLength = 0;
}

时间复杂度为 $O(1)$

析构函数

顺序表的运算实现

length()

只需要返回currentlength的值

1	int length() const {return currentLength;}

visit(i)

返回data[i]的值

elemType visit(int i) const 
{
	return data[i];
	if (i < 0 || i >= currentLength) throw OutOfBound();
}

注意：为增强程序健壮性，加入越界的判断，若越界则抛出错误

如果要抛出错误，可以借助C++的异常处理功能，建一个OutOfBound类来提供越界异常处理的功能，具体实现如下：

class OutOfBound : public std::exception {
public:
    const char* what() const noexcept override {
        return "Index out of bound";
    }
};

clear()

只要将currentlength置为0即可

1	void clear() {currentLength = 0;}

上述三个算法，时间复杂度均为 $O(1)$

traverse()

template<class elemType>
void seqList<elemType>::traverse() const {
    std::cout << std::endl;
    for (int i = 0; i < currentLength; ++i) {
        std::cout << data[i] << ' ';
    }
}

遍历的时间复杂度为 $O(n)$

search()

template <class elemType>
int seqList<elemType>::search(const elemType &x) const
{
   int i;
   for (i = 0; i < currentLength && data[i] != x; ++i);
   if (i == currentLength) return -1;
   else return i;
}

搜索最优时间复杂度 $O(1)$ ，最坏时间复杂度 $O(n)$ ，平均时间复杂度 $O(n)$

insert(i,elem)

template<class elemType>
void seqList<elemType>::insert(int i, const elemType& x) {
    if (i < 0 || i > currentLength)
        throw OutOfBound();
    if (currentLength == maxSize)
        doubleSpace();
    for (int j = currentLength; j > i; --j) {
        data[j] = data[j - 1];
    }
    data[i] = x;
    ++currentLength;
}

思路：从后向前遍历，直到要插入元素的位置 $i$ ，从而要插入的元素在越靠后的位置，所需时间越少
要检查是否超限，超限就得分配新空间
此处也加入了对于越界的判断，详情见前面，不再重复叙述
插入操作最优时间复杂度 $O(1)$ ，最坏时间复杂度 $O(n)$ ，平均时间复杂度 $O(n)$
别忘了改currentLength！（虽然这是个常识）

remove(i)

template<class elemType>
void seqList<elemType>::remove(int i) {
    for (int j = i; j < currentLength - 1; ++j) {
        data[j] = data[j + 1];
    }
    --currentLength;
}

思路：先找到要插入元素的位置 $i$ ，然后从前向后遍历，直到最后
搜索最优时间复杂度 $O(1)$ ，最坏时间复杂度 $O(n)$ ，平均时间复杂度 $O(n)$

空间分配：doubleSpace()

当数组空间不够时，调用doubleSpace扩容
doubleSpace操作按一定的比例扩大数组的空间，常用的比例是扩大一倍（当然也可以设置成其他的）。
数组空间在内存中必须是连续的，因此，扩大数组空间的操作如下：
- 重新申请一个更大规模的动态数组
- 将新数组作为存储线性表的存储区
- 将原有数组的内容拷贝到新数组中
- 释放原有数组空间
时间复杂度 $O(n)$

template<class elemType>
void seqList<elemType>::doubleSpace() {
    elemType* tmp = data;
    maxSize *= 2;
    data = new elemType[maxSize];
    for (int i = 0; i < currentLength; ++i) {
        data[i] = tmp[i];
    }
    delete[] tmp;
}

顺序表总结

需要连续的存储空间。直观来讲，就是手搓一个动态数组
由于逻辑次序和物理次序的一致性使得定位访问的性能很好
由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，性能不太理想；
顺序表比较适合静态的、经常做定位访问的线性表。

线性表链接实现

单链表

单链表的存储实现

定义：每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。

头结点：为了消除特殊情况（边界效应），通常在表头额外增加一个相同类型的特殊结点，称之为头结点。
- 头结点不是线性表的组成部分
- 添加头结点是为了使在表头位置上进行插入和删除和在其它结点位置上进行这些操作完全一致，从而简化插入和删除算法。简言之，头结点保证了操作的一致性。
链表中的节点包含两部分：数据字段和指针字段。数据字段是单链表中要存储的数据，指针字段存放后继结点的地址值。
链表的操作是通过对节点进行操作实现的，因此应该把节点定义成一个结构体（struct）。
一般情况下，结点类型是链表专用的，建议设置为内嵌类/结构体。

单链表类的定义

template<class elemType>
class sLinkList: public list<elemType> {
private:
    struct node {
        elemType data;
        node* next;

        node(const elemType& x, node* n = NULL) {
            data = x;
            next = n;
        }
        node(): next(NULL) {}
        ~node() {}
    };
    node* head; //头指针
    int currentLength; //表长 
    node* move(int i) const; //返回第i个结点的地址

public:
    sLinkList();
    ~sLinkList() {
        clear();
        delete head;
    }
    void clear();
    int length() const {
        return currentLength;
    }
    void insert(int i, const elemType& x);
    void remove(int i);
    int search(const elemType& x) const;
    elemType visit(int i) const;
    void traverse() const;
};

构造函数

template <class elemType>
sLinkList<elemType>::sLinkList() 
{ 
    head = new node;
    currentLength = 0;
}

析构函数：清除单链表clear()

把单链表变成一个空表
回收所有结点的空间
时间复杂度为 $O(n)$

template<class elemType>
void sLinkList<elemType>::clear() {
    node *p = head->next, *q;
    head->next = NULL;
    while (p != NULL) { //删除链表中的所有结点
        q = p->next;
        delete p;
        p = q;
    }
    currentLength = 0;
}

单链表的运算实现

返回第i个元素的指针：move(i)

应该定义为private函数
时间复杂度 $O(n)$

template<class elemType>
struct sLinkList<elemType>::node* sLinkList<elemType>::move(int i) const {
    node* p = head;
    while (i-- >= 0 && p)
        p = p->next;
    return p;
}

插入元素：insert(i,x)

让指针p指向第i-1个元素
执行插入操作：
1. new一个节点
2. 将新数据和下一节点的指针填入新节点
3. 将新节点链入队伍

template<class elemType>
void sLinkList<elemType>::insert(int i, const elemType& x) {
    node* pos;
    if (i < 0)
        return;
    pos = move(i - 1);
    if (pos) {
        pos->next = new node(x, pos->next);
        ++currentLength;
    }
}

删除第i个元素：remove(i)

找到被删节点前一节点pos
让delp指向被删节点
将delp的后继节点指针赋值给pos的后继节点指针
释放被删节点空间（别忘！）

template<class elemType>
void sLinkList<elemType>::remove(int i) {
    node *pos, *delp;
    if (i < 0)
        return;
    pos = move(i - 1);
    if (!pos || !pos->next)
        return;
    delp = pos->next;
    pos->next = delp->next;
    delete delp;
    --currentLength;
}

搜索某个元素：search(x)

思路：从头指针的后继结点开始往后检查链表的结点直到找到x或查找到表尾

千万注意：while条件判断括号里的两个式子不能对调！！！！

template<class elemType>
int sLinkList<elemType>::search(const elemType& x) const {
    node* p = head->next;
    int i = 0;
    while (p != NULL && p->data != x) {
        p = p->next;
        ++i;
    }
    if (p == NULL)
        return -1;
    else
        return i;
}

访问第i个元素：visit(i)

找到第i个节点
返回节点的数据部分
最好处理一下越界访问的异常情况（加个if判断move(i)返回的是否是空指针就行）

template<class elemType>
elemType sLinkList<elemType>::visit(int i) const {
    return move(i)->data;
}

遍历运算：traverse()

template<class elemType>
void sLinkList<elemType>::traverse() const {
    node* p = head->next;
    std::cout << std::endl;
    while (p != NULL) {
        std::cout << p->data << "  ";
        p = p->next;
    }
    std::cout << std::endl;
}

双链表

双链表的存储实现

每个结点附加了两个指针字段，如prev和next
- prev字段给出直接前驱结点的地址
- next字段给出直接后继结点的地址
为了保证表头、表尾插入删除操作的一致性，通常为双链表设一头结点，设一尾节点
- 结点中prev字段为空，它的next字段给出线性表中的首结点的地址
- 尾结点中next字段为空，它的prev字段给出线性表中最后一个结点的地址

循环链表

单循环链表

一般的单循环链表不带头节点，使用一个头指针即可

双循环链表

头结点中prev字段给出尾结点的地址，尾结点中next字段给出头结点的地址
一般也不设头尾结点，有一个头指针就可以

线性表总结

分析	顺序实现	链接实现
连续空间	√	×
空间浪费	√	指针
清除	O(1)	O(N)
插入	O(N)	O(N)
找到位置后插入	O(N)	O(1)
删除	O(N)	O(N)
找到位置后删除	O(N)	O(1)
访问	O(1)	O(N)
查找	O(N)	O(N)
遍历	O(N)	O(N)