本文共 17289 字，大约阅读时间需要 57 分钟。

.........

=====================================================================================

21课 线性表的链式存储结构

问题：顺序存储结构线性表的最大问题是插入和删除需要移动大量的元素，如果数据类型很大的时候，会非常的耗时，该如何解决这个问题？

链式存储的定义：为了表示每个数据元素与其后继元素之间的逻辑关系，数据元素除了存储本身的信息之外，还需要存储其直接后继的信息。

链式存储逻辑结构：

1 基于链式存储结构的线性表，每个结点都包含数据域和指针域1.1 数据域：存储数据元素本身1.2 指针域：存储相邻结点的地址

专业术语的统一：

1 顺序表：基于顺序存储结构的线性表2 链表：基于链式存储结构的线性表	2.1 单链表：每个结点只包含直接后继的地址信息	2.2 循环链表：单链表中的最后一个结点的直接后继为第一个结点	2.3 双向链表：单链表中的结点包含直接前驱和后继的地址信息

链表中的基本概念：

1 头结点：链表中的辅助结点，包含指向第一个数据元素的指针（没有实际功能，仅仅为了查找元素）	2 数据节点：链表中代表数据结构的结点，表现形式为：（数据元素，地址）	3 尾结点：链表中的最后一个数据结点，包含的地址信息为空

单链表中的结点定义：

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

单链表中的内部结构：

头结点在单链表中的意义是：辅助数据元素的定位，方便插入和删除操作，因此，头结点不存储实际的数据元素。

在单链表中目标位置插入一个数据元素：

1 从头节点开始，通过current指针定位到目标位置2 从堆空间申请新的Node节点3 执行操作：	node->value = e;	node->next = current->next;	current->next = node;

在单链表中目标位置删除数据元素：

1 从头节点开始，通过current指针定位到目标位置2 使用toDel指针指向需要删除的节点3 执行操作： toDel = current->next;current->next = toDel->next;delete toDel;

小结：

1 链表中的数据元素在物理内存中无相邻关系2 链表中的节点都包含数据域和指针域3 头结点用于辅助数据元素的定位，方便插入和删除操作4 插入和删除操作需要保证链表的完整性

======================================================================================

22课 单链表的具体实现

目标：

1 完成链式存储结构线性表（链表）的实现

LinkList设计要点

1 类模板，通过头结点访问后继结点2 定义内部结点类型Node,用于描述数据域和指针域3 实现线性表的关键操作（增、删、查等操作）

LinkList定义：

template
   
    class LinkList : public List
    
     {protected:	struct Node : public Object
     
      	{			T value; //数据域			Node* next; //指针域	}	Node m_header; //头结点	int m_length; //链表长度public:	LinkList();	...}
     
    
   

例1：单链表实现

#ifndef LINKLIST_H#define LINKLIST_H#include "List.h"#include "object.h"#include "exception.h"namespace DTLib{template
   
    class LinkList : public List
    
     {protected:    struct Node : public Object    {        T value;        Node* next;    };    mutable Node m_header;    int m_length;public:    LinkList()    {        m_header.next = NULL;        m_length = 0;    }    bool insert(int i,const T& e)    {        bool ret = ((0 <= i) && (i <= m_length));        if(ret)        {            Node* node = new Node();            if(node != NULL)            {                Node* current = &m_header;                for(int p = 0; p < i; p ++)                {                    current = current->next;                }                node->value = e;                node->next = current->next;                current->next = node;                m_length++;            }            else            {                THROW_EXCEPTION(NoEnoughMemoryException,"No enough memory to insert element ...");            }            return ret;        }    }    bool remove(int i)    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = &m_header;            for(int p =0; p < i; p ++)            {                current = current->next;            }            Node* todel = current->next;            current->next = todel->next;            delete todel;            m_length--;        }        return ret;    }    bool set(int i, const T& e)    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = &m_header;            for(int p = 0; p < i; i ++)            {                current = current->next;            }            current->next->value = e;        }        return ret;    }    bool get(int i, T& e) const    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = &m_header;            for(int p = 0; p < i; p ++)            {                current = current->next;            }            e = current->next->value;        }        return ret;    }    int length() const    {        return m_length;    }    void clear()    {        while(m_header.next)        {            Node* todel = m_header.next;            m_header.next = todel->next;            delete todel;        }        m_length = 0;    }    ~LinkList()    {        clear();    }};}#endif // LINKLIST_H
    
   

测试程序1：

#include 
   
    #include "Exception.h"#include "object.h"#include "SmartPointer.h"#include "List.h"#include "SeqList.h"#include "StaticList.h"#include "DynamicList.h"#include "StaticArray.h"#include "LinkList.h"using namespace std;using namespace DTLib;class test{    public:    test()    {        throw 0;    }};int main(){    LinkList
    
      list;    cout<<"mahaoran"<
    
   

