#include<iostream>
#include<stdexcept>
using namespace std;
#define eleType double
struct ListNode {//初始化 链表结点结构体
eleType data;//数据域
ListNode* next;//指针域
ListNode(eleType x):data(x),next(NULL){}
};
class LinkedList {
private:
ListNode* head;//头节点Private
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);//拿
void update(int i, eleType value);//更新
void print();//打印
};
//任何一个数据都是增删改查 搞清楚就可以
//析构函数
LinkedList::~LinkedList() {
ListNode* curr = head; //析构函数 从头节点开始 赋值给current
while (curr != NULL) {//当current不等于空的情况下
ListNode* tmp = curr;//把当前存储在tmp中
curr = curr->next;//把当前节点置为它的后继节点
delete tmp;//tmp游离掉了 所以把它删除掉
}
}
//链表元素的插入
void LinkedList::insert(int i, eleType value) {
if(i<0||i>size){//判断下标是否合法
throw std::out_of_range(“Invali position”); //std也可以省
}
ListNode* newNode = new ListNode(value);//调用一个ListNode的构造函数
if (i == 0) {//插入头结点的过程
newNode->next = head;//插入到链表头 必然要指向当前的头结点
head = newNode;//当前的头节点被替换掉了 需要重新赋值
}
else {//不是插入头结点的情况
ListNode* curr = head;//定义一个游标节点 当i等于1时 curr 不走 就等于链表头结点
for (int j = 0; j < i – 1; j++) {//这里的i一定从1开始
curr = curr->next;//一直遍历 让头结点等于它的后继 这个curr代表插入位置的前一个位置
}
//遍历完毕后 curr的值就是你要插入位置的前一个结点
newNode->next = curr->next;
curr->next = newNode;//以上两行不能交换 不然会形成一个环 自环
//遇到链表问题 最好方法是画图 画好图就自然知道怎么写了
}
++size;//代表加入了新的结点
}
//链表元素删除
void LinkedList::remove(int i) {
if (i < 0 || i >= size) {//看有没有超出范围
throw std::out_of_range(“Invalid position”);
}
if (i == 0) {//链表头结点删除的情况
ListNode* temp = head;//删除前的头结点游离出来
head = head->next;
delete temp;
}
else {//如果不是删除头结点 那就遍历这个链表
ListNode* curr = head; //current 从head开始
for (int j = 0; j < i – 1; j++) {//当i=1时这个循环不走 i=1时就是头结点 i=1时就是要删除头结点后面那个元素
curr = curr->next;
}
ListNode* temp = curr->next; //我们先把头结点后面那个元素给它存起来
curr->next = temp->next;//把要删除结点的前驱结点的后继置为要删除结点的后继
delete temp;//最后删除要删除的结点
}
–size;
}
//链表元素的查找过程
ListNode* LinkedList::find(eleType value) {
ListNode* curr = head;//从头结点开始
while (curr && curr->data != value) { //当前结点不等于空并且不等于传进来的value的时候
curr = curr->next; //然当前结点的值等于它的后继
//这样子要么链表遍历完 要么是找到一个跟value相等的情况
}
//当current = null的时候代表链表遍历完了
//如果链表遍历完没有找到 那么返回的是空结点
//如果链表没有遍历完跳出了循环 说明一定找到了一个值相等的结点
return curr;
}
//链表的索引 查找索引的过程
ListNode* LinkedList::get(int i) { //跟顺序表的命名统一
if (i < 0 || i >= size) {
throw std::out_of_range(“Invalid position”);
}
ListNode* curr = head;//初始化 从链表头结点开始 //当i等于0时返回根结点 当i等于1时就是根结点的后继结点 当i等于2时就是根结点的后继结点的后继结点
for (int j = 0; j < i; ++j) {//我执行i次迭代操作 当i等于2时就是根结点的后继结点的后继结点
curr = curr->next;//每次操作都把Current变成它的后继 跟插入删除查找做的一样
}
return curr;//所以curr就是我们要找的第i个结点了
}
//更新的过程
//更新：找到链表的第i个结点 并且把它的值更新为value
void LinkedList::update(int i,eleType value) {
get(i)->data = value;//直接调用get(i)找到链表的结点 然后直接拿它的数据更新掉
//这个是结构体指针 所以直接用箭头来取它的成员变量 取成员变量后进行赋值就好了
}
//调试函数
void LinkedList::print() {
ListNode* curr = head;
while (curr) {//如果说current不等于空 我们就输出current上的数据
cout << curr->data << ” “;
curr = curr->next;//然后让curr 等于它的后继
}
//我们无时无刻都在遍历这个列表
cout << endl;//最后换行
}
//一定要自己写一遍 会遇到 各种错误 但是解决问题的过程中才会成长
int main() {
LinkedList list;
list.insert(0, 10);//在第0个位置插入一个10
list.insert(1, 20);
list.insert(2, 30);
list.insert(3, 40);
list.insert(4, 50);
list.print();
list.remove(1);
list.print();
list.update(2, 666);
list.print();
ListNode* tmp = list.find(30);//找到30这个元素 存储到tmp里面
cout << tmp->data << endl; //找的元素肯定是30
cout << list.get(3)->data << endl;//找到第三个元素的值到底是多少
return 0;
}