数据结构

本片对于数据结构自行设计的ADT，以及常用的算法、性质做一个记录。

顺序表

const int MAXLISTSIZE = 100; //默认最大长度
template<class ElemType>
class SqList{
  	private:
    ElemType *elem;   // 存储空间基址
    int length;               // 当前长度
    int listsize;        // 允许的最大存储容量(以sizeof(ElemType)为单位
    public:
    //初始化顺序表
    SqList(int ms = MAXLISTSIZE)
    {
        elem = new ElemType[ms];
        length = 0;
        listsize = ms;
    }
    //删除顺序表
    ~SqList(){delete [] elem;}
    //将顺序表置为空表
    void ListClear( )
    {
        delete [] elem;
        elem = new ElemType[length];
        length = 0;}
    //返回顺序表的长度
    int ListLength() const {return length;}
    //设置顺序表的长度
    bool SetListLength(int len)
    {
        if(len <= listsize && len >= length)
        {
            length = len;
            return 1;
        }
        ElemType *t;
        t = new ElemType[len];
        for(int i = 0; i < min(length,len); ++i)
            t[i] = elem[i];
        length = len;
        delete [] elem;
        elem = t;
        return 1;
    }
    //判断顺序表是否为空表
    bool ListEmpty() const
    {
        return !length;
    }
    //判断顺序表是否为满表
    bool ListFull() const
    {
        return listsize == length ? 1 : 0;
    }
    //用e返回顺序表标号为i的元素
    ElemType GetElem(int i) const
    {
        return elem[i];
    }
    //返回元素e的标号，否则返回-1
    int GetElemIndex(ElemType e) const
    {
        for(int i = 0; i < length; i++)
        {
            if(elem[i] == e)
                return i;
        }
        return -1;
    }
    //用e设置顺序表标号为i的元素
    bool SetElem(int i, ElemType e)
    {
        if(i < 0 || i >= length)
            return 0;
        elem[i-1] = e;
        return 1;
    }
    //在顺序表的标号为pos的元素之前插入e元素
    bool ListInsert(ElemType e, int pos)
    {
        if(pos < 0 || pos > length)
            return 0;
        if(listsize - length > 0)
        {
            for(int i = length; i >= pos; i--)
            {
                elem[i] = elem[i-1];
            }
            elem[pos] = e;
            length ++;
        }else
        {
            ElemType *t;
            length ++;
            t = new ElemType[length];
            for(int i = 0; i < length; ++i)
                t[i] = elem[i];
            delete [] elem;
            elem = t;
            for(int i = length; i > pos; i--)
                elem[i] = elem[i-1];
            elem[pos] = e;
        }
        return 1;
    }
    //在顺序表的标号为pos的元素之前插入e元素
    bool Push(ElemType e)
    {
        if(listsize - length > 0)
        {
            elem[length] = e;
            length ++;
        }else
        {
            ElemType *t;
            length ++;
            t = new ElemType[length];
            for(int i = 0; i < length; ++i)
                t[i] = elem[i];
            delete [] elem;
            elem = t;
            elem[length-1] = e;
        }
        return 1;
    }
    //删除最后一个元素
    void Pop()
    {
        if(length > 0)
            length --;
    }
    //删除顺序表下表为pos的元素
    bool ListDelete(int pos)
    {
        if(pos < 0 || pos > length)
            return 0;
        if(length > 0)
            length--;
        else
            return 0;
        for(int i = pos; i < length; ++i)
            elem[i] = elem[i+1];
        return 1;
    }
    //compare函数，用来判断a和b是否相等
    bool compare(ElemType a, ElemType *b)
    {
        return a == *b;
    }
    //按指定条件查找
    int LocateElem(ElemType e)
    {
        for(int i = 0; i < length; ++i)
        {
            if(elem[i] = e)
                return i;
        }
        return -1;
    }
    //      //逆置顺序表
    //      void Invert(int, int);
    //返回线性表给定数据元素的前驱数据元素的值
    bool PriorElem(ElemType cur_e, ElemType &pri_e)
    {
        for(int i = 0; i < length; i++)
        {
            if(elem[i] == cur_e)
            {
                if(i > 0)
                {
                    pri_e = elem[i-1];
                    return 1;
                }else
                {
                    return 0;
                }
            }
        }
        return 0;
    }
    //返回线性表给定数据元素的后继数据元素的值
    bool NextElem(ElemType cur_e, ElemType &nex_e)
    {
        for(int i = 0; i < length; i++)
        {
            if(elem[i] == cur_e)
            {
                if(i < length-1)
                {
                    nex_e = elem[i+1];
                    return 1;
                }else
                {
                    return 0;
                }
            }
        }
        return 0;
    }
    //将线性表中的元素前移一次
    void MoveForward()
    {
        ElemType t = elem[0];
        for(int i = 0; i < length-1; i++)
            elem[i] = elem[i+1];
        elem[length - 1] = t;
    }
    //打印元素
    void Print()
    {
        if(length == 0)
        {
            cout<<"NULL"<<endl;
            return;
        }
        for(int i = 0; i < length; ++i)
        {
            cout<<elem[i];
            if(i < length - 1)
                cout<<',';
        }
        cout<<endl;
    }
    //销毁线性表
    void ListDestroy()
    {
        delete [] elem;
        elem = NULL;
        length = 0;
        listsize = 0;
    }
    //      //遍历顺序表
    //      int ListTraverse() const;
};

