数据结构——线性结构的应用实例（C实现）_线性结构的典型应用方法

线性结构是一种简单的逻辑结构，在该结构中，数据元素之间构成一个有序的序列，主要有线性表、广义表、堆栈、队列等几种结构，实现的方式主要有顺序存储（数组实现）以及链式存储（链表实现），下面给出了四个线性结构的应用实例及其对应的代码实现（C），可以帮助我们更好的理解线性结构在实际应用中的使用方法。

一、后缀表达式求值 && 中缀表达式转换为后缀表达式

后缀表达式是一种运算符号位于两个运算数之后的多项式，不同于我们日常使用的中缀表达式，后缀表达式在逻辑上更清晰，并且已经顾及到了符号之间的优先级，在程序中更易于实现，（比如1 + 1 * 2的后缀表达式为112 * +）因此我们选用后缀表达式作为该程序的输入值。
在该程序的具体实现结构上，选用了堆栈这种线性结构，堆栈是一种受约束的线性表，其特点是”先入后出“，其插入（入栈）和删除（出栈）都在栈顶（最后入栈的一个元素位置）实现，结合后缀表达式来看，在我们读取到运算数时需要有位置存放，在读取到运算符号时有需要把最近存入的运算数读取出来作运算，这恰恰可以用堆栈来实现，在存储方式的选择上，由于只需要在栈顶操作，而不需要在序列中插入元素，因此选择使用顺序存储。需要注意的是，为了简便起见，我们在该程序中假设后缀表达式的对象（运算数或运算符号）之间用空格分隔开来，运算数为正实数，具体代码实现如下：

#include <stdio.h>
#include <stdlib.h>  //用于atof、malloc函数
#include <stdbool.h>
#include <ctype.h>  //用于isdigit函数

#define MAXOP 30  //操作数序列的最大长度，可自行调整
#define INFINITY 1e9  //代表正无穷，在该程序中用于标记错误

typedef double ElementType;  //可根据需要自行定义元素类型，这样做是为了方便统一接口
typedef enum { num, opr, end } Type;  //依次对应运算数、运算符、字符串结尾
typedef int Position;
typedef struct SNode {
	ElementType* Data;  //存储元素的数组
	Position Top;  //记录栈顶位置的变量
	int MaxSize;  //栈的最大可容纳数量
} *Stack;  //定义顺序栈节点的结构指针

Stack CreatStack(int Maxsize);  //生成空栈
bool Push(Stack S, ElementType X);  //入栈函数
bool IsEmpty(Stack S); //判断栈是否空
ElementType Pop(Stack S);  //出栈函数

Type GetOp(char* Expr, int* start, char* Str);  //从star开始读入下一个对象（操作数或运算符），并保存在字符串str中
ElementType PostfixExp(char* Expr);  //调用GetOp函数读入后缀表达式并求值

int main(void)
{
	char Expr[MAXOP];
	ElementType f;

	gets(Expr);  //接收表达式存入字符数组Expr中
	f = PostfixExp(Expr);
	if (f < INFINITY)  
		printf("%.4f\n", f);
	else 
		printf("表达式错误\n");

	return 0;
}

Stack CreatStack(int Maxsize)
{
	Stack S = (Stack)malloc(sizeof(struct SNode));  //动态申请空间给空栈
	if (S) {
		S->Data = (ElementType*)malloc(Maxsize * sizeof(ElementType));
		S->Top = -1;
		S->MaxSize = Maxsize;
	}  //初始化操作

	return S;
}

bool Push(Stack S, ElementType X)
{
	if (S->Top == S->MaxSize - 1) {
		printf("栈满");  //先判断栈是否已满
		return false;
	}
	else  S->Data[++(S->Top)] = X; //将传入的运算值入栈
	return true;
}

bool IsEmpty(Stack S)
{
	return (S->Top == -1);  //Top=-1代表栈空
}

ElementType Pop(Stack S)
{
	return (S->Data[(S->Top)--]);  //出栈
}

Type GetOp(char* Expr, int* start, char* str)
{
	//该函数一次只读入一个数字或符号
	int i = 0;

	while ((str[0] = Expr[(*start)++]) == ' ')
		;  //跳过表达式前空格
	while (str[i] != ' ' && str[i] != '\0')  
		str[++i] = Expr[(*start)++];  //开始读入数字到字符串str中，当读到空格或字符串结束符时停止读入

	if (str[i] == '\0')  
		(*start)--;  //如果读到输入的结尾，start指向结束符
	str[i] = '\0';  //结束一个对象的获取，为str加上尾巴，表示其现在是一个完整的字符串

	if (i == 0)  
		return end;  //读到了结束
	//如果str[0]是数字，或者是符号跟个数字
	else if (isdigit(str[0]) || isdigit(str[1]))  
		return num;  //表示此时str中存的是一个数字
	else  
		return opr;  //表示此时str中存的是一个运算符
}

