1 顺序表

1) 定义顺序表模板类

const int MAXSIZE= 100; //顺序表最大容量
template <class T>
class SeqList
{
    public:
        SeqList() {length = 0;}             //构造函数：建立空顺序表
        SeqList(T d[], int len);            //构造函数：建立长度为len，数据为d[]的顺序表
        ~SeqList(){};                       //析构函数

        int GetLength(){return length};     //表长：获取表长
        T GetValue(int index);              //查找：根据索引获取对应数据
        int GetIndex(T x);                  //查找：根据值获得对应的索引
        void Insert(int index, T x);        //插入：在i位置，插入数据x
        void Delete(int index);             //删除：删除i位置数据
        void PrintList();                   //遍历

    private:
        int length;                         //表长
        T data[MAXSIZE];                    //存放列表元素（数组）
}

2) 成员函数实现

template <class T>
SeqList<T>::SeqList(T d[], int len) //构造函数：建立长度为len，数据为d[]的顺序表
{
    if(len<0 || len>MAXSIZE)
        throw "参数非法";

    length = len;

    for(int i=0;i<len;i++)
        data[i] = d[i];
}

template <class T>
T SeqList<T>::GetValue(int index)       //查找：根据索引获取对应数据
{
    if(index<0 || index>length-1)
        throw "参数非法";
    else
        return data[index];
}

template <class T>
int SeqList<T>::GetIndex(T x)           //查找：根据值获得对应的索引
{
    for(int i=0;i<length;i++)
        if(data[i] == x)
            return i

    return -1;
}

template <class T>
void SeqList<T>::Insert(int index, T x)//插入：在i位置，插入数据x
{
    if(length+1 > MAXSIZE)
        throw "列表已满，无法插入";

    if(index<0 || index>length)
        throw "参数非法";

    for(int i=length-1;i>index-1;i--)
            data[i+1] = data[i];        

    data[index] = x;
    length+=1;
    return;
}

template <class T>
void SeqList<T>::Delete(int index)      //删除：删除i位置数据
{
    if(0 == length)
        throw "列表为空，无法删除";

    if(index<0 || index>length-1)
        throw "参数非法";

    for(int i=index;i<length-1;i++)
            data[i] = data[i+1];

    length--;
}

template <class T>
void SeqList<T>::PrintList()            //遍历
{
    for(int i=0;i<length;i++)
        std::cout<<data[i]<<" ";
}

3) 有序表重复元素删除

template <class T>
void DelDup(SeqList<T> &L)
{
    for(int i=0;i<L.GetLength()-1;i++)
        while(L.GetValue(i)==L.GetValue(i+1))       //删除元素后，后续元素前移，因此依然是比较 i和i+1
            L.Delete(i+1);
}

4) 有序表合并

//不修改原表，假设合成的表有足够的空间容纳两个表的元素
template <class T>
void Merge(const SeqList<T> &L1, const SeqList<T> &L2，SeqList<T> &L3)
{
    int len1 = L1.GetLength();
    int len2 = L2.GetLength();
    int i=j=0;  //两个指针
    int k=0;
    while(i<len1 && j<len2)
    {
        if(L1[i] <= L2[j])
            L3.Insert(k++,L1[i++]);
        else
            L3.Insert(k++,L2[j++]);
    }
    while(i<len1)
        L3.Insert(k++,L1[i++]);

    while(j<len2)
        L3.Insert(k++,L2[j++]);

}

//在原表的基础上，添加，假设原表有足够的空间容纳添加的表
template <class T>
void Merge(SeqList<T> &L1, const SeqList<T> &L2)
{
    int len1 = L1.GetLength();
    int len2 = L2.GetLength();
    int i=len1-1;
    int j=len2-1;
    int k=len1+len2-1;

    while(i>-1 && j>-1)
    {
        if(L1[i]>L2[j])
            L1[k--]=L1[i--];
        else
            L1[k--]=L2[j--];        
    }

    while(j>-1)
        L1[k--]=L2[j--];
}

2 链表

链表与顺序表

