第二周
两个有序链表序列的合并
List Merge( List L1, List L2 ) { List L3 = (List)malloc(sizeof(struct Node)); List p3 = L3; List p1 = L1->Next, p2 = L2->Next; while (p1 && p2) { if (p1->Data <= p2->Data) { p3->Next = p1; p1 = p1->Next; } else { p3->Next = p2; p2 = p2->Next; } p3 = p3->Next; } if (p1) p3->Next = p1; else p3->Next = p2; L1->Next = NULL, L2->Next = NULL; return L3; }
一元多项式的乘法与加法运算
#include <iostream> using namespace std; typedef struct PolyNode* Polynomial; struct PolyNode { int coef; int expon; Polynomial next; }; // 输出表达式 void output(Polynomial list) { Polynomial cur = list; int cnt = 0; // 如果该多项式是零多项式，则输出 0 0 if (list->next == NULL) printf("0 0"); while (cur->next != NULL) { cur = cur->next; if (!cnt) printf("%d %d", cur->coef, cur->expon); else printf(" %d %d", cur->coef, cur->expon); cnt ++; } } // 读取表达式链表 Polynomial read() { Polynomial list = (Polynomial)malloc(sizeof(struct PolyNode)); list->next = NULL; int len; scanf("%d", &len); Polynomial cur = list; while (len --) { Polynomial p = (Polynomial)malloc(sizeof(struct PolyNode)); scanf("%d%d", &(p->coef), &(p->expon)); p->next = NULL; cur->next = p; cur = p; } return list; } // 计算两式之和 Polynomial compute_sum(Polynomial list1, Polynomial list2) { Polynomial list = (Polynomial)malloc(sizeof(struct PolyNode)); list->next = NULL; Polynomial p = list, p1 = list1->next, p2 = list2->next; while (p1 && p2) { Polynomial cur = (Polynomial)malloc(sizeof(struct PolyNode)); cur->next = NULL; if (p1->expon > p2->expon) { cur->coef = p1->coef; cur->expon = p1->expon; p->next = cur; p = cur; p1 = p1->next; } else if (p1->expon < p2->expon) { cur->coef = p2->coef; cur->expon = p2->expon; p->next = cur; p = cur; p2 = p2->next; } else { if (p1->coef + p2->coef != 0) { cur->coef = p1->coef + p2->coef; cur->expon = p1->expon; p->next = cur; p = cur; } p1 = p1->next, p2 = p2->next; } } while (p1) { Polynomial cur = (Polynomial)malloc(sizeof(struct PolyNode)); cur->next = NULL; cur->coef = p1->coef, cur->expon = p1->expon; p->next = cur; p = cur; p1 = p1->next; } while (p2) { Polynomial cur = (Polynomial)malloc(sizeof(struct PolyNode)); cur->next = NULL; cur->coef = p2->coef, cur->expon = p2->expon; p->next = cur; p = cur; p2 = p2->next; } return list; } // 计算两式乘积 Polynomial compute_prod(Polynomial list1, Polynomial list2) { Polynomial list = (Polynomial)malloc(sizeof(struct PolyNode)); list->next = NULL; Polynomial p1 = list1->next, p2 = list2->next; // 每次用list1的一个结点和list2所有结点相乘 while (p1) { Polynomial cur_head = (Polynomial)malloc(sizeof(struct PolyNode)); // 相乘得到的链表 Polynomial p = cur_head; p2 = list2->next; while (p2) { Polynomial cur = (Polynomial)malloc(sizeof(struct PolyNode)); cur->coef = p1->coef * p2->coef; cur->expon = p1->expon + p2->expon; p->next = cur; p = cur; p2 = p2->next; } // 至少要先乘一次，才能做加法 if (!list->next) list = cur_head; else list = compute_sum(list, cur_head); p1 = p1->next; } return list; } int main() { Polynomial list1 = read(); Polynomial list2 = read(); Polynomial prod = compute_prod(list1, list2); output(prod); puts(""); Polynomial sum = compute_sum(list1, list2); output(sum); return 0; }
Reversing Linked List
Data 数组记录 address 下的值，Next 数组记录下一个地址，list 数组按顺序记录存放的数值。
根据 k 值和 list 长度对 list 子数组进行翻转，注意这里 list 的长度 sum 和输入的长度 len 可能不同。
#include <iostream> using namespace std; const int N = 100010; int Data[N], Next[N], list[N]; int start, len, k; int main() { scanf("%d%d%d", &start, &len, &k); for (int i = 0; i < len; i ++) { int address, tmpData, tmpNext; scanf("%d %d %d", &address, &tmpData, &tmpNext); Data[address] = tmpData, Next[address] = tmpNext; } // 地址原顺序 int sum = 0; while (start != -1) { list[sum ++] = start; start = Next[start]; } // 每k个元素翻转1次地址顺序 for (int i = 0; i < sum - sum % k; i += k) for (int j = 0; j < k / 2; j ++) swap(list[i + j], list[i + k - j - 1]); // 输出地址和元素值 for (int i = 0; i < sum - 1; i ++) printf("%05d %d %05d ", list[i], Data[list[i]], list[i + 1]); printf("%05d %d -1 ", list[sum - 1], Data[list[sum - 1]]); return 0; }
Pop Sequence
直接模拟，按 1~N 的顺序入栈，若当前栈顶元素符合当前出栈元素 s[cur] ，就先出栈，然后再继续入栈。
如果最终 cur 不为 n + 1，就说明不能按照 s 数组中的顺序出栈，输出 NO；否则可以，输出 YES。
#include <iostream> using namespace std; const int N = 1010; int stack[N], s[N], top; int m, n, k; int main() { scanf("%d%d%d", &m, &n, &k); while (k --) { top = -1; int cur = 1; for (int i = 1; i <= n; i ++) scanf("%d", &s[i]); for (int i = 1; i <= n; i ++) { // 入栈 stack[++ top] = i; // 栈满 if (top >= m) break; // 出栈 while (top != -1 && stack[top] == s[cur]) { top --; cur ++; } } // 合法出栈n次，表示该序列合法 if (cur == n + 1) printf("YES "); else printf("NO "); } return 0; }