链表

单链表

// 结点
template<class ElemType>
struct LinkNode
{
    ElemType data; //数据域
    LinkNode<ElemType> *next; //指针域
    LinkNode(LinkNode<ElemType> *ptr = NULL){next = ptr;} //构造函数，默认指针域为空，数据域没有初始化
    LinkNode(const ElemType &item, LinkNode<ElemType> *ptr = NULL) //构造函数，默认指针域为空，数据域初始化
    {
        next = ptr;
        data = item;
    }
};

//带头结点的单链表
template<class ElemType>
class LinkList
{
  private:
      LinkNode<ElemType> *head;   // 头指针
      LinkNode<ElemType> *tail;   // 尾指针
  public:
      //无参构造
      LinkList(){head = new LinkNode<ElemType>; tail = head;}
      //有参构造，给头节点数据域赋值
      LinkList(const ElemType &item){head = new LinkNode<ElemType>(item); tail = head;}
      //拷贝构造
      LinkList(LinkList<ElemType> &List);
      //析构
      ~LinkList(){ListDestroy();}
      //等于号重载
      LinkList<ElemType>& operator=(LinkList<ElemType> &List);
      //销毁链表
      void ListDestroy();
      //清空链表
      void ListClear();
      //返回链表的长度
      int ListLength() const;
      //判断链表是否为空表
      bool ListEmpty() const;
      //在首节点之前插入一个结点
      bool InsFirst(ElemType e);
      //在尾节点之后添加一个结点
      bool InsEnd(ElemType e);
      //获取链表头结点
      LinkNode<ElemType>* GetHead() const{return head;}
      //获取链尾结点
      LinkNode<ElemType>* GetTail() const{return tail;}
      //设置链表头结点
      void SetHead(LinkNode<ElemType> *p);
      //设置链尾结点
      void SetTail(LinkNode<ElemType> *p);
      //返回链表的第i个元素
      ElemType GetElem(int pos);
      //在链表的第pos个位置之前插入e元素
      bool ListInsert(int pos,ElemType e);
      //删除链表的首结点
      bool DelFirst();
      //表头插入法动态生成链表
      void CreateList_Head(int n, ElemType *A);
      //表尾插入法动态生成链表
      void CreateList_Tail(int n, ElemType *A);
      //删除链表的第pos个位置的元素
      ElemType ListDelete(int pos);
      //compare函数，用来判断两个链表是否相等
      bool compare(const LinkList<ElemType> &b);
      //按指定条件查找，返回指向第一个符合条件（=e）的元素的指针
      bool LocateElem(const ElemType &e, LinkNode<ElemType> *pos);
      //返回链表给定数据元素的前驱数据元素的值
      //bool PriorElem(ElemType cur_e, ElemType &pri_e);
      //返回链表给定数据元素的后继数据元素的值
      bool NextElem(LinkNode<ElemType> *p, ElemType &e);
      //遍历链表
      bool ListTraverse() const;
};

