单链表类封装实例C++代码实现

落日映苍穹つ 2023-01-04 14:30 141阅读 0赞

**线性表：零个或多个数据元素的有限序列**

**节点类**  
节点包含数据域Data和链接域Next。  
node.hpp

#pragma once
    #ifndef Node_hpp
    #define Node_hpp
    
    
    typedef double value_data;
    class Node
    {
        
    
    public:
    	value_data Data;
    	Node *Next;
    };
    
    #endif /* Node_hpp */

**单链表类**  
single\_Linklist.h

#pragma once
    #include "node.hpp"
    #include <iostream>
    
    
    using namespace std;
    
    class Single_Linklist
    {
        
    public:
    	typedef double value_data;
    
    	Single_Linklist();
    
    	//运算符重载
    	Single_Linklist &operator=(Single_Linklist& s)
    	{
        
    		swap(Head_ptr, s.Head_ptr);
    		swap(Tail_ptr, s.Tail_ptr);
    		return *this;
    	}
    	//Single_Linklist(const value_data &item = value_data(), Node *ptr = NULL);
    	void Clear_List();				//清空链表
    	void Print_List();				//打印链表
    
    	void Create_ListHead(value_data x);			//头插法
    	void Delete_ListHead();						//头删法
    
    	void Create_ListTail(value_data x);			//尾插法
    	void Delete_ListTail();						//尾删法
    
    	Node *Find_List(value_data x);				//指定数值查找
    	void Insert_List(Node* pos,value_data x);			//指定位置插入
    	void Erase_List(Node* pos);							//指定位置删除
    	int List_Length();									//链表长度
    	~Single_Linklist();
    
    
    private:
    	Node *Head_ptr;
    	Node *Tail_ptr;
    };

single\_Linklist.cpp

