C++单向链表

谁借莪１个温暖的怀抱￠ 2023-06-04 06:57 9阅读 0赞

之前用C语言编过链表，这几天突然想用C++编一下链表，搞了大半天才搞出来，所以就赶紧整理一下记录下来，省的万一时间长了找不到代码哈哈。

## 一、链表代码 ##

1、Node.h文件代码

#pragma once
    class Node
    { 
    public:
    	int ID;
    	char alph;
    	Node* next;
    
    	Node(int ID,char alph);
    	~Node();
    private:
    
    };
    
    Node::Node(int ID,char alph)	//初始化内部数据
    { 
    	this->ID=ID;
    	this->alph=alph;
    	this->next=NULL;
    }
    
    Node::~Node()
    { 
    }

2、List.h文件代码

#pragma once
    #include<iostream>
    #include "Node.h"
    using namespace std;
    class List
    { 
    public:
    	Node* head;		//定义头指针
    	List();
    	~List();
    	void Add(Node* Node);
    	void Print();
    	void Delete(int ID);
    	void Modify(int ID);
    	void Query(int ID);
    	void Insert(Node* node, int ID);
    	void Swap(int ID1,int ID2);
    	void Sort();
    
    private:
    
    };
    
    List::List()
    { 
    	head=NULL;
    }
    
    List::~List()	//将分配的内存释放掉
    { 
    	if (head==NULL)return;
    	Node* p=head,*previous;
    	while (p->next!=NULL)
    	{ 
    		previous=p;
    		p=p->next;
    		delete previous;
    	}
    	delete p;
    	//delete head; //此时的head指针已经为空，所以不用释放内存
    }
    
    void List::Add(Node* node)
    { 	
    	Node* current=head;	//将current指针指向头节点
    	if (head==NULL)
    	{ 
    		head=node;
    	}
    	else
    	{ 
    		while (current->next!=NULL)	//判断是否到达末尾
    		{ 
    			current=current->next;
    		}
    		current->next=node;
    	}
    }
    
    //打印结果
    void List::Print()
    { 
    	if (head==NULL)return;
    	Node* current=head;
    	while (current!=NULL)
    	{ 
    		cout<<current->ID<<" "<<current->alph<<endl;
    		current=current->next;
    	}
    	cout<<endl;
    }
    
    //在指定位置插入节点
    void List::Insert(Node* node,int ID)
    { 
    	if (head==NULL)
    	{ 
    		cout<<"链表为空！"<<endl;
    		return;
    	}
    	bool flag=false;
    	Node* current=head,*p1=head,*p2=head;	//定义三个指针记录连续的三个节点位置
    	while (current!=NULL)
    	{ 
    		if (current->ID==ID)
    		{ 
    			if (current==head)	//头结点
    			{ 
    				head=node;
    				node->next=current;
    				flag=true;
    				break;
    			}
    			else
    			{ 
    				p1->next=node;
    				node->next=current;
    				flag=true;
    				break;
    			}
    		}
    		p1=current;
    		current=current->next;
    	}
    
    	if (flag==false)
    	{ 
    		cout<<"未找到符合条件的ID"<<endl;
    	}
    }
    
    //删除指定节点
    void List::Delete(int ID)
    { 
    	if (head==NULL)
    	{ 
    		cout<<"链表为空！"<<endl;
    		return;
    	}
    	bool flag=false;
    	Node* current=head,*p1=head,*p2=head;	//定义三个指针记录连续的三个节点位置
    	while (current!=NULL)
    	{ 
    		if (current->ID==ID)
    		{ 
    			if (current==head)	//头结点
    			{ 
    				current=current->next;
    				head=current;
    				flag=true;
    				delete p2;
    				break;
    			}
    			else if(current->next==NULL)	//尾节点
    			{ 
    				p2->next=NULL;
    				flag=true;
    				delete current;
    				break;
    			}
    			else     //中间节点
    			{ 
    				current=current->next;
    				p2->next=current;
    				flag=true;
    				delete p1;
    				break;
    			}
    		}
    		current=current->next;
    		p2=p1;
    		p1=current;
    	}
    
    	if (flag==false)
    	{ 
    		cout<<"未找到符合条件的ID";
    	}
    }
    
    //修改指定节点的信息
    void List::Modify(int ID)
    { 
    	if (head==NULL)
    	{ 
    		cout<<"链表为空！"<<endl;
    		return;
    	}
    	bool flag=false;
    	Node* current=head;
    	while (current!=NULL)
    	{ 
    		if (current->ID==ID)
    		{ 
    			cout<<"请输入要修改的内容:"<<endl;
    			cin.clear();	//清除错误标志
    			cin.sync();		//清空cin缓冲区内的数据
    			cin>>current->alph;
    			flag=true;
    			break;
    		}
    		current=current->next;
    	}
    
    	if (flag==false)
    	{ 
    		cout<<"未找到符合条件的ID"<<endl;
    	}
    }
    
    //查询指定的节点信息
    void List::Query(int ID)
    { 
    	if (head==NULL)
    	{ 
    		cout<<"链表为空！"<<endl;
    		return;
    	}
    	bool flag=false;
    	Node* current=head;
    	while (current!=NULL)
    	{ 
    		if (current->ID==ID)
    		{ 
    			cout<<"查询结果如下:"<<endl;
    			cout<<current->ID<<" "<<current->alph<<endl;
    			flag=true;
    			break;
    		}
    		current=current->next;
    	}
    
    	if (flag==false)
    	{ 
    		cout<<"未找到符合条件的ID"<<endl;
    	}
    }
    
    //节点的交换，想法可能有点问题，代码写的有点长，总感觉笨笨的
    void List::Swap(int ID1,int ID2)
    { 
    	if (head==NULL)
    	{ 
    		cout<<"链表为空！"<<endl;
    		return;
    	}
    	Node* p1=head,*prev1=head,*beh1;	//记录链表中连续的三个位置
    	Node* p2=head,*prev2=head,*beh2;
    	while (p1!=NULL)	//找到节点ID1的位置
    	{ 
    		beh1=p1->next;
    		if (p1->ID==ID1)
    		{ 
    			break;
    		}
    		prev1=p1;
    		p1=p1->next;
    	}
    	while (p2!=NULL)	//找到节点ID2的位置
    	{ 
    		beh2=p2->next;
    		if (p2->ID==ID2)
    		{ 
    			break;
    		}
    		prev2=p2;
    		p2=p2->next;
    	}
    	if (p1==NULL||p2==NULL)
    	{ 
    		cout<<"未找到符合条件的ID1或ID2,交换不能进行！"<<endl;
    		return;
    	}
    
    	if (p1==head||p2==head)		//节点ID1或ID2为头结点时
    	{ 
    		if (p1==head&&p2!=beh1)
    		{ 
    			head=p2;
    			p2->next=beh1;
    			prev2->next=p1;
    			p1->next=beh2;
    		}
    		else if(p2==beh1)
    		{ 
    			head=p2;
    			p2->next=p1;
    			p1->next=beh2;
    		}
    		else if(p1==beh2)
    		{ 
    			head=p1;
    			p1->next=p2;
    			p2->next=beh1;
    		}
    		else
    		{ 
    			head=p1;
    			p1->next=beh2;
    			prev1->next=p2;
    			p2->next=beh1;
    		}
    	}
    	else
    	{ 
    		if(p2==beh1)	//交换位置相邻
    		{ 
    			prev1->next=p2;
    			p2->next=p1;
    			p1->next=beh2;
    		}
    		else if(p1==beh2)
    		{ 
    			prev2->next=p1;
    			p1->next=p2;
    			p2->next=beh1;
    		}
    		else
    		{ 
    			prev1->next=p2;
    			p2->next=beh1;
    			prev2->next=p1;
    			p1->next=beh2;
    		}	
    	}
    }
    
    //由小到大排序，这里的排序方法有些简单，但当时只想到了这个
    void List::Sort()
    { 
    	if (head==NULL)
    	{ 
    		cout<<"链表为空！"<<endl;
    		return;
    	}
    	Node* p1=head,*p2=head->next,*temp;
    	while (p1!=NULL)
    	{ 
    		while (p2!=NULL)
    		{ 
    			if (p2->ID<p1->ID)	//比较ID的大小
    			{ 
    				Swap(p2->ID,p1->ID);
    				temp=p1;
    				p1=p2;
    				p2=temp;
    			}
    			p2=p2->next;
    		}
    		p1=p1->next;
    		p2=p1->next;
    		if (p2==NULL)
    			break;
    	}
    }

