线性表的顺序表示实现－C++版

     声明：本文内容属于本人原创，欢迎转载，请大家在转载时注明转贴地址

    使用一个模板类实现了线性表的顺序表示，我对这个模板类进行了简单的测试，大家如果在使用过程中或看代码的过程中遇到错误请及时提出，谢谢！该代码已经在VS2005环境下编译通过

  1. /**
  2. * @file ListSqu.h
  3. * @author Wang Liuqiang
  4. * @version 1.0
  5. * @date 2008-11-30
  6. * @brief 该类实现了线性表的顺序表示
  7. */
  9. #ifndef LISTSQU_H_
  10. #define LISTSQU_H_
  12. #include <assert.h>
  13. #include <iostream>
  14. using namespace std;
  16. #define LIST_INIT_SIZE 100
  17. #define LISTINCREMENT 10
  19. #define SQUSUCCEED 0
  20. #define SQUERROR -1
  21. #define SQUOVERFLOW -2
  23. /*
  24.  * 定义了两个默认的函数，如果用户在调用LocalElem()函数时没有指定
  25.  * 函数，则使用默认的equal()函数；如果指定了自己的比较函数，则将
  26.  * 自己的函数指针赋给LocalElem()函数
  27. */
  28. template <class T>
  29. bool equal(T e1, T e2)
  30. {
  31.     if (e1 == e2)
  32.     {
  33.         return true;
  34.     }
  35.     else
  36.     {
  37.         return false;
  38.     }
  39. }
  41. /*
  42. * 定义了两个默认的函数，如果用户在调用Traverse()函数时没有指定
  43. * 函数，则使用默认的show()函数；如果指定了自己的比较函数，则将
  44. * 自己的函数指针赋给Traverse()函数
  45. */
  47. template <class T>
  48. void show(T e)
  49. {
  50.     cout<<e<<endl;
  51. }
  53. template <class T>
  54. class ListSqu
  55. {
  56. public:
  57.     /*
  58.     *name 构造函数/析构函数
  59.     *@{
  60.     */
  61.     ListSqu();
  62.     ~ListSqu();
  64.     ListSqu(const ListSqu<T>& ls);
  65.     ListSqu<T>& operator=(const ListSqu<T>& ls);
  66.     /** @}*/ //构造函数/析构函数
  68. public:
  69.     /*
  70.      * 清空顺序表
  71.      * @return 返回函数执行结果:
  72.      * -0 表示执行成功
  73.      * -1 表示执行出错
  74.     */
  75.     int ClearList();
  77.     /*
  78.      * 判断顺序表是否为空
  79.      * @return 返回函数执行结果:
  80.      * -true 表示顺序表为空
  81.      * -false 表示顺序表不为空
  82.     */
  83.     bool IsEmpty();
  85.     /*
  86.      * 返回顺序表中元素个数
  87.      * @return 返回顺序表中元素个数
  88.     */
  89.     int Length();
  91.     /*
  92.      * 返回线性表中第一个与e满足关系Compare()的数据元素的位序
  93.      * @param[in] e 待判定的元素
  94.      * @param[in] Compare 函数指针，指向判定元素的函数指针，默认为比较元素是否相等
  95.      * @return 返回线性表中第一个与e满足关系Compare()的数据元素的位序
  96.     */
  97.     int LocalElem(const T& e, bool (*Compare)(T, T)= equal);
  99.     /*
  100.      * 返回顺序表中第i个位置的元素
  101.      * @param[in] i 需要获取元素的位置
  102.      * @param[out] e 顺序表中第i个位置的元素值
  103.      * @return 返回函数执行结果
  104.      * -SQUSUCCEED 表示函数执行成功
  105.      * -SQUERROR 表示函数执行失败
  106.      * @note C++中数组的下标是从0开始，因此第i个位置的元素应该取下标为i-1的元素
  107.     */
  108.     int GetItem(int i, T& e);
  110.     /*
  111.      * 在顺序表的第i个位置之前插入元素
  112.      * @param[in] 元素的插入位置
  113.      * @param[in] 插入元素值
  114.      * @return 返回函数的执行结果
  115.      * -SQUSUCCEED 表示函数执行成功
  116.      * -SQUERROR 表示函数执行失败
  117.     */
  118.     int InsertItem(int i, T& e);
  120.     /*
  121.      * 删除顺序表中第i个位置的元素
  122.      * @param[in] i 待删除元素位置
  123.      * @param[out] e 删除元素的值
  124.      * @return 返回函数的执行结果
  125.      * -SQUSUCCEED 表示函数执行成功
  126.      * -SQUERROR 表示函数执行失败
  127.     */
  128.     int DeleteItem(int i, T& e);
  130.     /*
  131.      * 显示顺序表中元素
  132.      * @return 返回函数的执行结果
  133.      * -SQUSUCCEED 表示函数执行成功
  134.      * -SQUERROR 表示函数执行失败
  135.     */
  136.     int Show(); // 输出表中元素
  138.     /*
  139.      * 遍历线性表中元素
  140.      * @param[in] vi 函数指针，指向处理元素函数，默认为在屏幕打印元素
  141.     */
  142.     void Traverse(void (*vi)(T e) = show);
  144. private:
  145.     T* items;
  146.     int length;
  147.     int listsize;
  148. };
  150. template <class T>
  151. ListSqu<T>::ListSqu()
  152. {
  153.     items = new T[LIST_INIT_SIZE];
  154.     assert(items);
  155.     length = 0;
  156.     listsize = LIST_INIT_SIZE;
  157. }
  159. template <class T>
  160. ListSqu<T>::~ListSqu()
  161. {
  162.     if (items != NULL)
  163.     {
  164.         delete[] items;
  165.         items = NULL;
  166.     }
  167. }
  169. template <class T>
  170. ListSqu<T>::ListSqu(const ListSqu<T>& ls)
  171. {
  172.     length = ls.length;
  173.     listsize = ls.listsize;
  175.     items = new T[listsize + 1];
  176.     memcpy(items, ls.items, _msize(ls.items));
  177. }
  179. template <class T>
  180. ListSqu<T>& ListSqu<T>::operator=(const ListSqu<T>& ls)
  181. {
  182.     if( this == &ls )
  183.         return *this;
  185.     if (items != NULL)
  186.     {
  187.         delete[] items;
  188.         items = NULL;
  189.     }   
  191.     length = ls.length;
  192.     listsize = ls.listsize;
  194.     items = new T[listsize + 1];
  195.     memcpy(items, ls.items, _msize(ls.items));
  196.     return *this;
  197. }
  199. template <class T>
  200. int ListSqu<T>::ClearList()
  201. {
  202.     length = 0;
  203.     return SQUSUCCEED;
  204. }
  206. template <class T>
  207. bool ListSqu<T>::IsEmpty()
  208. {
  209.     return length == 0;
  210. }
  212. template <class T>
  213. int ListSqu<T>::LocalElem(const T& e, bool (*Compare)(T, T))
  214. {
  215.     int i = 0;
  216.     T* p;
  217.     p = items;
  218.     while ( i < length && !Compare(*p++, e))
  219.     {
  220.         ++i;
  221.     }
  223.     if (i < length)
  224.     {
  225.         return i + 1;
  226.     }
  227.     else
  228.     {
  229.         return 0;
  230.     }
  231. }
  233. template <class T>
  234. int ListSqu<T>::GetItem(int i, T& e)
  235. {
  236.     if ( (i < 1) || ( i > length ))
  237.     {
  238.         cout<<"所给位置超出位置索引!"<<endl;
  239.         return SQUERROR;
  240.     }
  241.     else
  242.     {
  243.         e = items[i -1];
  244.         return SQUSUCCEED;
  245.     }
  246. }
  248. template <class T>
  249. int ListSqu<T>::InsertItem(int i, T& e)
  250. {
  251.     if ( i < 1 || i > length + 1)
  252.     {
  253.         cout<<"所给位置出错！"<<endl;
  254.         return SQUERROR;
  255.     }
  256.     else
  257.     {
  258.         if (length >= listsize)
  259.         {
  260.             T* pNew = new T[LISTINCREMENT];
  261.             memcpy(pNew, items, _msize(items));
  262.             items = pNew;
  264.             if (items == NULL)
  265.             {
  266.                 cout<<"申请内存空间失败！"<<endl;
  267.                 return SQUOVERFLOW;
  268.             }
  269.             listsize += LISTINCREMENT;
  270.         }
  272.         for(int k = length; k >= i - 1; k--)
  273.         {
  274.             items[k+1] = items[k];
  275.         }
  277.         items[i-1] = e;
  278.         length++;
  280.         return SQUSUCCEED;
  281.     }
  282. }
  284. template <class T>
  285. int ListSqu<T>::DeleteItem(int i, T& e)
  286. {
  287.     if ( i < 1 || i > length )
  288.     {
  289.         cout<<"所给删除位置出错！"<<endl;
  290.         return SQUERROR;
  291.     }
  293.     e = items[i-1];
  295.     for (i = i -1; i < length; i++)
  296.     {
  297.         items[i] = items[i + 1];
  298.     }   
  299.     length--;
  300.     return SQUSUCCEED;
  301. }
  303. template <class T>
  304. int ListSqu<T>::Show()
  305. {
  306.     for (int i = 0; i < length; i++)
  307.     {
  308.         cout<<items[i]<<endl;
  309.     }
  310.     return SQUSUCCEED;
  311. }
  313. template <class T>
  314. void ListSqu<T>::Traverse(void (*vi)(T e))
  315. {
  316.     for (int i = 0; i < length; i++)
  317.     {
  318.        vi(items[i]);
  319.     }
  320. }
  321. #endif

    通过编写这段代码，觉得以下几点需要特别注意：

    1. 需要特别注意内存越界的情况，对于动态申请的内存指针，如果对其进行越界操作，在使用delete操作释放该指针时会造成程序崩溃。在编写上面的程序时就将

template <class T> ListSqu<T>& ListSqu<T>::operator=(const ListSqu<T>& ls)

函数中items = new T[listsize + 1];错误的写成了items = new T[length + 1];而造成内存越界，详细解释如下：

template <class T>
ListSqu <T>& ListSqu <T>::operator=(const ListSqu <T>& ls)
{
    if( this == &ls )
        return *this;

    delete[] items;
    items = NULL;

    length = ls.length;
    listsize = ls.listsize;

    items = new T[length + 1];  
    memcpy(items, ls.items, _msize(ls.items));
    return *this;
}

items = new T[length + 1];
这里应该是
items = new T[listsize + 1]; 
listsize是我在类的构造函数中初始化分配的内存数，而length是当前线性表中存放的元素个数，这里用length+1分配内存，而在memcpy(items, ls.items, _msize(ls.items)); 又将sizeof(T)*listsize长的字节拷贝给items该处发生越界了

2. 注意模板类的复制构造函数和赋值操作符的声明方法

3. 注意如何把函数指针当作形参并对其使用默认参数的方法

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zhangyunlin/p/6167977.html