//拷贝构造
template<class ElemType>
LinkList<ElemType>::LinkList(LinkList<ElemType> &List){
  this->head = new LinkNode<ElemType>(List.head->data);
  LinkNode<ElemType> *p1 = this->head,*p2 = List.head;
  while(p2->next)
  {
    p1->next = new LinkNode<ElemType>(p2->next->data);
    p1 = p1->next;
    p2 = p2->next;
  }
  this->tail = p1;
}
//销毁链表
template<class ElemType>
void LinkList<ElemType>::ListDestroy()
{
    LinkNode<ElemType> *p = head, *t = p->next;
    while(p)
    {
        delete p;
        p = t;
        if(p) t = p->next;
    }
}
//重载赋值运算符
template<class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator=(LinkList<ElemType> &List)
{
  this->head = new LinkNode<ElemType>(List.head->data);
  LinkNode<ElemType> *p1 = this->head,*p2 = List.head;
  while(p2->next)
  {
    p1->next = new LinkNode<ElemType>(p2->next->data);
    p1 = p1->next;
    p2 = p2->next;
  }
  tail = p1;
  return *this;
}
//清空链表
template<class ElemType>
void LinkList<ElemType>::ListClear()
{
  ListDestroy(head->next);
  tail = head;
}
//返回链表的长度
template<class ElemType>
int LinkList<ElemType>::ListLength() const
{
  int length = 0;
  LinkNode<ElemType> *p = head;
  while(p->next)
  {
      p = p->next;
      length++;
  }
  return length;
}
//判断链表是否为空表
template<class ElemType>
bool LinkList<ElemType>::ListEmpty() const
{
  return head->next;
}
//在首节点之前插入一个结点
template<class ElemType>
bool LinkList<ElemType>::InsFirst(ElemType e)
{
  LinkNode<ElemType> *t = new LinkNode<ElemType>(e);
  t->next = head->next;
  head->next = t;
  return true;
}
//在尾节点之后添加一个结点
template<class ElemType>
bool LinkList<ElemType>::InsEnd(ElemType e)
{
  LinkNode<ElemType> *t = new LinkNode<ElemType>(e);
  tail->next = t;
  tail = t;
  return true;
}
//设置链表头结点
template<class ElemType>
void LinkList<ElemType>::SetHead(LinkNode<ElemType> *p)
{
  head = p;
}
//设置尾结点
template<class ElemType>
void LinkList<ElemType>::SetTail(LinkNode<ElemType> *p)
{
  tail = p;
}
//返回链表的第i个元素
template<class ElemType>
ElemType LinkList<ElemType>::GetElem(int pos)
{
  if(pos < 1)  //不合法数据返回头节点data
    return head->data;
  int num = 0;
  LinkNode<ElemType> *p = head;
  while(p->next)
  {
    num++;
    p = p->next;
    if(num == pos)
      return p->data;
  }
  return head->data; //不合法数据返回头节点data
}
//在链表的第pos个位置之前插入e元素
template<class ElemType>
bool LinkList<ElemType>::ListInsert(int pos,ElemType e)
{
  if(pos < 1)
      return false;
  int num = 0;
  LinkNode<ElemType> *p = head;
  LinkNode<ElemType> *t = new LinkNode<ElemType>(e);
  while(p->next)
  {

    num++;
    if(num == pos)
    {
      t->next = p->next;
      p->next = t;
      return true;
    }
    p = p->next;
  }
  return false;
}
//删除链表的首结点
template<class ElemType>
bool LinkList<ElemType>::DelFirst()
{
  if(!(head->next))
    return false;
  LinkNode<ElemType> *t = head->next;
  head->next = t->next;
  delete t;
  if(!head->next)
    tail = head;
  return true;
}
//表头插入法动态生成链表
template<class ElemType>
void LinkList<ElemType>::CreateList_Head(int n, ElemType *A)
{
  int m = n;
  while(n)
  {
    InsFirst(*(A+(m-n)));
    n--;
  }
}
//表尾插入法动态生成链表
template<class ElemType>
void LinkList<ElemType>::CreateList_Tail(int n, ElemType *A)
{
  int m = n;
  while(n)
  {
    InsEnd(*(A+(m-n)));
    n--;
  }
}
//删除链表的第pos个位置的元素
template<class ElemType>
ElemType LinkList<ElemType>::ListDelete(int pos)
{
  LinkNode<ElemType> *p = head, *t;
  while(--pos)
    p = p->next;
  t = p->next;
  p->next = t->next;
  if(!p->next)
    tail = p;
  ElemType res = t->data;
  delete t;
  return res;
}
//compare函数，用来判断a和b是否相等
template<class ElemType>
bool LinkList<ElemType>::compare(const LinkList<ElemType> &b)
{
  LinkNode<ElemType> *t = b.GetHead(), *p = head;
  while(p->next || t->next)
  {
    if(p->next->data != t->next->data)
      return false;
    p = p->next;
    t = t->next;
  }
  return true;
}
//返回链表给定数据元素的后继数据元素的值
template<class ElemType>
bool LinkList<ElemType>::NextElem(LinkNode<ElemType> *p, ElemType &e)
{
  if(p->next)
    e = p->next->data;
  else
    return false;
  return true;
}
//遍历链表
template<class ElemType>
bool LinkList<ElemType>::ListTraverse() const
{
  LinkNode<ElemType> *p = head;
  while(p->next)
  {
    p = p->next;
    cout<<p->data;
    if(p->next)
      cout<<"->";
  }
  cout<<endl;
  return 1;
}

