sqlist.cpp

线性表的使用 如何建立线性表

#include "StdAfx.h"
#include "SQList.h"

#include <iostream>

using namespace std;

enum Status {
  stOk = 1,
  stError = 0,
  stOutRange = -1,
  stOverflow = -2,
};

#define INIT_SIZE 100 // 静态常数，所有实例共享，作为数据成员是为了避免不同类的冲突，下同
#define INCREMENT 10

template <class T> class CSqList
{
public:
  CSqList(int nCap = INIT_SIZE, int nInc = INCREMENT);
  ~CSqList(void);
  bool IsEmpty() { return m_nLength == 0; } // 顺序表是否为空
  int Size() { return m_nLength; }
  int Capacity() { return m_nCap; }
  int Increment() { return m_nInc; }
  Status Resize(int nCap, int nInc = INCREMENT);
  Status Add(const T &rData); 
  void   RemoveTail() { if(m_nLength > 0) m_nLength--; };
  Status Insert(int i, const T &rData); // 插入数据
  Status Erase(int i);                  // 删除一个数据
  void   Clear();                            // 清除数据
  bool Traverse(bool (*Visit)(int i, const T &rData)); // 遍历顺序表，Visit 为自定义函数
protected:
  int m_nCap; // 现有容量
  int m_nInc;      // 尺寸增量
  int m_nLength;   // 实际元素数量
  T*  m_pData;
};

template <class T>
CSqList<T>::CSqList(int nCap, int nInc)
{
  m_nCap = (nCap > 0) ? nCap : INIT_SIZE;
  m_nInc = (nInc > 0) ? nInc : INCREMENT;
  m_nLength = 0;
  m_pData = new T[m_nCap];
  if(! m_pData) throw stOverflow;
}

template <class T>
CSqList<T>::~CSqList(void)
{
	if(m_pData) delete[]m_pData;
}

template <class T>
Status CSqList<T>::Resize(int nCap, int nInc = INCREMENT)
{
  m_nInc = (nInc > 0) ? nInc : INCREMENT;
  if(nCap >= 0 && nCap != m_nCap) {
    T *pTmp = m_pData;
    m_pData = new T[nCap];
    if(m_pData) {
      m_nCap = nCap;
      if(m_nLength > 0) {
        int nMin = (m_nLength < nCap) ? m_nLength : nCap;
        for(int i = 0; i < nMin; i++) m_pData[i] = pTmp[i];
        m_nLength = nMin;
      }
      if(pTmp) delete[] pTmp;
    }
    else {
      m_pData = pTmp; // 保持不变
      throw stOverflow;
    }
  }
  return stOk;
}

template <class T>
Status CSqList<T>::Add(const T &rData)
{
  if(m_nLength == m_nCap) // 若容量已满
    Resize(m_nCap + m_nInc);
  m_pData[m_nLength] = rData;
  m_nLength++;
  return stOk;
}

template <class T>
Status CSqList<T>::Insert(int i, const T &rData)
// 插入数据（前插）
{
  if(i >= 0 && i <= m_nLength) { // 下标合法性检测
    if(m_nLength == m_nCap) // 若容量已满
      Resize(m_nLength + m_nInc);
    else  
      for(int j = m_nLength - 1; j > i; j--)
		  m_pData[j] = m_pData[j - 1]; // 数据后移

    m_pData[i] = rData;
    m_nLength++;
    return stOk;
  }
  else throw stError; // 参数非法
}

template <class T>
Status CSqList<T>::Erase(int nWhere)
// 删除一个数据
{
  if(m_nLength > 0 && nWhere >= 0 && nWhere < m_nLength) { // 下标合法性检测
    for(int i = nWhere; i < m_nLength - 1; i++)
		m_pData[i] = m_pData[i + 1]; // 数据前移
    m_nLength--;
    return stOk;
  }
  else throw stError; // 参数非法
}

template <class T>
void CSqList<T>::Clear()
{
  m_nLength = m_nCap = 0;
  if(m_pData) {
    delete []m_pData;
    m_pData = 0;
  }
}

template <class T>
bool CSqList<T>::Traverse(bool (*Visit)(int i, const T &rData))
// 遍历顺序表，Visit 为调用者提供的自定义函数
// （函数名任意，只要接口一致即可）
{
  for(int i = 0; i < m_nLength; i++)
    if(! Visit(i, m_pData[i])) return false;
  return true;
}