第二周编程作业
1、两个有序链表序列的合并
List Merge( List L1, List L2 ) { List temp, cur, result; // 0. 初始化 result = (List) malloc(sizeof(struct Node)); cur = result; while (L1->Next && L2->Next) { // 1. 比较 if (L1->Next->Data <= L2->Next->Data) { // 2. 取小的那个 temp = L1->Next; // 3. 改造原链表 L1->Next = temp->Next; } else { temp = L2->Next; L2->Next = temp->Next; } // 4. 插到结果链表尾部 cur->Next = temp; cur = cur->Next; } // 5. 破坏条件 cur->Next = L1->Next ? L1->Next : L2->Next; if (L1->Next) { L1->Next = NULL; } else { L2->Next = NULL; } return result; }
2、一元多项式的乘法与加法运算
#include <cstdio> #include <cstdlib> typedef struct polynomial_node* polynomial; struct polynomial_node { int xs; // 系数 int zs; // 指数 polynomial next; }; typedef struct polynomial_node* Node; polynomial readPoly() { int n, xs, zs; // 1. 先读有多少位 scanf("%d", &n); // 2. 创建多项式的头结点 polynomial result, temp, rear; rear = result = (polynomial) malloc(sizeof(struct polynomial_node)); while (n--) { // 3. 逐个添加多项式的项 scanf("%d %d", &xs, &zs); // 创建项 temp = (polynomial) malloc(sizeof(struct polynomial_node)); temp->xs = xs; temp->zs = zs; // 添加项 rear->next = temp; rear = rear->next; } rear->next = NULL; return result; } void printPoly(polynomial poly) { if (poly->next == NULL) { printf("0 0 "); return; } printf("%d %d", poly->next->xs, poly->next->zs); poly = poly->next; while (poly->next) { printf(" %d %d", poly->next->xs, poly->next->zs); poly = poly->next; } printf(" "); } Node buildNode(int xs, int zs) { Node node = (Node) malloc(sizeof(struct polynomial_node)); node->xs = xs; node->zs = zs; node->next = NULL; return node; }; Node copyNode(Node node) { return buildNode(node->xs, node->zs); }; polynomial add(polynomial p1, polynomial p2) { polynomial result, rear; rear = result = (polynomial) malloc(sizeof(struct polynomial_node)); result->next = NULL; p1 = p1->next; p2 = p2->next; // p1 和 p2 都有头结点 while (p1 && p2) { // 1. 比较 if (p1->zs > p2->zs) { // 2. 取大的那一项添加到结果链表 rear->next = copyNode(p1); rear = rear->next; // 3. p1指向下一位 p1 = p1->next; } else if (p1->zs < p2->zs) { rear->next = copyNode(p2); rear = rear->next; p2 = p2->next; } else { // 相等的情况，指数不变系数相加 if (p1->xs + p2->xs != 0) { rear->next = buildNode(p1->xs + p2->xs, p1->zs); rear = rear->next; } p1 = p1->next; p2 = p2->next; } } // 4. 破坏条件 while (p1) { rear->next = copyNode(p1); rear = rear->next; p1 = p1->next; } while (p2) { rear->next = copyNode(p2); rear = rear->next; p2 = p2->next; } return result; } // 多项式乘以一项 polynomial multi0(polynomial p, Node node) { polynomial result, rear; rear = result = (polynomial) malloc(sizeof(struct polynomial_node)); result->next = NULL; p = p->next; // p有头结点 while (p) { rear->next = buildNode(p->xs * node->xs, p->zs + node->zs); rear = rear->next; p = p->next; } return result; } polynomial multi(polynomial p1, polynomial p2) { // 将乘法运算转化为加法运算 polynomial result = (polynomial) malloc(sizeof(struct polynomial_node)), temp; result->next = NULL; Node node = p2->next; while (node) { temp = multi0(p1, node); result = add(result, temp); node = node->next; } return result; } int main() { // 1. 读 2 个 多项式 polynomial p1 = readPoly(); polynomial p2 = readPoly(); // 2. 相乘与相加 polynomial pa = multi(p1, p2); polynomial pb = add(p1, p2); // 3. 输出结果 printPoly(pa); printPoly(pb); return 0; }
3、Reversing Linked List
#include <stdio.h> #include <stdlib.h> struct Node { int val; int next; }; typedef struct Node* MyNode; MyNode buildNode(int val, int next) { MyNode result = (MyNode) malloc(sizeof(struct Node)); result->val = val; result->next = next; return result; } MyNode nodes[(int) 1e5 + 1]; int order[(int) 1e5 + 1]; void reverse(int a[], int i, int j) { int tmp; while (i < j) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; i++; j--; } } int main() { int firstAddress, n, k, address, val, next; scanf("%d %d %d", &firstAddress, &n, &k); // 1. 读入数据 for (int i = 0; i != n; ++i) { scanf("%d %d %d", &address, &val, &next); nodes[address] = buildNode(val, next); } // 2. 将数据按原逻辑顺序存储到order数组 int realN = 0; // realN用于统计真正在链表上的结点数（有的结点不在链表上） address = firstAddress; while (address != -1) { order[realN++] = address; address = nodes[address]->next; } // 3. 重排序 int batch = realN / k; for (int i = 0; i != batch; ++i) { reverse(order, i * k, (i + 1) * k - 1); } // 4. 输出结果 for (int i = 0; i != realN - 1; ++i) { printf("%5.5d %d %5.5d ", order[i], nodes[order[i]]->val, order[i + 1]); } printf("%5.5d %d -1 ", order[realN - 1], nodes[order[realN - 1]]->val); return 0; }
4、Pop Sequence
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // bool true false #define MAX 1000 + 1 #define STACK_EMPTY -1 struct Stack { int a[MAX]; int maxSize; int top; }; typedef struct Stack* MyStack; MyStack buildStack(int maxSize) { MyStack result = (MyStack) malloc(sizeof(struct Stack)); result->maxSize = maxSize; result->top = STACK_EMPTY; return result; } void clearStack(MyStack s) { s->top = STACK_EMPTY; } bool push(MyStack s, int val) { if (s->top == s->maxSize - 1) return false; s->a[++(s->top)] = val; return true; } void pop(MyStack s) { if (s->top != STACK_EMPTY) { s->top = s->top - 1; } } int topVal(MyStack s) { if (s->top == STACK_EMPTY) return STACK_EMPTY; return s->a[s->top]; } bool check(MyStack s, int N, int checkSeq[]) { int cur = 0; int curPushVal = 1; bool ok = false; for (int i = 0; i != N + N; ++i) { if (topVal(s) == checkSeq[cur]) { pop(s); cur++; } else { if (curPushVal > N) return false; ok = push(s, curPushVal++); if (!ok) return false; } } return true; } int checkSeq[MAX]; int main() { int M, N, K; // M (the maximum capacity of the stack), // N (the length of push sequence), // K (the number of pop sequences to be checked). scanf("%d %d %d", &M, &N, &K); MyStack s = buildStack(M); for (int i = 0; i != K; ++i) { for (int j = 0; j != N; ++j) { scanf("%d", &checkSeq[j]); } printf("%s ", check(s, N, checkSeq) ? "YES" : "NO"); clearStack(s); } return 0; }