C++ 单链表 完整代码模版 数据结构入门 可直接复制运行
单向链表(概念篇+代码)
一、单向链表的概念
二、单向链表的元素插入
三、单向链表的元素删除
四、单向链表的元素查找
五、单向链表的元素索引
六、单向链表的元素修改
七、顺序表完整可运行源码
一、单向链表的概念
1、单链表的概念
对于顺序存储的结构，最大的缺点就是:插入和删除的时候需要移动大量的元素，所以基于前人的智慧，他们发明了链表。
链表是由一个个结点组成，每个结点之间通过链接关系串联起来，每个结点都有一个后继结点，最后一个结点的后继结点为空结点，如图所示：
由链接关系A->B组织起来的两个结点，B被称为A的后继结点，A被称为B的前驱结点。链表分为单向链表、双向链表、循环链表等等。本文只介绍单向链表。
一个链表结点由两部分组成:数据域和指针域。数据可以是任意类型，由编码的人自行指定。指针域指向后继结点的地址。一个结点包含的两部分如下图所示:
2、整个单链表的「类与节点定义 + 析构函数」
为了实现下面函数的所有操作，我们先定义链表的基础结构。以下是不带头结点单链表的完整类声明与析构函数实现：
typedef int eleType;
struct ListNode {
eleType data;
ListNode* next;
// 构造函数
ListNode(eleType x) : data(x), next(NULL) { }
};
class LinkedList {
private:
ListNode* head;
int size;
public:
LinkedList() : head(NULL) , size(0) { } // 构造函数
~LinkedList(); // 析构函数
void insert(int i, eleType value); // 插入
void remove(int i); // 删除
ListNode* find(eleType value); // 查找(按值)
ListNode* get(int i); // 取第i个节点(按索引查找)
void updata(int i, eleType value); // 修改
void print(); // 遍历
};
// 析构函数
LinkedList::~LinkedList() {
ListNode* curr = head;
while (curr) {
ListNode* temp = curr;
curr = curr->next;
delete temp;
}
}
二、单向链表的元素插入
1、元素插入的概念
单向链表的元素插入，就是指给定一个索引i和一个元素data，生成一个值为data的结点，并且插入到第i个位置上。
2、元素插入图解
本次插入操作，是给定一个数值5，要求插入到单向链表的索引为4的位置上。
p(即pre)代表目前正在遍历的结点，当计数到3的时候，p的后继结点a(即aft)也找到了，然后生成值为5的结点vtx，将p的后继指向vtx，将vtx的后继指向a。
3、元素插入的步骤
第1步、判断插入位置是否合法，如果不合法则抛出异常(比如:原本只有5个元素，给定的索引是100，那显然这个位置是不合法的)。
第2步、对给定的元素，生成一个链表结点。
第3步、如果插入位置是0，则直接把生成的结点的后继结点，设置为当前的链表头结点，并且把生成的结点设置为新的链表头。
第4步、如果插入位置不是0，则遍历到插入位置的前一个位置，把生成的结点插入进来。
第5步、更新链表的大小，即对链表的大小执行加一操作。
4、伪代码实现
// 插入
void LinkedList::insert(int i, eleType value) {
// 判断查如位置合法化 [0,size]
if (i < 0 || i > size) {
throw std::out_of_range("Invaild position");
}
// 用ListNode中的构造函数创建新节点
ListNode* newNode = new ListNode(value);
// 创建的是没有头结点的链表,当插入位置为0时,直接修改head首节点
if (i == 0) {
newNode->next = head;
head = newNode;
}
else { // 其他合法位置
ListNode* curr = head;
for (int j = 0; j < i - 1; j++) { //
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
}
size++;
}
三、单向链表的元素删除
1、元素删除的概念
单向链表的元素删除，就是指给定一个索引i，将从链表头开始数到的第i个结点删除。
2、元素删除的图解
要求删除索引为4的链表结点，从前往后遍历链表，当遍历到索引为3的链表结点，则将它的后继结点存储到del 中，并且将它的后继指向它后继的后继。
3、元素删除的步骤
第1步、判断删除位置是否合法，如果不合法则抛出异常。
第2步、如果删除位置为首个结点，直接把链表头更新为它的后继结点。
第3步、如果删除位置非首个结点，则遍历到要删除位置的前一个结点，并且把前一个结点的后继结点设置为它后继的后继。
第4步、更新链表的大小，也就是将链表的大小执行减一操作。
4、伪代码实现
// 删除
void LinkedList::remove(int i) {
// 判断删除位置合法化 [1,size-1]
if (i < 0 || i >= size) {
throw std::out_of_range("Invaild position");
}
// 删除首节点
if (i == 0) {
ListNode* curr = head;
head = curr->next;
delete curr;
}
else { // 删除其他合法节点
ListNode* curr = head;
for (int j = 0; j < i - 1; j++) { // 找前驱
curr = curr->next;
}
ListNode* tmp = curr->next;
curr->next = tmp->next;
delete tmp;
}
size--;
}
四、单向链表的元素查找
1、元素查找的概念
单向链表的元素查找，是指在链表中查找指定元素x是否存在，如果存在则返回该结点，否则返回NULL。由于需要遍历整个链表进行元素对比，所以查找的时间复杂度为0(n)。
2、元素查找的图解
如图所示，要求查找值为8的结点，从链表头结点开始遍历，直到遍历到值为8到结点以后，返回这个结点。
3、元素查找的步骤
第1步、遍历整个链表，对链表中的每个元素，和指定元素进行比较，如果相等则返回当前遍历到的结点
;第2步、如果遍历完整个链表，都没有找到相等的元素，则返回NULL;
4、伪代码实现
// 查找(按值)
ListNode* LinkedList::find(eleType value){
ListNode* curr = head;
while(curr && curr->data != value){
curr = curr->next;
}
return curr;
}
五、单向链表的元素索引
1、元素索引的概念
单向链表的元素索引，是指给定一个索引值i，从链表头结点开始数，数到第i个结点并且返回它，时间复杂度0(n)。
2、元素索引的图解
给定的索引值是5，tmp代表当前遍历到的结点，记录一个变量j，j自增的过程，判断是否和5相等，如果相等则代表找到对应的结点，直接返回图中值为8的结点。
3、元素索引的步骤
第1步、首先判断给定的索引是否合法，不合法就抛出异常;
第2步、直接通过索引访问即可获得对应的元素;
4、伪代码实现
// 取第i个节点(按索引查找)
ListNode* LinkedList::get(int i) {
// 判断取节点位置合法
if (i < 0 || i >= size) {
throw std::out_of_range("Invaild position");
}
ListNode* curr = head;
for (int j = 0; j < i; j++) { // 找目标本身
curr = curr->next;
}
return curr;
}
六、单向链表的元素修改
1、元素修改的概念
单向链表的元素修改是指将链表中指定索引的元素更新为新的值。
2、元素索引的步骤
直接通过索引访问即可获得对应的节点,修改成指定的值;
3、伪代码实现
// 修改
void LinkedList::updata(int i, eleType value) {
get(i)->data = value;
}
七、单链表完整可运行源码
#include<iostream>
#include<stdexcept>
using namespace std;
typedef int eleType;
struct ListNode {
eleType data;
ListNode* next;
// 构造函数
ListNode(eleType x) : data(x), next(NULL) { }
};
class LinkedList {
private:
ListNode* head;
int size;
public:
LinkedList() : head(NULL) , size(0) { } // 构造函数
~LinkedList(); // 析构函数
void insert(int i, eleType value); // 插入
void remove(int i); // 删除
ListNode* find(eleType value); // 查找(按值)
ListNode* get(int i); // 取第i个节点(按索引查找)
void updata(int i, eleType value); // 修改
void print(); // 遍历
};
// 析构函数
LinkedList::~LinkedList() {
ListNode* curr = head;
while (curr) {
ListNode* temp = curr;
curr = curr->next;
delete temp;
}
}
// 插入
void LinkedList::insert(int i, eleType value) {
// 判断查如位置合法化 [0,size]
if (i < 0 || i > size) {
throw std::out_of_range("Invaild position");
}
// 用ListNode中的构造函数创建新节点
ListNode* newNode = new ListNode(value);
// 创建的是没有头结点的链表,当插入位置为0时,直接修改head首节点
if (i == 0) {
newNode->next = head;
head = newNode;
}
else { // 其他合法位置
ListNode* curr = head;
for (int j = 0; j < i - 1; j++) { //
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
}
size++;
}
// 删除
void LinkedList::remove(int i) {
// 判断删除位置合法化 [1,size-1]
if (i < 0 || i >= size) {
throw std::out_of_range("Invaild position");
}
// 删除首节点
if (i == 0) {
ListNode* curr = head;
head = curr->next;
delete curr;
}
else { // 删除其他合法节点
ListNode* curr = head;
for (int j = 0; j < i - 1; j++) { // 找前驱
curr = curr->next;
}
ListNode* tmp = curr->next;
curr->next = tmp->next;
delete tmp;
}
size--;
}
// 查找(按值)
ListNode* LinkedList::find(eleType value) {
ListNode* curr = head;
while (curr && curr->data != value) { //
curr = curr->next;
}
return curr;
}
// 取第i个节点(按索引查找)
ListNode* LinkedList::get(int i) {
// 判断取节点位置合法
if (i < 0 || i >= size) {
throw std::out_of_range("Invaild position");
}
ListNode* curr = head;
for (int j = 0; j < i; j++) { // 找目标本身
curr = curr->next;
}
return curr;
}
// 修改
void LinkedList::updata(int i, eleType value) {
get(i)->data = value;
}
// 打印
void LinkedList::print() {
ListNode* curr = head;
for (int i = 0; i < size; i++) {
cout << curr->data << " ";
curr = curr->next;
}
cout << endl;
}
int main()
{
LinkedList list;
cout << "1. 插入5个元素: ";
list.insert(0, 10);
list.insert(1, 20);
list.insert(2, 30);
list.insert(3, 40);
list.insert(4, 50);
list.print();
cout << "2. 删除索引为2的元素: ";
list.remove(2);
list.print();
cout << "3. 查找(按值): ";
ListNode* curr1 = list.find(10);
cout << curr1->data << "\n";
cout << "4. 取第4个节点的值: ";
ListNode* curr2 = list.get(3);
cout << curr2->data << endl;
cout << "5. 修改链表索引为0的值: ";
list.updata(0, 1314);
list.print();
return 0;
}
更多推荐
15
0- 0
已为社区贡献5条内容
所有评论(0)