1) 空间上，顺序表静态分配内存，结构紧凑，但需要预估内存大小，不够灵活， 另外空间连续性会导致存储碎片
2) 时间上，顺序表按位存取快，两者按值存取均为O(n)；顺序表增删数据效率不高，链表的增删时间主要花费在指针移动

单链表

data	next

表达：链表由结点构成，以头结点为链表起始，结点包括数据和下一结点的指针，头结点数据为null，尾指针为null（为使得空链表与非空链表中结点表达方式的统一，引入头结点）

1) 定义链表模板类

template <class T>
class LinkList
{
    public:
        LinkList();                         //构造函数：只有头结点的空单链表
        LinkList(T d[], int len);           //构造函数：以数组元素建立链表
        ~LinkList(){};                      //析构函数

        int GetLength();                    //表长
        T GetValue(int index);              //查找：根据索引获取对应数据
        int GetIndex(T x);                  //查找：根据值获得对应的索引
        void Insert(int index, T x);        //插入：在i位置，插入数据x
        void Delete(int index);             //删除：删除i位置数据
        void PrintList();                   //遍历

    private:
        Node<T>* first;     //头指针
}

2) 成员函数实现

表长/查找/插入/删除/构造/析构：遍历即工作指针的后移与非空的判断，在遍历的基础上计数、查找、删除，注意删除和析构中，先备份再delete

template <class T>
LinkList<T>::LinkList()             //构造函数：只有头结点的空单链表
{
    first = new Node<T>;            //生成头结点
    first->next = NULL;             //指向空值
}

template <class T>
LinkList<T>::LinkList(T d[], int len)//构造函数：以数组元素建立链表，这个算法的核心就是不断申请新的节点，申请后，再考虑数据域和指针域，最后考虑首尾的处理
{
    if(len<1)
        throw "参数非法";

    Node<T> *p,*q;
    first = new Node<T>;            //头结点，注意不是首元结点
    p = first;  

    for(int i=0;i<len;i++)
    {
        q= new Node<T>;             //新申请一个结点
        q->data = d[i];             //写入数据
        p->next = q;                //把地址给前一个结点的指针域
        p = q;                      //把当前节点更新成上一个节点
    }   
    p->next = NULL;                 //单链表的尾指针为空
}

template <class T>
LinkList<T>::~LinkList()            //析构函数
{
    Node<T> *q;
    while(first != NULL) 
    {
        q = first;
        first = first->next;
        delete q;
    }
}

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

template <class T>
int LinkList<T>::GetLength()        //表长
{
    int cnt = 0;
    Node<T> *p = first->next;
    while(p != NULL)
    {
        cnt++;
        p = p->next;
    }
    return cnt;
}

template <class T>
T LinkList<T>::GetValue(int index)  //查找：根据索引获取对应数据
{
    int i = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if(i == imdex)
            return p->data;

        i++;
        p = p->next;
    }

    throw "参数非法";
}

template <class T>
int LinkList<T>::GetIndex(T x)      //查找：根据值获得对应的索引
{
    int index = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if(p->data == x)
            return index;

        index++;
        p = p->next;
    }

    return -1;
}

template <class T>
void LinkList<T>::Insert(int index, T x)//插入：在i位置，插入数据x
{
    int i = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if((i+1) == index)      //指针定位到index结点的前一个结点
            break;

        i++;
        p = p->next;
    }

    if(p==NULL)
        throw "参数非法";

    Node<T> *q = new Node<T>;
    q->data = x;
    q->next = p->next;
    p->next = q;
}

template <class T>
void LinkList<T>::Delete(int index) //删除：删除i位置数据
{
    int i = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if((i+1) == index)      //指针定位到index结点的前一个结点
            break;

        i++;
        p = p->next;
    }

    if(p==NULL)
        throw "参数非法";

    Node<T> *q = p->next;   //备份待删除的结点的指针
    p->next = q->next;
    delete q;   
}

3) 单链表原地逆置

