17_StaticList和DynamicList

关键词： StaticList类的具体实现、DynamicList类的具体实现

1. 课程目标：

• 完成StaticList类的具体实现
• 完成DynamicList类的具体实现
  

2. StaticList设计要点

类模板：

• 使用原生数组作为顺序存储空间
• 使用模板参数决定数组大小

3. StaticList的实现

StaticList

#ifndef STATICLIST_H
#define STATICLIST_H

#include "SeqList.h"

namespace DTLib
{

template <typename T, int N>
class StaticList : public SeqList<T>
{
protected:
    T m_space[N];       // 顺序存储空间， N 为模板参数
public:
    StaticList()
    {
        this->m_array = m_space;
        this->m_length = 0;
    }

    int capacity() const
    {
        return N;
    }
};

}

#endif // STATICLIST_H

4. DynamicList设计要点

1. 类模板：

• 申请连续堆空间作为顺序存储空间
• 动态设置顺序存储空间的大小
• 保证重置顺序存储空间时的异常安全性

2. 函数异常安全的概念

• 不泄露任何资源
• 不允许破坏数据

3. 函数异常安全的基本保证

• 如果异常被抛出，对象内的任何成员仍然能保持有效状态
• 如果异常被抛出，没有数据的破坏及资源泄露

5. DynamicList的实现

DynamicList.h

#ifndef DYNAMICLIST_H
#define DYNAMICLIST_H

#include "SeqList.h"
#include "Exception.h"

namespace DTLib
{

template <typename T>
class DynamicList : public SeqList<T>
{
protected:
    int m_capacity;         // 顺序存储空间的大小
public:
    DynamicList(int capacity)   // 申请空间
    {
        this->m_array = new T[capacity];

        if( this->m_array != NULL )
        {
            this->m_length = 0;
            this->m_capacity = capacity;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create DynamicList Object...");
        }
    }

    int capacity() const
    {
        return m_capacity;
    }

    void resize(int capacity)   // 重置顺序存储空间的大小
    {
        if( capacity != m_capacity )
        {
            T* array = new T[capacity];

            if( array != NULL )
            {
                int length = (this->m_length < capacity ? this->m_length : capacity);

                for(int i=0; i<length; i++)
                {
                    array[i] = this->m_array[i];
                }

                T* temp = this->m_array;

                this->m_array = array;
                this->m_length = length;
                this->m_capacity = capacity;

                delete[] temp;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to resize DynamicList Object... ");
            }
        }
    }

    ~DynamicList()      // 归还空间
    {
        delete[] this->m_array;
    }
};

}

#endif // DYNAMICLIST_H

6. 是否可以将DynamicList作为StaticList的子类实现？

不可以：DynamicList内存结构和StaticList内存结构完全不同，之间没有任何关系，不能作为父子关系，只能作为平级。

7. 小结

• StaticList 通过模板参数定义顺序存储空间
• DynamicList通过动态内存申请定义顺序存储空间
• DynamicList支持动态重置顺序存储空间的大小
• DynamicList中的resize()函数实现需要保证异常安全

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4