3、mian.cpp文件代码

#include<iostream>
    #include "Node.h"
    #include "List.h"
    using namespace std;
    
    int main()
    { 
    	int ID,INPUT;
    	char alph;
    	List list;	//定义链表
    	cout<<"请输入数据，创建链表:"<<endl;
    	while (cin>>ID>>alph)	//连续输入数据,直到遇到文件结束符或是输入错误才会结束
    	{ 
    		//cout<<ID<<" "<<alph<<endl;
    		Node* node=new Node(ID,alph);	//使用new关键字返回的是一个指针类型
    		list.Add(node);
    	}
    	cout<<"创建结果如下:"<<endl;
    	list.Print();
    
    	list.Sort();
    	cout<<"首先进行排序,排序结果如下:"<<endl;
    	list.Print();
    
    	cout<<"请输入要进行交换的ID(形如* *):"<<endl;
    	cin.clear();	//清除错误标志
    	cin.sync();		//清空cin缓冲区内的数据
    	cin>>ID>>INPUT;
    	list.Swap(ID,INPUT);
    	cout<<"交换结果如下:"<<endl;
    	list.Print();
    
    	cout<<"请输入要插入的数据(形如* *):"<<endl;
    	cin.clear();	//清除错误标志
    	cin.sync();		//清空cin缓冲区内的数据
    	cin>>ID>>alph;
    	Node* node=new Node(ID,alph);
    	cout<<"请输入要插入的位置ID:"<<endl;
    	cin.clear();	//清除错误标志
    	cin.sync();		//清空cin缓冲区内的数据
    	cin>>ID;
    	list.Insert(node,ID);
    	cout<<"插入结果如下:"<<endl;
    	list.Print();
    
    	cout<<"请输入要删除数据的ID:"<<endl;
    	cin.clear();	//清除错误标志
    	cin.sync();		//清空cin缓冲区内的数据
    	cin>>ID;
    	list.Delete(ID);
    	cout<<"删除结果如下:"<<endl;
    	list.Print();
    
    	cout<<"请输入要修改数据的ID:"<<endl;
    	cin.clear();	//清除错误标志
    	cin.sync();		//清空cin缓冲区内的数据
    	cin>>ID;
    	list.Modify(ID);
    	cout<<"修改结果如下:"<<endl;
    	list.Print();
    
    	cout<<"请输入要查询数据的ID:"<<endl;
    	cin.clear();	//清除错误标志
    	cin.sync();		//清空cin缓冲区内的数据
    	cin>>ID;
    	list.Query(ID);
    
    	cout<<endl;
    	return 0;
    }

## 二、实现效果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70 2]

## 三、小结 ##

链表在C++中可能没有在C语言中那么重要，但是学习链表对于我来说主要是学习对指针的灵活运用，所以在本次编写链表的过程中这加深了我对指针的理解。也希望上面的内容对大家有所帮助，算是共勉吧。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191007160040471.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019100716014089.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70 2]: /images/20230601/4a41fa8fcc8a442fa3817e1a2d5eea38.png