编程宝库 - 技术改变世界

编程宝库

Search

编程技术

单链表的优化（十三）

线性表的本质、操作及顺序存储结构（六）

典型问题分析（十五）

本文讲解"典型问题分析（十五）"，用于解决相关问题。

在经过一段时间的编写，我们的数据结构库已经有了一定的规模。那么我们之前编写的代码就没有一点 bug 吗？之前每个代码都是经过测试了的，因此阔能是没有 bug 的，但是我们还是来对它进行分析，看看究竟是否一点 bug 都没有呢。

测试 1 ：创建异常对象时的空指针问题，如下

典型问题分析（十五）

main.cpp 如下

#include <iostream>
#include "Exception.h"

using namespace std;
using namespace DTLib;

int main()
{
    try
    {
        NullPointerException npe;

        cout << "throw" << endl;

        throw npe;
    }
    catch(const Exception& e)
    {
        cout << "catch" << endl;
    }

    return 0;
}

我们来看看编译结果

典型问题分析（十五）

我们看到编译运行时正常结束的，并没有出错。那么这是否就说明我们之前所编写的代码一点 bug 也没有呢？我们来看看之前的 Exception 类族是怎样实现的，它调用的是 strdup 函数实现的。我们在网上搜下 strdup 函数是怎样实现的，它的源码如下

典型问题分析（十五）

我们看到它并没有做指针 s 为空的判断，因此我们直接使用这个函数还是有问题的。我们要在 message 赋值这块使用下三目运算符来进行判断，代码如下

void Exception::init(const char* message, const char* file, int line)
{
    m_message = (message ? strdup(message) : NULL);

    if( file != NULL )
    {
        char s1[16] = {0};

        itoa(line, s1, 10);

        m_location = static_cast<char*>(malloc(strlen(file) + strlen(s1) + 2));
        m_location = strcpy(m_location, file);
        m_location = strcat(m_location, ":");
        m_location = strcat(m_location, s1);
    }
    else
    {
        m_location = NULL;
    }
}

这样的话，代码就足够安全了。

测试 2 ：LinkList 中的数据元素删除

main.cpp 如下

#include <iostream>
#include "LinkList.h"

using namespace std;
using namespace DTLib;

class Test : public Object
{
    int m_id;
public:
    Test(int id = 0)
    {
        m_id = id;
    }

    ~Test()
    {
        if( m_id == 1 )
        {
            throw m_id;
        }
    }
};

int main()
{
    LinkList<Test> list;
    Test t0(0), t1(1), t2(2);

    try
    {
        list.insert(t0);
        list.insert(t1);
        list.insert(t2);

        list.remove(1);
    }
    catch(int e)
    {
        cout << e << endl;
        cout << list.length() << endl;
    }

    return 0;
}

我们在 QT 中编译运行的时候直接崩溃了，因为 Test 类在析构时抛出异常了。在 VS 上运行时可以得到一丁点的结果，打印出的结果是链表的长度为 3。在销毁 t1 对象之后，结果还是为 3，这个结果就有点问题了。我们来看看 LinkList 的 remove 操作是怎样实现的，它是在 destroy 之后才进行 m_length-- 的。我们应该在 destroy 之前进行 m_length--才行。那么 remove 操作有问题，clear 操作肯定也有问题了。我们应该在 destroy 之前进行 m_length-- 的操作，而不是在最后将它赋值为 0。

测试 3 ：LinkList 中遍历操作与删除操作的混合使用

main.cpp 如下

#include <iostream>
#include "LinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    LinkList<int> 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() << endl;
        }
    }

    for(int i=0; i<list.length(); i++)
    {
        cout << list.get(i) << endl;
    }

    return 0;
}

我们来编译运行，看看结果

典型问题分析（十五）

结果是正确的，那么上面在查找数值为 3 的元素，查找成功之后删除。那么删除完之后他的 current 值为多少呢？我们看到结果是一个随机数。那么问题来了，我们在删除之后，理论上看到的数据元素应该是它的下一个数字 4 啊。这是就需要修改 remove 函数了。我们在 remove 函数中添加一个判断，如果它是指向即将要被删除的元素，那么就将它指向 toDel->next。具体改动如下

bool remove(int i)
{
    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;
}

我们再来看看编译结果

典型问题分析（十五）

那么此时这个 bug 就已经解决了。

测试 4 ：StaticLinkList 中数据元素删除时的效率问题

main.cpp 如下

#include <iostream>
#include "StaticLinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    StaticLinkList<int, 10> list;

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

    list.remove(3);

    for(int i=0; i<list.length(); i++)
    {
        cout << list.get(i) << endl;
    }

    return 0;
}

我们来看看编译结果

典型问题分析（十五）

结果自然是没错的，我们再来仔细看看 StaticLinkList 类的 destroy 函数。在归还空间之后，我们应该直接跳出循环，这样效率会高一点。

测试 5 ：StaticLinkList 是否需要提供析构函数？

main.cpp 如下

#include <iostream>
#include "StaticLinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    StaticLinkList<int, 10> list;

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

    for(int i=0; i<list.length(); i++)
    {
        cout << list.get(i) << endl;
    }

    return 0;
}

我们在 LinkList 类中是提供了析构函数的，并且这个析构函数是虚函数。我们根据之前的知识，虽然父类 LinkList 有析构函数的实现，但是这个析构函数不会发生多态的，所以说在 LinkList 中调用的 clear 函数是 LinkList 中的 clear 函数，在 StaticLinkList 中的 clear 函数调用的也是 LinkList 中的 clear 函数。但是在 clear 函数中调用的是 destroy 函数，所以两个类调用的 destroy 函数都是 LinkList 类中的 destroy 函数。我们在 LinkList 和 StaticLinkList 中的 create 和 destroy 函数中都打上断点，然后进行断点调试，看看结果

典型问题分析（十五）

我们看到在进行 create 的时候，因为类对象是 StaticLinkList 类型的，所以它会去按照 StaticLinkList 的方式来进行 create，再来看看 destroy 时，进行的是哪个类函数的实现

典型问题分析（十五）

我们看到在进行 destroy 时进行的是 LinkList 方式，这时便出现问题了。此时 delete 操作有可能不是进行的是堆空间上的操作，那么程序没直接崩溃时因为这个程序太短小了。我们要将它改为实现的是 StaticLinkList 方式的 destroy 函数。那么该如何操作呢？我们就需要在 StaticLinkList 类中加上它的析构函数了，如下

~StaticLinkList()
{
    this->clear();
}

我们再来断点调试下，看看它调用的 destroy 函数究竟是哪个版本的实现。

典型问题分析（十五）

我们看到这下调用的是 StaticLinkList 类方式的实现了。

测试 6 ：DTLib 库是否有必要增加多维数组类呢？ 多维数组的本质其实就是数组的数组！

main.cpp 如下

#include <iostream>
#include "StaticLinkList.h"
#include "DynamicArray.h"

using namespace std;
using namespace DTLib;

int main()
{
    DynamicArray< DynamicArray<int> > d;

    d.resize(3);

    for(int i=0; i<d.length(); i++)
    {
        d[i].resize(3);
    }

    for(int i=0; i<d.length(); i++)
    {
        for(int j=0; j<d[i].length(); j++)
        {
            d[i][j] = i + j;
        }
    }

    for(int i=0; i<d.length(); i++)
    {
        for(int j=0; j<d[i].length(); j++)
        {
            cout << d[i][j] << " ";
        }

        cout << endl;
    }

    return 0;
}

我们来看看编译运行结果

典型问题分析（十五）