1-1 sdut-C单链表的创建及遍历
任务描述:
读入n值及n个整数，建立单链表并遍历输出。
输入格式:
读入n及n个整数。
输出格式:
输出n个整数，以空格分隔（最后一个数的后面没有空格）。
输入样例:
2 10 5
输出样例:
10 5
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,i;
cin>>n;
int a[n];
for(i=1;i<=n;i++) cin>>a[i];
if(n==0)
return 0;
else
{
for(i=1;i<=n-1;i++)
cout<<a[i]<<" ";
cout<<a[i];
}
}
1-2 sdut-C两个有序链表序列的合并
任务描述:
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用表示序列的结尾（不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 3 5 -1 2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10
相关限制：
代码长度限制16KB 时间限制1500ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
list add()
{
list l;
int a;
while(1)
{
cin>>a;
if(a==-1)
break;
l.push_back(a);
}
return l;
}
void put(list s,list &s3)
{
while(!s.empty())
{
s3.push_back(s.front());
s.pop_front();
}
}
int main()
{
lists1=add(),s2=add(),s3;
while(!s1.empty()&&!s2.empty())
{
if(s1.front()>s2.front())
{
s3.push_back(s2.front());
s2.pop_front();
}
else
{
s3.push_back(s1.front());
s1.pop_front();
}
}
put(s1,s3);
put(s2,s3);
if(!s3.empty())
{
cout<<s3.front();
s3.pop_front();
while(!s3.empty())
{
cout<<" "<<s3.front();
s3.pop_front();
}
}
else
cout<<"NULL";
}
1-3 sdut-C两个有序链表序列的交集
任务描述:
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用表示序列的结尾（不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 2 5 -1 2 4 5 8 10 -1
输出样例:
2 5
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
long long int a[100005],b[1000005],c[100005];
long long int top1=0,top2=0,top3=0;
long long int x;
int main ()
{
while(cin>>x)
{
if(x==-1)
break;
else
a[++top1]=x;
}
while(cin>>x)
{
if(x==-1)
break;
else
b[++top2]=x;
}
int p1=1,p2=1;
while(p1<=top1&&p2<=top2) { if(a[p1]==b[p2]) { c[++top3]=a[p1]; p1++; p2++; } else if(a[p1]>b[p2])
p2++;
else
p1++;
}
for(int i=1;i<=top3;i++)
{
if(i==1)
cout<<c[i];
else
cout<<" "<<c[i];
}
if(top3==0)
cout<<"NULL";
}
1-4 sdut-C约瑟夫环
任务描述:
N个人围成一圈顺序编号，从1号开始按1、2、3……顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。请按退出顺序输出每个退出人的原序号。
输入格式:
输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。
输出格式:
按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。
输入样例:
在这里给出一组输入。例如：
7 3
输出样例:
3 6 2 7 5 1 4
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
struct circle
{
int num;
struct circle *next;
};
int main()
{
int n,number,i;
struct circle a[3000],*p,*q;
cin>>n>>number;
for(i=0;i<n;i++)
a[i].num=i+1;
for(i=0;i<n-1;i++) a[i].next=&a[i+1]; a[n-1].next=a; q=p=a; while(p!=p->next)
{
for(i=0;i<number-1;i++) { q=p; p=p->next;
}
q->next=p->next;
printf("%d ",p->num);
p=q->next;
}
printf("%d\n",p->num);
}
1-5 sdut-C链表去重
任务描述:
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过的整数，下一个结点是下个结点的地址。
输出格式:
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例:
在这里给出一组输入。例如：
00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854
输出样例:
在这里给出相应的输出。例如：
00100 21 23854 23854 -15 99999 99999 -7 -1 00000 -15 87654 87654 15 -1
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
struct name{
int data;//存数
int next;//存下一个数的下标
};
struct name a[100005];
int h,n;//头结点和数的数量
int tidx[100005];//未被删除的元素的下标
int fidx[100005];//被删除的元素的下标
int ab[100005];//标记每个数的绝对值
int t=0,f=0;//删除后序列的数量和删除的数量
int main(){
cin>>h>>n;
for(int i=0;i<n;i++){ int idx,x,nidx; cin>>idx>>x>>nidx;
a[idx].data =x;
a[idx].next =nidx;
}
if(n==1){//这里要特判一下n==1的情况
printf("%05d %d %d",h,a[h].data ,-1);
}else{
while(h!=-1){//遍历链表
if(ab[abs(a[h].data )]==0){//如果没有出现过
tidx[t++]=h;//把他的下标存入未被删除的序列
ab[abs(a[h].data )]=1;//标记
}else{
fidx[f++]=h;//把他放入删除元素的下标
}
h=a[h].next ;
}
for(int i=0;i<t-1;i++){
printf("%05d %d %05d\n",tidx[i],a[tidx[i]].data ,tidx[i+1]);
}
printf("%05d %d %d\n",tidx[t-1],a[tidx[t-1]].data ,-1);
for(int i=0;i<f-1;i++){
printf("%05d %d %05d\n",fidx[i],a[fidx[i]].data ,fidx[i+1]);
}
printf("%05d %d %d\n",fidx[f-1],a[fidx[f-1]].data ,-1);
}
return 0;
}
1-6 sdut-C带头节点的双向循环链表操作
任务描述:
本题目要求读入一系列整数，依次插入到双向循环链表的头部和尾部，然后顺序和逆序输出链表。链表节点类型可以定义为：
typedef int DataType;
typedef struct LinkedNode{
DataType data;
struct LinkedNode *prev;
struct LinkedNode *next;
}LinkedNode;
链表类型可以定义为
typedef struct LinkedList{
int length; /* 链表的长度 */
LinkedNode head; /* 双向循环链表的头节点 */
}LinkedList;
初始化链表的函数可声明为
void init_list(LinkedList *list);
分配节点的函数可声明为
LinkedNode *alloc_node(DataType data);
头部插入的函数可声明为
void push_front(LinkedList *list, DataType data);
尾部插入的函数可声明为
void push_back(LinkedList *list, DataType data);
顺序遍历的函数可声明为
void traverse(LinkedList *list);
逆序遍历的函数可声明为
void traverse_back(LinkedList *list);
输入格式:
输入一行整数（空格分隔），以-1结束。
输出格式:
第一行输出链表顺序遍历的结果，第二行输出逆序遍历的结果。
输入样例:
在这里给出一组输入。例如：
1 2 3 4 5 6 -1
输出样例:
在这里给出相应的输出。例如：
5 3 1 2 4 6 6 4 2 1 3 5
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
import java.util.Scanner;
class Node{
int val;
Node pre;
Node next;
Node(int val, Node pre, Node next){
this.val = val;
this.pre = pre;
this.next = next;
}
}
public class Main {
public static Node head = new Node(0, null, null);
public static Node tail = head;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = 0, f = 0;
while((n = cin.nextInt()) != -1) {
if(f++ % 2 == 0) {
addFirst(n);
}else {
addLast(n);
}
}
showPre();
System.out.println();
showPost();
}
public static void addFirst(int n) {
Node old = head.next;
Node t = new Node(n, head, old);
head.next = t;
if(head == tail) {
tail = t;
}else {
old.pre = t;
}
}
public static void addLast(int n) {
Node t = new Node(n, tail, null);
tail.next = t;
tail = t;
}
public static void showPre() {
Node t = head.next;
while(t != null) {
if(t.next == null)
System.out.print(t.val);
else
System.out.print(t.val + " ");
t = t.next;
}
}
public static void showPost() {
Node t = tail;
while(t != head) {
if(t.pre == head)
System.out.print(t.val);
else
System.out.print(t.val + " ");
t = t.pre;
}
}
}
1-7 sdut-C单链表就地逆置
任务描述:
输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表进行就地逆置（不增加新结点），并输出逆置后的单链表数据。
输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入多个整数，以-1作为该组测试的结束（-1不处理）。
输出格式:
对于每组测试，输出逆置后的单链表数据（数据之间留一个空格）。
输入样例:
在这里给出一组输入。例如：
1 1 2 3 4 5 -1
输出样例:
在这里给出相应的输出。例如：
5 4 3 2 1
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
int main ()
{
int t,i,x,j;
int a[10005];
cin>>t;
while(t--)
{
i=0;
while(cin>>x&&x!=-1)
{
a[i++]=x;
}
for(j=i-1;j>0;j--)
{
cout<<a[j]<<" ";
}
cout<<a[j]<<endl;
}
}
1-8 sdut-C合并有序数组
任务描述:
给定一个单链表 →→→→，请编写程序将链表重新排列为 →→→→。例如：给定为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
输入格式:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数 ()。结点的地址是5位非负整数，NULL地址用表示。接下来有行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式:
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例:
在这里给出一组输入。例如：
00100 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
输出样例:
在这里给出相应的输出。例如：
68237 6 00100 00100 1 99999 99999 5 12309 12309 2 00000 00000 4 33218 33218 3 -1
相关限制：
代码长度限制16KB 时间限制500ms 内存限制64MB 栈限制8192KB
答案：
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int addr;
int data;
int next;
}node[100005],sortNode[100005];
int main()
{
int First_Addr,N,addr,data,next,n=0;
scanf("%5d %d",&First_Addr,&N);
for(int i=0;i<N;i++)
{
scanf("%5d %d %5d",&addr,&data,&next);
node[addr].data=data;
node[addr].next=next;
}
int sort_i=0;
addr=First_Addr;
while (addr!=-1)
{
sortNode[sort_i].addr=addr;
sortNode[sort_i].data=node[addr].data;
sortNode[sort_i].next=node[addr].next;
sort_i++;
addr=node[addr].next;
n++;
}
int j=0,min=0,max=n-1;
while (n--)//不能用N
{
j++;
if(j%2==1)
{
if(n==0)printf("%05d %d -1\n",sortNode[max].addr,sortNode[max].data);
else {
printf("%05d %d %05d\n",sortNode[max].addr,sortNode[max].data,sortNode[min].addr);
max--;}
}
else
{
if(n==0)printf("%05d %d -1\n",sortNode[min].addr,sortNode[min].data);
else {
printf("%05d %d %05d\n",sortNode[min].addr,sortNode[min].data,sortNode[max].addr);
min++;}
}
}
return 0;
}
