2020数据结构课程设计之大爱线性表

大爱线性表
不少参赛同学刚学数据结构，对线性表最是熟悉不过。这里我们给线性表增加两个特殊的操作，第一个是‘R’ 操作，表示逆转整个表，如果表长为L，原来的第i个元素变成第L-i+1个元素。第二个操作是‘D’，表示删除表的第一个元素，如果表为空，则返回一个“error”信息。我们可以给出一系列的‘R’ 和‘D’组合，例如“RDD”表示先逆转表，然后删除最前面的两个元素。

本题的任务是给定表和一个操作串S，求出执行S后的表，如果中途出现‘D’操作于空表，输出“error”。

输入
第一行是一个整数，表示有多少组数据。每组测试数据格式如下：

(1)第一行是操作串S，有‘R’ 和‘D’组成，S的长度大于0，不超过100 000。
(2)第二行是整数n，表示初始时表中的元素个数。n的值不小于0，不超过100 000。
(3) 第三行是包含n个元素的表，用‘[’ 和 ‘]’括起来，元素之间用逗号分开。各元素值在[1,100]之间。

解题思路：
1）对我而言，本题的难点在于如何正确处理输入与输出操作。所以在输入输出问题上要下功夫。
2）如何处理R与D呢？此解法用了两个技巧，头尾指针与计数器。头尾指针k，q分别记录数组元素的位置。计数器记录翻转次数，如果翻转次数模2为0，那么相当于没有翻转。如果R一次，D一次，计数器模2为1，那么q++，模拟元素被移出数组。如果计数器模2为0，那么k++。这样操作！

下面是源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstring>
using namespace std;
#define MAXSIZE 100005
//利用数组
typedef struct
{
	int array[MAXSIZE];//元素
	int length;//数组长度
}Arry;
Arry L;
char option[MAXSIZE];
//利用标识符记录翻转次数，如果为偶数，那么相当于没翻转
void clean(int len)//清空
{
	for (int i = 0; i < len; i++)
		option[i] = '\0';
}
int main()
{
	int n,m,length_option,p;//n为程序运行次数，m为含有多少个元素，p为输入元素的临时变量,length_option为操作步数
	cin >> n;
	while (n)
	{
		char h;
		int i = 0;//记录元素录入情况
		int count = 0;//记录翻转次数
		int flag = 0;//记录数是否为空
		int k = 0,q=0;//元素指针，记录位置
		cin >> option;
		length_option = strlen(option);//一共有多少个操作步骤
		cin >> m;
		L.length = m;
		if (m)//输入部分
			while (cin >> h)
			{
				if (h == ']')
					break;
				cin >> p;
				L.array[i] = p;
				i++;
			}
		else
			cin >> h >> h;
		for (i = 0; i < length_option; i++)
		{
			if (option[i] == 'R')
				count++;
			else if (option[i] == 'D')
			{
				if (!L.length)
				{
					flag = 1;
					break;
				}	
				L.length--;//数组长度减小
				if (count%2==0)
					k++;//头指针移动位置
				else 
					q++;//尾指针移动位置
			}
		}
		if (flag==1)
		{
			cout << "error" << endl;
			n--;
			continue;
		}
		else if(flag==0)
		{
				cout << "[";
				if (count % 2==0)
				{
					for (i = k; i < m - q; i++)
					{
						cout << L.array[i];
						if (i != m - q-1)
							cout << ",";
					}
				}
				else
				{
					for (i = m - q - 1; i >= k; i--)
					{
						cout << L.array[i];
						if (i != k)
							cout << ",";
					}
				}
				cout << "]" << endl;
		}
		clean(length_option);
		n--;
	}
	return 0;
}

常见错误：
1）输出[]为空。元素录入出了问题。
2）多余逗号。格式控制出了问题。
3）应该正序输出却逆序输出，而且少了数字。大概率!(count%2)写成了!count%2这种形式，疏忽运算符优先级导致的错误。