万字长文，整理不易。点赞加评论期末高分过！
感谢你这么帅（漂亮）还支持我
训练网站：PTA训练平台
7-1 一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0
解析：
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct LNode *List; struct LNode { ElementType coe;//系数 ElementType exp;//指数 List Next;//下一个节点 }; void Insert(List L, ElementType coe, ElementType exp);//插入 List Multi(List p1, List p2);//乘法 List Plus(List p1, List p2);//加法 int compare(List p1, List p2);//比较系数大小 int main() { List p1, p2; List p; int num1, num2, coe, exp; int i; p1 = (List) malloc(sizeof(struct LNode)); p2 = (List) malloc(sizeof(struct LNode)); p1->Next = NULL; p2->Next = NULL; scanf("%d", &num1); for (i = 0; i < num1; i++) { scanf("%d %d", &coe, &exp); Insert(p1, coe, exp); } scanf("%d", &num2); for (i = 0; i < num2; i++) { scanf("%d %d", &coe, &exp); Insert(p2, coe, exp); } //乘法运算 p = Multi(p1->Next, p2->Next); while (p) { if (p->Next != NULL) { printf("%d %d ", p->coe, p->exp);//非最后一个节点,不换行打印,后接空格 } else { printf("%d %d\n", p->coe, p->exp);//最后一个节点,换行打印 } p = p->Next; } //加法运算 p = Plus(p1->Next, p2->Next); if (p) { while (p) { if (p->Next != NULL) { printf("%d %d ", p->coe, p->exp); } else { printf("%d %d\n", p->coe, p->exp); } p = p->Next; } } else {//防止出现p1,p2抵消为零的情况 printf("0 0\n"); } return 0; } /** * 向链表中添加元素 * @param L 需要添加的链表 * @param coefficient 系数 * @param exponent 指数 */ void Insert(List L, ElementType coe, ElementType exp) { List s, p; p = L; while (p->Next)//找到最后一个节点 p = p->Next; s = (List) malloc(sizeof(struct LNode)); s->Next = NULL; s->coe = coe; s->exp = exp; p->Next = s; } /** * 两个多项式相乘 * @param p1 代表多项式1的链表 * @param p2 代表多项式2的链表 * @return p 相乘后生成的新链表 */ List Multi(List p1, List p2) { List p, p1a, p2a, s; int flag = 1; p = (List) malloc(sizeof(struct LNode)); p->Next = NULL; p1a = p1; while (p1a) { p2a = p2;//确保p1多项式中的每一项可以与p2多项式中的每一项分别相乘 s = (List) malloc(sizeof(struct LNode)); s->Next = NULL; while (p2a) {//与p2多项式中的每一项分别相乘 Insert(s, p1a->coe * p2a->coe, p1a->exp + p2a->exp); p2a = p2a->Next; } s = s->Next; if (flag == 1) { p = p->Next; /* * 如果是p1第一项与p2每一项相乘,那么先将链表p向后移一位,将头结点屏蔽 * 因为默认初始化的P1头结点有默认的exp = 0,coe = 0,这两个数据是多余的 * 如果不后移,那么头结点默认的数值0将会一直尾随整个乘法运算,导致最后的结果后面多两个0 0 */ flag = 0; } p = Plus(p, s);//相加,确保同类项合并 p1a = p1a->Next; free(s); } return p; } /** * 比较两多项式指数大小 * @param p1 代表多项式1的链表 * @param p2 代表多项式2的链表 * @return 返回值为0时表示两指数相同,可以进行加法运算 */ int compare(List p1, List p2) { if (p1->exp > p2->exp) return 1;//p1指数大 else if (p1->exp < p2->exp) return -1;//p1指数小 else return 0;//指数相同 } /** * 两个多项式相加 * @param p1 代表多项式1的链表 * @param p2 代表多项式2的链表 * @return p 相加后生成的新链表 */ List Plus(List p1, List p2) { List p, p1a, p2a; int temp; p = (List) malloc(sizeof(struct LNode)); p->Next = NULL; p1a = p1; p2a = p2; while (p1a && p2a) { temp = compare(p1a, p2a); //判断指数大小,同指数才可以运算 switch (temp) { case 1: //当前p1a的指数大,将当前p1a的数据放入新链表 Insert(p, p1a->coe, p1a->exp); p1a = p1a->Next;//p1a向后移动,p2a不改变 break; case -1: //当前p2a的指数大,将当前p2a的数据放入新链表 Insert(p, p2a->coe, p2a->exp); p2a = p2a->Next;//p2a向后移动,p1a不改变 break; case 0: //指数相同,进行运算 if ((p1a->coe + p2a->coe) == 0) { //系数为0,数据不放入新链表,直接将p1a和p2a后移 p1a = p1a->Next; p2a = p2a->Next; } else { //数据放入新链表,p1a和p2a后移 Insert(p, p1a->coe + p2a->coe, p2a->exp); p1a = p1a->Next; p2a = p2a->Next; } break; default: break; } } while (p1a) { //p1a的项数多,将剩余项放入链表 Insert(p, p1a->coe, p1a->exp); p1a = p1a->Next; } while (p2a) { //p2a的项数多,将剩余项放入链表 Insert(p, p2a->coe, p2a->exp); p2a = p2a->Next; } p = p->Next; return p; }
7-2 符号配对
请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。
输入格式:
输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。
输出格式:
首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。
输入样例1：
void test() { int i, A[10]; for (i=0; i<10; i++) { /*/ A[i] = i; } . • 1 • 2 • 3 • 4 • 5 • 6 • 7
输出样例1：
NO /*-?
输入样例2：
void test() { int i, A[10]; for (i=0; i<10; i++) /**/ A[i] = i; }] .
输出样例2：
NO ?-]
输出样例3：
YES
解析：
#include <stdio.h> #include <stdlib.h> #define Maxsize 105 typedef struct StackRecord *Stack; struct StackRecord { int top; char *array; }; Stack creat();//创建空栈 int cheekEmpty(Stack s);//判断栈是否为空 void push(Stack s, char x);//添加新元素 void pop(Stack s);//删除 char top(Stack s);//取出 char a[100]; char str[200]; int main() { int i, j = 0, flag = 0; char ch; Stack s = creat(); while (gets(str)) { if (str[0] == '.' && !str[1]) break; for( i=0; str[i]; i++){ if(str[i]=='('||str[i]=='['||str[i]=='{'||str[i]==')'||str[i]=='}' ||str[i]==']') a[j++]=str[i]; else if(str[i]=='/'&&str[i+1]=='*'){ a[j++]='<'; i++; }else if(str[i]=='*'&&str[i+1]=='/'){ a[j++]='>'; i++; } } } for (i = 0; i < j; i++) { if (a[i] == '(' || a[i] == '[' || a[i] == '{' || a[i] == '<') { push(s, a[i]); } else if (a[i] == ')') { if (s->top != -1 && top(s) == '(') { pop(s); } else { ch = a[i]; flag = 1; break; } } else if (a[i] == ']') { if (s->top != -1 && top(s) == '[') pop(s); else { ch = a[i]; flag = 1; break; } } else if (a[i] == '}') { if (s->top != -1 && top(s) == '{') pop(s); else { ch = a[i]; flag = 1; break; } } else if (a[i] == '>') { if (s->top != -1 && top(s) == '<') pop(s); else { ch = a[i]; flag = 1; break; } } } if (!flag && cheekEmpty(s)) { printf("YES\n"); } else { printf("NO\n"); if (!cheekEmpty(s)) { if (top(s) == '<') printf("/*-?\n"); else printf("%c-?\n", top(s)); } else { if (ch == '>') printf("?-*/\n"); else printf("?-%c\n", ch); } } return 0; } /** * 创建新栈 * @return */ Stack creat() { Stack s = (Stack) malloc(sizeof(struct StackRecord)); s->top = -1; s->array = (char *) malloc(sizeof(char) * Maxsize); return s; } /** * 判断是否为空栈 * @param s * @return */ int cheekEmpty(Stack s) { if (s->top == -1) return 1; else return 0; } /** *添加元素 * @param s * @param x */ void push(Stack s, char x) { s->array[++(s->top)] = x; } /** *删除 * @param s */ void pop(Stack s) { s->top--; } /** *取出 * @param s */ char top(Stack s) { return s->array[s->top]; }
7-3 银行业务队列简单模拟
设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入格式:
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例:
8 2 1 3 9 4 11 13 15
输出样例:
1 3 2 9 11 4 13 15
解答
#include <stdio.h> const int MAX = 1010; int main() { int a[MAX], b[MAX], cnta, cntb; cnta = cntb = 0; int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { int temp; scanf("%d", &temp); if (temp % 2) a[++cnta] = temp; else b[++cntb] = temp; } int flag = 0, x = 1, y = 1; while (x <= cnta || y <= cntb) { if (x <= cnta) { if (flag++) printf(" "); printf("%d", a[x++]); } if (x <= cnta) { if (flag++) printf(" "); printf("%d", a[x++]); } if (y <= cntb) { if (flag++) printf(" "); printf("%d", b[y++]); } } return 0; }
