|
|
#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;
|
|
|
}
|