循环链表

// 结点
template<class ElemType>
struct LinkNode
{
    ElemType data,num; //数据域
    LinkNode<ElemType> *next; //指针域
    LinkNode(LinkNode<ElemType> *ptr = NULL){next = ptr;} //构造函数，默认指针域为空，数据域没有初始化
    LinkNode(const ElemType &item, LinkNode<ElemType> *ptr = NULL) //构造函数，默认指针域为空，数据域初始化
    {
        next = ptr;
        data = item;
        num = 0;
    }
};

//带头结点的单链表
template<class ElemType>
class LinkList
{
  private:
      LinkNode<ElemType> *head;   // 头指针
      LinkNode<ElemType> *tail;   // 尾指针
  public:
      //无参构造
      LinkList(){head = new LinkNode<ElemType>; tail = head;}
      //有参构造，给头节点数据域赋值
      LinkList(const ElemType &item){head = new LinkNode<ElemType>(item); tail = head;}
      //拷贝构造
      LinkList(LinkList<ElemType> &List);
      //析构
      ~LinkList(){ListDestroy();}
      //等于号重载
      LinkList<ElemType>& operator=(LinkList<ElemType> &List);
      //销毁链表
      void ListDestroy();
      //清空链表
      void ListClear();
      //返回链表的长度
      int ListLength() const;
      //判断链表是否为空表
      bool ListEmpty() const;
      //在首节点之前插入一个结点
      bool InsFirst(ElemType e);
      //在尾节点之后添加一个结点
      bool InsEnd(ElemType e);
      //获取链表头结点
      LinkNode<ElemType>* GetHead() const{return head;}
      //获取链尾结点
      LinkNode<ElemType>* GetTail() const{return tail;}
      //设置链表头结点
      void SetHead(LinkNode<ElemType> *p);
      //设置链尾结点
      void SetTail(LinkNode<ElemType> *p);
      //返回链表的第i个元素
      ElemType GetElem(int pos);
      //在链表的第pos个位置之前插入e元素
      bool ListInsert(int pos,ElemType e);
      //删除链表的首结点
      bool DelFirst();
      //表头插入法动态生成链表
      void CreateList_Head(int n, ElemType *A);
      //表尾插入法动态生成链表
      void CreateList_Tail(int n, ElemType *A);
      //删除链表的第pos个位置的元素
      ElemType ListDelete(int pos);
      //compare函数，用来判断两个链表是否相等
      bool compare(const LinkList<ElemType> &b);
      //按指定条件查找，返回指向第一个符合条件（=e）的元素的指针
      bool LocateElem(const ElemType &e, LinkNode<ElemType> *pos);
      //返回链表给定数据元素的前驱数据元素的值
      //bool PriorElem(ElemType cur_e, ElemType &pri_e);
      //返回链表给定数据元素的后继数据元素的值
      bool NextElem(LinkNode<ElemType> *p, ElemType &e);
      //遍历链表
      bool ListTraverse() const;
};

