C++实现单向链表
嵌入式Linux
共 3313字，需浏览 7分钟
·
2020-12-07 21:35
之前相关的文章
#什么是链表
链表是一种基本的数据结构，之前我在C语言里面写过链表的知识，现在延申到C++，不管是什么语言，链表表示的是一种数据结构，跟语言没有强相关性的。
如果我们需要实现一个链表，首先最关键的就是节点，一个节点表示链表的一个数据存储点，链表是由很多个节点组成的。
链表还需要很多线把很多节点串联在一起，可以用数组的特性串联，也可以用指针串联。
/*节点类*/
class Node
{
public:
DataType data;
Node *next;
};
#链表头部
链表是一种数据结构，跟数组一样，和整型的数据一样，都需要一个起始位置，链表头就是这个起始位置，链表头存在，就表示链表存在，链表头没有了，那这个链表也就没有了。
链表头也是一个节点，只是这个节点保存的是这个链表的起始位置
头节点有点意思，它其实是不需要存储数据的，所以data的值可有可无。
代码上我们可以这样写，创建一个链表也就是创建一个链表头
LinkList::LinkList()
{
head = new Node;
head->data = 0;
head->next = NULL;
size = 0;
}
#插入一个数据到链表中
如果是一个已经成型的链表，我们要把一个数据插入到链表中，我们需要有几个判断，是从链表头插入，还是链表尾部插入，还是从链表的中间插入
— — 如果从链表头插入，如下图
— — 如果从链表中间插入，如下图
— — 如果从链表尾部插入，如下图
— —代码实现
int LinkList::InsertLinklList(Node *data, int n)
{
Node *ptemp;
if (this->head == NULL) {
cout << "链表为空" << endl;
return -1;
}
if (data == NULL) {
cout << "插入节点为空" << endl;
return -1;
}
/*头部插入*/
if (n<2) {
Node *pnew = new Node;
pnew->data = data->data;
pnew->next = this->head->next;
this->head->next = pnew;
this->size++;
return 0;
}
/*尾部插入*/
if (n > this->size) {
ptemp = this->head;
while (ptemp->next != NULL) {
ptemp = ptemp->next;
}
Node *pnew = new Node;
pnew->data = data->data;
pnew->next = NULL;
ptemp->next = pnew;
this->size++;
return 0;
}else {/*中间插入*/
ptemp = this->head;
for (int i = 1; i < n; i++) {
ptemp = ptemp->next;
}
Node *pnew = new Node;
pnew->data= data->data;
pnew->next = ptemp->next;
ptemp->next = pnew;
this->size++;
return 0;
}
}
#完整的代码
#include
#include
using namespace std;
/*节点类*/
class Node
{
public:
int data;
Node *next;
};
class LinkList
{
public:
LinkList();/*构造函数*/
~LinkList();/*析构函数*/
int CreateLinkList(int size);/*新建一个链表*/
int DestroyLinkList();/*销毁一个链表*/
int TravalLinkList();/*遍历一个链表*/
int InsertLinklList(Node *data, int n);/*向链表插入一个数据*/
int DeleteLinklist(int n);/*删除链表中的某个值*/
int GetLength();/*获取链表的长度*/
bool IsEmpty();/*判断链表是否为空*/
Node *head;/*链表头*/
int size;/*链表长度*/
};
LinkList::LinkList()
{
head = new Node;
head->data = 0;
head->next = NULL;
size = 0;
}
LinkList::~LinkList()
{
delete head;
}
int LinkList::CreateLinkList(int n)
{
if (n<0) {
cout<<"error"< return -1;
}
Node *ptemp = NULL;
Node *pnew = NULL;
this->size = n;
ptemp = this->head;
for(int i =0 ; i {
pnew = new Node;
pnew->next = NULL;
cout << "输入第" << i+1 << "个节点值" << endl;
cin >> pnew->data;
ptemp->next = pnew;
ptemp = pnew;
}
cout << "创建完成" << endl;
return 0;
}
int LinkList::DestroyLinkList()
{
Node *ptemp;
if (this->head == NULL) {
cout << "链表原本就为空" << endl;
return -1;
}
while (this->head)
{
ptemp = head->next;
free(head);
head = ptemp;
}
cout << "销毁链表完成" << endl;
return 0;
}
int LinkList::TravalLinkList()
{
Node *ptemp = this->head->next;
if (this->head == NULL) {
cout << "链表为空" << endl;
return -1;
}
while(ptemp)
{
cout << ptemp->data << "->";
ptemp = ptemp->next;
}
cout <<"NULL"<< endl;
return 0;
}
int LinkList::InsertLinklList(Node *data, int n)
{
Node *ptemp;
if (this->head == NULL) {
cout << "链表为空" << endl;
return -1;
}
if (data == NULL) {
cout << "插入节点为空" << endl;
return -1;
}
/*头部插入*/
if (n<2) {
Node *pnew = new Node;
pnew->data = data->data;
pnew->next = this->head->next;
this->head->next = pnew;
this->size++;
return 0;
}
/*尾部插入*/
if (n > this->size) {
ptemp = this->head;
while (ptemp->next != NULL) {
ptemp = ptemp->next;
}
Node *pnew = new Node;
pnew->data = data->data;
pnew->next = NULL;
ptemp->next = pnew;
this->size++;
return 0;
}
/*中间插入*/
else {
ptemp = this->head;
for (int i = 1; i < n; i++) {
ptemp = ptemp->next;
}
Node *pnew = new Node;
pnew->data= data->data;
pnew->next = ptemp->next;
ptemp->next = pnew;
this->size++;
return 0;
}
}
int LinkList::DeleteLinklist(int n)
{
Node *ptemp;
Node *ptemp2;
if (n > this->size) {
cout << "n太大" << endl;
return -1;
}
/*删头节点*/
if (n < 2) {
ptemp = this->head->next;
this->head->next = ptemp->next;
free(ptemp);
this->size--;
return 0;
}
/*尾部删除*/
if (n == this->size) {
ptemp = this->head;
for (int i = 1; i < this->size;i++) {
ptemp = ptemp->next;
}
ptemp2 = ptemp->next;
ptemp->next = NULL;
free(ptemp2);
this->size--;
return 0;
}
/*中间删除*/
else
{
ptemp = this->head;
for (int i = 1; i < n; i++) {
ptemp = ptemp->next;
}
ptemp2 = ptemp->next;
ptemp->next = ptemp2->next;
free(ptemp2);
this->size--;
return 0;
}
}
int LinkList::GetLength()
{
return this->size;
}
bool LinkList::IsEmpty()
{
if (this->head == NULL) {
return true;
}
else{
return false;
}
}
int main(void)
{
LinkList list;
LinkList *plist = &list;
/*创建6个节点的链表*/
plist->CreateLinkList(5);
plist->TravalLinkList();
/*向链表中插入一个数据*/
Node temp;
temp.data = 77;
temp.next = NULL;
/*向0号位置插入一个节点*/
plist->InsertLinklList(&temp, 0);
/*遍历整个链表*/
plist->TravalLinkList();
/*向尾部插入一个链表*/
plist->InsertLinklList(&temp, plist->GetLength()+1);
/*遍历整个链表*/
plist->TravalLinkList();
/*向5号位置插入一个链表*/
plist->InsertLinklList(&temp, 5);
/*遍历整个链表*/
plist->TravalLinkList();
plist->DeleteLinklist(0);
/*遍历整个链表*/
plist->TravalLinkList();
/*删除第二个节点*/
plist->DeleteLinklist(4);
/*遍历整个链表*/
plist->TravalLinkList();
/*删除整个链表*/
plist->DestroyLinkList();
system("pause");
return (0);
}
#代码输出
输入第1个节点值
2
输入第2个节点值
22
输入第3个节点值
3
输入第4个节点值
44
输入第5个节点值
5
创建完成
2->22->3->44->5->NULL
77->2->22->3->44->5->NULL
77->2->22->3->44->5->77->NULL
77->2->22->3->77->44->5->77->NULL
2->22->3->77->44->5->77->NULL
2->22->3->44->5->77->NULL
销毁链表完成
请按任意键继续. . .
评论