数据结构实验一

#include <stdio.h>
#include <stdlib.h>
#include <math.h>// 数据类型定义
typedef struct {float coef;   // 系数int expn;     // 指数
} ElemType;// [核心改造] LinkList 本身就是指针类型，声明变量时不用加 *
typedef struct LNode {ElemType data;struct LNode *next;
} LNode, *LinkList;typedef LinkList polynomial;// -------------------------- 基础操作 --------------------------// 初始化：直接返回头结点指针，内部不用 *L
polynomial InitList() {polynomial L = (polynomial)malloc(sizeof(LNode));if (!L) { printf("内存分配失败\n"); exit(1); }L->next = NULL;return L;
}// 插入项：自动排序 + 合并同类项 + 过滤零系数
int InsertPolyn(polynomial P, ElemType e) {if (fabs(e.coef) < 1e-6) return 0; // 忽略系数为0的项polynomial pre = P;while (pre->next && pre->next->data.expn < e.expn) {pre = pre->next;}// 指数已存在：直接累加系数if (pre->next && pre->next->data.expn == e.expn) {pre->next->data.coef += e.coef;// 累加后抵消为0，则删除节点if (fabs(pre->next->data.coef) < 1e-6) {polynomial q = pre->next;pre->next = q->next;free(q);}} else {// 指数不存在：申请新节点插入（直接赋值，无多余 *）polynomial q = (polynomial)malloc(sizeof(LNode));q->data = e;q->next = pre->next;pre->next = q;}return 1;
}// 创建多项式：返回构建好的链表指针
polynomial CreatPolyn(int m) {polynomial P = InitList(); // 直接接收返回值，无 *ElemType e;printf("请输入%d个项（系数 指数）：\n", m);for (int i = 0; i < m; i++) {scanf("%f %d", &e.coef, &e.expn);InsertPolyn(P, e);}return P;
}// 多项式加法：复用原节点，返回新链表
polynomial AddPolyn(polynomial Pa, polynomial Pb) {polynomial Pc = InitList();polynomial p1 = Pa->next, p2 = Pb->next, p3 = Pc;while (p1 && p2) {if (p1->data.expn < p2->data.expn) {p3->next = p1; p3 = p1; p1 = p1->next;} else if (p1->data.expn > p2->data.expn) {p3->next = p2; p3 = p2; p2 = p2->next;} else {float sum = p1->data.coef + p2->data.coef;if (fabs(sum) > 1e-6) { // 未抵消p1->data.coef = sum;p3->next = p1; p3 = p1; p1 = p1->next;polynomial tmp = p2; p2 = p2->next; free(tmp);} else { // 抵消为0polynomial tmp1 = p1, tmp2 = p2;p1 = p1->next; p2 = p2->next;free(tmp1); free(tmp2);}}}p3->next = p1 ? p1 : p2; // 拼接剩余部分free(Pa); free(Pb); // 释放原头结点return Pc;
}// -------------------------- 打印与销毁 --------------------------void PrintPolyn(polynomial P) {if (!P->next) { printf("0\n"); return; }polynomial p = P->next;int first = 1;while (p) {float c = p->data.coef;int e = p->data.expn;if (first) { if (c < 0) printf("-"); }else { printf(c > 0 ? " + " : " - "); }printf("%.2f", fabs(c));if (e > 0) printf("x");if (e > 1) printf("^%d", e);first = 0; p = p->next;}printf("\n");
}void DestroyPolyn(polynomial P) {polynomial p = P, q;while (p) { q = p->next; free(p); p = q; }
}// -------------------------- 主函数 --------------------------
int main() {// [清爽声明] 变量本身就是指针，完全不用写 *polynomial Pa, Pb, Pc;int m1, m2;printf("=== 创建多项式Pa ===\n");printf("项数: "); scanf("%d", &m1);Pa = CreatPolyn(m1);printf("Pa = "); PrintPolyn(Pa);printf("\n=== 创建多项式Pb ===\n");printf("项数: "); scanf("%d", &m2);Pb = CreatPolyn(m2);printf("Pb = "); PrintPolyn(Pb);printf("\n=== 计算 Pa + Pb ===\n");Pc = AddPolyn(Pa, Pb);printf("Pa + Pb = "); PrintPolyn(Pc);DestroyPolyn(Pc);return 0;
}