数据结构实验之链表之数组操作

红太狼 2022-12-13 12:46 142阅读 0赞

## 数据结构实验之链表之数组操作 ##

Description  
给你一个长度为 n 的数组，并给出如下几种操作：

在下标为 a 的位置插入一个整数 b，如果其后有元素，则全部后移。例如，数组为 1, 2, 3，在下标为 1 的位置插入 4，则数组变为：1, 4, 2, 3。  
删除下标为 a 的元素，如果其后有元素，则全部前移。例如，数组为 1, 2, 3，删除下标为 0 的元素，则数组变为：2, 3。  
修改下标为 a 的元素的值为 b。  
输出整个数组。  
Input  
输入数据有多组（数据组数不超过 10），到 EOF 结束。

对于每组数据：

首先输入一行 n, m (1 <= n <= 10^6, 1 <= m <= 10^4)，分别表示初始数组的长度和操作次数。  
接下来一行输入 n 个用空格隔开的整数 Ai (0 <= Ai <= 1000)，表示初始的数组。  
最后有 m 行，每行对应一次操作，根据操作类型分为不同的输入格式（具体含义参见描述部分，0 <= a, b <= 1000）：  
1 a b  
2 a  
3 a b  
4  
Output  
对于每组数据中的每次类型为 4 的操作，输出一行，表示此时的数组，每个整数之间用空格隔开。

Sample  
Input  
3 6  
1 2 3  
1 1 4  
4  
2 2  
4  
3 2 8  
4  
Output  
1 4 2 3  
1 4 3  
1 4 8  
Hint  
建议使用链表完成。

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        
    	int data;
    	struct node* next;
    };
    int main()
    {
        
    	int i, m, n, a, b, c;
    	struct node* head, * p, * tail, * t;
    	while (~scanf("%d %d", &n, &m))
    	{
        
    		head = (struct node*)malloc(sizeof(struct node));
    		head->next = 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;
    			tail = p;
    		}
    		while (m--)
    		{
        
    			scanf("%d", &a);
    			if (a == 1)//增加数据
    			{
        
    				p = head;
    				scanf("%d %d", &b, &c);
    				while (b--)
    				{
        
    					p = p->next;
    				}
    				t = (struct node*)malloc(sizeof(struct node));
    				t->next = NULL;
    				t->data = c;
    				t->next = p->next;
    				p->next = t;
    			}
    			else if (a == 2)//删除数据
    			{
        
    				p = head;
    				scanf("%d", &b);
    				while (b--)
    				{
        
    					p = p->next;
    				}
    				t = p->next;
    				p->next = t->next;
    			}
    			else if (a == 3)//更改数据
    			{
        
    				p = head->next;
    				scanf("%d %d", &b, &c);
    				while (b--)
    				{
        
    					p = p->next;
    				}
    				p->data = c;
    			}
    			else if (a == 4)//输出当前的所有数据
    			{
        
    				p = head->next;
    				while (p)
    				{
        
    					printf("%d", p->data);
    					if (p->next)
    					{
        
    						printf(" ");
    					}
    					else
    					{
        
    						printf("\n");
    					}
    					p = p->next;
    				}
    			}
    		}
    	}
    }