//拷贝构造
template<class ElemType>
LinkList<ElemType>::LinkList(LinkList<ElemType> &List){
  this->head = new LinkNode<ElemType>(List.head->data);
  LinkNode<ElemType> *p1 = this->head,*p2 = List.head;
  while(p2->next)
  {
    p1->next = new LinkNode<ElemType>(p2->next->data);
    p1 = p1->next;
    p2 = p2->next;
  }
  this->tail = p1;
}
//销毁链表
template<class ElemType>
void LinkList<ElemType>::ListDestroy()
{
    LinkNode<ElemType> *p = head, *t = p->next;
    while(p!=head)
    {
        delete p;
        p = t;
        if(p) t = p->next;
    }
}
//重载赋值运算符
template<class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator=(LinkList<ElemType> &List)
{
  this->head = new LinkNode<ElemType>(List.head->data);
  LinkNode<ElemType> *p1 = this->head,*p2 = List.head;
  while(p2->next)
  {
    p1->next = new LinkNode<ElemType>(p2->next->data);
    p1 = p1->next;
    p2 = p2->next;
  }
  tail = p1;
  return *this;
}
//清空链表
template<class ElemType>
void LinkList<ElemType>::ListClear()
{
  ListDestroy(head->next);
  tail = head;
}
//返回链表的长度
template<class ElemType>
int LinkList<ElemType>::ListLength() const
{
  int length = 0;
  LinkNode<ElemType> *p = head;
  while(p->next)
  {
      p = p->next;
      length++;
  }
  return length;
}
//判断链表是否为空表
template<class ElemType>
bool LinkList<ElemType>::ListEmpty() const
{
  return head->next;
}
//在首节点之前插入一个结点
template<class ElemType>
bool LinkList<ElemType>::InsFirst(ElemType e)
{
  LinkNode<ElemType> *t = new LinkNode<ElemType>(e);
  t->next = head->next;
  head->next = t;
  return true;
}
//在尾节点之后添加一个结点
template<class ElemType>
bool LinkList<ElemType>::InsEnd(ElemType e)
{
  LinkNode<ElemType> *t = new LinkNode<ElemType>(e);
  tail->next = t;
  tail = t;
  tail->next = head;
  return true;
}
//设置链表头结点
template<class ElemType>
void LinkList<ElemType>::SetHead(LinkNode<ElemType> *p)
{
  head = p;
}
//设置尾结点
template<class ElemType>
void LinkList<ElemType>::SetTail(LinkNode<ElemType> *p)
{
  tail = p;
}
//返回链表的第i个元素
template<class ElemType>
ElemType LinkList<ElemType>::GetElem(int pos)
{
  if(pos < 1)  //不合法数据返回头节点data
    return head->data;
  int num = 0;
  LinkNode<ElemType> *p = head;
  while(p->next)
  {
    num++;
    p = p->next;
    if(num == pos)
      return p->data;
  }
  return head->data; //不合法数据返回头节点data
}
//在链表的第pos个位置之前插入e元素
template<class ElemType>
bool LinkList<ElemType>::ListInsert(int pos,ElemType e)
{
  if(pos < 1)
      return false;
  int num = 0;
  LinkNode<ElemType> *p = head;
  LinkNode<ElemType> *t = new LinkNode<ElemType>(e);
  while(p->next)
  {

    num++;
    if(num == pos)
    {
      t->next = p->next;
      p->next = t;
      return true;
    }
    p = p->next;
  }
  return false;
}
//删除链表的首结点
template<class ElemType>
bool LinkList<ElemType>::DelFirst()
{
  if(!(head->next))
    return false;
  LinkNode<ElemType> *t = head->next;
  head->next = t->next;
  delete t;
  if(!head->next)
    tail = head;
  return true;
}
//表头插入法动态生成链表
template<class ElemType>
void LinkList<ElemType>::CreateList_Head(int n, ElemType *A)
{
  int m = n;
  while(n)
  {
    InsFirst(*(A+(m-n)));
    n--;
  }
}
//表尾插入法动态生成链表
template<class ElemType>
void LinkList<ElemType>::CreateList_Tail(int n, ElemType *A)
{
  int m = n;
  while(n)
  {
    InsEnd(*(A+(m-n)));
    n--;
  }
}
//删除链表的第pos个位置的元素
template<class ElemType>
ElemType LinkList<ElemType>::ListDelete(int pos)
{
  LinkNode<ElemType> *p = head, *t;
  while(--pos)
    p = p->next;
  t = p->next;
  p->next = t->next;
  if(!p->next)
    tail = p;
  ElemType res = t->data;
  delete t;
  return res;
}
//compare函数，用来判断a和b是否相等
template<class ElemType>
bool LinkList<ElemType>::compare(const LinkList<ElemType> &b)
{
  LinkNode<ElemType> *t = b.GetHead(), *p = head;
  while(p->next || t->next)
  {
    if(p->next->data != t->next->data)
      return false;
    p = p->next;
    t = t->next;
  }
  return true;
}
//返回链表给定数据元素的后继数据元素的值
template<class ElemType>
bool LinkList<ElemType>::NextElem(LinkNode<ElemType> *p, ElemType &e)
{
  if(p->next)
    e = p->next->data;
  else
    return false;
  return true;
}
//遍历链表
template<class ElemType>
bool LinkList<ElemType>::ListTraverse() const
{
  LinkNode<ElemType> *p = head;
  while(p->next != head)
  {
    p = p->next;
    cout<<'('<<p->num<<','<<p->data<<')';
    if(p->next != head)
      cout<<"->";
  }
  cout<<endl;
  return 1;
}

