c++实现带头结点的单链表的基本操作

本文参考代码：https://blog.csdn.net/qq_35143440/article/details/78896638

目录结构：

LinkList.h

struct ListNode {
int val;//数据域
ListNode* next;//指针域
};
class LinkList
{
public:
LinkList();
~LinkList();
void CreateLinkList(int n);
void TravelLinkList();
int getLength();
bool isEmpty();
bool findData(int data);//查找节点，如果能够找到，返回true；否则返回false;
void InsertElemAtEnd(int data);
//在尾部插入指定的元素
void InsertElemAtIndex(int data, int n);
//在指定位置插入指定元素
void InsertElemAtHead(int data);
//在头部插入指定元素
void DeleteElemAtEnd();
//在尾部删除元素
void DeleteAll();
//删除所有数据
void DeleteElemAtPoint(int data);
//删除指定的数据
void DeleteElemAtHead();//在头部删除节点
private:
ListNode *head;
};

LinkList.cpp

#include "stdafx.h"
#include "LinkList.h"
#include <iostream>
using namespace std;
LinkList::LinkList()
{
head = new ListNode;
head->val = 0;
head->next = NULL;
}
LinkList::~LinkList()
{
delete head;
}
void LinkList::CreateLinkList(int n) {
if (n < 0) {
cout << "节点个数错误，请重新输入" << endl;
exit(EXIT_FAILURE);
}
else {
ListNode* p = head;
ListNode* nextNode;
for (int i = 0; i < n;i++) {
nextNode = new ListNode;
cout << "请输入新节点的值域" << endl;
cin >> nextNode->val;
nextNode->next = NULL;
p->next = nextNode;
p = p->next;
}
}
}
void LinkList::TravelLinkList() {
if (head == NULL || head->next == NULL) {
cout << "链表为空" << endl;
}
else {
ListNode* p = head;
while (p ->next!= NULL) {
p = p->next;
cout << p->val << endl;
}
}
}
int LinkList::getLength() {//头结点不计入总长度
int length = 0;
ListNode* p = head->next;
while (p != NULL) {
length++;
p = p->next;
}
return length;
}
bool LinkList::isEmpty() {
if (head == NULL) {
return true;
}
else {
return false;
}
}
bool LinkList::findData(int data)//查找节点，如果能够找到，返回true；否则返回false;
{
if (head == NULL || head->next == NULL) { return false; }
else {
ListNode* p = head->next;
while (p != NULL) {
if (p->val == data) { return true; }
else { p = p->next; }
}
return false;
}
}
void LinkList::InsertElemAtEnd(int data)//在尾部插入指定的元素
{
//准备好新的节点
ListNode* newNode;
newNode = new ListNode;
newNode->val = data;
newNode->next = NULL;
//在链表尾部插入节点
if (head == NULL) { head = newNode; }
else {
ListNode* p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
}
}
void LinkList::InsertElemAtIndex(int data, int n)//在指定位置插入指定元素,插入的元素在head之后。
{
int length = this->getLength();
if (n > length||n<1) { cout << "输入的位置不存在" << endl; }
else {
ListNode* p = head;
ListNode* q = head->next;
ListNode* newNode=new ListNode;
newNode->val = data;
newNode->next = NULL;
int i = 0;
for (; i != n; i++) {
p = p->next;
q = q->next;
}
p->next = newNode;
newNode->next = q;
}
}
void LinkList::InsertElemAtHead(int data)//在头部插入指定元素
{
ListNode* newNode = new ListNode;
newNode->val = data;
newNode->next = NULL;
if (head == NULL) { head = newNode; }
else {
newNode->next = head->next;
head->next = newNode;
}
}
void LinkList::DeleteElemAtEnd()//在尾部删除元素
{
if (head == NULL) { cout << "链表为空，无须删除" << endl;; }
else {
ListNode* p = head;
ListNode* q = head->next;
while (q->next != NULL) {
p = p->next;
q = q->next;
}
p->next = NULL;
delete q;
}
}
void LinkList::DeleteAll()//删除所有数据
{
if (head == NULL) { ; }
else {
ListNode* p = head->next;
//ListNode* p_temp = new ListNode;
while (p != NULL) {
/*p_temp = p;
p = p->next;
head->next = p;
p_temp->next = NULL;
delete p_temp;*/
head->next = p->next;
delete p;
p = head->next;
}
}
}
void LinkList::DeleteElemAtPoint(int data)//删除指定的数据
{
//也就是说要考虑data 是否存在的两种情况。
if (findData(data)) {
//如果能够找到该数据
ListNode* p = head;
ListNode* q = head->next;
while (q->val != data) {
p = p->next;
q = q->next;
}
//此时q的值为data,接下来删除q节点。
p->next = q->next;
q->next = NULL;
delete q;
}
}
void LinkList::DeleteElemAtHead()//在头部删除节点
{
if (head == NULL) { ; }
else {
ListNode* p = head;
ListNode* q = head->next;
p->next = q->next;
delete q;
}
}

source.cpp

#include<vector>
using namespace std;
int main()
{
LinkList lst;
int i;
int pos;
int data;
cout << "1.创建单链表
2.遍历单链表
3.获取单链表的长度
4.判断单链表是否为空
5.获取节点n";
cout << "6.在尾部插入指定元素
7.在指定位置插入指定元素
8.在头部插入指定元素n";
cout << "9.在尾部删除元素
10.删除所有元素
11.删除指定元素
12.在头部删除元素
0.退出" << endl;
do {
cout << "请输入指令" << endl;
cin >> i;
switch (i)
{
case 1:
cout << "请输入表单的长度" << endl;
int length;
cin >> length;
lst.CreateLinkList(length);
continue;
case 2:
lst.TravelLinkList();
continue;
case 3:
cout << "该链表的长度为" << lst.getLength()<<endl;
continue;
case 4:
cout << "该链表是否为空 " << lst.isEmpty() << endl;
continue;
case 5:
cout << "输入待寻找的数值：" << endl;
cin >> data;
cout << "是否找到了该数 " << lst.findData(data)<<endl;
continue;
case 6:
cout << "请输入在结尾插入的数据" << endl;
cin >> data;
lst.InsertElemAtEnd(data);
continue;
case 7:
cout << "请输入插入数据的位置" << endl;
cin >> pos;
cout << "请输入插入的数据" << endl;
cin >> data;
lst.InsertElemAtIndex(data, pos);
continue;
case 8:
cout << "请输入插入的数据" << endl;
cin >> data;
lst.InsertElemAtHead(data);
continue;
case 9:
lst.DeleteElemAtEnd();
continue;
case 10:
lst.DeleteAll();
continue;
case 11:
cout << "请输入要删除的数据" << endl;
cin >> pos;
lst.DeleteElemAtPoint(pos);
continue;
case 12:
lst.DeleteElemAtHead();
continue;
default:
break;
}
} while (i != 0);
return 0;
}

最后

以上就是尊敬大地为你收集整理的c++实现带头结点的单链表的基本操作的全部内容，希望文章能够帮你解决c++实现带头结点的单链表的基本操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。