链表合并
题目描述：
已有a、b两个链表，每个链表中的结点包括学号、姓名、成绩。要求把两个链表合并，按学号升序排列。
输入：
第一行，a、b两个链表元素的数量N、M,用空格隔开。接下来N行是a的数据然后M行是b的数据每行数据由学号、姓名和成绩三部分组成。
输出：
按照学号升序排列的数据。
样例输入：
2 3
5 a 100
6 b 89
3 c 82
4 d 95
2 e 10
样例输出：
2 e 10.0
3 c 82.0
4 d 95.0
5 a 100.0
6 b 89.0
# include <iostream>
# include <string>
# include <iomanip>
using namespace std;
struct student {
int number;
float score;
string name;
student* next;
};
student* list(int n)
{
student* p, * head;
p = head = new student;
for (int i = 1; i < n; i++)
{
cin >> p->number >> p->name >> p->score;
p->next = new student;
p = p->next;
}
cin >> p->number >> p->name >> p->score;
p->next = NULL;
return head;
}
student* connect(student* h1, student* h2)
{
student* p;
p = h1;
while (p->next != NULL)
{
p = p->next;
}
p->next = h2;
return h1;
}
void sort(student* head)
{
student* p = head;
for (; p->next != NULL; p = p->next)
{
student* min = p;
student* q;
for (q = p->next; q != NULL; q = q->next)
{
if (min->number > q->number)
{
min = q;
}
}
int t = min->number; min->number = p->number; p->number = t;
float a = min->score; min->score = p->score; p->score = a;
string b = min->name; min->name = p->name; p->name = b;
}
}
void print(student* head)
{
student* p;
for (p = head; p != NULL; p = p->next)
{
cout << p->number << " " << p->name << " " << setprecision(1) << fixed << p->score << endl;
}
}
int main()
{
int n, m;
cin >> n >> m;
student* l1, * l2, * l;
l1 = list(n);
l2 = list(m);
l = connect(l1, l2);
sort(l);
print(l);
return 0;
}
单链表
题目描述：
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第 k 个插入的数后面的数；
- 在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式：
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
1.H x，表示向链表头插入一个数 x。
2.D k，表示删除第 k 个插入的数后面的数（当 k为 0 时，表示删除头结点）。
3.I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式：
共一行，将整个链表从头到尾输出。
数据范围：
1≤M≤100000
所有操作保证合法。
解题代码：
# include <iostream>
using namespace std;
const int N = 100010;
int head, ne[N], e[N], idx;
//head表示头节点下标
//e[i]表示节点i的值
//ne[i]表示e[i]指向的下一个值的下标
//idx 表示存储当前已经用到了那个点，更重要的是表示到了第几次插入数值
//初始化
void init()
{
head = 0;
idx = 1;
}
//将x插入头节点
void add_head(int k)
{
e[idx] = k;//将e[idx]赋值
ne[idx] = head;//将e[idx]下一个值指向空，保证以后每次操作后最后一个节点的ne[i]都为0
head = idx;//将此时的idx确定为头指针
idx++;//为下一次插入做准备
}
//将下标是k的点后面的点删掉
void del(int k)
{
ne[k] = ne[ne[k]];//使下标为k的节点直接指向((下标为k的节点指向的节点)所指向的节点)
//例如：
//1->2->3
//现变为1->3
}
//在下标是k的点的值后面插入n
void insert(int k, int n)
{
e[idx] = n;//将e[idx]赋值
ne[idx] = ne[k];//将现在idx节点指向原来k所指向的节点
ne[k] = idx;//将k节点指向idx,实现idx插入
idx++;//为下一次插入做准备
}
int main()
{
init();
int m, x, k;
cin >> m;
while (m--)
{
char wor;
cin >> wor;
if (wor == 'H')
{
cin >> x;
add_head(x);
}
else if (wor == 'D')
{
cin >> x;
if (!x)head = ne[head];//如果x为0，那么删除头节点
else del(x);
}
else
{
cin >> x >> k;
insert(x, k);
}
}
for (int i = head; i != 0; i = ne[i])//此操作中的i!=0与初始化中的head=0还有add_head中的（ne[idx] = head;）相关联
{
cout << e[i] << " ";
}
cout << endl;
}