数据结构C++（8）字典——链表实现（linkDictionary）-白红宇

数据结构C++（8）字典——链表实现（linkDictionary）

阅读量：6921 次

发布时间：2019-06-27

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

异常类同。

节点类型 pairNode 定义在 pairNode.h 中：

1 #pragma once 2  3  4 template
     
       5 struct pairNode 6 { 7     std::pair
      
        element; 8     pairNode
       
         *next; 9 10     pairNode(const std::pair
        
         & thePair) :element(thePair) {}        //element 委托构造函数11     pairNode(const std::pair
         
          & thePair, pairNode
          
           * theNext) :element(thePair)12 {13 next = theNext;14 }15 };

字典的抽象基类 dictionary 定义在 dictionary.h 中：

1 #pragma once 2  3 template
     
       4 class dictionary 5 { 6 public: 7     virtual ~dictionary() {}; 8     virtual bool empty() const = 0; 9     virtual int size() const = 0;10     virtual std::pair
      
       * find(const K &theKey) const = 0;    //查找键为key的数对11     virtual void erase(const K &theKey) = 0;12     virtual void insert(const std::pair
       
        & thePair) = 0;13 };

类 linkDictionary 的定义在 linkDictionary.h 中：

1 #pragma once  2 #include 
     
        3 #include 
      
         4 #include "pairNode.h"  5 #include "dictionary.h"  6 #include "myExceptions.h"  7   8   9 template
       
         10 class linkDictionary : public dictionary
        
          11 { 12 public: 13     linkDictionary() { headerNode = nullptr; dictionarySize = 0; } 14     ~linkDictionary(); 15     bool empty() const; 16     int size() const; 17     std::pair
         
          * find(const K &theKey) const;    //查找键为key的数对 18     void erase(const K &theKey); 19     void insert(const std::pair
          
           & thePair); 20 21 void output(std::ostream &out); 22 protected: 23 pairNode
           
             *headerNode; 24 int dictionarySize; 25 }; 26 27 template
            
              28 linkDictionary
             
              ::~linkDictionary() 29 { 30 pairNode
              
                *Del = headerNode; 31 while (Del != nullptr) 32 { 33 headerNode = Del->next; 34 delete Del; 35 Del = headerNode; 36 } 37 } 38 39 template
               
                 40 bool linkDictionary
                
                 ::empty() const 41 { 42 return dictionarySize == 0; 43 } 44 45 template
                 
                   46 int linkDictionary
                  
                   ::size() const 47 { 48 return dictionarySize; 49 } 50 51 template
                   
                     52 std::pair
                    
                     * linkDictionary
                     
                      ::find(const K &theKey) const //查找键为key的数对 53 { 54 pairNode
                      
                        *Tmp = headerNode; 55 while ((Tmp != nullptr) && (Tmp->element.first != theKey)) 56 Tmp = Tmp->next; 57 if ((Tmp != nullptr) && (Tmp->element.first == theKey)) 58 return &Tmp->element; 59 60 return nullptr; 61 } 62 63 template
                       
                         64 void linkDictionary
                        
                         ::erase(const K &theKey) 65 { 66 pairNode
                         
                           *Tmp = nullptr; 67 pairNode
                          
                            *Del = headerNode; 68 while ((Del != nullptr) && (Del->element.first < theKey)) 69 { 70 Tmp = Del; 71 Del = Del->next; 72 } 73 74 if ((Del == nullptr) || (Del->element.first != theKey)) //要删除的数对不存在 75 { 76 std::ostringstream s; 77 s << "theKey = " << theKey << "inexistence"; 78 throw keyInexistence(s.str()); 79 } 80 if (Tmp == nullptr) //要删除的数对是首节点 81 headerNode = Del->next; 82 else 83 Tmp->next = Del->next; 84 85 delete Del; 86 dictionarySize--; 87 } 88 89 template
                           
                             90 void linkDictionary
                            
                             ::insert(const std::pair
                             
                              & thePair) 91 { 92 pairNode
                              
                                *Tmp = nullptr; 93 pairNode
                               
                                 *New = headerNode; 94 while ((New != nullptr) && (New->element.first < thePair.first)) 95 { 96 Tmp = New; 97 New = New->next; 98 } 99 if ((New != nullptr) && (New->element.first == thePair.first)) //键为key的数对存在，修改值100 New->element.second = thePair.second;101 else //不存在，创建新节点，插入102 {103 pairNode
                                
                                  *newNode = new pairNode
                                 
                                  (thePair, New);104 if (Tmp == nullptr) //要插入到首节点105 headerNode = newNode;106 else107 Tmp->next = newNode;108 }109 dictionarySize++;110 }111 112 template
                                  
                                   113 void linkDictionary
                                   
                                    ::output(std::ostream &out)114 {115 out << "Key ->" << " value" << std::endl;116 pairNode
                                    
                                      *Tmp = headerNode;117 while (Tmp != nullptr)118 {119 out << Tmp->element.first << " " << Tmp->element.second << std::endl;120 Tmp = Tmp->next;121 }122 }123 124 template
                                     
                                      125 std::ostream &operator<<(std::ostream &out, linkDictionary
                                      
                                        &cLinkDictionary)126 {127 cLinkDictionary.output(out);128 return out;129 }