ElementType PostfixExp(char* Expr)
{
	Stack S;
	Type T;
	ElementType Op1, Op2;
	char str[MAXOP];
	int start = 0;

	S = CreatStack(MAXOP); //申请新堆栈

	Op1 = Op2 = 0;
	while ((T = GetOp(Expr, &start, str)) != end) {  //当未读到输入结束时
		if (T == num)  Push(S, atof(str));  //若读到的是数字，将其转化为相应类型（该程序中是浮点型）并入栈
		else {
			if (!IsEmpty(S)) Op2 = Pop(S); //若读到的是运算符，且栈不为空，将一个运算数出栈用临时变量保存
			else Op2 = INFINITY;  //栈已空，则设置临时变量为无穷
			if (!IsEmpty(S)) Op1 = Pop(S); //将第二个运算数出栈并用另一个临时变量保存
			else Op2 = INFINITY;
			switch (str[0]) {
			case '+': Push(S, Op1 + Op2); break;  //读到的符号是加号，对两个运算数作加法
			case '*': Push(S, Op1 * Op2); break;  //读到的符号是乘号，对两个运算数作乘法
			case '-': Push(S, Op1 - Op2); break;  //读到的符号是乘号，对两个运算数作减法
			case '/':
				if (Op2 != 0.0)  //读到的是除号，检查除法分母是否为0
					Push(S, Op1 / Op2);
				else {
					printf("错误：除法分母为零");
					Op2 = INFINITY;
				}
				break;
			default:
				printf("错误：未知运算符%s\n", str);
				Op2 = INFINITY;
				break;
			}
			if (Op2 >= INFINITY)  break;
		}
	}
	if (Op2 < INFINITY)
		if (!IsEmpty(S))
			Op2 = Pop(S);  //若处理完表达式时堆栈正常，则记录计算结果
		else 
			Op2 = INFINITY;  //否则标记错误
	free(S);  //释放堆栈

	return Op2;
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

下面给出了中缀表达式转换为后缀表达式的程序，程序默认表达式的最大长度为21，在使用中可自行改变，程序的关键就在于在读入不同的内容时，作出相应的处理办法，将结果保存在一个字符数组中，用空格分开，比如读到数字时，直接加入到数组中，而读到符号时，需要先将其保存，在适当的时候输出，并且根据后缀表达式的特性可知，在输出时，先保存的符号后输出，因而可以使用栈这种结构用于保存符号，同时需要注意的点还有：对左右括号的处理、对+和-为正负号还是运算符的判断、以及对各种运算符优先级的处理，这些都体现在了程序中，已经用函数对具体功能做了区分，同时对栈做处理时，同样对出入栈函数做了简化（此程序在出入栈时不需要担心栈空或栈满问题），程序代码如下（程序逻辑可跟着代码梳理）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

#define MAXL 21  //表达式最大字符数
typedef char ElementType;

//堆栈的定义及相关操作函数
typedef int Position;
typedef struct SNode {
	ElementType* Data;
	Position Top;
	int MaxSize;
} *Stack;
Stack CreateStack(int MaxSize);
bool IsEmpty(Stack S);
void Push(Stack S, ElementType X);
ElementType Peek(Stack S);  //只获取栈顶的元素值
ElementType Pop(Stack S);

typedef enum { lpr, rpr, plus, minus, times, divide, eos, operand } Precedence; //运算符的优先级
bool IsSign(char* expr, int i);  //判断+与-是运算符还是正负号
char GetOp(char* expr, int* i, char* Postfix, int* j);  //读入中缀表达式的函数
Precedence GetToken(char op);  //返回运算符优先级类型
void ToPostfix(char* expr);  //表达式转换核心函数，整个处理过程大部分在此进行

int main(void)
{
	char Str[MAXL];
	scanf("%s", Str);
	ToPostfix(Str);

	return 0;
}

void ToPostfix(char* expr)  //表达式转换核心函数
{
	int i, j, L;
	char Postfix[2 * MAXL], Op;  //Postfix是结果数组
	Stack S;
	Precedence token;  //运算符优先级的变量

	S = CreateStack(MAXL);
	L = strlen(expr);  //中缀表达式长度
	j = 0;  //j为Postfix[]中当前要写入的位置
	for (i = 0; i < L; i++) {
		Op = GetOp(expr, &i, Postfix, &j);  //读入
		token = GetToken(Op);  //获取优先级
		if (token == operand)  continue; //不处理数字
		switch (token) {  //处理运算符
		case lpr:  Push(S, '(');  break;  //左括号入栈
		case rpr:  //括号内的中缀表达式已经扫描完毕，把左括号前的所有运算符写入Postfix[]
			while (Peek(S) != '(') {
				Postfix[j++] = Pop(S);
				Postfix[j++] = ' ';
			}
			Pop(S);  //删除左括号
			break;
		default:  //其他运算符
			//当栈非空且栈顶符号不是左括号且栈顶符号优先级大于当前符号时，将栈顶符号出栈，加至结果数组中
			while (!IsEmpty(S) && Peek(S) != '(' && token <= GetToken(Peek(S))) {
				Postfix[j++] = Pop(S);
				Postfix[j++] = ' ';
			}
			Push(S, Op);  //读到符号时，将当前符号入栈
			break;
		}
	}
	while (!IsEmpty(S)) {  //读入结束时栈非空，将栈内运算符一并输出
		Postfix[j++] = Pop(S);
		Postfix[j++] = ' ';
	}
	Postfix[j - 1] = '\0';  //附上结尾
	printf("%s\n", Postfix);  //打印
}

bool IsSign(char* expr, int i)  //判断读到的是否为正负号
{  //是正负号的条件：符号出现在开头 || 符号前一个位置不是数字和右括号
	if (!i || (!isdigit(expr[i - 1]) && (expr[i - 1] != ')')))  return true;
	else  return false;
}

char GetOp(char* expr, int* i, char* Postfix, int* j)  //读入中缀表达式的函数
{
	if (isdigit(expr[(*i)])) {  //读入一个纯数字
		while (isdigit(expr[(*i)]) || (expr[(*i)] == '.'))
			Postfix[(*j)++] = expr[(*i)++];  //如果是数字则直接写入结果数组
		Postfix[(*j)++] = ' ';
		(*i)--;
		return '0';
	}
	switch (expr[*i]) {
	case '+':
		if (IsSign(expr, (*i))) {  //如果是正号，直接忽略读入下一个数字
			(*i)++;
			return GetOp(expr, i, Postfix, j);  //如果是运算符则返回字符
		}
		else return '+';
	case '-':
		if (IsSign(expr, (*i))) {  //如果是负号，直接加入结果数组并读入下一个数字
			Postfix[(*j)++] = '-';
			(*i)++;
			return GetOp(expr, i, Postfix, j);  //如果是运算符则返回字符
		}
		else return '-';
	default:  return expr[(*i)];  //其他符号则直接返回符号
	}
}

Precedence GetToken(char op)  //返回运算符优先级类型
{
	switch (op) {
	case '(':  return lpr;
	case ')':  return rpr;
	case '+':  return plus;
	case '-':  return minus;
	case '*':  return times;
	case '/':  return divide;
	case '\0':  return eos;
	default:  return operand;
	}
}

Stack CreateStack(int MaxSize)
{
	Stack S = (Stack)malloc(sizeof(struct SNode));
	S->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
	S->Top = -1;
	S->MaxSize = MaxSize;

	return S;
}

bool IsEmpty(Stack S)
{
	return (S->Top == -1);
}

void Push(Stack S, ElementType X)
{
	S->Data[++(S->Top)] = X;  //简版入栈，不担心栈满的问题
}

ElementType Peek(Stack S)
{
	return (S->Data[S->Top]);  //只返回栈顶元素的值，用于判断
}

ElementType Pop(Stack S)
{
	return (S->Data[(S->Top)--]);  //简版出栈，不担心栈空的问题
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

掌握了以上两个程序，还可以将二者结合，直接求中缀表达式的值，读者可自行尝试。

二、多项式加法/乘法运算

首先要解决的问题是多项式的表达，在不知道多项式项数的情况下，显然不适合采用数组的方式来表达，在该程序中，默认在输入时已经给出了多项式的项数，因此此时采用动态数组或链表的方式均可，此处选用了单链表实现，按照指数递减的顺序排列各项。输入输出的格式示例如下：
如多项式$3x^5-6x^4+12x^2+5$，其在程序内的表达格式为

4 3 5 -6 4 12 2 5 0 
1

说明：第一项（4）为多项式项数，后面依次按指数递减顺序输出每项的的系数加指数。
在运算操作时，对两个多项式，可以采用两个指针分别指向两个多项式第一个结点（指数最高项）。通过不断比较两个指针所指的个节点，当作多项式加法时，比较结果为以下两种情况之一，分别作不同处理：

• 两数据指数相等时，此时将量数据系数相加，若结果不为零，则作为结果多项式对影响系数，连同指数一并存入多项式，最后将两指针同时后移一格。
• 当某一指针所指数据比另一指针大时，将大的项存入结果多项式，并后移一格，而所指值较小的指针保持不变

在做多项式乘法时，需要将其中一个多项式中的每一项分别与另一多项式的每一项中的系数相乘，指数相加，在形成新多项式后，还需要合并同类项以及消除系数为0的项，最后放入结果多项式中，可以采用这样的思路，先计算乘积，而后跟据其指数项，依照指数递减的顺序将其插入到结果多项式中（当然仅保存非零项），那么具体的主函数框架就为：

int main()
{
	/*读入多项式1
	  读入多项式2
	  乘法运算并输出
	  加法运算并输出*/
}
1
2
3
4
5
6
7

同时为了避免对链表操作时需要频繁的判断表头指针是否为空，在多个函数中为链表创建了一个临时的头结点，在函数结束时会将其释放，具体代码实现如下：

#include <stdio.h>
#include <stdlib.h>

//数据结构的设计
typedef struct PolyNode* Polynomial;
struct PolyNode {
	int coef;  //系数
	int expon;  //指数
	Polynomial link;  //指向下一个结点
};  //多项式结点的结构指针

Polynomial PolyRead();  //读入多项式

void PolyAttach(int c, int e, Polynomial* pRear);  //接收输入并将结果插入到结果多项式上，并修改尾指针的值

int PolyCompare(int expon1, int expon2);  //多项式的指数比较，根据结果返回不同值

Polynomial PolyAdd(Polynomial P1, Polynomial P2);  //多项式加法

Polynomial PolyMult(Polynomial P1, Polynomial P2);  //多项式乘法

void PolyPrint(Polynomial P);  //多项式打印

int main(void)  //定义主函数
{
	Polynomial P1, P2, PP, PS;  //定义多项式结构指针
	//读取，计算，打印
	P1 = PolyRead();
	P2 = PolyRead();
	printf("\n");
	PS = PolyAdd(P1, P2);
	PolyPrint(PS);
	PP = PolyMult(P1, P2);
	PolyPrint(PP);

	return 0;
}

Polynomial PolyRead()
{
	Polynomial P, Rear, t;  //定义临时节点
	int c, e, N; //c，e，N分别代表系数、指数以及项数
	//注：申请链表时会带头节点，但读取完返回时会消除头结点，这省去了判断P是否为NULL的麻烦
	scanf("%d", &N);
	P = (Polynomial)malloc(sizeof(struct PolyNode));  //申请空结点作为头节点，并令P指向该节点
	P->link = NULL;
	Rear = P;  //初始时尾指针指向头结点
	while (N--) {
		scanf("%d %d", &c, &e);
		PolyAttach(c, e, &Rear);  //读入数据后将其插入多项式尾部
	}
	t = P;
	P = P->link;
	free(t);  //释放临时生成的头结点

	return P;
}

void PolyAttach(int c, int e, Polynomial* pRear)
{ //注意，Polynomial本身就是指针类型，即pRear是一个二级指针，这是为了在该函数中修改指针Rear的值
	Polynomial P;

	P = (Polynomial)malloc(sizeof(struct PolyNode));
	//对新节点赋值
	P->coef = c;
	P->expon = e;
	P->link = NULL;
	(*pRear)->link = P;  //将P赋值给pRear的下一个节点
	*pRear = P;  //将pRear向后移动
}

int PolyCompare(int expon1, int expon2)
{
	if (expon1 > expon2)  return 1;
	else if (expon1 < expon2)  return -1;
	else  return 0;
}

Polynomial PolyAdd(Polynomial P1, Polynomial P2)
{ //同样，该函数创建了一个临时的表头空节点，会在程序结束时释放
	Polynomial P, Rear, Temp;
	int sum;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	Rear = P;  //P记录结果多项式链表头结点
	while (P1 && P2) {
		//比较两多项式每项系数，根据不同情况作出不同操作
		switch (PolyCompare(P1->expon, P2->expon)) {
		case 1:
			PolyAttach(P1->coef, P1->expon, &Rear);
			P1 = P1->link;
			break;
		case -1:
			PolyAttach(P2->coef, P2->expon, &Rear);
			P2 = P2->link;
			break;
		case 0:
			sum = P1->coef + P2->coef;
			if (sum) PolyAttach(sum, P1->expon, &Rear);
			P1 = P1->link;
			P2 = P2->link;
			break;
		}
	}
	//将未处理完的另一多项式的所有节点依次复制到结果多项式中去
	for (; P1; P1 = P1->link) PolyAttach(P1->coef, P1->expon, &Rear);
	for (; P2; P2 = P2->link) PolyAttach(P2->coef, P2->expon, &Rear);
	Rear->link = NULL;
	Temp = P;
	P = P->link;  //令P指向结果多项式第一个非零项
	free(Temp);  //释放临时空表头结点
	return P;
}

Polynomial PolyMult(Polynomial P1, Polynomial P2)
{
	Polynomial P, Rear, t1, t2, t;
	int c, e;

	if (!P1 || !P2)  return NULL;  //若P1或P2为空，返回NULL
	//t1、t2接收两个多项式
	t1 = P1;
	t2 = P2;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;  //令P指向空表头结点
	Rear = P;
	while (t2) {
		PolyAttach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
		t2 = t2->link;
	}
	t1 = t1->link;  //先用P1的第一项乘以P2的每一项，形成初始的结果多项式
	while (t1) {
		t2 = P2;
		Rear = P;  //外层循环重置指向P2以及指向结果多项式的指针，使其重新移动至第一个结点
		while (t2) {
			e = t1->expon + t2->expon;
			c = t1->coef * t2->coef;
			while (Rear->link && Rear->link->expon > e)
				Rear = Rear->link;  //当结果的指数值比结果多项式中的指数值小时，将Rear不断向后移动
			if (Rear->link && Rear->link->expon == e) {
				if (Rear->link->coef + c)
					Rear->link->coef += c;  //当遇到指数相等项且它们的系数之和不为0时，将其插入结果多项式（系数加和）
				else {  //否则释放该指数对应项所在结点
					t = Rear->link;
					Rear->link = t->link;
					free(t);
				}
			}
			else {  //若遍历至多项式尾未找到指数相等项，则建立新结点接收该多项式的值，将其差入至多项式尾，同时移动Rear
				t = (Polynomial)malloc(sizeof(struct PolyNode));
				t->coef = c;
				t->expon = e;
				t->link = Rear->link;
				Rear->link = t;
				Rear = Rear->link;
			}
			t2 = t2->link;
		}
		t1 = t1->link;  //完成处理后，内循环移动t2，外循环移动t1；
	}
	t2 = P;
	P = P->link;
	free(t2);  //释放表头空结点 

	return P;
}

void PolyPrint(Polynomial P)
{
	int flag = 0;  //辅助调整输出格式用
	if (!P) {
		printf("0 0\n"); //零多项式时的输出
		return;
	}
	while (P) {
		if (!flag)  flag = 1;  //第一次进入循环时调整falg的值，确保除第一次循环外每次循环都可以打印空格
		else  printf(" ");
		printf("%d %d", P->coef, P->expon);
		P = P->link;
	}
	printf("\n");
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

当然，链表也只是实现该程序的一种数据表达方式之一，下面给出了该程序的另一种数据表达方式，使用动态数组来实现，这两种程序在逻辑上几乎是一致的，唯一的区别是数据结构的表达。另一个不可忽视的地方是时空复杂度，这是影响程序选择的一个至关重要的因素，各位开发者有兴趣的也可自行对比一下两种程序在时空复杂度上有何差别。

#include <stdio.h>
#include <stdlib.h>

//定义多项式结构
typedef struct PolyNode {
	int *Coef;
	int *Expon;  //系数和指数用指针定义，用于动态内存分配
	int Last;  //Last表示最后一个元素的下标位置
} *Polynomial;

//读入
Polynomial ReadPoly(int N)
{
	Polynomial Pa;

	Pa = (Polynomial)malloc(sizeof(struct PolyNode));
	Pa->Coef = (int*)malloc(N * sizeof(int));
	Pa->Expon = (int*)malloc(N * sizeof(int));  //动态分配系数和指数的数组元素个数
	Pa->Last = N - 1;
	for (int i = 0; i <= Pa->Last; i++) {
		scanf("%d %d", &Pa->Coef[i], &Pa->Expon[i]);
	}

	return Pa;
}

Polynomial PolyMult(Polynomial Pa1, Polynomial Pa2)
{
	Polynomial Pa;
	int c, e, N = (Pa1->Last + 1) * (Pa2->Last + 1);  
	//结果数组最大元素个数为多项式1的元素个数 * 多项式2的元素个数，由于数组需要提前分配，因而无可避免会出现空间浪费
	if (!Pa1 || !Pa2)  return NULL;
	Pa = (Polynomial)malloc(sizeof(struct PolyNode));  //使用动态内存分配动态数组，作为结果数组
	Pa->Coef = (int*)calloc(N, sizeof(int));
	Pa->Expon = (int*)calloc(N, sizeof(int));
	Pa->Last = 0;
	//计算逻辑与链表相同，只不过在数据表达上由数组实现
	for (int i = 0; i <= Pa1->Last; i++) {
		for (int j = 0; j <= Pa2->Last; j++) {
			e = Pa1->Expon[i] + Pa2->Expon[j];
			c = Pa1->Coef[i] * Pa2->Coef[j];
			int k = 0;
			while (k <= Pa->Last && Pa->Expon[k] > e)  k++;
			if (k <= Pa->Last && Pa->Expon[k] == e) {  //对应指数相等系数相加的情形
				if (Pa->Coef[k] + c)  Pa->Coef[k] += c;
				else {  //系数相加后为0，则需要通过移动数组的后面元素来消除该项
					for (int p = k; p < Pa->Last; p++) {
						Pa->Coef[p] = Pa->Coef[p + 1];
						Pa->Expon[p] = Pa->Expon[p + 1];
					}
					(Pa->Last)--;
				}
			}
			else {  //对应指数大于某项时的情形，此时需要通过该项后的元素来将结果插入到数组合适位置
				(Pa->Last)++;
				for (int p = Pa->Last; p > k; p--) {
					Pa->Coef[p] = Pa->Coef[p - 1];
					Pa->Expon[p] = Pa->Expon[p - 1];
				}
				Pa->Coef[k] = c;
				Pa->Expon[k] = e;
			}
		}
	}

	return Pa;
}

int Compare(int e1, int e2)
{
	if (e1 > e2)  return 1;
	else if (e1 < e2)  return -1;
	else return 0;
}

Polynomial PolyAdd(Polynomial Pa1, Polynomial Pa2)
{
	Polynomial Pa;
	int sum, N = Pa1->Last + Pa2->Last, i = 0, j = 0;  //结果数组最大元素个数为多项式1元素个数 + 多项式2元素个数
	Pa = (Polynomial)malloc(sizeof(struct PolyNode));
	Pa->Coef = (int*)calloc(N, sizeof(int));
	Pa->Expon = (int*)calloc(N, sizeof(int));
	Pa->Last = 0;
	//逻辑与链表表达完全相同，数据表达方式不同
	while (i <= Pa1->Last && j <= Pa2->Last) {
		switch (Compare(Pa1->Expon[i], Pa2->Expon[j])) {
		case 1:
			Pa->Coef[Pa->Last] = Pa1->Coef[i];
			Pa->Expon[Pa->Last] = Pa1->Expon[i];
			i++;
			break;
		case -1:
			Pa->Coef[Pa->Last] = Pa2->Coef[j];
			Pa->Expon[Pa->Last] = Pa2->Expon[j];
			j++;
			break;
		case 0:
			sum = Pa1->Coef[i] + Pa2->Coef[j];
			if (sum) {
				Pa->Coef[Pa->Last] = sum;
				Pa->Expon[Pa->Last] = Pa1->Expon[i];
			}
			i++;  j++;
			break;
		}
		(Pa->Last)++;
	}
	for (; i <= Pa1->Last; i++) {
		Pa->Coef[Pa->Last] = Pa1->Coef[i];
		Pa->Expon[Pa->Last] = Pa1->Expon[i];
		if (i != Pa1->Last)  (Pa->Last)++;
	}
	for (; j <= Pa2->Last; j++, (Pa->Last)++) {
		Pa->Coef[Pa->Last] = Pa2->Coef[j];
		Pa->Expon[Pa->Last] = Pa2->Expon[j];
		if (i != Pa2->Last)  (Pa->Last)++;
	}

	return Pa;
}

void PrintPoly(Polynomial Pa)
{
	if (!Pa) {
		printf("0 0\n");
		return;
	}
	else {
		printf("%d %d", Pa->Coef[0], Pa->Expon[0]);
		for (int i = 1; i <= Pa->Last; i++) {
			if (!Pa->Coef[i])  break;
			printf(" %d %d", Pa->Coef[i], Pa->Expon[i]);
		}
		printf("\n");
	}
}

int main(void)
{
	Polynomial Pa1, Pa2, PaP, PaS;
	int N1, N2;
	//由于需要知道元素数量以定义和处理数组，故此时需要在主函数内获取表达式项数
	scanf("%d", &N1);
	Pa1 = ReadPoly(N1);
	scanf("%d", &N2);
	Pa2 = ReadPoly(N2);

	PaS = PolyAdd(Pa1, Pa2);
	PaP = PolyMult(Pa1, Pa2);
	printf("\n");
	PrintPoly(PaS);
	PrintPoly(PaP);
	//释放内存
	free(Pa1);
	free(Pa2);
	free(PaP);
	free(PaS);

	return 0;
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

三、迷宫问题

迷宫是一种可以用矩阵（二维数组）来表示的结构，考虑一个正方形的迷宫矩阵，其中可行处值为0，障碍处值为1，要求从一个入口出发，经过若干连同的格子到达指定的出口。对该问题的求解，可以从入口开始尝试各个方向以找到下一个位置，并进而在新的位置再尝试所有可能找到出口的下一个位置。当在某位置所有可能都找不到新位置时，说明进入了“死胡同”需要返回，即“回溯”。为了记住回溯的位置，需要采用一种数据结构来保存和回复从前尝试过的潜在路径的位置信息，这个数据结构应该具有“后入先出”的特点，因而就是堆栈。
在移动时，位于迷宫边缘的位置只有5个可移动方向，处于四角的位置只有3个可移动方向，而其它位置有8个可移动方向，为避免这类特殊情况，可以人为地环绕迷宫增加一圈障碍（即值为1的正方形环）。
关于堆栈创建、入栈、以及出栈的函数与实例一中一致，此处不再赘述。调用该函数时，假设迷宫已经给出，用带边界的二维数组Maze[ ][ ]来表示；入口位置为(1, 1)，出口位置为(EXITROW, EXITCOL)。若迷宫无解，该函数将输出“该迷宫无解。”；若有解，则将顺序输出从入口到出口的路径上每个位置的横、纵坐标。
同时为了避免重复访问，选用一个二维数组Mark[MAXMATRIXSIZE][MAXMATRIXSIZE]来标记已经走过的位置，如果位置[Row][Col]已经被走过，则Mark[Row][Col]为1，否则为0。
注：由于堆栈弹出的路径是反向的，因此选用从出口向入口反向搜索比较方便。其方法与正向搜索是一致的，以下为反向搜索的求解程序：

#define MAXMATRIXSIZE 100  //迷宫矩阵最大行列数
#define MAXSTACKSIZE 100  //堆栈最大规模

typedef int Position;
typedef struct SNode {
	ElementType* data;
	Position Top;
	int Maxsize;
} *Stack; 

struct Offsets {  //偏移结构量
	short int Vert;
	short int Horiz;
};

struct MazePosition {  //迷宫中的位置结构
	short int Row;  //行号
	short int Col;  //列号
	short int Dir;  //对应偏移量数组的方向号
};

typedef struct MazePosition ElementType;  //堆栈元素类型

void Path(int Maze[][MAXMATRIXSIZE], int EXITROW, int EXITCOL)
{   //从出口向入口反向搜索的迷宫问题路径求解程序
	//默认迷宫Maze的入口为(1,1)，出口为(EXITROW, EXITCOL)
	
	//迷宫8个方向的偏移量数组
	struct Offsets Move[8] = { {-1,0}, {-1, 0}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
	int Mark[MAXMATRIXSIZE][MAXMATRIXSIZE];  //标记位置是否走过，走过则该位置的值为1，否则为0
	Stack S;  //辅助求解的堆栈
	struct MazePosition P;
	short int Row, Col, NextRow, NextCol, Dir;
	bool Found = false;

	S = CreateStack(MAXSTACKSIZE);  //初始化空堆栈
	Mark[EXITROW][EXITCOL] = 1;  //从出口位置开始，标记为走过
	//将出口位置及下一个方向放入堆栈
	P.Row = EXITROW;
	P.Col = EXITCOL;
	P.Dir = 0;
	Push(S, P);

	while (!IsEmpty(S) && !Found) {  //当栈非空且未找到入口时
		P = Pop(S);  //取出栈顶元素为当前位置
		Row = P.Row;  Col = P.Col;  Dir = P.Dir;
		while (Dir < 8 && !Found) {  //当还有方向可探且没找到入口时
			//尝试往下一个方向的Dir移动
			NextRow = Row + Move[Dir].Vert;
			NextCol = Col + Move[Dir].Horiz;
			if (NextRow == 1 && NextCol == 1)  Found = true;  //如果到达入口
			else {  //否则若下一个位置不是入口，并可通，且未经过
				if (!Maze[NextRow][NextCol] && !Mark[NextRow][NextCol]) {
					Mark[NextRow][NextCol] = 1;  //标记为走过
					//当前位置和下一个方向存入堆栈
					P.Row = Row;
					P.Col = Col;
					P.Dir = Dir + 1;
					Push(S, P);
					//更新当前位置，从方向0开始
					Row = NextRow; Col = NextCol; Dir = 0;
				}  //结束if
				else  ++Dir;  //若此路不通，则在当前位置尝试下一个方向
			}
		}  //结束8方向探测
	}   //结束搜索
	if (Found) {  //找到一条路径并输出
		printf("找到路径如下\n");
		printf("行 列\n");
		printf("1  1\n");  //打印入口
		printf("%d  %d\n", Row, Col);  //不要忘记最后一步未入堆栈
		while (!IsEmpty(S)) {
			P = Pop(S);
			printf("%d  %d\n", P.Row, P.Col);
		}
	}
	else  printf("该迷宫无解。\n");
}
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

四、符号配对

该实例编写了一段可以检查符号是否配对的程序，包括以下几个符号：/* /、{ }、[ ]、( )。
输入说明：输入为一段c语言源程序。当读到某一行中只有一个据点“.”和回车时，标志着输入结束。程序中需要检查配对的符号不超过100个。
输出说明：若所有符号配对正确，则在第一行输处“YES”，否则输出“NO”；此外，若符号配对错误，还会在第二行输出“?-缺少的符号”（缺少左符号时）/“缺少的符号-？”（缺少右符号时。
问题思路分析：程序的大体逻辑就是读入字符，在读入左半符时保存下来，在读入右半符时，检查其与最近一次读到的左半符是否匹配，若匹配就可以消除一对，否则报错，可以发现，对于需要保存的左半符，最近被保存的需要最先被拿出，因而可以使用栈这种结构来保存左半符，在判断“/”时，需要连续判断两个符号，若两个符号并未连在一起，则说明只是不用匹配的普通字符。判断程序结束的标志是“另起一行，读到句点，后面是回车”，因此需要设置一个变量记录是否读到了回车，读到就说明新起了一行，因此在读到句点时需要判断其是否在一个新行，同时还要判断句点后是否是换行符，由此，我们可以定义一个枚举来保存所有需要处理的符号，不同的符号代表不同的值，在判断是否匹配时，可以通过它们的相互之差来确定。
此外，与前几个实例中不同，为了使程序处理起来更加方便，在该程序中出栈函数被拆成了两个部分，Pop只删除栈顶元素，Peek只返回栈顶元素值。
最后，当主函数调用核心函数Check时，除了需要知道其返回的错误类型，如果有错还需要知道出错的半边符号是什么，以便最后输出，所以Check函数带了两个符号变量的地址作为参数，完成检查后，需要把出问题的左右两个半符 存到两个对应的地址里去。
具体程序代码如下：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100  //处理符号的最大数量
typedef enum { false, true } bool;
//Token即符号类型的枚举，从左至右依次对应\n, /*, {, [, (, }, ], ), */, others为其他不用匹配的普通字符
typedef enum { ret, lc, lbrc, lbrkt, lpr, rc, rbrc, rbrkt, rpr, others } Token;
typedef Token ElementType;

//堆栈的定义
typedef int Position;
typedef struct SNode {
    ElementType* Data;
    Position Top;
    int MaxSize;
} *Stack;

//堆栈的一系列操作函数
Stack CreateStack(int MaxSize);
bool IsTempty(Stack S);
void Push(Stack S, ElementType X);
ElementType Peek(Stack S);  //只返回栈顶元素的值
void Pop(Stack S);  //只删除栈顶元素

//问题相关函数
bool IsEnd(int newline, char* c);  //判断程序是否结束
Token GetToken(char c);  //检查输入符号的类型并返回对应值
bool IsPaired(Token t1, Token t2);  //检查符号是否配对
void PrintS(Token t);  //打印结果
int Check(Token* T1, Token* T2);  //核心函数

int main(void)
{
    Token T1, T2;  //定义符号的枚举类型
    int error = Check(&T1, &T2);

    if (!error) printf("YES\n");  //符号全部匹配，打印YES
    else {
        printf("NO\n");
        switch (error) {
        case 1:  //缺少左半符
            printf("?-");
            PrintS(T1);
            break;
        case 2:  //缺少右半符
            PrintS(T2);
            printf("-?");
            break;
        default:
            break;
        }
        printf("\n");
    }
    return 0;
}

Stack CreateStack(int MaxSize)
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;

    return S;
}

bool IsEmpty(Stack S)
{
    return (S->Top == -1);
}

void Push(Stack S, ElementType X)
{
    S->Data[++(S->Top)] = X;
}

ElementType Peek(Stack S)
{
    return (S->Data[S->Top]);
}

void Pop(Stack S)
{
    (S->Top)--;
}

//符号配对的核心函数
int Check(Token* T1, Token* T2)
{
    Stack S;  //检测匹配用的堆栈
    char c;  //存读入的字符
    Token t;  //存字符转换后的类型
    int newline, error;  //newline标识当前是否新行，error标识错误
    S = CreateStack(MAXN);
    newline = 1;  //初始为新行
    error = 0;  //初始无错误
    while (1)
    {
        scanf("%c", &c);
        if (IsEnd(newline, &c))  break;  //如果已经读到结尾，则跳出循坏
        else {
            switch (t = GetToken(c)) {  //否则，解析c的类型
                //如果是左半符
            case lc:
            case lbrc:
            case lbrkt:
            case lpr:
                //左半符入栈，不再是新行
                Push(S, t);
                newline = 0;
                break;
            case rc:
            case rbrc:
            case rbrkt:
            case rpr:
                //若堆栈已空，右半符不匹配
                if (IsEmpty(S))  error = 1;
                //若栈顶元素和当前读入不匹配，左半符不匹配
                else if (!IsPaired(t, Peek(S)))  error = 2;
                else Pop(S);  //一切正常，消去一对、、
                newline = 0;  //不再是新行
                break;
            case ret:  newline = 1; break;  //遇到回车则标识新行
            default:  newline = 0; break;  //其他字符跳过不处理
            }
            if (error)  break;  //发现错误则跳出循坏
        }
    }
    //读到结尾时堆栈为空，则左半符过多，报错
    if (!error && !IsEmpty(S))  error = 2;
    (*T1) = t;
    (*T2) = Peek(S);

    return error;
}

bool IsEnd(int newline, char* c)
{  //判断是否读到结尾
    if (newline && (*c) == '.') {
        scanf("%c", c);
        if ((*c) == '\n')  return true;  //检查.后面是否为换行符
        else  return false;
    }
    else  return false;
}

Token GetToken(char c)  //判断读入符号的类型并返回对应值
{
    switch (c) {
    case '\n':  return ret;
    case '{':  return lbrc;
    case '[':  return lbrkt;
    case '(':  return lpr;
    case '/':
        scanf("%c", &c);
        if (c == '*')  return lc;
        else return GetToken(c);  //如果不是左注释符，还要递归检查c的类型
    case '}':  return rbrc;
    case ']':  return rbrkt;
    case ')':  return rpr;
    case '*':
        scanf("%c", &c);
        if (c == '/')  return rc;
        else  return GetToken(c);  //如果不是右注释符，还要递归检查c的类型
    default:  return others;
    }
}

bool IsPaired(Token t1, Token t2)
{
    //t1是右半符，t2是左半符
    //若它们的enum值差4，说明是匹配的
    return (t1 - t2) == 4;
}

void PrintS(Token t)  //打印结果
{
    switch (t) {
    case lc:  printf("/*");  break;
    case lbrc:  printf("{");  break;
    case lbrkt:  printf("[");  break;
    case lpr:  printf("(");  break;
    case rc:  printf("*/");  break;
    case rbrc:  printf("}");  break;
    case rbrkt:  printf("]");  break;
    case rpr:  printf(")");  break;
    default:  break;
    }
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189