C++实现单链表（Single Linked List）
语言这个东西不用真的会忘， 我记得前前后后C++的基本语法我也看了好几遍了，一直没有动手写过什么东西，所以一遍遍的看，一遍遍的忘... ...
正好最近在看数据结构，想着自己用C++来实现一下，一方面是熟悉整个逻辑过程，加深对数据结构的理解，另一方面，也熟悉一下C++。
单链表是线性表的链式存储结构，同顺序存储结构（可以理解为C++中的数组）不同的是，单链表在插入和删除一个结点时，不需要移动大量的元素，但是单链表没有数组中索引的概念，所以在查询一个元素时没有数组方便。
单链表由结点（Node）组成，结点中有一个数据域和一个指针域，数据域存放结点中的数据，指针域指向下一个结点的地址，我们所实现的单链表是带有头结点的单链表，与其他结点不同，头结点中的数据域不存放数据。下图是结点和单链表结构的示意图。
结点示意图:
Node
单链表示意图:
Single Linked List
需要说明的是，我的这个程序中的索引是从0开始的，而且默认数据都是正的
int类型。
单链表的类定义：
class LinkList {
private:
class Node {
public:
int data;
Node *next;
};
Node *head;
int length = 0;
public:
LinkList();
void create(int n);//初始化n个结点的单链表
void print() const;//打印单链表中的数据
int getLength() const;//获取单链表的长度
void isEmpty() const;//判断单链表是否为空
int search(int index) const;//查找索引为index的数据并返回
int find(int elem) const;//查找数据为elem的索引并返回
void insertByIndex(int index, int data);//在索引为index之前的位置插入数据为data的结点
void deleteByIndex(int index);//删除索引为index的结点
};
类中的函数实现：
LinkList::LinkList() {
head = new Node;
head->data = 0;
head->next = nullptr;
}
int LinkList::getLength() const {
cout << "链表中的元素个数为：" << length << endl;
return length;
}
void LinkList::create(int n) {
Node *pre = head;
length = n;
int i = 1;
while (i <= n) {
cout << "请输入第" << i << "个结点的数据：";
Node *cur = new Node;
cin >> cur->data;
++i;
pre->next = cur;
pre = cur;
cur->next = nullptr;
}
}
void LinkList::print() const {
Node *cur = head->next;
if (!length) {
cout << "链表为空！" << endl;
return;
}
cout << "*******************" << endl;
cout << "链表中的元素为：" << endl;
while (cur) {
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
cout << "*******************" << endl;
}
void LinkList::isEmpty() const {
if (!length) {
cout << "链表为空~" << endl;
return;
}
cout << "链表不为空" << "，";
this->getLength();
}
int LinkList::search(int index) const { //认为索引从0开始
if (index < 0 || index >= length)
cout << "索引输入错误！" << endl;
else {
Node *temp = head->next;
int i = 0;
while (temp) {
if (i == index) {
cout << "链表中索引为" << index << "的数据为" << temp->data << endl;
return temp->data;
} else {
++i;
temp = temp->next;
}
}
}
return -1;//假定链表中不存入负数
}
int LinkList::find(int elem) const {
Node *cur = head->next;
int index = 0;
while (cur) {
if (cur->data == elem)
return index;
else {
cur = cur->next;
++index;
}
}
cout << elem << "不在链表中！" << endl;
return -1;
}
void LinkList::insertByIndex(int index, int data) { //在index之前插入数据为data的结点
if (index < 0 || index >= length) {
cout << "索引位置不合法" << endl;
} else {
Node *cur = head;
int pos = 0;
while (pos != index) {
cur = cur->next;
++pos;
}
Node *temp = new Node;
temp->data = data;
temp->next = cur->next;
cur->next = temp;
++length;
cout << data << "插入成功！" << endl;
}
}
void LinkList::deleteByIndex(int index) {
if (index < 0 || index >= length) {
cout << "索引输入错误！" << endl;
} else {
Node *cur = head;
int pos = 0;
while (pos != index) {
cur = cur->next;
++pos;
}
Node *temp = cur->next;
cur->next = temp->next;
delete temp;
--length;
cout << "删除成功!" << endl;
}
}
测试代码：
/*
* Software:Jetbrains clion 2022.1
* Created by xiaoxin_zh@foxmail.com
* Implementing Singly Linked List with C++
*/
#include <iostram>
using std::cin;
using std::cout;
using std::endl;
int main() {
LinkList linkList;
cout << "请输入链表中结点的个数：";
int n;
cin >> n;
linkList.create(n);
linkList.print();
linkList.getLength();
linkList.isEmpty();
cout << "请输入需要查询的索引位置：";
int index;
cin >> index;
linkList.search(index);
cout << "请输入需要查询的数据:";
int elem;
cin >> elem;
if (linkList.find(elem) != -1) {
cout << elem << "在链表中的索引位置是" << linkList.find(elem) << endl;
}
cout << "请输入需要插入结点的位置索引和数值：";
int pos, data;
cin >> pos >> data;
linkList.insertByIndex(pos, data);
linkList.print();
linkList.getLength();
cout << "请输入需要删除的结点索引：";
int deleteIndex;
cin >> deleteIndex;
linkList.deleteByIndex(deleteIndex);
linkList.print();
linkList.getLength();
return 0;
}
假设实现的原始单链表有4个结点，数值分别为12、23、34、45，结构如图所示：
create
查询索引为1的元素，应该返回23；
查找数据为45的索引位置，应该返回3；
在索引为2的前面插入一个数值为88的结点，其步骤如图所示：
insert
删除索引为3的结点，其步骤如图所示：
delete
测试代码执行：
result
