算法导论单链表-白红宇

算法导论单链表

阅读量：4088 次

发布时间：2019-05-25

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

单链表

1. 单链表是什么？

单链表是一种常见的简单数据结构，链表由很多个结点组成，每个结点有储存数据的数据域和指向下一个结点的地址。因为每个结点都有下一个结点的地址，因此通过当前结点可以找到下一个结点，将各种数据就像链子一样连接起来。相比于数组，链表的优点就是大小可以改变，删除和插入数据也不必作太大的改动，缺点是不可以随机访问（必须通过一个结点访问下一个结点来访问你想访问的结点）。

2. 单链表的实现（C++）

//SinglyLink.h#pragma once#include 
   
    #include 
    
     template
     
      class Node{public:    Node(Node
      
       * pNext = NULL, ElemType* pData = NULL);    ElemType const& GetData() const;    void SetData(ElemType val) ;    Node
       
        * const& GetNext() const;    void SetNext(Node
        
         * val);private: ElemType* m_pData; Node
         
          * m_pNext;};template
          
           class SinglyLinkList{public: SinglyLinkList(); unsigned int const& GetLength() const; bool Insert(ElemType elem, unsigned int pos); bool Delete(unsigned int pos, ElemType* elem); bool Search(unsigned int pos, ElemType* elem) const; bool Visit(ElemType* elem, const unsigned int& pos) const; bool Empty();private: Node
           
            * m_pHeadNode; unsigned int m_length;};//————————————————————————————————//Node类的实现template
            
             Node
             
              ::Node(Node
              
               * pNext /*= NULL*/, ElemType* pData /*= NULL*/) :m_pNext(pNext),m_pData(pData){}template
               
                void Node
                
                 ::SetNext(Node
                 
                  * val){ m_pNext = val;}template
                  
                   Node
                   
                    * const& Node
                    
                     ::GetNext() const{ return m_pNext;}template
                     
                      void Node
                      
                       ::SetData(ElemType val){ m_pData = val;}template
                       
                        ElemType const& Node
                        
                         ::GetData() const{ return *m_pData;}//————————————————————————————————//SinglyLink类实现template
                         
                          SinglyLinkList
                          
                           ::SinglyLinkList() :m_pHeadNode(new Node
                           
                            ()),m_length(0){}template
                            
                             bool SinglyLinkList
                             
                              ::Insert(ElemType elem, unsigned int pos){ if (pos > GetLength() || pos < 0) { assert(false && "Error: SinglyLink's insert pos is out of range!\n"); return false; } for(Node
                              
                               * pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node
                               
                                * insertNode = new Node
                                
                                 (pCurrentNode->GetNext(),new ElemType(elem)); pCurrentNode->SetNext(insertNode); ++m_length; return true; } } assert(false && "Error: SinglyLink Insert failed for unknow reason!"); return false;}template
                                 
                                  bool SinglyLinkList
                                  
                                   ::Delete(unsigned int pos, ElemType* elem){ if (pos >= GetLength() || pos < 0) { assert(false && "Error: SinglyLink's delete pos is out of range!\n"); } for(Node
                                   
                                    * pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node
                                    
                                     * deleteNode = pCurrentNode->GetNext(); pCurrentNode->SetNext(deleteNode->GetNext()); *elem = deleteNode->GetData(); delete deleteNode; --m_length; return true; } } assert(false && "Error: SinglyLink pos delete failed for unknow reason!"); return false;}template
                                     
                                      unsigned int const& SinglyLinkList
                                      
                                       ::GetLength() const{ return m_length;}template
                                       
                                        bool SinglyLinkList
                                        
                                         ::Search(unsigned int pos, ElemType* elem) const{ if (pos >= GetLength() || pos < 0) { assert(false && "Error: SinglyLink's search pos is out of range!\n"); } for(Node
                                         
                                          * pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0 && (pCurrentNode->GetNext() != NULL) ) { *elem = pCurrentNode->GetNext()->GetData(); return true; } } return false;}template
                                          
                                           bool SinglyLinkList
                                           
                                            ::Visit(ElemType* elem, const unsigned int& pos) const{ if (pos >= GetLength() || pos < 0) { return false; } return Search(pos,elem);}template
                                            
                                             bool SinglyLinkList
                                             
                                              ::Empty(){ return !m_length;}

//Util.h#pragma oncenamespace Util{    template
   
        void PrintMemory(const T& dateStruct, unsigned int size)    {        cout << "PrintMemory: ";        for (int i = 0; i != size; i++)        {            ElemType tempElem;            if (!dateStruct.Visit(&tempElem,i))            {                printf("\n");                return;            }            printf("%d ",tempElem);        }        printf("\n");    }}

//main.cpp#include "Util.h"#include "SinglyLinkList.h"#include 
   
    using namespace std;typedef int ElemType;int main(){    SinglyLinkList
    
      testSinglyLinkList;    cout << "testSinglyLinkList is " << (testSinglyLinkList.Empty() ? "Empty." : "Not Empty.") << endl;    Util::PrintMemory(testSinglyLinkList,testSinglyLinkList.GetLength());    for (int i = 0; i != 5; i++)    {        testSinglyLinkList.Insert(i+1,i);        cout << "\nInsert:" << i+1 << endl;        cout << "testSinglyLinkList is " << (testSinglyLinkList.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testSinglyLinkList,testSinglyLinkList.GetLength());    }    for (int i = 0; i != 2; i++)    {        ElemType tempElem;        testSinglyLinkList.Delete(i,&tempElem);        cout << "\nDelete:" << tempElem << endl;        cout << "testSinglyLinkList is " << (testSinglyLinkList.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testSinglyLinkList,testSinglyLinkList.GetLength());    }    return 0;}

3. 程序运行结果

testSinglyLinkList is Empty.
PrintMemory:

Insert:1
testSinglyLinkList is Not Empty.
PrintMemory: 1

Insert:2
testSinglyLinkList is Not Empty.
PrintMemory: 1 2

Insert:3
testSinglyLinkList is Not Empty.
PrintMemory: 1 2 3

Insert:4
testSinglyLinkList is Not Empty.
PrintMemory: 1 2 3 4

Insert:5
testSinglyLinkList is Not Empty.
PrintMemory: 1 2 3 4 5

Delete:1
testSinglyLinkList is Not Empty.
PrintMemory: 2 3 4 5

Delete:3
testSinglyLinkList is Not Empty.
PrintMemory: 2 4 5