运行报错说明： 程序运行结果并没有打印 “mahaoran” 而是报错 为什么？？？？

因为在创建链表对象的时候

第一步 ：创建LinkList对象，首先构造成员对象 mutable Node m_header;//头结点对象第二步 ：构造头结点对象的时候又会构造 Node类的成员变量 T value ！！！！！！第三步 ：构建 T value 的时候调用 test 类的构造函数 抛出异常

所以结论看似并非是我们库的问题，而是test类的问题（第三方用户）。但是在使用DTLib库的时候 第三方用户并没有创建自己的对象，LinkList list; 创建的依然是单链表对象。本质原因是使用DTLib这个库的程序员所编写的代码有问题导致的。但是作为设计者，为了DTLib库更好的稳定兼容性。就本问题而言就要想方设法的使得 我们在构造头结点的时候不去调用泛指类型的构造函数。

解决思路在于我们在构造头结点的时候避免去掉用泛指类型的构造函数。我们在LinkList类中定义新的类型，匿名类型，即没有类型名的类型

//该类型没有具体的名字，该类型的定义仅仅是为了头结点mutable struct {	char reserved[sizeof(T)];	Node* next;}m_header;

例2：单链表头结点优化 ：用匿名类型实现头结点，避免在构造单链表对象的时候调用泛指类型构造函数。

#ifndef LINKLIST_H#define LINKLIST_H#include "List.h"#include "object.h"#include "exception.h"namespace DTLib{template 
   
    class LinkList : public List
    
     {protected:    struct Node : public Object    {        T value;        Node* next;    };   //mutable Node m_header;    mutable struct : public Object    {        char reserved[sizeof(T)];        Node* next;    }m_header;    int m_length;public:    LinkList()    {        m_header.next = NULL;        m_length = 0;    }    bool insert(int i,const T& e)    {        bool ret = ((0 <= i) && (i <= m_length));        if(ret)        {            Node* node = new Node();            if(node != NULL)            {                Node* current = reinterpret_cast
     
      (&m_header);                for(int p = 0; p < i; p ++)                {                    current = current->next;                }                node->value = e;                node->next = current->next;                current->next = node;                m_length++;            }            else            {                THROW_EXCEPTION(NoEnoughMemoryException,"No enough memory to insert element ...");            }            return ret;        }    }    bool remove(int i)    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = reinterpret_cast
      
       (&m_header);            for(int p =0; p < i; p ++)            {                current = current->next;            }            Node* todel = current->next;            current->next = todel->next;            delete todel;            m_length--;        }        return ret;    }    bool set(int i, const T& e)    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = reinterpret_cast
       
        (&m_header);            for(int p = 0; p < i; i ++)            {                current = current->next;            }            current->next->value = e;        }        return ret;    }    bool get(int i, T& e) const    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = reinterpret_cast
        
         (&m_header); for(int p = 0; p < i; p ++) { current = current->next; } e = current->next->value; } return ret; } int length() const { return m_length; } void clear() { while(m_header.next) { Node* todel = m_header.next; m_header.next = todel->next; delete todel; } m_length = 0; } ~LinkList() { clear(); }};}#endif // LINKLIST_H
        
       
      
     
    
   

结果OK

代码中，在插入，删除，设置，获取的时候都有定位数据元素的操作，所以可以将“定位数据元素”的操作抽象出来

例3：代码整体优化：将插入，删除，设置，获取中的定位数据元素的操作抽象出来

#ifndef LINKLIST_H#define LINKLIST_H#include "List.h"#include "object.h"#include "exception.h"namespace DTLib{template 
   
    class LinkList : public List
    
     {protected:    struct Node : public Object    {        T value;        Node* next;    };   //mutable Node m_header;    mutable struct : public Object    {        char reserved[sizeof(T)];        Node* next;    }m_header;    int m_length;    Node* position(int i) const//被const成员函数调用    {         Node* ret = reinterpret_cast
     
      (&m_header);         if(ret)         {             for(int p=0; p
      
       next;             }         }         return ret;    }public:    LinkList()    {        m_header.next = NULL;        m_length = 0;    }    bool insert(int i,const T& e)    {        bool ret = ((0 <= i) && (i <= m_length));        if(ret)        {            Node* node = new Node();            if(node != NULL)            {                Node* current = position(i);                for(int p = 0; p < i; p ++)                {                    current = current->next;                }                node->value = e;                node->next = current->next;                current->next = node;                m_length++;            }            else            {                THROW_EXCEPTION(NoEnoughMemoryException,"No enough memory to insert element ...");            }            return ret;        }    }    bool remove(int i)    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = position(i);            for(int p =0; p < i; p ++)            {                current = current->next;            }            Node* todel = current->next;            current->next = todel->next;            delete todel;            m_length--;        }        return ret;    }    bool set(int i, const T& e)    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = position(i);            for(int p = 0; p < i; i ++)            {                current = current->next;            }            current->next->value = e;        }        return ret;    }    bool get(int i, T& e) const    {        bool ret = ((0 <= i)&&(i <= m_length));        if(ret)        {            Node* current = position(i);            for(int p = 0; p < i; p ++)            {                current = current->next;            }            e = current->next->value;        }        return ret;    }    int length() const    {        return m_length;    }    void clear()    {        while(m_header.next)        {            Node* todel = m_header.next;            m_header.next = todel->next;            delete todel;        }        m_length = 0;    }    ~LinkList()    {        clear();    }};}#endif // LINKLIST_H
      
     
    
   

