【数据结构】26_典型问题分析(Bugfix)

ISSUE_1 创建对象时的空指针问题

【数据结构】26_典型问题分析(Bugfix)_第1张图片

strdup 源代码:
char * __strdup(const char *s)  
{  
   size_t  len = strlen(s) +1;  
   void *new = malloc(len);  
   if (new == NULL)  
      return NULL;  
   return (char *)memecpy(new,s,len);  
}
问题:strdup 未对空指针做处理。
m_message = strdup(message);

==>

m_message = (message != nullptr) ? strdup(message) : nullptr;

[修复] 文件:Exception.cpp

#include "Exception.h"

#include 
#include 

namespace DTLib
{

Exception::Exception(const char *message) : Exception(message, nullptr, 0)
{
}

Exception::Exception(const char *file, int line) : Exception(nullptr, file, line)
{
}

Exception::Exception(const char *message, const char *file, int line)
{
    m_message = (message != nullptr) ? strdup(message) : nullptr;  // 修复!!

    if (file != nullptr)
    {
        char sl[16] = {0};

        itoa(line, sl, 10);

        m_location = static_cast(malloc(strlen(file) + strlen(sl) + 2));
        m_location = strcpy(m_location, file);
        m_location = strcat(m_location, ":");
        m_location = strcat(m_location, sl);
    }
    else
    {
        m_location = nullptr;
    }
}

Exception::Exception(const Exception &e)
{
    m_message = strdup(e.m_message);
    m_location = strdup(e.m_location);
}

Exception &Exception::operator= (const Exception &e)
{
    if (this != &e)
    {
        free(m_message);
        free(m_location);

        m_message = strdup(e.m_message);
        m_location = strdup(e.m_location);
    }

    return *this;
}

const char *Exception::message() const
{
    return m_message;
}

const char *Exception::location() const
{
    return m_location;
}

Exception::~Exception()
{
    delete m_message;
    delete m_location;
}

}

ISSUE_2 LinkList 中数据元素删除

LinkList list;
Test t0(0), t1(1), t2(2);  // t1 在析构时抛出异常

try
{
}
catch(...)
{
    cout << list.length() << endl;  // ???
}
输出:[Qt]
说明:Qt中析构函数抛出的异常,无法被外部捕获
terminate called after throwing an instance of 'int'
输出:[vs]
1
3
问题:单链表状态出现问题,期望结果为 2。
定位:remove 函数未考虑异常安全。
bool remove(int i)
{
    // ...
    destroy(toDel);
    --m_length;
    // ...
}

==>

bool remove(int i)
{
    // ...
    --m_length;
    destroy(toDel);
    // ...
}

[修复]文件:LinkList.h

#ifndef LINKLIST_H
#define LINKLIST_H

#include "List.h"
#include "Exception.h"

namespace DTLib
{

template 
class LinkList : public List
{
public:
    LinkList()
    {
        m_header.next = nullptr;
        m_length      = 0;

        m_step        = 0;
        m_current     = nullptr;
    }

    bool insert(const T &e) override  // O(n)
    {
        return insert(m_length, e);
    }

    bool insert(int i, const T &e) override  // O(n)
    {
        bool ret = ((0 <= i) && (i <= m_length));

        if (ret)
        {
            Node *node = create();
            if (node != nullptr)
            {
                Node *current = position(i);

                node->value = e;
                node->next = current->next;
                current->next = node;

                ++m_length;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
            }
        }

        return ret;
    }

    bool remove(int i) override  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if (ret)
        {
            Node *current = position(i);

            Node *toDel = current->next;
            current->next = toDel->next;

            --m_length;

            destroy(toDel);
        }

        return ret;
    }

    bool set(int i, const T &e) override  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if (ret)
        {
            position(i)->next->value = e;
        }

