以下是我编写的链表类,有一部分的函数功能我不太清楚该怎么实现,我想知道该怎么实现“链表复制构造函数、链表赋值运算符重载、简单合并在链表尾部、链表反转、有序链表创建(升序)、链表尾部插入节点、删除链表尾部节点、获取链表尾部指针(末节点)、链表节点个数(不含头节点)”,感谢!
#pragma once
#include <iostream>
using namespace std;
class Node
{
public:
Node(int n = 0, Node* p = NULL) { num = n; next = p; }
friend class Linklist;
private:
int num;
Node* next;
};
class Linklist
{
public:
Linklist(int n = 0) { head = new Node(n); }//创建只含头节点的空链表
void insert(int n);//n代表插入节点的位置
void visitAllNode();//遍历
Node* find(int num); //查找num值节点
void deleteNum(int num);//删除值为num的节点
void release();//清空链表,只留下头节点
~Linklist() { release(); delete head; }
Linklist(const Linklist&);//链表复制构造函数
Linklist& operator = (const Linklist&);//链表赋值运算符重载
void operator+=(const Linklist&); //简单合并在链表尾部
void List_Reverse(); //链表反转
void Creat_OrderList(int); //有序链表创建(升序)
void push_back(int); //链表尾部插入节点
void pop_back(); //删除链表尾部节点
Node* back(); //获取链表尾部指针(末节点)
int size(); //链表节点个数(不含头节点)
private:
Node* head;
};
void Linklist::insert(int n)//n代表插入节点的位置
{
Node *p = head, *ptr;
int value;
if (head->num < n)
{
cout << "插入位置有误" << endl;
return;
}
for (int i = 0; i < n; i++)
{
p = p->next;
}
cout << "请输入插入节点的数据:";
cin >> value;
ptr = new Node(value);
ptr->next = p->next;
p->next = ptr;
head->num++;
}
void Linklist::visitAllNode()//遍历
{
Node* p;
p = head->next;
if (p == NULL)
{
cout << "空链表" << endl;
return;
}
cout << "表头--";
while (p != NULL)
{
cout << p->num << "--";
p = p->next;
}
cout << "表尾" << endl;
}
Node* Linklist::find(int num)//查找num值节点
{
Node *p1 = head->next, *p2 = head;
if (p1 == NULL)
{
cout << "空链表";
return NULL;
}
while (p1 != NULL)
{
if (p1->num != num)
{
p2 = p1;
p1 = p1->next;
}
else
return p2;
}
return NULL;
}
void Linklist::deleteNum(int num)//删除值为num的节点
{
Node *p1 = find(num), *p2;
if (p1 != NULL)
{
p2 = p1->next;
p1->next = p2->next;
delete p2;
head->num--;
}
else
cout << "没有被删除的数据" << endl;
}
void Linklist::release()//清空链表,只留下头节点
{
Node *p = head->next;
while (p != NULL)
{
head->next = p->next;
delete p;
p = head->next;
}
}
Linklist::Linklist(const Linklist& l)//链表复制构造函数
{
}
Linklist& Linklist::operator=(const Linklist&)//链表赋值运算符重载
{
}
void Linklist::operator+=(const Linklist&)//简单合并在链表尾部
{
}
void Linklist::List_Reverse()//链表反转
{
}
void Linklist::Creat_OrderList(int)//有序链表创建(升序)
{
}
void Linklist::push_back(int)//链表尾部插入节点
{
}
void Linklist::pop_back()//删除链表尾部节点
{
}
Node* back()//获取链表尾部指针(末节点)
{
}
int Linklist::size()//链表节点个数(不含头节点)
{
}
基于new bing的代码完善:
#pragma once
#include <iostream>
using namespace std;
class Node
{
public:
Node(int n = 0, Node* p = NULL) { num = n; next = p; }
friend class Linklist;
private:
int num;
Node* next;
};
class Linklist
{
public:
Linklist(int n = 0) { head = new Node(n); } //创建只含头节点的空链表
//在第n个位置插入节点
void insert(int n);
//遍历链表
void visitAllNode();
//查找值为num的节点并返回其前一个节点指针
Node* find(int num);
//删除值为num的节点
void deleteNum(int num);
//清空链表,只留下头节点
void release();
//链表复制构造函数
Linklist(const Linklist&);
//链表赋值运算符重载
Linklist& operator=(const Linklist&);
//简单合并在链表尾部
void operator+=(const Linklist&);
//链表反转
void List_Reverse();
//有序链表创建(升序)
void Creat_OrderList(int);
//链表尾部插入节点
void push_back(int);
//删除链表尾部节点
void pop_back();
//获取链表尾部指针(末节点)
Node* back();
//链表节点个数(不含头节点)
int size();
~Linklist() { release(); delete head; }
private:
Node* head;
};
void Linklist::insert(int n)
{
Node *p = head, *ptr;
int value;
if (head->num < n)
{
cout << "插入位置有误" << endl;
return;
}
for (int i = 0; i < n; i++)
{
p = p->next;
}
cout << "请输入插入节点的数据:";
cin >> value;
ptr = new Node(value);
ptr->next = p->next;
p->next = ptr;
head->num++;
}
void Linklist::visitAllNode()
{
Node* p;
p = head->next;
if (p == NULL)
{
cout << "空链表" << endl;
return;
}
cout << "表头--";
while (p != NULL)
{
cout << p->num << "--";
p = p->next;
}
cout << "表尾" << endl;
}
Node* Linklist::find(int num)
{
Node* p1 = head->next, *p2 = head;
if (p1 == NULL) //空链表
{
cout << "空链表" << endl;
return NULL;
}
while (p1 != NULL)
{
if (p1->num != num)
{
p2 = p1;
p1 = p1->next;
}
else
return p2;
}
return NULL; //未找到
}
void Linklist::deleteNum(int num)
{
Node* pre = find(num);
if (pre != NULL)
{
Node* tmp = pre->next;
pre->next = tmp->next;
delete tmp;
head->num--;
}
else
cout << "没有找到值为" << num << "的节点" << endl;
}
void Linklist::release()
{
Node *p = head->next;
while (p != NULL)
{
head->next = p->next;
delete p;
p = head->next;
}
}
Linklist::Linklist(const Linklist& l)
{
head = new Node(0);
Node* p = l.head->next;
Node* pre = head;
while (p != NULL)
{
Node* tmp = new Node(p->num);
pre->next = tmp;
pre = pre->next;
p = p->next;
head->num++;
}
}
Linklist& Linklist::operator=(const Linklist& l)
{
if (this == &l)
return *this; //避免自赋值
release();
head = new Node(0);
Node* p = l.head->next;
Node* pre = head;
while (p != NULL)
{
Node* tmp = new Node(p->num);
pre->next = tmp;
pre = pre->next;
p = p->next;
head->num++;
}
return *this;
}
void Linklist::operator+=(const Linklist& l)
{
Node* p1 = head, *p2 = l.head->next;
while (p1->next != NULL)
p1 = p1->next;
while (p2 != NULL)
{
Node* tmp = new Node(p2->num);
p1->next = tmp;
p1 = p1->next;
p2 = p2->next;;
head->num++;
}
}
void Linklist::List_Reverse()
{
Node *pre, *cur, *tmp;
if (head->next == NULL)
return;
pre = head->next;
cur = pre->next;
while (cur != NULL)
{
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
head->next->next = NULL;
head->next = pre;
}
void Linklist::Creat_OrderList(int n)
{
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
Node* tmp = new Node(num);
Node* p1 = head, *p2 = head->next;
while (p2 != NULL && p2->num < num)
{
p1 = p2;
p2 = p2->next;
}
tmp->next = p2;
p1->next = tmp;
head->num++;
}
}
void Linklist::push_back(int n)
{
Node* p = head;
while (p->next != NULL)
p = p->next;
Node* tmp = new Node(n);
p->next = tmp;
head->num++;
}
void Linklist::pop_back()
{
if (head->next == NULL)
return;
Node* p1 = head, *p2 = head->next;
while (p2->next != NULL)
{
p1 = p2;
p2 = p2->next;
}
p1->next = NULL;
delete p2;
head->num--;
}
Node* Linklist::back()
{
if (head->next == NULL)
return NULL;
Node* p = head;
while (p->next != NULL)
p = p->next;
return p;
}
int Linklist::size()
{
return head->num;
}
这种是刚开始学习的难度,简单的案例可以跟同学商讨而不是直接寻求解决方案,其他代码结果已发,主要你要学会用指针对链表节点遍历,不管正着来反着来,可以在纸上用笔自己画画运行到哪一个节点了,具体系统学习可以参考王道考研->>单链表章节:
Node* Linklist::back() {
Node* p = head;
while(p->next != nullptr) {
p = p->next;
}
return p;
}
int Linklist::size() {
int cnt = 0;
Node* p = head->next;
while(p != nullptr) {
cnt++;
p = p->next;
}
return cnt;
}