A - 数据结构实验之链表一：顺序建立链表
Description
输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。
Input
第一行输入整数的个数N；
第二行依次输入每个整数。
Output
输出这组整数。
Sample
Input
8 12 56 4 6 55 15 33 62
Output
12 56 4 6 55 15 33 62
Hint
不得使用数组！
// 尾插法
#include <iostream>
using namespace std;
struct node
{int data;struct node *next;
};int main()
{int n;struct node *head, *tail, *p;// 头、尾、游动指针head = new node;// c++里可以这样写，c中应该要用mallochead -> next = NULL;// 将头指针初始化tail = head;// ？cin >> n;for(int i = 0; i < n; i++){p = new node;// ？这行没有的话会出现警告cin >> p->data;// 输入链表中的每个数p -> next = NULL;// tail -> next = p;// 将每个新的数字放到链表尾部tail = p;// 更新尾指针}p = head -> next;while(p){if(p -> next == NULL){// 最后一个数cout << p->data;}else{cout << p->data << " ";}p = p -> next;// 更新p，遍历链表}return 0;
}
**当链表顺序插入结点后，尾指针的值要随之修改，以指向新的尾结点。
c：
#include<stdio.h>
#include<stdlib.h>struct node
{int data;struct node *next;
};
int main()
{struct node *head, *tail, *p;// 头指针，尾指针，游动指针// 为链表开辟空间并设为空head = (struct node*)malloc(sizeof(struct node));head->next = NULL;tail = head;int n;scanf("%d", &n);// 尾插法for(int i = 0; i < n; i++){p = (struct node*)malloc(sizeof(struct node));scanf("%d", &p->data);p->next = NULL;tail->next = p;tail = p;// 更新尾结点}p = head->next;while(p){if(p->next == NULL) printf("%d\n", p->data);else printf("%d ", p->data);p = p->next;}// 顺序输出链表的方法return 0;
}
B - 数据结构实验之链表二：逆序建立链表
Description
输入整数个数N，再输入N个整数，按照这些整数输入的相反顺序建立单链表，并依次遍历输出单链表的数据。
Input
第一行输入整数N;；
第二行依次输入N个整数，逆序建立单链表。
Output
依次输出单链表所存放的数据。
Sample
Input
10 11 3 5 27 9 12 43 16 84 22
Output
22 84 16 43 12 9 27 5 3 11
Hint
不能使用数组！
/*头插法*/
#include<iostream>
using namespace std;
struct node
{int data;struct node *next;
};
int main()
{int n;struct node *head, *p;head = new node;head -> next = NULL;cin >> n;for(int i = 0; i < n; i++){p = new node;cin >> p -> data;p -> next = head -> next;// 觉得这个操作是关键！！头插法的灵魂head -> next = p;}p = head -> next;while(p != NULL){if(p -> next != NULL){cout << p -> data << " ";}else{cout << p -> data;}p = p -> next;}return 0;
}
C - 师--链表的结点插入
Description
给出一个只有头指针的链表和 n 次操作，每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。
Input
多组输入。每组数据首先输入一个整数n(n∈[1,100])，代表有n次操作。
接下来的n行，每行有两个整数Mi(Mi∈[0,10000])，Xi。
Output
对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。
Sample
Input
4 1 1 1 2 0 3 100 4
Output
3 1 2 4
Hint
样例中第一次操作1 1，由于此时链表中没有元素，1>0,所以此时将第一个数据插入到链表的最后，也就是头指针的后面。
#include<iostream>
using namespace std;
typedef struct node
{int data;struct node *next;
}tree;int main()
{int n, m, x;struct node *head, *tail, *p, *q;while(cin >> n){head = new tree;// 分配地址head -> next = NULL;tail = head;// 若是空链表则头尾节点一样 while(n > 0){q = head;cin >> m >> x;while(m-- && q -> next){q = q -> next;}p = new tree;p -> data = x;p -> next = NULL;p -> next = q -> next;q -> next = p;n--;}p = head -> next;while(p){if(p -> next == NULL)cout << p->data << endl;elsecout << p->data << " ";p = p -> next;}}return 0;
}D - 数据结构实验之链表七：单链表中重复元素的删除
Description
按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
Input
第一行输入元素个数 n (1 <= n <= 15)；
第二行输入 n 个整数，保证在 int 范围内。
Output
第一行输出初始链表元素个数；
第二行输出按照逆位序所建立的初始链表；
第三行输出删除重复元素后的单链表元素个数；
第四行输出删除重复元素后的单链表。
Sample
Input
10 21 30 14 55 32 63 11 30 55 30
Output
10 30 55 30 11 63 32 55 14 30 21 7 30 55 11 63 32 14 21
#include<iostream>
using namespace std;
typedef struct node
{int data;struct node *next;}tree;int main()
{int n;tree *head, *p, *q, *w;head = new tree;head->next = NULL;cin >> n;for (int i = 0; i < n; i++) {p = new tree;cin >> p->data;p->next = head->next;head->next = p;}cout << n << endl;p = head->next;while (p) {if (p->next == NULL) {cout << p->data << endl;}else {cout << p->data << " ";}p = p->next;}p = head->next;while (p) {q = p;w = q->next;while (w) {if (w->data == p->data) {n--;q->next = w->next;w = w->next;}else {q = w;w = w->next;}}p = p->next;}cout << n << endl;p = head->next;while (p) {if (p->next == NULL) {cout << p->data << endl;}else {cout << p->data << " ";}p = p->next;}return 0;
}E - 数据结构实验之链表三：链表的逆置
Description
输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表的数据进行逆置，并输出逆置后的单链表数据。
Input
输入多个整数，以-1作为结束标志。
Output
输出逆置后的单链表数据。
Sample
Input
12 56 4 6 55 15 33 62 -1
Output
62 33 15 55 6 4 56 12
Hint
不得使用数组。
#include<iostream>
using namespace std;
typedef struct node
{int data;struct node *next;
}tree;
int main()
{tree *head, *p;head = new tree;head->next = NULL;int m;while (cin >> m && m != -1) {p = new tree;p->data = m;p->next = head->next;head->next = p;}p = head->next;while (p) {if (p->next == NULL) {cout << p->data;}else {cout << p->data << " ";}p = p->next;}return 0;
}F - 数据结构实验之链表四：有序链表的归并
Description
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
Input
第一行输入M与N的值；
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。
Output
输出合并后的单链表所包含的M+N个有序的整数。
Sample
Input
6 5 1 23 26 45 66 99 14 21 28 50 100
Output
1 14 21 23 26 28 45 50 66 99 100
Hint
不得使用数组！
#include<bits/stdc++.h>
using namespace std;
typedef struct node
{int data;struct node *next;
}tree;
// 两个链表
struct node *h1, *p1, *t1;
struct node *h2, *p2, *t2;
int main()
{int m, n;cin >> m >> n;h1 = new tree;h2 = new tree;h1 -> next = NULL;h2 -> next = NULL;t1 = h1;t2 = h2;// 开始建链表while(m--){p1 = new tree;cin >> p1 -> data;p1 -> next = NULL;t1 -> next = p1;t1 = p1;}while(n--){p2 = new tree;cin >> p2 -> data;p2 -> next = NULL;t2 -> next = p2;t2 = p2;}// （开始操作hhh） 再建一个链表struct node *h, *p, *t;h = h1;p1 = h1 -> next;p2 = h2 -> next;free(h2);// 释放链表二的头部t = h1;// 第三个表的尾指针指向第一个表的头部，（尾插法吧？）while(p1 && p2){// 当两个链表都没遍历完时// 谁小谁在前if(p1 -> data < p2 -> data){t -> next = p1;t = p1;p1 = p1 -> next;}else{t -> next = p2;t = p2; p2 = p2 -> next;}// 总有一个先遍历完，对吧if(p1 != 0){t -> next = p1;}else{t -> next = p2;}}// 输出辣p = h -> next;while(p -> next){cout << p -> data << " " ;p = p -> next;}cout << p -> data ;system("pause");return 0;
}G - 数据结构实验之链表五：单链表的拆分
Description
输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。
Input
第一行输入整数N;；
第二行依次输入N个整数。
Output
第一行分别输出偶数链表与奇数链表的元素个数；
第二行依次输出偶数子链表的所有数据；
第三行依次输出奇数子链表的所有数据。
Sample
Input
10 1 3 22 8 15 999 9 44 6 1001
Output
4 6 22 8 44 6 1 3 15 999 9 1001
Hint
不得使用数组！
// 代码较长，如果想更加清晰最好利用函数！
#include<bits/stdc++.h>
using namespace std;struct node *star(int n);// 建表函数
void division(struct node *h, struct node *h1, struct node *h2, int *data1, int *data2);// 拆分函数
void print(struct node *h);// 输出函数
typedef struct node
{int data;struct node *next;
}tree;
// 思路与上一题差不多。不过是先建一个链表 再建两个链表
int main()
{int n, data1 = 0, data2 = 0;struct node *h;struct node *h1, *h2;h1 = new tree;h1 -> next = NULL;h2 = new tree;h2 -> next = NULL; cin >> n;h = star(n);division(h, h1, h2, &data1, &data2);cout << data1 << " " << data2 << endl;print(h1);print(h2);system("pause");return 0;
}
struct node *star(int n)
{struct node *h, *p, *t;h = new tree;h -> next = NULL;t = h;for(int i = 0; i < n; i++){p = new tree;p -> next = NULL;cin >> p -> data;t -> next = p;t = p;}return (h);
}
void division(struct node *h, struct node *h1, struct node *h2, int *data1, int *data2)
{struct node *p = h -> next;struct node *t1 = h1, *t2 = h2;free(h);while(p){if(p -> data % 2 == 0){// 偶数t1 -> next = p;t1 = p;p = p -> next;t1 -> next = NULL;(*data1)++;// 好神奇！}else{// 奇数t2 -> next = p;t2 = p;p = p -> next;t2 -> next = NULL;(*data2)++;}}
}
void print(struct node *h)
{struct node *p = h -> next;while(p){if(p != NULL){cout << p -> data << " ";}else{cout << p -> data;}p = p -> next;}cout << endl;
}H - 数据结构实验之链表九：双向链表
Description
学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B，他们的关系是B是A的后继，A指向了B，便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。
Input
第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。第二行是n个数（n个数没有重复），利用这n个数建立双向链表。接下来有m个关键字，每个占一行。
Output
对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。
注意：每个给定关键字的输出占一行。一行输出的数据之间有一个空格，行首、行末无空格。
Sample
Input
10 3 1 2 3 4 5 6 7 8 9 0 3 5 0
Output
2 4 4 6 9
#include<bits/stdc++.h>
using namespace std;typedef struct node
{int data;struct node *next;struct node *before;
}tree;
int main()
{int n, m, x;struct node *h, *p, *t;h = new tree;h -> next = NULL;t = h;cin >> n >> m;for(int i = 0; i < n; i++){p = new tree;cin >> p -> data;p -> next = NULL;t -> next = p;p -> before = t;t = p;}for(int i = 1; i <= m; i++){int j = 0;cin >> x;for(p = h -> next; p != NULL; p = p -> next){j++;if(j == n && p -> data == x){cout << p -> before -> data << endl;}else if(j== 1 && p -> data == x){cout << p -> next -> data << endl;}else if(p -> data == x){cout << p -> before -> data << " " << p -> next -> data << endl;}}}system("pause");return 0;
}I - 约瑟夫问题
Description
n个人想玩残酷的死亡游戏，游戏规则如下：
n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。
请输出最后一个人的编号。
Input
输入n和m值。
Output
输出胜利者的编号。
Sample
Input
5 3
Output
4
Hint
第一轮：3被杀第二轮：1被杀第三轮：5被杀第四轮：2被杀
#include<bits/stdc++.h>
using namespace std;struct node *creat(int n);
int sel(struct node *h,int m, int n);
typedef struct node
{int num;struct node *next;
}tree;
int main()
{int n, m;struct node *h;cin >> n >> m;h = creat(n);cout << sel(h, m, n);system("pause");return 0;
}
struct node *creat(int n)// 创建链表 的函数
{struct node *h, *p, *t;p = new tree;p -> num = 1;p -> next = NULL;h = p;t = p;for(int i = 2; i <= n; i++){p = new tree;p -> num = i;// 不同之处：这个链表里的数是 1、2、3……t -> next = p;t = p;p -> next = NULL;}t ->next = h;// 不同之处：最后一个节点的指针域指向第一个节点return h;
}
int sel(struct node *h,int m, int n)
{int num = 0;// 表示报数计数的计数变量struct node *p, *q;// 分别指向当前节点及其前驱动点的指针q = h;while(q -> next != h){q = q -> next;// 使前驱动点指向尾节点}while(q -> next != q){// 若q -> next == q，则说明此时链表只剩一个节点了p = q -> next;num++;if(num % m == 0){q -> next = p -> next;// 删去了pfree(p);// 释放p。养成好习惯1}else{q = p;}}return q -> num;
}
// 我好没用啊J - 不敢死队问题
Description
说到“敢死队”，大家不要以为我来介绍电影了，因为数据结构里真有这么道程序设计题目，原题如下：
有M个敢死队员要炸掉敌人的一个碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
这题本来就叫“敢死队”。“谁都不想去”，就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号，按照上面介绍，从1号开始数，数到5的那名战士去执行任务，那么排长是第几个去执行任务的？
Input
输入包括多组数据，每组一行，包含一个整数M（0<=M<=10000)（敢死队人数），若M==0，输入结束，不做处理。
Output
输出一个整数n，代表排长是第n个去执行任务。
Sample
Input
9 6 223 0
Output
2 6 132
#include<bits/stdc++.h>
using namespace std;struct node *creat(int n);
int sel(struct node *h,int m, int a);
typedef struct node
{int num;struct node *next;
}tree;
int main()
{int m;int a = 5;struct node *h;while(cin >> m){if(m == 0){return 0;}else{h = creat(m);cout << sel(h, m, a) << endl;}}system("pause");return 0;
}
struct node *creat(int m)// 创建链表 的函数
{struct node *h, *p, *t;p = new tree;p -> num = 1;p -> next = NULL;h = p;t = p;for(int i = 2; i <= m; i++){p = new tree;p -> num = i;// 不同之处：这个链表里的数是 1、2、3……t -> next = p;t = p;p -> next = NULL;}t ->next = h;// 不同之处：最后一个节点的指针域指向第一个节点return h;
}
int sel(struct node *h,int m, int a)
{int num = 0;// 表示报数计数的计数变量int cnt = 0;struct node *p, *q;// 分别指向当前节点及其前驱动点的指针q = h;while(q -> next != h){q = q -> next;// 使前驱动点指向尾节点}while(cnt < m - 1){// 若q -> next == q，则说明此时链表只剩一个节点了p = q -> next;num++;if(num % a == 0){if(p -> num == 1){break;}else{q -> next = p -> next;// 删去了pfree(p);// 释放p。养成好习惯1cnt++;}}else{q = p;}}return (cnt+1);
}
// 我是fw
**和上一题基本一样