测试程序：

#include 
   
    #include "Exception.h"#include "object.h"#include "SmartPointer.h"#include "List.h"#include "SeqList.h"#include "StaticList.h"#include "DynamicList.h"#include "StaticArray.h"#include "LinkList.h"using namespace std;using namespace DTLib;class test{    public:    test()    {        throw 0;    }};int main(){    LinkList
    
      list;    test t;//bug     cout<<"mahaoran"<
    
   

小结：

1 通过类模板实现链表，包含头结点成员和长度信息2 定义结点类型，并通过堆空间中的结点对象构成链式存储3 为了避免构造错误的隐患，头结点类型需要重新定义4 代码优化是编码完成必不可少的环节

====================================================================================

23课 顺序表和单链表的对比分析

分析：截止到目前我们已经拥有了线性表的两种不同的实现，第一种是顺序表，第二种是单链表，那么问题来了，如果在实际工程开发的时候，需要使用线性表的时候，那么究竟是使用顺序表呢？还是使用单链表呢？

问题：如何判断某个数据元素是否存在于线性表

答案：通常的做法是遍历整个线性表，逐一进行比对

说明：在实际的工程中我们经常会判断一个线性表中是否存在一个指定的数据元素，通常的做法是用一个for循环进行遍历解决问题。所以我们会经常写这个for循环，那么我们既可以将这个查找元素是否存在的操作抽象出来

遗失的操作 - find

可以为线性表(List)增加一个查找操作：int find(const T& e) const参数：待查找的数据元素返回值： 返回0 表示数据元素在线性表中第一次出现的位置	返回-1 表示数据元素不存在

在List中添加：

virtual int find(const T* e) const

在SeqList中添加：

