数据结构实验之素数链表

桃扇骨 2022-12-14 13:39 134阅读 0赞

## 数据结构实验之素数链表 ##

Description  
我们定义素数链表为元素全部是素数的链表。

给定一个初始含有 n 个元素的链表，并给出 q 次删除操作，对于每次操作，你需要判断链表中指定位置上的元素，如果元素存在且不是素数则删除。

在所有操作完成后你还需要检查一下最终链表是否是一个素数链表。

Input  
输入数据有多组。第 1 行输入 1 个整数 T (1 <= T <= 25) 表示数据组数。

对于每组数据：

第 1 行输入 2 个整数 n (1 <= n <= 50000), q (1 <= q <= 1000) 表示链表初始元素数量和操作次数  
第 2 行输入 n 个用空格隔开的整数（范围 \[0, 1000\]）表示初始链表  
接下来 q 行，每行输入 1 个整数 i (1 <= i <= 50000)，表示试图删除链表中第 i 个元素  
Output  
对于每组数据：

先输出 1 行 “\#c”，其中 c 表示当前是第几组数据  
对于每次删除操作，根据情况输出 1 行：  
如果要删除的位置不存在元素（位置超出链表长度），则输出 “Invalid Operation”  
如果要删除的位置存在元素且此位置的元素是非素数，则删除元素并输出 “Deleted x”，其中 x 为成功删除的数（必须为非素数才能删除）  
如果要删除的位置存在元素且此位置的元素是素数，则输出 “Failed to delete x”，其中 x 为此位置上的数  
删除操作全部进行完毕后，则还需判断该链表现在是否为一个素数链表。如果链表非空且是素数链表，则输出 “All Completed. It’s a Prime Linked List”，否则输出 “All Completed. It’s not a Prime Linked List”  
所有输出均不包括引号。

Sample  
Input  
2  
1 2  
0  
5  
1  
6 3  
1 2 3 3 4 5  
1  
1  
4  
Output  
\#1  
Invalid Operation  
Deleted 0  
All Completed. It’s not a Prime Linked List  
\#2  
Deleted 1  
Failed to delete 2  
Deleted 4  
All Completed. It’s a Prime Linked List  
Hint  
推荐直接复制粘贴输出语句字符串到你的代码中，以防手打敲错。

链表中第 1 个元素的位置为 1，第 2 个元素的位置为 2，以此类推。

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    struct node
    {
        
    	int data;
    	struct node* next;
    };
    int main()
    {
        
    	int t, n, m, i, d, j, flag;
    	struct node* head, * tail, * p, * q;
    	scanf("%d", &t);
    	for (j = 1; j <= t; j++)
    	{
        
    		head = (struct node*)malloc(sizeof(struct node));
    		head->next = NULL;
    		tail = head;
    		scanf("%d %d", &n, &m);
    		for (i = 0; i < n; i++)//建表
    		{
        
    			p = (struct node*)malloc(sizeof(struct node));
    			p->next = NULL;
    			scanf("%d", &p->data);
    			tail->next = p;
    			tail = p;
    		}
    		printf("#%d\n", j);
    		while (m--)//操作次数
    		{
        
    			p = head;
    			q = head->next;
    			scanf("%d", &d);
    			if (d > n)//如果要删除的位置不存在元素（位置超出链表长度），则输出 "Invalid Operation"
    			{
        
    				printf("Invalid Operation\n");
    			}
    			else
    			{
        
    				d = d - 1;//细节处理
    				while (d--)
    				{
        
    					p = p->next;
    					q = q->next;
    				}
    				if (q->data == 2)//素数判断
    					flag = 1;
    				else if(q->data==0||q->data==1)
    					flag = 0;
    				else
    				{
        
    					flag = 1;
    					for (i = 2; i <= sqrt(q->data); i++)//i <= sqrt(q->data)，不然会超时
    					{
        
    						if (q->data % i == 0)
    						{
        
    							flag = 0;
    							break;
    						}
    					}
    				}
    				if (flag == 0)//如果要删除的位置存在元素且此位置的元素是非素数，则删除元素并输出 "Deleted x"
    				{
        
    					printf("Deleted %d\n", q->data);
    					p->next = q->next;
    					n--;
    				}
    				else//如果要删除的位置存在元素且此位置的元素是素数，则输出 "Failed to delete x"
    					printf("Failed to delete %d\n", q->data);
    			}
    		}
    		q = head->next;
    		while (q)//依次遍历结点的数据判断是否为素数
    		{
        
    			if (q->data == 2)
    				flag = 1;
    			else if (q->data == 0 || q->data == 1)
    				flag = 0;
    			else
    			{
        
    				flag = 1;
    				for (i = 2; i <= sqrt(q->data); i++)
    				{
        
    					if (q->data % i == 0)
    					{
        
    						flag = 0;
    						break;
    					}
    				}
    				if (flag == 0)
    					break;
    			}
    			q = q->next;
    		}
    		if (flag == 1)
    		{
        
    			printf("All Completed. It's a Prime Linked List");
    		}
    		else
    			printf("All Completed. It's not a Prime Linked List");
    		if (j != t)
    			printf("\n");
    	}
    }

*按照题意做即可，思路的大方向大体相同，注意细节处理便是。*