//接着在类里定义逆置函数
//另存当前点的后继，然后修改为前驱
template <class T>
void LinkList<T>::Reverse() //原地逆置
{
    Node<T> *pLast, *pCur, *pNext;
    pLast = first;          //上一个结点：初始化为头结点
    pCur = first->next;     //当前结点：初始化为首元结点
    pNext = NULL;

    while(pCur != NULL)
    {
        pNext = pCur->next;     //保存下一个结点的指针
        pCur->next = pLast;     //当前点把前驱作为自己的后继

        pLast = pCur;           //更细当前点和前一个点
        pCur = pNext;
    }
    first->next = pLast;
}   

4) 单链表有序性、排序、合并、删除重复

1) 有序性

template <class T>
int LinkList<T>::IsOrdering() 
{
    Node<T> *p,*q = NULL;
    p = first->next;
    int flag = 1;
    if(p) 
        q = p->next;

    /*比较相邻的结点是否逆序*/
    while((p != NULL) && (q != NULL)) 
    {
        if(p->data > q->data) 
        {
            flag = 0;
            break;
        }
        else
        {
            p = q;
            q = q->next;
        }
    }
    return flag;
}

2) 排序

//保留首元结点，从第二个结点开始依次前插
//每插入一个值，都从first开始遍历当前排好序的链表
template <class T>
void LinkList<T>::Sort() 
{
    Node<T> *p,*q,*r,*s;
    p = first->next;

    if(p != NULL) 
    {
        //在首元结点后断开
        q = p->next;
        p->next = NULL; 

        //依次将q插入到有序单链表中
        while(q)
        {
            r = q->next;    //保存后继
            s = first;      //从first开始遍历
            while((s->next) && ((s->next->data) < (q->data))) //符合顺序则s后移，逆序则退出循环，执行插入操作
                s = s->next;

            q->next = s->next;
            s->next = q;

            //q后移
            q = r; 
        }
    }    
}

3) 有序表合并

template <class T>
void Merge(LinkList<T> &L1, LinkList<T> &L2) 
{
    /*将单链表L1和L2合并至L1*/
    Node<T> *first1, *first2;
    first1 = L1.GetFirst(); /*获取单链表L1的头指针*/
    first2 = L2.GetFirst(); /*获取单链表L2的头指针*/ 
    Node<ElemType> *p,*q,*r;
    r = first1; /*单链表L1的尾指针*/
    p = first1->next;
    q = first2->next;
    while(p != NULL && q != NULL) 
    {
        if(p->data <= q->data) 
        {
            r->next = p;
            r = p;
            p = p->next;
        }
        else 
        {
            r->next = q;
            r = q;
            q = q->next;
        }
    }
    while(p != NULL) 
    {
            r->next = p;
            r = p;
            p = p->next;
    }
    while(q != NULL) 
    {
            r->next = q;
            r = q;
            q = q->next;
    }
    r->next = NULL;
}

4) 删除重复

//两个指针，比较，相等则删除后一个，删除之前要另存下下个结点
template <class T>
void LinkList<T>::LinkListDelDup() 
{
    Node<T> *p,*q,*r;
    p = first->next;
    while(p != NULL) 
    {
        q = p->next;
        while(q != NULL && p->data == q->data) 
        {
            /*删除q*/
            r = q->next;
            p->next = q->next;
            delete q;
            q = r;
        }
        p = p->next;
    }
}

5) 无序表删除重复

//对每个结点，比较后面的所有节点，只向后比较，不向前比较，O(n2)
template <class T>
void LinkList<T>::LinkListDelNormalDup() 
{
    Node<T> *p,*q,*r;
    p = first->next;
    while(p != NULL)
    {
        q = p;
        while(q->next != NULL) 
        {
            if(p->data == q->next->data) 
            {
                r = q->next;                
                q->next = r->next; 
                delete r;
            }
            else
                q = q->next;    
        }
        p = p->next;
    }
}

6) 循环链表:尾标志指向头结点

双向链表

prior	data	next

1) 插入： 指针修改顺序，未被处理的部分不断开
2) 删除

系列参考

1) 《数据结构（C++）边学边做》任平红等著
2) 《剑指offer》何海涛著