#include<iostream>
using namespace std;
struct LinkNode{
int data;
LinkNode *link;
};
typedef LinkNode* NodePtr;
//头部插入
void Insert(NodePtr &head, int data){
NodePtr temp = new LinkNode;
temp -> link = head;
temp -> data = data;
head = temp;
}
//迭代输出
void Iter(NodePtr head){
for(NodePtr here = head; here != 0; here = here -> link){
cout << here -> data << endl;
}
}
//搜索 data 返回指针
NodePtr Search(NodePtr head, int target){
for(NodePtr here = head; here != 0; here = here -> link){
if(here -> data == target){
return here;
}
}
}
//后插入
void AfterInit(NodePtr head, int target, int value){
NodePtr afterMe = Search(head, target);
NodePtr newNode = new LinkNode;
newNode -> link = afterMe -> link;
newNode -> data = value;
afterMe -> link = newNode;
}
//前插入
void BeforeInit(NodePtr head, int target, int value){
NodePtr beforeMe = Search(head, target); //位于新元素之后
NodePtr newNode = new LinkNode;
newNode -> data = value;
for(NodePtr here = head; here != 0; here = here -> link){
if(here -> link == beforeMe){
//此时的 here 就是新元素之前的元素
here -> link = newNode;
newNode -> link = beforeMe;
break;
}
}
}
int main(){
NodePtr head;
head = new LinkNode;
head -> data = 13;
head -> link = 0;
cout << head -> data << endl << "---" << endl;
Insert(head, 11);
Insert(head, 10);
Insert(head, 9);
Insert(head, 8);
Iter(head);
cout << "---" << endl;
BeforeInit(head, 13, 12);
Iter(head);
return 0;
}
head -> data = 12;
head -> link = nullptr; //指向“空”
这样，我们就造好了一个链表。可以用以下代码验证我们真的把数据存进去了：
cout << head -> data;
二、在链表的头部插入节点
链表的头部，通常被称作首元节点。我们现在写一个函数，使得可以插入任意链表的头部。
假设头指针已经定义好为head。
void InsertAfterHead(ListNodePtr &head, int data){
//注意，上方 head 前要有“&”，因为我们需要修改 head 的值。
cin >> data; //传入新节点 data
ListNodePtr temp; //创建一个“指向新节点的指针”
temp = new ListNode; //该指针指向一个新节点
temp -> data = data; //把 data 写入新节点
temp -> link = head; //新节点的指针用原来的头指针
head = temp; //把原来的头指针换做“指向新节点的指针”
}
三、查找节点
假设有下图的结构，我们需要查找第一项值为9的节点，并将其改为6。
链表示意图2
我们设计一个函数，返回值类型是指针，以命中符合要求的链表的节点。
LinkNodePtr Search(LinkNodePtr head, int target){
//head 为头指针，target 是要查找的目标值
LinkNodePtr here = head; //设置一个指针，并使之指向头部
bool gotIt = false; //设置一个判断标志，如果标志为真则证明找到了目标
for(; here != nullptr; here = here -> link){
//当指针没有到链表尾部（为空）时进行，并搜索完一个就跳到下一个链表的地址
if(here -> data == target){
gotIt = true;
break;
//如果找到了，就退出循环
}
}
if(gotIt) return here;
else return nullptr;
}
LinkNodePtr target = Search(head, 9);
target -> data = 6;
对于上述代码中的 for 循环行为，有一个很酷的名字——迭代。指针here叫做迭代器。
for(LinkNodePtr here = head; here != nullptr; here = here -> link){
//需要迭代做的事情
}
比如这样就可以逐一打印链表的数据：
for(LinkNodePtr here = head; here != nullptr; here = here -> link){
cout << here -> data << endl;
}
四、插入节点
假如我们需要找到第一个值为6的节点，并在其后插入数据9。
我们写一个插入函数，可以在指定的地址after_me后插入一个节点。
void Insert(LinkNodePtr &after_me, int data){
LinkNodePtr temp;
temp = new LinkNode;
temp -> data = data;
temp -> link = after_me -> link;
after_me -> link = temp;
}