        return ret;
    }

    T get(int i) const  // O(n)
    {
        T ret;

        if (!get(i, ret))
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
        }

        return ret;
    }

    bool get(int i, T &e) const override  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if (ret)
        {
            e = position(i)->next->value;
        }

        return ret;
    }

    int  find(const T &e) override  // O(n)
    {
        int ret = -1;

        int i = 0;
        Node *node = m_header.next;
        while (node)
        {
            if (node->value == e)
            {
                ret = i;
                break;
            }
            else
            {
                node = node->next;
                ++i;
            }
        }

        return ret;
    }

    int length() const  // O(1)
    {
        return m_length;
    }

    void clear()  // O(n)
    {
        while (m_header.next)
        {
            Node *toDel = m_header.next;

            m_header.next = toDel->next;

            --m_length;

            destroy(toDel);
        }
    }

    bool move(int i, int step = 1)  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length) && (step > 0));

        if (ret)
        {
            m_current = position(i)->next;
            m_step = step;
        }

        return ret;
    }

    bool end()  // O(1)
    {
        return (m_current == nullptr);
    }

    T current()  // O(1)
    {
        if (!end())
        {
            return m_current->value;
        }
        else
        {
             THROW_EXCEPTION(InvalidOpertionExcetion, " No value at current posotion ...");
        }
    }

    bool next()  // O(n)
    {
        int i = 0;

        while ((i < m_step) && !end())
        {
            m_current = m_current->next;
            ++i;
        }

        return (i == m_step);
    }

    ~LinkList()  // O(n)
    {
        clear();
    }

protected:
    struct Node : public Object
    {
        T value;
        Node *next;
    };

    mutable struct : public Object
    {
        char reserved[sizeof (T)];
        Node *next;
    }m_header;

    int m_length;
    int m_step;
    Node *m_current;

    Node *position(int i) const  // O(n)
    {
        Node *ret = reinterpret_cast(&m_header);

        for (int p=0; pnext;
        }

        return ret;
    }

    virtual Node *create()  // N(1)
    {
        return new Node();
    }

    virtual void destroy(Node *pn)  // N(1)
    {
        delete pn;
    }
};

}

#endif // LINKLIST_H

ISSUE_3 LinkList 中遍历操作与删除操作的混合使用

LinkList list;
for (int i=0; i<5; ++i)
{
    list.insert(i);
}

for (list.move(0); !list.end(); list.next())
{
    if (list.current() == 3)
    {
        list.remove(list.find(list.current()));
        
        cout << list.current->value() << endl; ???
    }
}
输出:[随机值]
18022592
原因:current 指向的堆空间被释放。
bool remove(int i) override  // O(n)
{
    bool ret = ((0 <= i) && (i < m_length));

    if (ret)
    {
        Node *current = position(i);
        Node *toDel = current->next;
        current->next = toDel->next;
        --m_length;
        destroy(toDel);
    }

    return ret;
}

==>

bool remove(int i) override  // O(n)
{
    bool ret = ((0 <= i) && (i < m_length));

    if (ret)
    {
        Node *current = position(i);
        Node *toDel = current->next;
        if (m_current == toDel)
        {
            m_current = toDel->next;
        }
        current->next = toDel->next;
        --m_length;
        destroy(toDel);
    }

    return ret;
}

[修复]LinkList.h

#ifndef LINKLIST_H
#define LINKLIST_H

#include "List.h"
#include "Exception.h"

namespace DTLib
{

template 
class LinkList : public List
{
public:
    LinkList()
    {
        m_header.next = nullptr;
        m_length      = 0;

        m_step        = 0;
        m_current     = nullptr;
    }

    bool insert(const T &e) override  // O(n)
    {
        return insert(m_length, e);
    }

    bool insert(int i, const T &e) override  // O(n)
    {
        bool ret = ((0 <= i) && (i <= m_length));

        if (ret)
        {
            Node *node = create();
            if (node != nullptr)
            {
                Node *current = position(i);

                node->value = e;
                node->next = current->next;
                current->next = node;

                ++m_length;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
            }
        }

        return ret;
    }

    bool remove(int i) override  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if (ret)
        {
            Node *current = position(i);

            Node *toDel = current->next;

            if (m_current == toDel)
            {
                m_current = toDel->next;
            }

            current->next = toDel->next;

            --m_length;

            destroy(toDel);
        }

        return ret;
    }

    bool set(int i, const T &e) override  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if (ret)
        {
            position(i)->next->value = e;
        }

