问题1：
glibc中的strdup实现如下：
没有对参数s进行空指针判断。
我们的Exception.cpp中应做改进：
在第12行进行判断空指针操作。
问题2：
t1在析构时会抛出异常，我们在remove一个对象时，要保证链表还是合法的，也就是保证异常安全性。
如上图，我们期望打印的链表长度为2。
示例程序：
#include <iostream>
#include "LinkList.h" using namespace std;
using namespace DTLib; class Test : public Object
{
int m_id;
public:
Test(int id = )
{
m_id = id;
} ~Test()
{
if( m_id == )
{
throw m_id;
}
}
}; int main()
{
LinkList<Test> list;
Test t0(), t1(), t2(); try
{
list.insert(t0);
list.insert(t1);
list.insert(t2); list.remove();
}
catch(int e)
{
cout << e << endl;
cout << list.length() << endl;
} return ;
}
结果如下：
程序直接崩溃了。
vc下的运行结果如下：
打印e的值为1，链表长度为3，意味着单链表的状态出问题了。
我们的remove函数没有考虑异常安全性。
修改LinkList.h：
#ifndef LINKLIST_H
#define LINKLIST_H #include "List.h"
#include "Exception.h" namespace DTLib
{ template < typename T >
class LinkList : public List<T>
{
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<Node*>(&m_header); for(int p = ; p < i; p++)
{
ret = ret->next;
} return ret;
} virtual Node* create()
{
return new Node();
} virtual void destroy(Node* pn)
{
delete pn;
} public:
LinkList()
{
m_header.next = NULL;
m_length = ;
m_step = ;
m_current = NULL;
} bool insert(const T& e)
{
return insert(m_length, e);
} bool insert(int i, const T& e) // O(n)
{
bool ret = (( <= i) && (i <= m_length)); if( ret )
{
Node* node = create(); if( node != NULL )
{
Node* current = position(i); node->value = e;
node->next = current->next;
current->next = node; m_length++;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memery to insert new element...");
}
} return ret;
} bool remove(int i) // O(n)
{
bool ret = (( <= 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) // O(n)
{
bool ret = (( <= i) && (i < m_length)); if( ret )
{
position(i)->next->value = e;
} return ret;
} T get(int i) const
{
T ret; if( get(i, ret) )
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
} return ret;
} bool get(int i, T& e) const // O(n)
{
bool ret = (( <= i) && (i < m_length)); if( ret )
{
e = position(i)->next->value;
} return ret;
} int find(const T& e) const // O(n)
{
int ret = -;
int i = ; 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);
} // m_length = 0;
} bool move(int i, int step = )
{
bool ret = ( <= i) && (i < m_length) && (step > ); if( ret )
{
m_current = position(i)->next;
m_step = step;
} return ret;
} bool end()
{
return (m_current == NULL);
} T current()
{
if( !end() )
{
return m_current->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
}
} bool next() //每次移动step步
{
int i = ; while((i < m_step) && !end())
{
m_current = m_current->next;
i++;
} return (i == m_step);
} ~LinkList() // O(n)
{
clear();
}
}; } #endif // LINKLIST_H
在remove函数中，先让m_length--，再做摧毁节点的操作。
在clear函数中，注释掉原来的196行，添加第191行，每次摧毁前让m_length--。
问题3：
测试程序如下：
结果如下：
删除之后，游标m_current指向这个释放之后的内存，current函数返回的是这个释放了的内存中保存的value。
图解：
删除之后current函数返回的这块被释放了的堆内存中的value的值，所以会打印出随机值。
修改LinkList.h中的remove函数：
bool remove(int i) // O(n)
{
bool ret = (( <= 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;
}
我们添加了第11-14行，在删除时，先进行判断，如果m_current和toDel指向的是同一个节点，那么先将m_current指向toDel的下一个节点，然后再删除。
运行结果如下：
问题4：
程序改进：
void destroy(Node* pn)
{
SNode* space = reinterpret_cast<SNode*>(m_space);
SNode* psn = dynamic_cast<SNode*>(pn); for(int i = ; i<N; i++)
{
if( psn == (space + i))
{
m_used[i] = ;
psn->~SNode();
break;
}
}
}
添加了第12行的break。
问题5：
StaticLinkList的构造函数中没有申请系统资源，从资源方面来看不用提供析构函数。
不提供析构函数的第二个条件是，该类为一个独立的类，没有任何继承关系，但是我们StaticLinkList不满足。
StaticLinkList继承自LinkList，LinkList中有析构函数，且这个析构函数调用了一个虚函数，但是多态是不会发生的。
构造函数和析构函数中不会发生多态。
StaticLinkList类中没有clear函数，因此，默认的析构函数会调用到LinkList的析构函数，进一步调用到clear函数，这个clear函数在子类和在父类中调用是一样的。
如果子类StaticLinkList中也有一个clear函数版本，那就要提供析构函数了。因为这两个含本的析构函数都要调用到。
但是我们再仔细观察可以发现，在clear函数中还调用了destroy函数，而这个函数在子类和父类中各有一个版本。
子类中的版本是：
父类中提供的版本是：
这意味着父类中的析构函数被调用的时候，调用到的destroy一直是父类中的destroy。子类中的destroy无法被调用到，因为析构函数中不能发生多态。
析构时父类中的destroy直接delete掉申请的空间，而这个空间是在我们的预留区域中申请的，不是堆空间，因此，可能会出现bug，造成程序的不稳定，因为delete关键字只能释放堆空间。
改进程序，添加子类的析构函数：
#ifndef STATICLINKLIST_H
#define STATICLINKLIST_H #include "LinkList.h" namespace DTLib
{ template< typename T, int N >
class StaticLinkList : public LinkList<T>
{
protected:
// Node和泛指类型T有关系，因此，不能直接在子类中使用sizeof(Node),而应该
// sizeof(LinkList<T>::Node)
// unsigned char m_space[sizeof(typename LinkList<T>::Node) * N]; // 预留空间
typedef typename LinkList<T>::Node Node; struct SNode : public Node
{
void* operator new(unsigned int size, void* loc)
{
(void)size; // 消除 size没有使用的警告
return loc;
}
}; unsigned char m_space[sizeof(SNode) * N]; // 预留空间
int m_used[N]; //预留空间的标记数组 Node* create()
{
SNode* ret = NULL; for(int i = ; i < N; i++)
{
if( !m_used[i] )
{
ret = reinterpret_cast<SNode*>(m_space) + i;
ret = new(ret)SNode(); //在指定空间ret上调用SNode类的构造函数。
m_used[i] = ;
break;
}
} return ret;
} void destroy(Node* pn)
{
SNode* space = reinterpret_cast<SNode*>(m_space);
SNode* psn = dynamic_cast<SNode*>(pn); for(int i = ; i<N; i++)
{
if( psn == (space + i))
{
m_used[i] = ;
psn->~SNode();
break;
}
}
} public:
StaticLinkList()
{
for(int i = ; i < N; i++)
{
m_used[i] = ;
}
} int capacity()
{
return N;
} ~StaticLinkList()
{
this->clear();
}
}; } #endif // STATICLINKLIST_H
添加了第78-81行的析构函数，这时的clear是从父类继承来的，但是clear中的destroy函数就是子类自己实现的了。
这样的话析构时，先调用子类的析构函数，然后是子类继承过来的clear函数，然后子类的destroy函数。子类的析构函数执行完时，再调用父类的析构函数，然后父类的clear函数，最后调用父类的destroy函数。但是单步执行时，我们发现并没有调用到父类的destroy函数，这里可能令人迷惑，其实是因为调用父类的析构函数时，clear函数中的while循环已经不成立的，也就不会再调用父类的destroy函数了。单步执行时要注意这一点，调用不到父类的destroy是因为条件不成立，而不是其他的机制导致的。如下：
从子类的析构函数执行完，到调用到父类的析构函数时，clear函数中的190行的条件已经不成立了。
我们在子类的析构函数和destroy函数，父类的析构函数和destroy函数加上打印，测试程序如下：
#include <iostream>
#include "StaticLinkList.h" using namespace std;
using namespace DTLib; int main()
{
StaticLinkList<int, > list; list.insert(); cout << list.get() << endl; return ;
}
结果如下：
问题6：
没有必要定义多维数组的类，由一位数组就可以构成。
示例程序：
#include <iostream>
#include "StaticLinkList.h"
#include "DynamicArray.h" using namespace std;
using namespace DTLib; int main()
{
StaticLinkList<int, > list; DynamicArray< DynamicArray<int> > d; d.resize(); for(int i=; i < d.length(); i++)
{
d[i].resize();
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
d[i][j] = i * j;
}
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
cout << d[i][j] << " ";
} cout << endl;
} return ;
}
结果如下：
还可以构造不规则的数组：
#include <iostream>
#include "StaticLinkList.h"
#include "DynamicArray.h" using namespace std;
using namespace DTLib; int main()
{
StaticLinkList<int, > list; DynamicArray< DynamicArray<int> > d; d.resize(); for(int i=; i < d.length(); i++)
{
d[i].resize(i + );
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
d[i][j] = i + j;
}
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
cout << d[i][j] << " ";
} cout << endl;
} return ;
}
第19行使得每个数组元素大小不一样，运行结果如下：
实践经验：
