[数据结构与算法][数据结构2]线性表的链表C++实现

基本都加上注释了，所有函数在本地运行的功能都可以实现
代码如下:

// 线性表的链式存储实现
// @data:2021/11/22
// @author:Raften
#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 500
#define stop systeam("pause");

struct Node
{
    int data;           // 数据域，存放数据
    Node *next;        // 指针域指向下一个结点
};

class ChainList
{
public:
    ChainList();   // 构造函数
    ~ChainList();    // 析构函数
    void CreateChainList();     // 创建链表
    int GetChainList();         // 获取链表长度
    void ShowChainList();       // 显示链表
    bool EmptyChainList();      // 判断链表是否为空
    Node *FindChainList(int data);  //查找链表中一个位次为data的结点，并且将他的结点指针返回
	void InsertElemAtHead(int data);            //在头部插入元素
    void InsertElemAtEnd(int data);             //在尾部插入指定的元素
	void InsertElemAtIndex(int data, int n);    //在指定位置插入指定元素
    void DeleteHead();                         //头部删除
    void DeleteEnd();                          //尾部删除
	void DeleteIndex(int data);                删除链表中第data的结点
	void DeleteAll();                          //删除所有数据
    void nume();            // 菜单
private:
    Node *head; // 头结点
};

// 初始化头结点
ChainList::ChainList()
{
    head = new Node;  // 创建head
    head->data = 0;
    head->next = NULL;
}

// 删除头结点
ChainList::~ChainList()
{
    delete head;
}

 // 创建链表
void ChainList::CreateChainList()
{
    Node *pnew,*ptemp;
    ptemp=this->head;
    int n; cout<<"需要的结点个数："<<endl;
    cin>>n;
    for(int i=0;i<n;i++){
        pnew = new Node;    // 新创建一个pnew指针
        cout<<"请输入第"<<i+1<<"结点的值"<<endl;
        cin>>pnew->data;    // pnew数据域存入数据
        ptemp->next = pnew; // ptemp指针域指向新创的pnew
        pnew->next = NULL;  // pnew指针域指向空
        ptemp = pnew;       // ptemp存入pnew（可能表达有误，就是现在pnew的内存成为ptemp），准备创建下一个pnew
    }   
    cout<<"--链表创建完成--"<<endl;
}

// 获取链表长度
int ChainList::GetChainList()
{   
    if(this->EmptyChainList()){
        cout<<"--链表为空--"<<endl;
    }
    else{
        int count = 0;  // 计数长度   // 头结点不存放数据
        Node *p = this->head;   // 指向头结点
        while(p->next!=NULL){    
            p = p->next;
            count++;    // 下一个结点不是空的，则长度++
        }
        return count;
    }
}

// 显示链表
void ChainList::ShowChainList()
{
    if(this->EmptyChainList()){
        cout<<"--链表为空--"<<endl;
    }
    else{
        Node *p = this->head;   // 第一个为头节点
        int i = 1;  // 计数
        while(p->next!=NULL){
            p = p->next;    // p 指向下一个结点
            cout<<"第"<<i<<"个结点："<<p->data<<endl;   // 如果下一个结点不为空，则继续
            i++;
        }
    }

}

// 判断链表是否为空
bool ChainList::EmptyChainList()
{
    if(this->head->next==NULL){     // 头结点指向空 为空链表
        return true;        // 表空返回true
    }
    return false;
}

//查找链表中一个位次为data的结点，并且将他的结点指针返回
Node* ChainList::FindChainList(int data)
{
    if(this->EmptyChainList()){
        cout<<"--链表为空--"<<endl;
    }
    else{
        Node* p = this->head;
	    int i = 0;
	
	    while (data!=i){
		    p = p->next;
		    i++;
	    }
	    return p;
    }
}

//在头部插入元素
void ChainList::InsertElemAtHead(int data)
{
    Node*p = this->head;
	Node*pnew = new Node;   // 创建一个新指针
	pnew->data = data;      // pnew的数据域存入data
	pnew->next = p->next;   // pnew的指针域指向 p的指针域，也就是头结点的下一个结点
	p->next = pnew;         // p的指针域，也就是head指针域 指向pnew         
}

//在尾部插入指定的元素
void ChainList::InsertElemAtEnd(int data)
{
    Node *pnew = new Node;   // 新结点存入数据
	pnew->data = data;
	pnew->next = NULL;
	Node* p = this->head;
	while (p->next != NULL) // 找到最后一个结点
	{
		p = p->next;
	}
	p->next = pnew;     // 连接新结点
}

//在指定位置插入指定元素
void ChainList::InsertElemAtIndex(int data, int n)
{
    if (n<1 || n>this->GetChainList())                   //输入有误报异常
		cout << "--erro输入异常--" << endl;
	if (n == 1){    // 头结点插入法
		Node *p = this->head;
		Node*pnew = new Node;
		pnew->data = data;
		pnew->next = p->next;
		p->next = pnew;
	}
	else{	
		int i = 0;
		Node *p = this->head;   
		while (n > i){
			p = p->next;
			i++;    //找到要插入的位置
		}
		Node*pnew = new Node;
		pnew->data = data;
		pnew->next = p->next;
		p->next = pnew;
		
	}
}
//头部删除
void ChainList::DeleteHead()
{
    if (this->EmptyChainList()){
		cout << "空链表！" << endl;
	}
	else{
		Node*p = this->head;    // 新创建一个结点head结点的下一个（也就是第一个结点）
		Node *ptemp;            // 缓存结点
		p = p->next;            // p=第一个结点
		ptemp = p->next;        // ptemp 等于 第二个结点
		delete p;               // 删除p 就是删除第一个结点
		p = NULL;               // 上完厕所洗手
		head->next = ptemp;	    // 头结点指向ptemp：ptemp成为第一个结点了
	}
}