#include "single_linklist.h"
    #include <iostream>
    #include<assert.h>
    
    
    //构造函数
    Single_Linklist::Single_Linklist()
    {
        
    	Head_ptr = new Node;
    	//Head_ptr->Data = 0;
    	Head_ptr = NULL;
    	Tail_ptr = NULL;
    }
    
    
    /* 清空链表 */
    void Single_Linklist::Clear_List() 
    {
        
    	Node *temp = Head_ptr;
    	while (temp)
    	{
        
    		Node *del = temp;
    		temp = temp->Next;
    		delete del;
    		del = NULL;
    	}
    }
    
    /* 读取打印链表 */
    void Single_Linklist::Print_List()
    {
        
    	Node *cur = Head_ptr;
    	while (cur)
    	{
        
    		cout << cur->Data << "->";
    		cur = cur->Next;
    	}
    	cout << "NULL" << endl;
    }
    
    /*头插 and 头删*/
    void Single_Linklist::Create_ListHead(value_data x)
    {
        
    	Node *temp = Head_ptr;
    	Head_ptr = new Node();
    	Head_ptr->Data = x;
    	Head_ptr->Next = temp;
    }
    
    void Single_Linklist::Delete_ListHead()
    {
        
    	if (NULL == Head_ptr)
    	{
        
    		cout << "空链表" << endl;
    	}
    	else if (NULL == Head_ptr->Next)
    	{
        
    		delete Head_ptr;
    		Head_ptr = NULL;
    	}
    	else
    	{
        
    		Node *temp = Head_ptr->Next;
    		delete Head_ptr;
    		Head_ptr = temp;
    	}
    }
    
    /*尾插 and 尾删*/
    void Single_Linklist::Create_ListTail(value_data x)
    {
        
    	if (NULL == Head_ptr)
    	{
        
    		Head_ptr = new Node();
    		Head_ptr->Data = x;
    		Tail_ptr = Head_ptr;
    
    	}
    		
    	else
    	{
        
    		/*Tail_ptr = Head_ptr ;
    		Tail_ptr->Next = new Node();
    		Tail_ptr->Next->Data = x;
    		Tail_ptr = Tail_ptr->Next ;	
    		*/
    
    		Node *a =new Node();
    		a->Data = x;
    		Tail_ptr->Next =a;
    		Tail_ptr = a;
    	}
    }
    
    void Single_Linklist::Delete_ListTail()
    {
        
    	if (NULL == Head_ptr)
    	{
        
    		cout << "空链表" << endl;
    	}
    	else if (Tail_ptr == Head_ptr)
    	{
        
    		delete Head_ptr;
    		Tail_ptr=Head_ptr = NULL;
    	}
    	else
    	{
        
    		Node *temp = Head_ptr;
    		while (temp->Next->Next)
    		{
        
    			temp = temp->Next;
    		}
    		delete temp->Next;
    		temp->Next = NULL;
    		Tail_ptr = temp;
    	}
    }
    /* 指定数值查找 */
    Node* Single_Linklist::Find_List(value_data x)
    {
        
    	Node* temp = Head_ptr;
    	while (temp)
    	{
        
    		if (x == temp->Data)
    		{
        
    			return temp;
    		}
    		temp = temp->Next;
    	}
    	return NULL;
    }
    
    /* 链表指定位置插入元素 */
    void Single_Linklist::Insert_List(Node* pos, value_data x)
    {
        
    	assert(pos);
    	Node *temp = Head_ptr;
    	while (temp)
    	{
        
    		if (temp->Next == NULL)
    			Single_Linklist::Create_ListHead(x);
    		else if (pos==temp->Next)
    		{
        
    			Node *cur = new Node();
    			cur->Data = x;
    			cur->Next = temp->Next;
    			temp->Next = cur;
    			return;
    		}
    		temp = temp->Next;
    	}
    }
    /* 删除链表指定元素 */
    void Single_Linklist::Erase_List(Node* pos)
    {
        
    	assert(pos);
    	Node *temp = Head_ptr;
    	while (temp)
    	{
        
    		if (temp->Next == NULL)
    			Single_Linklist::Delete_ListHead();
    		else if (pos == temp->Next)
    		{
        
    			Node *cur = temp->Next->Next;
    			delete temp->Next;
    			temp->Next = NULL;
    			temp->Next = cur;
    			return;
    		}
    		temp = temp->Next;
    	}
    }
    
    /* 链表长度 */
    int Single_Linklist::List_Length()
    {
        
    	int sum = 0;
    	Node *temp = Head_ptr;
    	while (temp)
    	{
        
    		Node *cur = temp;
    		temp = temp->Next;
    		sum += 1;
    	}
    	return sum;
    }
    
    //析构函数
    Single_Linklist::~Single_Linklist()
    {
        
    	Clear_List();
    }

**测试函数**

#include "single_linklist.h"
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        
    	//新建链表
    	Single_Linklist a;
    	Single_Linklist b;
    	Single_Linklist d;
    
    	a.Create_ListHead(20.3);
    	a.Create_ListHead(10.3);
    	a.Print_List();			//打印链表
    	a.Delete_ListHead();	//头删
    	a.Print_List();
    
    	b.Create_ListTail(4.3); 
    	b.Create_ListTail(14.3);
    	b.Create_ListTail(66);
    	b.Print_List();	
    	b.Delete_ListTail();		//尾删
    	b.Print_List();
    	Node *c = b.Find_List(14.3);	//查询
    	b.Insert_List(c, 2.3);		//指定位置插入
    	b.Print_List();
    
    	d = b;
    	cout << "a 链表的长度：" << a.List_Length() << endl;
    	cout << "b 链表的长度：" << b.List_Length() << endl;
    	cout << "d 链表的长度：" << d.List_Length() << endl;
    	system("pause");
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NTI4MQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NTI4MQ_size_16_color_FFFFFF_t_70]: /images/20221119/c9fa93334dc749e2afd2110bcb5df179.png