157 lines
3.7 KiB
C++
157 lines
3.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
|
||
#pragma region C++实现的单链表通用模板
|
||
// https://blog.csdn.net/wonggonghong/article/details/21716597
|
||
// C++实现的单链表通用模板
|
||
// https://blog.csdn.net/wonggonghong/article/details/21527577
|
||
//创建一个单链表结构，包含一些常见的操作
|
||
struct Node {
|
||
int element; //节点存储信息可以根据需要修改！
|
||
Node *next;
|
||
};
|
||
|
||
//创建一个空表，并返回表头
|
||
Node *CreateLists() {
|
||
Node *head = new Node;
|
||
head->next = NULL;
|
||
return head;
|
||
}
|
||
|
||
//删除表头为head的该链表
|
||
void DeleteLists(Node *head) {
|
||
Node *P = head->next, *temp;
|
||
head->next = NULL;
|
||
while (P) {
|
||
temp = P->next;
|
||
delete P;
|
||
P = temp;
|
||
}
|
||
}
|
||
|
||
//判断是不是最后一个链表节点
|
||
bool IsLast(Node *P) {
|
||
return P->next == NULL;
|
||
}
|
||
|
||
//按值X进行查询，找到第一个
|
||
Node *Find(int X, Node *head) {
|
||
Node *P = head->next;
|
||
while (P && P->element != X)
|
||
P = P->next;
|
||
return P;
|
||
}
|
||
|
||
//按值X进行查询，找到符合条件的前一个节点
|
||
Node *FindPrevious(int X, Node *head) {
|
||
Node *P = head;
|
||
while (P->next && P->next->element != X)
|
||
P = P->next;
|
||
return P;
|
||
}
|
||
|
||
//按值X进行删除
|
||
void Delete(int X, Node *head) {
|
||
Node *P = FindPrevious(X, head), *temp; //如果没找到X，则返回的是链表最后一项
|
||
if (P->next) {
|
||
temp = P->next;
|
||
P->next = temp->next;
|
||
delete temp;
|
||
}
|
||
}
|
||
|
||
//在节点P后面插入X
|
||
void Insert(Node *P, int X) {
|
||
Node *tempX = new Node;
|
||
tempX->element = X;
|
||
tempX->next = P->next;
|
||
P->next = tempX;
|
||
}
|
||
|
||
//输出链表中所有元素的值
|
||
void OutputLists(Node *head) {
|
||
Node *P = head->next;
|
||
while (P) {
|
||
std::cout << P->element << " ";
|
||
P = P->next;
|
||
}
|
||
std::cout << std::endl;
|
||
}
|
||
|
||
|
||
// 带头节点的单链表元素互换
|
||
void DoExchange(Node *A, Node *B, Node *head) {
|
||
if (A == B)
|
||
return;
|
||
Node *PreA = FindPrevious(A->element, head);
|
||
Node *PreB = FindPrevious(B->element, head);
|
||
Node *PostA = A->next;
|
||
Node *PostB = B->next;
|
||
//先考虑A、B节点相邻的情况
|
||
if (PostA == B) {
|
||
PreA->next = B;
|
||
B->next = A;
|
||
A->next = PostB;
|
||
return;
|
||
}
|
||
if (PostB == A) {
|
||
PreB->next = A;
|
||
A->next = B;
|
||
B->next = PostA;
|
||
return;
|
||
}
|
||
//再考虑其他情况
|
||
PreA->next = B;
|
||
B->next = PostA;
|
||
PreB->next = A;
|
||
A->next = PostB;
|
||
}
|
||
|
||
#pragma endregion C++实现的单链表通用模板
|
||
|
||
|
||
int main() {
|
||
int n, m, p;
|
||
cin >> n >> m >> p;
|
||
|
||
//头节点
|
||
Node *head = CreateLists();
|
||
Node *P = head; //P为一个链表的指针，用它来进行移动
|
||
//读入第一个数字，做为head头
|
||
cin >> head->element;
|
||
|
||
//第二行为n个不相同的数字-->创建链表
|
||
for (int i = 1; i < n; i++) {
|
||
int temp;
|
||
cin >> temp;
|
||
//插入数据
|
||
Insert(P, temp); //P为移动的指针,Data[i]为每一个数据
|
||
//移动P，方便下一次插入数据
|
||
P = P->next;
|
||
}
|
||
//处理m行读入数据
|
||
for (int i = 0; i < m; ++i) {
|
||
int a, b;
|
||
cin >> a >> b;
|
||
//交换两个位置的数据
|
||
Node *A = head;
|
||
Node *B = head;
|
||
for (int j = 1; j < a; ++j) {
|
||
A = A->next;
|
||
}
|
||
for (int j = 1; j < b; ++j) {
|
||
B = B->next;
|
||
}
|
||
DoExchange(A, B, head);
|
||
}
|
||
//输出第p个位置的数字
|
||
Node *A = head;
|
||
for (int i = 1; i < p; ++i) {
|
||
A = A->next;
|
||
}
|
||
cout << A->element << endl;
|
||
return 0;
|
||
}
|