利记手机网
  咨询电话:13900856965

利记体育官网

十二、典型问题分析

问题1:创建异常对象时的空指针问题

创建一个空指针异常对象,意味着这会调用父类的构造函数Exception(0),然后调用init(0, NULL,0),然后调用m_message = strdup(0)

/* Duplicate S, returning an identical malloc"d string. */char * __strdup (const char *s){ size_t len = strlen (s) + 1; void *new = malloc (len); if (new == NULL) return NULL; return (char *) memcpy (new, s, len);}

缺陷:没有处理参数为空指针的情况,默认为参数不能为空。

参数为空指针的情况应该合法,空指针作为字符串的一个特殊值,是有意义的,如果要复制的字符串是一个空指针,只需要返回一个空指针就可以了,

m_message = strdup(message);// 改为m_message = (message ? strdup(message) : NULL);// 在外部对message为空的情况进行了处理

改进之后增强了代码的健壮性

问题2:单链表LinkList中的数据元素删除,异常安全性问题

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); // t1 在析构时抛出异常 list.insert(t2); list.remove(1); } catch(int e) { cout << e << endl; cout << list.length() << endl; } return 0;}

析构函数中抛出是一个不推荐的操作,但是强制这样做之后,要保证单链表对象list的合法性,这叫异常安全性。list.remove(1)删除下表为1的对象的时候,即删除t1对象的时候,肯定会调用t1的析构函数,从而抛出异常,那么期望的结果就是list.length()长度变为2,因为删除了一个元素t1。但是结果是程序直接崩溃,原因是QT使用的编译器所使用的g++编译器实现细节问题,不允许在析构函数中抛出异常,这个异常无法被捕捉。

使用vs之后,发现程序有输出:1 3,之后崩溃,过程如下:

vs中允许析构函数抛出异常,可以捕捉,故list.remove(1)之后会产生异常并被捕捉,e的信息就是m_id值为1,故输出1然后打印list.length(),值为3,意为着单链表的状态和我们期望的不一样,这里就是隐藏的问题,remove()函数没有考虑异常安全性

查看remove()的代码:

bool remove(int i) // O(n){ bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = position(i); Node* toDel = current->next; current->next = toDel->next; destroy(toDel); m_length--; } return ret;}

发现在实现这个函数的时候,是先destroy(toDel)之后,再进行长度的m_length--,这里就不够异常安全,因为在destroy之后,就进入了异常,不会进行长度运算,修改代码,交换两条代码的位置:

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

同样的,clear()函数也会有问题,在destroy之后再将m_length清0,同样的问题存在,也会导致单链表的状态混乱

void clear() // O(n){ // 释放每一个结点 while(m_header.next) { Node* toDel = m_header.next; m_header.next = toDel->next; //delete toDel; destroy(toDel); } m_length = 0;}

改进之后:

void clear() // O(n){ // 释放每一个结点 while(m_header.next) { Node* toDel = m_header.next; m_header.next = toDel->next; // 做完指针操作之后,就意味着对应的数据元素已经从单链表中剥离出来的,长度应该-- m_length--; //delete toDel; destroy(toDel); } }

问题3:LinkList中遍历操作与删除操作的混合使用

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())); // 删除成功后,list.current()的返回值是什么 cout << list.current() << endl; }}for (int i = 0; i<list.length(); i++){ cout << list.get(i) << endl;}

分析:

bool remove(int i) // O(n){ // 注意i的范围 bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = position(i); Node* toDel = current->next; current->next = toDel->next; //delete toDel; m_length--; destroy(toDel); } return ret;}

遍历之后current()指向3,删除该元素之后,current()的指向不明,故出现了随机数,改进:再remove中对m_current进行重新定位

bool remove(int i) // O(n){ // 注意i的范围 bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = position(i); Node* toDel = current->next; // 对m_current进行处理,移动到下一个位置 if (m_current == toDel) { m_current = toDel->next; } current->next = toDel->next; //delete toDel; m_length--; destroy(toDel); } return ret;}