        return ret;
    }

    T get(int i) const  // O(n)
    {
        T ret;

        if (!get(i, ret))
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
        }

        return ret;
    }

    bool get(int i, T &e) const override  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if (ret)
        {
            e = position(i)->next->value;
        }

        return ret;
    }

    int  find(const T &e) override  // O(n)
    {
        int ret = -1;

        int i = 0;
        Node *node = m_header.next;
        while (node)
        {
            if (node->value == e)
            {
                ret = i;
                break;
            }
            else
            {
                node = node->next;
                ++i;
            }
        }

        return ret;
    }

    int length() const  // O(1)
    {
        return m_length;
    }

    void clear()  // O(n)
    {
        while (m_header.next)
        {
            Node *toDel = m_header.next;

            m_header.next = toDel->next;

            --m_length;

            destroy(toDel);
        }
    }

    bool move(int i, int step = 1)  // O(n)
    {
        bool ret = ((0 <= i) && (i < m_length) && (step > 0));

        if (ret)
        {
            m_current = position(i)->next;
            m_step = step;
        }

        return ret;
    }

    bool end()  // O(1)
    {
        return (m_current == nullptr);
    }

    T current()  // O(1)
    {
        if (!end())
        {
            return m_current->value;
        }
        else
        {
             THROW_EXCEPTION(InvalidOpertionExcetion, " No value at current posotion ...");
        }
    }

    bool next()  // O(n)
    {
        int i = 0;

        while ((i < m_step) && !end())
        {
            m_current = m_current->next;
            ++i;
        }

        return (i == m_step);
    }

    ~LinkList()  // O(n)
    {
        clear();
    }

protected:
    struct Node : public Object
    {
        T value;
        Node *next;
    };

    mutable struct : public Object
    {
        char reserved[sizeof (T)];
        Node *next;
    }m_header;

    int m_length;
    int m_step;
    Node *m_current;

    Node *position(int i) const  // O(n)
    {
        Node *ret = reinterpret_cast(&m_header);

        for (int p=0; pnext;
        }

        return ret;
    }

    virtual Node *create()  // N(1)
    {
        return new Node();
    }

    virtual void destroy(Node *pn)  // N(1)
    {
        delete pn;
    }
};

}

#endif // LINKLIST_H

ISSUE_4 StaticLinkList 是否需要提供析构函数?

int main()
{
    StaticLinkList sll;
    
    for (int i=0; i<10; ++i)
    {
        sll.insert(i);
    }
    
    return 0;  // 如何析构???
}
背景知识:

在构造函数和析构函数中,不会发生多态行为,只会调用自身版本的成员函数(无论直接还是间接调用)

知识点传送门

析构过程分析:

==> StaticLinkList 析构函数执行
==> LinkList 析构函数执行
==> LinkList::clear() 函数执行
==> LinkList::destroy() 函数执行
==> delete 非堆空间指针,行为未定义

解决方案:为StaicLinkList 提供析构函数
~StaticLinkList()  // O(n)
{
    this->clear();
}
析构过程分析:

==> StaticLinkList 析构函数执行
==> StaticLinkList::clear() 函数执行
==> StaticLinkList::destroy() 函数执行

[修复] 文件:StaticLinkList.h

#ifndef STATICLINKLIST_H
#define STATICLINKLIST_H

#include "LinkList.h"

#include 

using namespace std;

namespace DTLib
{

template 
class StaticLinkList : public LinkList
{
public:
    StaticLinkList()  // O(n)
    {
        for (int i=0; iclear();
    }

protected:
    //typedef typename LinkList::Node Node;
    using Node = typename LinkList::Node;

    struct SNode : public Node
    {
        void *operator new (unsigned int size, void *loc)
        {
            (void)size;

            return loc;
        }
    };

    unsigned char m_space[N * sizeof(SNode)];
    char m_used[N];

    Node *create() override  // O(n)
    {
        SNode *ret = nullptr;

        for (int i=0; i(m_space) + i;
                ret = new(ret)SNode;
                m_used[i] = 1;
                break;
            }
        }

        return ret;
    }

    void destroy(Node *pn) override  // O(n)
    {
        SNode *space = reinterpret_cast(m_space);
        SNode *psn = dynamic_cast(pn);

        for (int i=0; i~Node();
                break;
            }
        }
    }
};

}

#endif // STATICLINKLIST_H

ISSUE_5 DTLib 是否有必要增加多维数组类?

No. 多维数组的本质:数组的数组!
main.cpp
#include 
#include "DynamicArray.h"

using namespace std;
using namespace DTLib;

int main()
{
    DynamicArray< DynamicArray > d;

    d.resize(3);

    for (int i=0; i

输出:

0
1 2
2 3 4

实践经验

是软件就有bug,因此需要不停的迭代升级,解决问题。
库是一种特殊的软件产品,也会存在各种bug,也需要迭代升级,解决问题。
只要代码发生改动,就需要测试。

以上内容整理于狄泰软件学院系列课程,请大家保护原创!

你可能感兴趣的