顺序栈

const int MAXLISTSIZE = 100;

template<class ElemType>
class SqStack{
private:
    ElemType *base;   // 栈底指针
    ElemType *top;   // 栈顶指针
    int maxSize;        // 允许的最大存储容量(以sizeof(ElemType)为单位
public:
    //初始化顺序栈
    SqStack(int ms = MAXLISTSIZE)
    {
        maxSize = ms;
        base = new ElemType[maxSize];
        top = base;
    }
    //删除顺序栈
    ~SqStack(){StackDestroy();}
    //将顺序栈置为空表
    bool StackClear( ){top = base;}
    //返回顺序栈的长度
    int StackLength() const {return top - base;}
    //设置顺序栈的长度
    //bool SetListLength(int len);
    //判断顺序栈是否为空栈
    bool StackisEmpty() const{ return top == base; }
    //判断顺序栈是否为满栈
    bool StackFull() const{ return base - top == maxSize;}
    //用e返回栈顶元素
    bool GetTop(ElemType &e) const
    {
        e = *(top-1);
    }
    ElemType GetTop() const
    {
        return *(top-1);
    }
    //入栈
    bool push(ElemType &e)
    {
        if(StackFull())
            return 0;
        *top = e;
        top++;
        return 1;
    }
    //顺序打印
    void print()
    {
        ElemType *p = base;
        while(p!=top)
        {
            cout<<*(p++);
        }
        cout<<endl;
    }
    //出栈
    bool pop(ElemType &e)
    {
        if(StackisEmpty())
            return 0;
        GetTop(e);
        top--;
        return 1;
    }
    ElemType pop()
    {
        if(StackisEmpty())
            return 0;
        ElemType t = GetTop();
        top--;
        return t;
    }
    //销毁顺序栈
    bool StackDestroy()
    {
        delete[] base;
        base = top = nullptr;
    }
    //遍历顺序栈
    void StackTraverse() const
    {
        for(ElemType* i = base; i != top; i++)
        {
            cout<<*i;
        }
    }
    //栈空间加倍
    bool DoubleSpace()
    {
        maxSize *= 2;
    }
    //比较栈是否相等
    bool isEqual(SqStack &t) const
    {
        if(t.StackLength() != this->StackLength())
            return false;
        for(ElemType *p1 = base, *p2 = t.base; p1 != top; p1++, p2++)
            if(*p1 != *p2)
                return false;
        return true;
    }
};

队列

顺序队列

const int MAXLISTSIZE = 100;
template<class ElemType>
class SqQueue{
private:
  ElemType *elem;   // 存储空间基址
  int front;   // 队头指针
  int rear;   // 队尾指针
  int maxSize;        // 允许的最大存储容量(以sizeof(ElemType)为单位
public:
  //初始化顺序队列
  SqQueue(int ms = MAXLISTSIZE){maxSize = ms;front = rear = 0; elem = new ElemType[ms];}
  //删除顺序队列
  ~SqQueue(){QueueDestroy();}
  //将顺序队列置为空
  bool QueueClear(){rear = front;return true;};
  //设置顺序栈的长度
  //bool SetListLength(int len);
  //判断顺序队列是否为空
  bool QueueisEmpty() const{ return front == rear; }
  //判断顺序队列是否为满
  bool QueueFull() const{return rear+1 == front;}
  //用e返回队头元素
  bool GetFront(ElemType &e)
  {
      if(!QueueisEmpty())
      {
        e = elem[front];
        return true;
      }else return false;
  }
  //入队
  bool enQueue(const ElemType &e)
  {
      if(QueueFull())
        return false;
      elem[rear] = e;
      rear++;
      return true;
  }
  //出队
  bool deQueue(ElemType &e)
  {
      if(!QueueisEmpty())
      {
          e = elem[front];
          front++;
          return true;
      }else return false;

  }
  //销毁顺序队列
  bool QueueDestroy()
  {
      if(!elem)
        return false;
      delete[] elem;
      return true;
  }
  //打印
  void print();
  //顺序队列最大存储空间加倍
  bool DoubleSpace();
};
template<class ElemType>
void SqQueue<ElemType>::print()
{
  int t = front;
  while(t != rear)
  {
      cout<<elem[t];
      if(++t != rear)
        cout<<' ';
  }
  cout<<endl;
}

