SDUT-数据结构实验2-链表

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;
}
如果对您有帮助的话,能否支持一下博主?
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