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

以你之姓@ 2023-01-12 10:10 168阅读 0赞

**双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。**

**Double\_Linklist.h**

#pragma once
    #include <iostream>
    
    using namespace std;
    typedef int DataType;
    
    class Double_Node
    {
        
    public:
    	DataType data;
    	Double_Node *next;
    	Double_Node *prev;
    };
    
    
    class Double_Linklist
    {
        
    public:
    	Double_Linklist();
    	~Double_Linklist();
    	int Create_Linklist(int size);	//创建链表
    	void Clear_Linklist();		//清空链表
    	void Print_Linklist();		//遍历链表
    
    	void Insert_Head(DataType x);			//头插法
    	void Insert_Tail(DataType x);			//尾插法
    	void Insert_Centre(DataType x,int n);	//中间插法
    
    	void Delete_Head();					//头删法
    	void Delete_Tail();					//尾删法
    	void Delete_Centre(int n);			//中间删法
    
    	int Linklist_Size();				//链表长度
    
    	Double_Node *phead;
    	int size;
    
    };

**Double\_Linklist.cpp**

#include "Double_Linklist.h"
    #include <iostream>
    
    using namespace std;
    
    Double_Linklist::Double_Linklist()
    {
        
    	phead = new Double_Node;
    	phead->data = 0;
    	phead->prev = NULL;
    	phead->next = NULL;
    	size = 0;
    }
    
    Double_Linklist::~Double_Linklist()
    {
        
    	delete phead;
    }
    
    int Double_Linklist::Create_Linklist(int size) 
    {
        
    	if (size < 0) 
    	{
        
    		cout << "error" << endl;
    		return -1;
    	}
    	else
    	{
        
    		Double_Node *ptemp = NULL;
    		Double_Node *pnew = NULL;
    		this->size = size;
    		ptemp = this->phead;
    
    		for (int i = 0; i<size; i++)
    		{
        
    			pnew = new Double_Node;
    			pnew->next = NULL;
    			pnew->prev = NULL;
    			cout << "输入第" << i + 1 << "个节点值" << endl;
    			cin >> pnew->data;
    			ptemp->next = pnew;
    			pnew->prev = ptemp;
    			ptemp = pnew;
    		}
    		return 0;
    	}
    }
    
    void Double_Linklist::Clear_Linklist()
    {
        
    	Double_Node *ptemp;
    	if (this->phead == NULL)
    	{
        
    		cout << "空链表" << endl;
    	}
    	while (this->phead)
    	{
        
    		ptemp = phead->next;
    		delete ptemp;
    		phead = ptemp;
    	}
    }
    
    void Double_Linklist::Print_Linklist() 
    {
        
    	Double_Node *ptemp = this->phead->next;
    	if (this->phead == NULL) {
        
    		cout << "空链表" << endl;
    	}
    	while (ptemp)
    	{
        
    		cout << ptemp->data << "->";
    		ptemp = ptemp->next;
    	}
    	cout << "NULL" << endl;
    }
    
    void Double_Linklist::Insert_Head(DataType x)
    {
        
    	
    	if (this->phead == NULL) {
        
    		cout << "空链表" << endl;
    	}
    	if (x == NULL) {
        
    		cout << "The insertion node is NULL" << endl;
    	}
    	//头插
    	Double_Node *pnew = new Double_Node;
    	pnew->data = x;
    	pnew->next = this->phead->next;
    	pnew->prev = this->phead;
    	this->phead->next->prev = pnew;
    	this->phead->next = pnew;
    	this->size++;
    }
    
    void Double_Linklist::Insert_Tail(DataType x)
    {
        
    	Double_Node *ptemp;
    	ptemp = this->phead;
    	while (ptemp->next != NULL) {
        
    		ptemp = ptemp->next;
    	}
    	Double_Node *pnew = new Double_Node;
    	pnew->data = x;
    	pnew->next = NULL;
    	pnew->prev = ptemp;
    	ptemp->next = pnew;
    	this->size++;
    }
    
    void Double_Linklist::Insert_Centre(DataType x, int n)
    {
        
    	Double_Node *ptemp;
    	ptemp = this->phead;
    	for (int i = 1; i < n; i++) {
        
    		ptemp = ptemp->next;
    	}
    	Double_Node *pnew = new Double_Node;
    	pnew->data = x;
    	pnew->next = ptemp->next;
    	pnew->prev = ptemp;
    	ptemp->next->prev = pnew;
    	ptemp->next = pnew;
    	this->size++;
    }
    
    void Double_Linklist::Delete_Head() 
    {
        
    	Double_Node *ptemp;
    	ptemp = this->phead->next;
    	this->phead->next = ptemp->next;
    	ptemp->next->prev = this->phead;
    	delete ptemp;
    	this->size--;
    }
    
    void Double_Linklist::Delete_Tail() 
    {
        
    	Double_Node *ptemp;
    	Double_Node *ptemp2;
    	ptemp = this->phead;
    	for (int i = 1; i < this->size; i++) {
        
    		ptemp = ptemp->next;
    	}
    	ptemp2 = ptemp->next;
    	ptemp->next = NULL;
    	delete ptemp2;
    	this->size--;
    }
    
    void Double_Linklist::Delete_Centre(int n) 
    {
        
    	Double_Node *ptemp;
    	Double_Node *ptemp2;
    	ptemp = this->phead;
    	for (int i = 1; i < n; i++) {
        
    		ptemp = ptemp->next;
    	}
    	ptemp2 = ptemp->next;
    	ptemp->next = ptemp2->next;
    	ptemp2->next->prev = ptemp;
    	delete ptemp2;
    	this->size--;
    }
    
    int Double_Linklist::Linklist_Size()
    {
        
    	return this->size;
    }

**main.cpp**

#include "Double_Linklist.h"
    #include <iostream>
    
    
    using namespace std;
    
    int main() 
    {
        
    	Double_Linklist c;
    	cout << "请输入节点个数：" << endl;
    	int t;
    	cin >> t ;
    	c.Create_Linklist(t);
    	c.Print_Linklist();
    	c.Insert_Head(7);	//头插
    	c.Insert_Tail(9);	//尾插
    	c.Insert_Centre(5, 3);	//中间插
    	c.Print_Linklist();		//遍历链表
    
    	int a=c.Linklist_Size();
    	cout << endl;
    	cout << "链表长度：" << a << endl;
    	system("pause");
    	return 0;
    }