1-1 数据结构实验之链表一：顺序建立链表
任务描述:
输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。
输入格式:
第一行输入整数的个数N(1 <= N <= 100000)。第二行依次输入每个整数。
输出格式:
输出这组整数。
输入样例:
8 12 56 4 6 55 15 33 62
输出样例:
12 56 4 6 55 15 33 62
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int main()
{
int n,i,a[100000];
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
for(i=0; i<n-1; i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[n-1]);
return 0;
}
1-2 数据结构实验之链表二：逆序建立链表
任务描述:
输入整数个数N，再输入N个整数，按照这些整数输入的相反顺序建立单链表，并依次遍历输出单链表的数据。
输入格式:
第一行输入整数N（1<=N<=100000)。第二行依次输入N个整数，逆序建立单链表。
输出格式:
依次输出单链表所存放的数据。
输入样例:
10 11 3 5 27 9 12 43 16 84 22
输出样例:
22 84 16 43 12 9 27 5 3 11
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int main ()
{
int n,a[100000],i;
scanf("%d",&n);
for(i=0; i<n; i++) { scanf("%d",&a[i]); } for(i=n-1; i>0; i--)
printf("%d ",a[i]);
printf("%d\n",a[0]);
return 0;
}
1-3 数据结构实验之链表三：链表的逆置
任务描述:
输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表的数据进行逆置，并输出逆置后的单链表数据。
输入格式:
输入多个整数，以-1作为结束标志。（整数个数不超过100000，不低于1）
输出格式:
输出逆置后的单链表数据。
输入样例:
12 56 4 6 55 15 33 62 -1
输出样例:
62 33 15 55 6 4 56 12
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int main ()
{
int n,a[100000],i,t=0;
while(~scanf("%d",&n))
{
if(n==-1)
{
break;
}
else
{
a[t]=n;
t++;
}
}
for(i=t-1; i>0; i--)
printf("%d ",a[i]);
printf("%d\n",a[0]);
return 0;
}
1-4 数据结构实验之链表四：有序链表的归并
任务描述:
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
输入格式:
第一行输入M与N的值。(1 <= M <=100000, 1 <= N <= 100000)第二行依次输入M个有序的整数。第三行依次输入N个有序的整数。
输出格式:
输出合并后的单链表所包含的M+N个有序的整数。
输入样例:
在这里给出一组输入。例如：
6 5 1 23 26 45 66 99 14 21 28 50 100
输出样例:
在这里给出相应的输出。例如：
1 14 21 23 26 28 45 50 66 99 100
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
struct node
{
int data;
struct node *next;
};
int main()
{
int n,m,i;
struct node *head,*q,*p,*head1,*head2,*p1,*p2,*q1,*q2;
head=(struct node *)malloc(sizeof(struct node));
head1=(struct node *)malloc(sizeof(struct node));
head2=(struct node *)malloc(sizeof(struct node));
head->next=NULL;
head1->next=NULL;
head2->next=NULL;
q=head;
q1=head1;
q2=head2;
scanf("%d%d",&m,&n);
for(i=0;i<m;i++) { p1=(struct node *)malloc(sizeof(struct node)); scanf("%d",&p1->data);
p1->next=NULL;
q1->next=p1;
q1=p1;
}
p1=head1->next;
for(i=0;i<n;i++) { p2=(struct node *)malloc(sizeof(struct node)); scanf("%d",&p2->data);
p2->next=NULL;
q2->next=p2;
q2=p2;
}
p2=head2->next;
while(p1&&p2)
{
p=(struct node *)malloc(sizeof(struct node));
if(p1->data<=p2->data)
{
q->next=p1;
q=p1;
p1=p1->next;
}
else if(p1->data>p2->data)
{
q->next=p2;
q=p2;
p2=p2->next;
}
}
if(p1)
{
q->next=p1;
q=p1;
p1=p1->next;
}
else if(p2)
{
q->next=p2;
q=p2;
p2=p2->next;
}
p=head->next;
while(p!=NULL)
{
if(p->next!=NULL)
{
printf("%d ",p->data);
}
else
printf("%d\n",p->data);
p=p->next;
}
return 0;
}
1-5 数据结构实验之链表五：单链表的拆分
任务描述:
输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。
输入格式:
第一行输入整数N（1<=N<=100000)。第二行依次输入N个整数。 （保证奇数偶数都存在）
输出格式:
第一行分别输出偶数链表与奇数链表的元素个数；第二行依次输出偶数子链表的所有数据；第三行依次输出奇数子链表的所有数据。
输入样例:
在这里给出一组输入。例如：
10 1 3 22 8 15 999 9 44 6 1001
输出样例:
在这里给出相应的输出。例如：
4 6 22 8 44 6 1 3 15 999 9 1001
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int main()
{
int a[100000],n,i,b[100000],t=0,c=0,d[100000];
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
for(i=0; i<n; i++)
{
if(a[i]%2==0)
{
b[t]=a[i];
t++;
}
else
{
d[c]=a[i];
c++;
}
}
printf("%d %d\n",t,c);
for(i=0; i<t-1; i++)
{
printf("%d ",b[i]);
}
printf("%d\n",b[t-1]);
for(i=0; i<c-1;i++)
{
printf("%d ",d[i]);
}
printf("%d\n",d[c-1]);
return 0;
}
1-6 数据结构实验之链表七：单链表中重复元素的删除
任务描述:
按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
输入格式:
第一行输入元素个数 n (1 <= n <= 15)；第二行输入 n 个整数，保证在 int 范围内。
输出格式:
第一行输出初始链表元素个数；第二行输出按照逆位序所建立的初始链表；第三行输出删除重复元素后的单链表元素个数；第四行输出删除重复元素后的单链表。
输入样例:
在这里给出一组输入。例如：
10 21 30 14 55 32 63 11 30 55 30
输出样例:
在这里给出相应的输出。例如：
10 30 55 30 11 63 32 55 14 30 21 7 30 55 11 63 32 14 21
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int main()
{
int a[20],n,i,b[20],j,t=0,c;
scanf("%d",&n);
for(i=0; i<n; i++) { scanf("%d",&a[i]); } printf("%d\n",n); for(i=n-1; i>=0; i--)
{
b[t]=a[i];
t++;
}
for(i=0;i<n-1;i++)
printf("%d ",b[i]);
printf("%d\n",b[i]);
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(b[i]==b[j])
{
for(c=j; c<n; c++)
{
b[c]=b[c+1];
}
j--;
n--;
}
}
}
printf("%d\n",n);
for(i=0; i<n-1; i++)
{
printf("%d ",b[i]);
}
printf("%d\n",b[i]);
return 0;
}
1-7 师–链表的结点插入
任务描述:
给出一个只有头指针的链表和 n 次操作，每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。
输入格式:
多组输入。每组数据首先输入一个整数n(1<=n<=100)，代表有n次操作。接下来的n行，每行有两个整数Mi(0<=Mi<=10000)，Xi。
输出格式:
对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。
输入样例:
在这里给出一组输入。例如：
4 1 1 1 2 0 3 100 4
输出样例:
在这里给出相应的输出。例如：
3 1 2 4
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
struct sdut
{
int data;
struct sdut *next;
};
int main()
{
int n, a, t, count, i;
while(scanf("%d", &n) != EOF)
{
struct sdut *head, *p, *q;
head = (struct sdut*)malloc(sizeof(struct sdut));
head -> next = NULL;
t = 0;
for(i = 0; i < n; i++) { count = 0; q = head; p = (struct sdut*) malloc(sizeof(struct sdut)); scanf("%d%d", &a, &p -> data);
if(a <= t)
{
while(count <= a) { if(count == a) { p -> next = q -> next;
q -> next = p;
break;
}
q = q -> next;
count ++;
}
}
else
{
while(q -> next)
{
q = q -> next;
}
q -> next = p;
p -> next = NULL;
}
t++;
}
p = head -> next;
while(p)
{
if(p -> next)
printf("%d ", p -> data);
else
printf("%d\n", p -> data);
p = p -> next;
}
}
return 0;
}
1-8 约瑟夫问题
任务描述:
n个人想玩残酷的死亡游戏，游戏规则如下：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。请输出最后一个人的编号。
输入格式:
输入n和m值。 (1<=n<=100 , 1<=m<=100)
输出格式:
输出胜利者的编号。
输入样例:
在这里给出一组输入。例如：
5 3
输出样例:
在这里给出相应的输出。例如：
4
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int main()
{
int p=0,n,m,i;
scanf("%d%d",&n,&m);
for(i=2; i<=n; i++)
{
p=(p+m)%i;
}
printf("%d\n",p+1);
return 0;
}
1-9 数据结构实验之链表九：双向链表
任务描述:
学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B，他们的关系是B是A的后继，A指向了B，便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。
输入格式:
第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。第二行是n个数（n个数没有重复），利用这n个数建立双向链表。接下来有m个关键字，每个占一行。(1<=n<=50)
输出格式:
对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。
注意：每个给定关键字的输出占一行。
一行输出的数据之间有一个空格，行首、行末无空格。
输入样例:
在这里给出一组输入。例如：
10 3 1 2 3 4 5 6 7 8 9 0 3 5 0
输出样例:
在这里给出相应的输出。例如：
2 4 4 6 9
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
struct node
{
int data;
struct node *next,*front;
};
struct node *creat(int n)
{
struct node *head,*p,*tail;
int i;
head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
head->front=NULL;
tail=head;
for(i=0;i<n;i++) { p=(struct node*)malloc(sizeof(struct node)); scanf("%d",&p->data);
p->next=NULL;
tail->next=p;
p->front=tail;
tail=p;
}
return (head);
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
struct node *head, *p;
head=creat(n);
while(m--)
{
p=head->next;
int x;
scanf("%d",&x);
while(p->data!=x)
{
p=p->next;
}
if(p->front==head)printf("%d\n",p->next->data);
else if(p->next==NULL)printf("%d\n",p->front->data);
else printf("%d %d\n",p->front->data,p->next->data);
}
return 0;
}
1-10 不敢死队问题
任务描述:
说到“敢死队”，大家不要以为我来介绍电影了，因为数据结构里真有这么道程序设计题目，原题如下：
有M个敢死队员要炸掉敌人的一个碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
这题本来就叫“敢死队”。“谁都不想去”，就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号，按照上面介绍，从一号开始数，数到5的那名战士去执行任务，那么排长是第几个去执行任务的？
输入格式:
输入包括多组数据，每行一个整数M（0<=M<=10000)（敢死队人数），若M=0，输入结束，不做处理。
输出格式:
输出一个整数n，代表排长是第n个去执行任务。
输入样例:
在这里给出一组输入。例如：
9 6 223 0
输出样例:
在这里给出相应的输出。例如：
2 6 132
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
struct node
{
int no;
struct node *next;
};
int main()
{
int n,m,i,num = 0,count = 0;
struct node *head, *p, *tail;
while(scanf("%d",&n) != EOF&&n){
num = 0,count = 0;
head = (struct node *)malloc(sizeof(struct node));
tail = head;
for(i = 1;i <= n;i++) { p = (struct node *)malloc(sizeof(struct node)); p->no = i;
p->next = NULL;
tail->next = p;
tail = p;
}
tail->next = head->next;
p = head->next;
tail = head;
m = 5;
while(count < n - 1) { p = tail->next;
num++;
if(num % m== 0)
{
if(tail->next == head->next)
break;
tail->next = p->next;
free(p);
count++;
}
else
{
tail = p;
p = p->next;
}
}
printf("%d\n",count+1);
}
return 0;
}