int find(const T& e) const	{		int ret = -1;		for(int i=0; i

在LinkList中添加：

int find(const T& e)const   {       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;   }

例1：添加find函数后的LinkList类

#ifndef LINKLIST_H#define LINKLIST_H#include "List.h"#include "object.h"#include "exception.h"namespace DTLib{template 
   
    class LinkList : public List
    
     {protected:   struct Node : public Object   {       T value;       Node* next;   };   // mutable Node m_header;   // 构造头结点时候避免调用泛指类型的构造函数,另外希望创建一个匿名的类，在内存布局上和Node是一样的。   //需要注意的是，该匿名类也要和Node一样，继承自public Object，否则会导致内存布局上面的不同。   mutable struct : public Object   {       char reserved[sizeof(T)];       Node* next;   }m_header;   int m_length;   Node* position(int i) const   {        Node* ret = reinterpret_cast
     
      (&m_header);        if(ret)        {            for(int p=0; p
      
       next;            }        }        return ret;   }public:   LinkList()   {       m_header.next = NULL;       m_length = 0;   }   bool insert(const T& e)   {       return insert(m_length, e);   }   bool insert(int i, const T& e)   {       bool ret = ((0 <= i)&&(i <= m_length));       if(ret)       {           Node* node = new Node();           if(node != NULL)           {               Node* current = position(i);               node->value = e;               node->next = current->next;               current->next = node;               m_length++;           }           else           {               THROW_EXCEPTION(NoEnoughMemoryException,"No enough memory to insert element ...");           }       }       return ret;   }   bool remove(int i)   {       bool ret = ((0<=i)&&(i<=m_length));       if(ret)       {           Node* current = position(i);           Node* todel = current->next;           current->next = todel->next;           delete todel;           m_length--;       }       return ret;   }   bool set(int i, const T& e)   {       bool ret = ((0<=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   {       bool ret = ((0<=i)&&(i<=m_length));       if(ret)       {           e = position(i)->next->value;       }       return ret;   }   int find(const T& e)const   {       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   {       return m_length;   }   virtual void clear()   {       while(m_header.next)       {           Node* todel = m_header.next;           m_header.next = todel->next;           delete todel;       }       m_length = 0;   }    ~LinkList()    {        clear();    }};}#endif // LINKLIST_H
      
     
    
   

测试程序

#include 
   
    #include "Exception.h"#include "object.h"#include "SmartPointer.h"#include "List.h"#include "SeqList.h"#include "StaticList.h"#include "DynamicList.h"#include "StaticArray.h"#include "LinkList.h"using namespace std;using namespace DTLib;class Test{public :    int i;    Test(int v = 0)    {        i = v;    }};int main(){    Test t1(1);    Test t2(2);    Test t3(3);    LinkList
    
      List;}
    
   

报错说明：

此时会报错：提示LinkList类中的find 函数…\DTLib\LinkList.h:132: 错误:no match for ‘operator==’ in ‘node->DTLib::LinkList::Node::value == e’ 因为此时 编译的时候 find 函数在比较 两个Test 对象，而非普通数值，但是此时 没有重载 == 操作符。所以我们添加了 find() 之后就出现了一个问题，如果我们的单链表对象所保存的数据元素是类对象，就会报错 没有重载 == 操作符。

解决方案：在顶层父类 Object中添加 重载 == 操作符

bool operator == (const Object& Obj);bool operator != (const Object& Obj);在 Object.cpp 中实现bool Object :: operator ==(const Object& obj){    return (this == &obj);}bool Object :: operator !=(const Object& obj){    return (this != &obj);}

说明：在创建链表类对象的时候，如果模板参数T类型为 int、char等基本数据类型，则不会报错，因为此时LinkList类中的find函数中的的 == 符号运用合理，比较的是常规数据类型。但是如果T类型是自定义类型，那么编译 LinkList类中的find函数的时候， == 比较符就会报错，C++原生库不支持类对象比较。所以在Object顶层父类中添加==重载函数，并且将自定义类设置成Object类顶层父类的子类就可以避免编译报错。但是这样也只是避免了编译报错，却不能达到自定义类对象的比较预期效果。因为Object顶层父类中定义的 == != 比较操作符重载是根据地质进行比较的。而我们的链表操作 在添加Node结点的时候并非是将初始数据的地址拷贝的链表结点的对应位置，而是先申请的结点空间，再将目标初始数据赋值给Node结点中的Value参数。所以Node结点中的Value 和 初始数据的地址是不同的，用Object类中的操作符重载比较无效。所以自定义类需要自己重新定义 == !=操作符，根据值比较。如下：

class Test : public Object{    int i;public:    Test(int v = 0)    {        i = v;    }    bool operator ==(const Test& obj)    {        return ( i == obj.i);    }};

测试程序：

#include 
   
    #include "Exception.h"#include "object.h"#include "SmartPointer.h"#include "List.h"#include "SeqList.h"#include "StaticList.h"#include "DynamicList.h"#include "StaticArray.h"#include "LinkList.h"using namespace std;using namespace DTLib;class Test //: public Object{public :    int i;    Test(int v = 0)    {        i = v;    }    bool operator ==(const Test& obj)    {        return ( i == obj.i);    }};int main(){    Test t1(1);    Test t2(2);    Test t3(3);    LinkList
    
      List;    List.insert(t1);    List.insert(t2);    List.insert(t3);    cout << List.find(t2) <
    
   

至此我们完成了查找功能的添加，然后在分析单链表的时间复杂度后发现：顺序表的整体时间复杂度比单链表要低，那么单链表还有使用价值吗？

分析：

效率的深度分析：

1 插入和删除操作1.1 顺序表：涉及到大量的数据对象的复制操作1.2 单链表：只涉及到指针操作，效率与数据对象无关2 数据访问：2.1 顺序表：随机访问，可以直接定数据对象2.2 单链表：顺序访问，必须从头访问数据对象，无法直接定位

工程开发中的选择：

顺序表：1 数据元素的类型相对简单，不涉及深拷贝2 数据元相对稳定，访问操作远多于插入和删除操作单链表：1 数据元素的类型相对复杂，复制操作相对耗时2 数据元素不稳定，需要经常插入和删除，访问操作少。

小结：

1 线性表中的元素的查找以来与相等比较操作符 ==2 顺序表适用于访问需求量较大的场合（随机访问）3 单链表适用于数据元素频繁插入删除的场合（顺序访问，插入 和删除是只操作指针不涉及数据拷贝）4 当数据类型相对简单的时，顺序表和单链表的效率不相上下