//尾部删除
void ChainList::DeleteEnd()
{
    Node *p= this->head;
	Node* ptemp=NULL;
	if (this->EmptyChainList()){
		cout << "空链表！" << endl;
	}
	else{
		while (p->next != NULL){     // 找到前一个结点	
			ptemp = p;          //用ptemp记录要删除的尾部元素的前一个结点
			p = p->next;
		}
		delete p;
		ptemp->next = NULL;     //把ptemp作为新的末尾结点指向空

	}
}                         
//删除链表中第data的结点
void ChainList::DeleteIndex(int data)
{
    if (this->EmptyChainList())
	{
		cout << "空链表！" << endl;
	}
	else{
		Node*ptemp =this->FindChainList(data);   // 第一个结点的话就删除头结点
		if (ptemp == this->head->next)
		{
			DeleteHead();
		}
		else{
			Node*p = this->head;
			while (p->next != ptemp)      //p循环到指定位置的前一个节点
			{
				p = p->next;
			}
			p->next = ptemp->next;         //删除指定位置的节点
			delete ptemp;
			ptemp = NULL;
			
		}
	}
}
//删除所有数据
void ChainList::DeleteAll()
{
    Node*p = this->head->next;          //头节点的下一个
	Node* ptemp = NULL;
	if (this->EmptyChainList()){
		cout << "空链表！" << endl;
	}
	else{
		while (p == NULL){              
			ptemp = p;
			p = p->next;
			this->head->next = p;
			ptemp->next = NULL;
			delete ptemp;
		}
		this->head->next = NULL;
        cout<<"--删除成功--"<<endl;
	}
}
// 菜单
void ChainList::nume()
{
    while(1){
        cout<<"1.void CreateChainList();     // 创建链表"<<endl;
        cout<<"2.int GetChainList();         // 获取链表长度"<<endl;
        cout<<"3.void ShowChainList();       // 显示链表"<<endl;
        cout<<"4.bool EmptyChainList();      // 判断链表是否为空"<<endl;
        cout<<"5.Node *FindChainList(int data);  //查找链表中一个位次为data的结点，并且将他的结点指针返回"<<endl;
        cout<<"6.void InsertElemAtHead(int data);            //在头部插入元素"<<endl;
        cout<<"7.void InsertElemAtEnd(int data);             //在尾部插入指定的元素"<<endl;
        cout<<"8.void InsertElemAtIndex(int data, int n);    //在指定位置插入指定元素"<<endl;
        cout<<"9.void DeleteHead();                         //头部删除"<<endl;
        cout<<"10.void DeleteEnd();                          //尾部删除"<<endl;
        cout<<"11.void DeleteIndex(int data);                删除链表中第data的结点"<<endl;
        cout<<"12.void DeleteAll();                          //删除所有数据  "<<endl;
        int num; cin>>num;
        int data;
        int n;
        Node *p = new Node;
        switch(num){
            case 0: system("cls"); 
            cout<<"==2s后退出程序=="<<endl; _sleep(2000); 
            return;
            case 1: system("cls"); 
                    CreateChainList();
                    break;
            case 2: system("cls"); 
                    cout<<"链表长度为:"<<GetChainList()<<endl;
                    break;
            case 3: system("cls"); 
                    ShowChainList();
                    break;
            case 4: system("cls"); 
                    if(EmptyChainList()){
                        cout<<"链表为空"<<endl;
                    }
                    else{
                        cout<<"链表不为空"<<endl;
                    }
                    break;
            case 5: system("cls"); 
                    cout<<"请输入需要查找的结点: "<<endl;
                    cin>>data; 
                    p = FindChainList(data);  
                    cout<<"该结点的数据为:"<<p->data<<endl;
                    break;
            case 6: system("cls"); 
                    cout<<"输入需要插入的元素"<<endl;
                    cin>>data;
                    InsertElemAtHead(data);
                    break;
            case 7: system("cls"); 
                    cout<<"输入需要插入的元素"<<endl;
                    cin>>data;
                    InsertElemAtEnd(data);
                    break;                 
            case 8: system("cls");
                    cout<<"输入需要插入的元素"<<endl;
                    cin>>data;
                    cout<<"输入元素位置"<<endl;
                    cin>>n;
                    InsertElemAtIndex(data,n);
                    break;
            case 9: system("cls"); 
                    DeleteHead();
                    break;
            case 10: system("cls"); 
                    DeleteEnd();
                    break;
            case 11: system("cls");
                cout<<"输入需要删除的位置"<<endl;
                cin>>data; 
                    DeleteIndex(data);
                    break;                                        
            case 12: system("cls"); 
            DeleteAll();
                    break;        
        }
    }
}

int main(void)
{
    ChainList CL;
    CL.nume();
    return 0;
}