SDUT-数据结构实验2-链表
|
刷题,C/C++,学习笔记,数据结构,日常小记
|
36
|
0

1861 字
|
8 分钟

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
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
建立个人博客

							
							

							
b站保存视频到本地

							
							

							
力扣hot100之234.回文链表

							
							

							
力扣hot100之160.相交链表

							
							

							
力扣hot100之236.二叉树的最近公共祖先

							
							

							
计算机网络实验3之路由器配置

							
							

							
PDF图片清晰化

							
							

							
计算机网络实验4之网络协议与实现

							
							

							
计算机网络实验2之交换机配置

							
							

							
SDUT-程序设计基础Ⅰ-单元测试1模拟