现在的位置: 首页 > 综合 > 正文

C++ 学习练手 – 双向链表的模板实现

2018年04月06日 ⁄ 综合 ⁄ 共 5338字 ⁄ 字号 评论关闭
 

#ifndef __LINKEDLISTPRACTICE__H__
#define __LINKEDLISTPRACTICE__H__ 1
namespace FengChen
{
    
// template for double link list
    template <class Type> class LinkedList;

    template 
<class T>
    std::ostream
& operator<<(std::ostream& os, const LinkedList<T>& L)
    
{
        os 
<< "";
        ListNode
<T> *p;
        
if(L.Size() < 1) os << "Empty!";

        
for (p = L.m_Head->next ; p != 0; p = p->next)
            os 
<< p->item << " ";
        os 
<<">";
        
return os;
    }


    template 
<class Type> class ListNode {
        friend 
class LinkedList<Type>;
        
// needs access to item and next
        friend std::ostream& operator<< <Type>(std::ostream&const LinkedList<Type>&);

        ListNode():next(
0), previous(0{}

        
// private class: no public section
        ListNode(const Type &t): item(t), next(0), previous(0){}
        Type item;
        ListNode 
*next;
        ListNode 
*previous;
    }
;

    template 
<class Type> class LinkedList{
        friend std::ostream
&
        
operator<< <Type>(std::ostream&const LinkedList<Type>&);
        
        
public:
        
        LinkedList():m_Head(
new ListNode<Type>), m_Tail(m_Head),m_size(0){}
        
        LinkedList(
const LinkedList &List): m_Head(new ListNode<Type>), m_Tail(m_Head), m_size(0)
            
{copy_elems(List);}
        
        LinkedList(
const Type* start, int Size): m_Head(new ListNode<Type>), m_Tail(m_Head), m_size(0)
        
{
            copy_elems (start,Size);
        }


        
void Assign(const Type* start, int Size)
        
{
            
this->MakeEmpty();
            copy_elems (start, Size);
        }


        
void MakeEmpty()
        
{
            ListNode
<Type>* node = m_Head->next;
            ListNode
<Type>* temp = 0;

            m_Head
->next = 0;

            
while( node != 0 )
            
{
                temp 
= node->next;
                delete node;
                node 
= temp;
            }

            m_Tail 
= m_Head;
            m_size 
= 0;
        }

        inline 
bool IsEmpty() const return m_size != 0; }
        inline 
int IsLast(ListNode<Type>* p)return IsEmpty() && p == m_Tail; }

        ListNode
<Type>* Find(const Type& X)
        
{
            ListNode
<Type>* node = m_Head->next;
            
while (node != 0 && node->item != X)
                node
= node->next;
            
return node;
        }


        ListNode
<Type>* FindLast (const Type& X)
        
{
            ListNode
<Type>* node = m_Tail;
            
while(node != m_Head && node->item != X )
                node 
= node->previous;
        }

        
void Delete(Type X)
        
{
            ListNode
<Type>* node = Find(X);
            
if(node != 0)
            
{
                node
->previous->next = node->next;
                node
->next->previous = node->previous;

                
if(node == m_Tail) m_Tail = node->previous;

                delete node;
            }

            m_size
--;
        }


        
void Push(Type X)
        
{
            Insert(X, m_Tail);
        }


        
void Insert(Type X, ListNode<Type>* p)
        
{
            ListNode
<Type>* node = new ListNode<Type>(X);
            
if(node == 0throw std::runtime_error("Out of space!");
            
            node
->next = p->next;
            node
->previous = p;

            
if(p->next != 0)
                p
->next->previous = p;
            
else
                m_Tail 
= node;

            p
->next = node;
            

            m_size
++;
        }

        Type Value(ListNode
<Type>* p)
        
return p->item;}
        
        ListNode
<Type>* Previous(ListNode<Type>* p)
        
return p->previous; }
        
        ListNode
<Type>* Next(ListNode<Type>* p)
        
return p->next; }
        
        Type
& Front()
        
{
            
if(m_size == 0throw std::runtime_error("Empty List!"); 
            
return m_Head->next->item;
        }

        Type
& Tail()
        
{
            
if(m_size == m_Head) throw std::runtime_error("Empty List!"); 
            
return m_Tail->item;
        }


        
void Inverse()
        
{
            
if(m_size < 1return;

            ListNode
<Type>* pFirst = m_Head->next;  // First element
            while(m_Tail != pFirst)
            
{
                ListNode
<Type>* node = m_Tail;
                m_Tail 
= node->previous;
                m_Tail
->next = 0;

                node
->previous = pFirst->previous;
                node
->next = pFirst;

                pFirst
->previous->next = node;
                pFirst
->previous = node;
            }

        }


        
int Size() const
        
return m_size; }

        LinkedList
<Type>& operator=(const LinkedList& rhs)
        
{ copy_elems (rhs); }

        
~LinkedList<Type>()
        
{
            MakeEmpty ();
            delete m_Head;
            m_Head 
= 0;
        }

            
        
private:
        ListNode
<Type> *m_Head;
        ListNode
<Type> *m_Tail;
        
int m_size;

        
void copy_elems(const Type* start, int Size)
        
{
            assert(Size 
>= 0);
            
int idx = 0;
            
while(idx < Size) Push (start[idx++]);
        }

        
        
void copy_elems(const LinkedList& List)
        
{
            MakeEmpty ();
            
if(List.Size () == 0 ) return;

            ListNode
<Type>* src = List.m_Head->next;
            
while(src != 0)
            
{
                
this->Push(src->item);
                src 
= src->next;
            }

        }

    }
;
}

#endif

抱歉!评论已关闭.