上一个文章我们简单的了解的顺序存储与单链表的区别,相信大家和以前的我一样还不太会写单链表,因为本人是c++的,所以就用c++来实现一下简单的单链表基本操作,,都注意了:基操,勿6,新人需要点赞 上级链接::: 论链表和顺序储存的优缺点(干货)
#include"LinkList.h"
LinkList::LinkList()
{
head = new Node;
head->data=0;
head->next=nullptr;
}
LinkList::~LinkList()//析构
{
delete head;
}
int LinkList::GetLen()
{
int size=0;
Node * p = head->next;
while (p!=nullptr)
{
size++;
p=p->next;
}
return size;
}
bool LinkList::isEmpty()
{
if(head->next==nullptr)
{
return true;
}
else
{
return false;
}
}
void LinkList::CreateLinkList(int size)
{
using namespace std;
Node * pnew,* ptemp;
ptemp = head;
if (size<0)
{
cout<<"输入的节点有误"<<endl;
exit(-1);
}
for (int i=0;i<size;i++)
{
//不断new新的指针,将当前指针的下一节点指向新的指针
pnew = new Node;//开辟堆区
cout<<"请输入第"<<i+1<<"个元素的值"<<endl;
cin>>pnew->data;
pnew->next=nullptr; //下一节点设为空指针
ptemp->next = pnew; //当前节点的下一节点设为新的节点
ptemp = pnew; //当前节点节点设为新节点
}
}
void LinkList::showLinkList()
{
using namespace std;
if(head==nullptr&&head->next==nullptr)
{
cout<<"链表为空表"<<endl;
}
Node * p =head;
while (p->next!=nullptr)
{
p = p->next;
cout<<p->data<<endl;
}
}
//查找元素
Node * LinkList::Find(int data )
{
using namespace std;
Node * p = head;
if (p==nullptr)
{
cout<<"链表为空表"<<endl;
return nullptr;
}
else
{
while(p->next!= nullptr)
{
if(p->data == data)
{
return p;
}
p=p->next;
}
}
if(p->data == data)
{
return p;
}
else
{
return nullptr;
}
}
//在尾部插入指定的元素
void LinkList::InsertElemAtEnd(int data)
{
Node * newNode = new Node; //定义一个Node结点指针newNode
newNode->next = nullptr; //定义newNode的数据域和指针域
newNode->data = data;
Node * p = head; //定义指针p指向头结点
if (head == nullptr) { //当头结点为空时,设置newNode为头结点
head = newNode;
}
else //循环知道最后一个节点,将newNode放置在最后
{
while (p->next != nullptr)
{
p = p->next;
}
p->next = newNode;
}
}
//在指定位置插入指定元素
void LinkList::InsertElemAtIndex(int data,int n)
{
using namespace std;
if (n<1 || n>GetLen()) //输入有误报异常
cout << "输入的值错误" << endl;
else
{
Node * ptemp = new Node; //创建一个新的节点
ptemp->data = data; //定义数据域
Node * p = head; //创建一个指针指向头结点
int i = 1;
while (n > i) //遍历到指定的位置
{
p = p->next;
i++;
}
ptemp->next = p->next; //将新节点插入到指定位置
p->next = ptemp;
}
}
//在头部插入指定元素
void LinkList::InsertElemAtHead(int data)
{
Node * newNode = new Node; //定义一个Node结点指针newNode
newNode->data = data;
Node * p = head; //定义指针p指向头结点
if (head == nullptr) { //当头结点为空时,设置newNode为头结点
head = newNode;
}
newNode->next = p->next; //将新节点插入到指定位置
p->next = newNode;
}
//在尾部删除元素
void LinkList::DeleteElemAtEnd()
{
using namespace std;
Node * p = head; //创建一个指针指向头结点
Node * ptemp = nullptr; //创建一个占位节点
if (p->next == nullptr) { //判断链表是否为空
cout << "单链表空" << endl;
}
else
{
while (p->next != nullptr) //循环到尾部的前一个
{
ptemp = p; //将ptemp指向尾部的前一个节点
p = p->next; //p指向最后一个节点
}
delete p; //删除尾部节点
p = nullptr;
ptemp->next = nullptr;
}
}
//删除所有数据
void LinkList::DeleteAll()
{
Node * p = head->next;
Node * ptemp = new Node;
while (p != nullptr) //在头结点的下一个节点逐个删除节点
{
ptemp = p;
p = p->next;
head->next = p;
ptemp->next = nullptr;
delete ptemp;
}
head->next = nullptr; //头结点的下一个节点指向NULL
}
//删除指定的数据
void LinkList::DeleteElemAtPoint(int data)
{
Node * ptemp = Find(data); //查找到指定数据的节点位置
if (ptemp == head->next) { //判断是不是头结点的下一个节点,如果是就从头部删了它
LinkList Link;
Link.DeleteElemAtHead();
}
else
{
Node * p = head; //p指向头结点
while (p->next != ptemp) //p循环到指定位置的前一个节点
{
p = p->next;
}
p->next = ptemp->next; //删除指定位置的节点
delete ptemp;
ptemp = nullptr;
}
}
//在头部删除节点
void LinkList::DeleteElemAtHead()
{
using namespace std;
Node * p = head;
if (p == nullptr || p->next == nullptr)
{ //判断是否为空表,报异常
cout << "该链表为空表" << endl;
}
else
{
Node * ptemp = nullptr; //创建一个占位节点
p = p->next;
ptemp = p->next; //将头结点的下下个节点指向占位节点
delete p; //删除头结点的下一个节点
p = nullptr;
head->next = ptemp; //头结点的指针更换
}
}
```cpp
//主函数:
#include <iostream>
#include"LinkList.h"
using namespace std;
int main()
{
LinkList l;
int i;
cout << "1.创建单链表 2.遍历单链表 3.获取单链表的长度 4.判断单链表是否为空 5.获取节点\n";
cout << "6.在尾部插入指定元素 7.在指定位置插入指定元素 8.在头部插入指定元素\n";
cout<<"9.在尾部删除元素 10.删除所有元素 11.删除指定元素 12.在头部删除元素 0.退出" << endl;
do
{
cout << "请输入要执行的操作: ";
cin >> i;
switch (i)
{
case 1:
int n;
cout << "请输入单链表的长度: ";
cin >> n;
l.CreateLinkList(n);
break;
case 2:
l.showLinkList();
break;
case 3:
cout << "该单链表的长度为" << l.GetLen() << endl;
break;
case 4:
if (l.isEmpty() == 1)
cout << "该单链表是空表" << endl;
else
{
cout << "该单链表不是空表" << endl;
}
break;
case 5:
int data;
cout << "请输入要获取节点的值: ";
cin >> data;
cout << "该节点的值为" << l.Find(data)->data << endl;
break;
case 6:
int endData;
cout << "请输入要在尾部插入的值: ";
cin >> endData;
l.InsertElemAtEnd(endData);
break;
case 7:
int pointData;
int index;
cout << "请输入要插入的数据: ";
cin >> pointData;
cout << "请输入要插入数据的位置: ";
cin >> index;
l.InsertElemAtIndex(pointData, index);
break;
case 8:
int headData;
cout << "请输入要在头部插入的值: ";
cin >> headData;
l.InsertElemAtHead(headData);
break;
case 9:
l.DeleteElemAtEnd();
break;
case 10:
l.DeleteAll();
break;
case 11:
int pointDeleteData;
cout << "请输入要删除的数据: ";
cin >> pointDeleteData;
l.DeleteElemAtPoint(pointDeleteData);
break;
case 12:
l.DeleteElemAtHead();
break;
default:
break;
}
}while (i != 0);
return 0;
}