问题4:StaticLinkList中数据元素删除时的效率问题

void destroy(Node* pn){ SNode* space = reinterpret_cast<SNode*>(m_space); SNode* spn = dynamic_cast<SNode*>(pn); for(int i = 0; i < N; i++) { if (spn == space + i) { m_used[i] = 0; spn->~SNode(); // 空间归还,对象析构,即可跳出循环,没必要再继续循环下去,加上break break; } }}

问题5:StaticLinkList是否需要提供析构函数

一个类是否需要提供析构函数,由资源来决定,如果在类的构造函数中申请了系统资源,就需要提供析构函数,在析构函数中对应地释放系统资源。这个判断依据的前提条件是:

所实现的类是一个独立的类,没有任何继承关系

StaticLinkList(){ for(int i = 0; i < N; i++) { m_used[i] = 0; }}// 从资源的角度看,构造函数只是进行了成员函数的赋值操作,没有申请系统资源,那么是不是可以不提供析构函数

但是这里的StaticLinkList是有继承关系的

template <typename T>class LinkList : public List<T>{... void clear() // O(n) { // 释放每一个结点 while(m_header.next) { Node* toDel = m_header.next; m_header.next = toDel->next; //delete toDel; destroy(toDel); } m_length = 0; }... ~LinkList() { clear(); }...};

在继承的类中有析构函数,并且在析构函数中调用了一个虚函数,但是构造函数和析构函数中是不会发生多态的,这个clear()函数就是类中实现的函数。所以对于StaticLinkList来说,父类中提供了clear()函数,但是子类中并没有提供该函数,所以不管在子类还是父类中调用这个函数,始终调用的都是LinkList中的clear();继续分析clear()函数,在里面又调用另外一个虚函数destroy(),父类LinkList中有一个destroy()函数版本,子类StaticLinkList中也有一个destroy()函数版本,这意味着:父类的析构函数被调用的时候,始终调用到的都是父类中的destroy()函数,子类中的destroy()是没有办法在析构的时候被调用到的。

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;}

list对象是一个子类StaticLinkList的对象,于是在主程序结束的时list对象就会被析构,接着就调用到父类的析构函数,从而调用父类中的clear()函数,其中的destroy()函数肯定是父类中的实现,这里就会有问题了

template <typename T>class LinkList : public List<T>{protected: virtual void destroy(Node* pn) { delete pn; }};

父类的destroy直接delete对应的内存空间,这个内存空间来自于子类creat()函数创建的空间toDel,这个空间是子类中的unsigned char m_space[sizeof(SNode) * N]中的空间,所以对于现在父类的destroy的空间就不是堆空间了,这就会造成程序的不稳定了,因为delete关键字只能释放堆空间,程序的崩溃时间无法预测。子类中所希望的destroy函数并没有被调用,这种问题在实际工程中不允许出现。

解决办法:在子类中添加自己的析构函数

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

调用的还是父类中clear()函数,但是clear调用的destroy函数却是当前类中的实现,原因是:构造函数和析构函数是不会发生多态的,在构造函数或析构函数中调用的虚函数必然是当前类中实现的版本,不管是直接调用还是间接调用,都是这样。所以这里一定会调用到子类中的destroy()函数,断点调试:

发现在父类的clear()函数中调用的确实是子类的destroy()函数,符合预期。

注意:经典问题

构造函数和析构函数中是不会发生多态的,所调用的虚函数都是当前类中实现的版本,不管直接调用还是间接调用

问题6:是否有必要增加多维数组类?

没有必要

多维数组的本质:数组的数组,本质还是一维数组

二维数组类对象

int main(){ DynamicArray< DynamicArray<int> > d; d.resize(3); for(int i=0; i<d.length(); i++) { // d[i].resize(3); d[i].resize(i + 1); // 不规则二维数组 } 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;}