C++链表（single-linked list）

桃扇骨 2022-07-31 05:31 26阅读 0赞

单向链表（single-linked list）

直接代码

//IntSLList.h
    #ifndef INTSLLIST_H
    #define INTSLLIST_H
    
    class IntSLLNode
    {
    public:
    	IntSLLNode()
    	{
    		data = 0;
    		next = 0;
    	}
    
    	IntSLLNode(int el, IntSLLNode* ptr = 0)
    	{
    		data = el;
    		next = ptr;
    	}
    
    	int data;
    	IntSLLNode* next;
    };
    
    class IntSLList
    {
    public:
    	IntSLList();
    	~IntSLList();
    	
    	bool IsEmpty();
    	void AddToHead(int el);
    	void AddToTail(int el);
    	void DeleteFromHead();
    	void DeleteFromTail();
    	void DeleteNode(int el);
    	bool IsInList(int el);	
    
    	void ReverseList();	//反转链表
    
    	IntSLLNode* GetListHead();	//获取链表头节点
    
    private:
    	IntSLLNode* head;
    	IntSLLNode* tail;
    };
    
    #endif // !INTSLLIST_H

//IntSLList.cpp
    #include "IntSLList.h"
    #include <iostream>
    using namespace std;
    
    IntSLList::IntSLList()
    {
    
    }
    
    IntSLList::~IntSLList()
    {
    
    }
    
    bool IntSLList::IsEmpty()
    {
    	return head == NULL;
    }
    
    void IntSLList::AddToHead(int el)
    {
    	head = new IntSLLNode(el, head);
    	if (tail == 0)
    	{
    		tail = head;
    	}
    }
    
    void IntSLList::AddToTail(int el)
    {
    	if (tail == NULL)
    	{
    		head = tail = new IntSLLNode(el);
    	}
    	else
    	{
    		tail->next = new IntSLLNode(el);
    		tail = tail->next;
    	}
    }
    
    void IntSLList::DeleteFromHead()
    {
    	if (head != NULL)
    	{
    		IntSLLNode* ptemp = head;
    		head = head->next;
    		delete ptemp;
    		ptemp = NULL;
    	}
    }
    
    void IntSLList::DeleteFromTail()
    {
    	if (tail != NULL)
    	{
    		if (head == tail)
    		{
    			delete tail;
    			head = tail = NULL;
    		}
    		else
    		{
    			IntSLLNode* ptemp = head;
    			while (ptemp->next != tail)
    			{
    				ptemp = ptemp->next;
    			}
    
    			delete tail;
    			tail = ptemp;
    			tail->next = NULL;
    		}
    	}
    }
    
    void IntSLList::DeleteNode(int el)
    {
    	if (head != NULL)
    	{
    		if (head == tail && head->data == el)
    		{
    			delete head;
    			head = tail = NULL;
    		}
    		else if (head->data == el)
    		{
    			IntSLLNode* ptemp = head;
    			head = head->next;
    			delete ptemp;
    			ptemp = NULL;
    		}
    		else if (head->next != NULL)
    		{
     			IntSLLNode* pFront = head;
     			IntSLLNode* pBehind = head->next;
    			while (pBehind != 0)
    			{
    				if (pBehind->data == el)
    				{
    					pFront->next = pBehind->next;
    					if (pBehind == tail)
    						tail = pFront;
    
    					delete pBehind;
    					pBehind = NULL;
    					break;
    				}
    
    				pFront = pBehind;
    				pBehind = pBehind->next;
    			}
    		}
    	}
    }
    
    bool IntSLList::IsInList(int el)
    {
    	IntSLLNode* ptemp = head;
    	while (ptemp != NULL)
    	{
    		if (ptemp->data == el)
    			return true;
    
    		ptemp = ptemp->next;
    	}
    
    	return false;
    }
    
    void IntSLList::ReverseList()
    {
    	if (head != tail)
    	{
    		IntSLLNode* p1 = head;
    		IntSLLNode* p2 = head->next;
    		IntSLLNode* p3 = NULL;
    		p1->next = NULL;
    		while (p2 != NULL)
    		{
    			p3 = p2->next;
    			p2->next = p1;
    			p1 = p2;
    			p2 = p3;
    		}
    
    		swap(head, tail);
    
    	}
    }
    
    IntSLLNode* IntSLList::GetListHead()
    {
    	return head;
    }

//MainProcess.cpp
    #include "IntSLList.h"
    #include <iostream>
    using namespace std;
    
    void Print(IntSLLNode* phead)
    {
    	while (phead != NULL)
    	{
    		cout << phead->data << " ";
    		phead = phead->next;
    	}
    	cout << endl;
    }
    
    
    int main()
    {
    	IntSLList listt;
    	listt.AddToTail(1);
     	listt.AddToTail(2);
    	listt.AddToTail(3);
    	listt.AddToTail(4);
    
    	IntSLLNode* phead = listt.GetListHead();
    	Print(phead);
    
    	listt.ReverseList();
    	phead = listt.GetListHead();
    	Print(phead);
    
    	cout << endl;
    	return 0;
    }