链队列

template<class ElemType>

struct LinkQueueNode

{
    ElemType data;
    LinkQueueNode<ElemType> *next;
    LinkQueueNode(LinkQueueNode<ElemType> *ptr = NULL){next = ptr;} //构造函数1，用于构造头结点
    LinkQueueNode(const ElemType &item, LinkQueueNode<ElemType> *ptr = NULL) //构造函数2，用于构造其他结点
    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    {
        next = ptr;
        data = item;
    }
    ElemType getData(){ return data;}  //取得结点中的数据
    void SetLink( LinkQueueNode<ElemType> *link ){ next = link; }  //修改结点的next域
    void SetData( ElemType value ){ data = value; }   //修改结点的data域

};



//带头结点的链队列

template<class ElemType>

class LinkQueue{

   private:
      LinkQueueNode<ElemType> *front;   // 队头指针
      LinkQueueNode<ElemType> *rear;   // 队尾指针
      int length = 0;   //队列当前元素个数

   public:

      //无参数的构造函数
      LinkQueue()
      {
          front = rear = new LinkQueueNode<ElemType>;
      }
      //析构函数
      ~LinkQueue(){LinkQueueDestroy();}
      //销毁链队列
      bool LinkQueueDestroy();
      //清空链表
      bool LinkQueueClear();

      //返回链队列的长度
      int QueueLength() const{ return length;}

      //判断链队列是否为空队列

      bool QueueisEmpty() const{ return front == rear;}

      //出队
      bool deQueue( ElemType &e );

      //入队

      bool enQueue( ElemType e );

      //获取链队列头结点指针

      LinkQueueNode<ElemType>* GetFront() { return front;}

      //获取队头元素

      ElemType GetFrontData(){ return front->next->data;}

      //获取链队列队尾指针

      LinkQueueNode<ElemType>* GetRear() { return rear;}

      //遍历链队列

      bool QueueTraverse() const;

};
//销毁链队列
template <class ElemType>
bool LinkQueue<ElemType>::LinkQueueDestroy()
{
    if(!front)
        return 0;
    LinkQueueNode<ElemType> *p;
    while(front->next)
    {
        p = front->next;
        front->next = p->next;
        delete p;
    }
    delete front;
    front = rear = nullptr;
    return 1;
}
//清空链表
template <class ElemType>
bool LinkQueue<ElemType>::LinkQueueClear()
{
    if(!front)
        return 0;
    LinkQueueNode<ElemType> *p;
    while(front->next)
    {
        p = front->next;
        front->next = p->next;
        delete p;
    }
    rear = front;
    return 1;
}
//出队
template <class ElemType>
bool LinkQueue<ElemType>::deQueue( ElemType &e )
{
    if(QueueisEmpty())
        return 0;
    LinkQueueNode<ElemType> *p = front->next;
    e = p->data;
    front->next = p->next;
    delete p;
    length--;
}
//入队
template <class ElemType>
bool LinkQueue<ElemType>::enQueue( ElemType e )
{
    LinkQueueNode<ElemType> *p;
    p = new LinkQueueNode<ElemType>(e);
    rear->next = p;
    rear = p;
    length++;
}
//遍历链队列
template <class ElemType>
bool LinkQueue<ElemType>::QueueTraverse() const
{
    if(QueueisEmpty())
        return 0;
    LinkQueueNode<ElemType> *p = front;
    while(p->next)
    {
        p = p->next;
        cout<<p->data<<' ';
    }
    return 1;
}

二叉树

还没写TT