下载文档原格式
数据结构——链表实现⼀元多项式的表⽰和加法⼀元多项式的链式结构：Typedef struct Lnode{float coef;///系数int expn;///指数struct Lnode *next;} PLnode, *PLinkList;基本思想：（1）若pa->expn⼩于pb->expn,则pa继续向前扫描；(2）若pa->expn等于pb->expn,将其系数相加，若相加结果不为0，将结果放⼊pa->coef中，并删除pb所指的结点，否则同时删除pa和pb所指的结点，然后pa和pb继续向前扫描；（3）若pa->expn⼤于pb->expn,则将pb所指的结点插⼊pa所指的结点之前，然后pb继续向前扫描；（4）重复上述过程直到pa或pb有⼀个为空为⽌，最后将剩余结点的链表接在结果链表上。
PLinklist Add(PLinklist pa,PLinklist pb){PLinklist p,q,r,s; /*两个多项式相加*/int cmp,x;p=pa->next; /*指向pa的第⼀个元素*/q=pb->next; /*指向pb的第⼀个元素*/s=pa; /*s作为P的跟踪指针*/r=pb;/*r作为q的跟踪指针*/while(p!=NULL&&q!=NULL){if(p->exp<q->exp){cmp=-1;}else if(p->exp>q->exp){cmp=1;}else///指数相等{cmp=0;}switch(cmp){/*根据指数的⽐较情况进⾏不同的处理*/case -1:{s=p;p=p->next;///pa表指针后移，没有插⼊break;}case0:{x=p->coef+q->coef;///指数相等，系数相加if(x!=0) /*系数不为0*/{p->coef=x;s=p;p=p->next;}/*if*/else///系数为0,在pa表中删除该结点{s->next=p->next;free(p);p=s->next;}/*else*/r->next=q->next;///在pb表中删除该结点free(q);q=r->next;break;} /*case0*/case1:{q->next=s->next;s->next=q;///将pb表中的q插⼊到pa表中的s的后⾯r->next=q->next;s=q;q=r->next;break;} /*case1*/}/*switch*/}/*while*/if(q!=NULL)///当pb连表还有剩余时接⼊到pa连表的尾部 {s->next=q;}free(pb);return pa;}/* Add*/。
单链表实现多项式的表⽰及运算单链表实现多项式的加法运算最近学习数据结构的线性表，有顺序存储和链表两种，多项式的表⽰和运算，最能巩固学习成果，现在提供详细代码，来实现多项式的加法运算。
多项式⽤单链表最为合适，不会造成更多的资源浪费。
如果你恰好⽤的这本书--数据结构（Java版）（第4版）（叶核亚），推荐你去下⾯这个链接下载书本源代码，将更助你学的轻松。
1//单链表类，实现⼀些基本单链表的操作2public class SinglyList<T> extends Object {3public Node<T> head; // 头指针，指向单链表的头结点45public SinglyList() {6this.head = new Node<T>();7 }89public SinglyList(T[] values) { // values数组中的值构成结点10this();11 Node<T> rear = this.head;12for (int i = 0; i < values.length; i++) {13 rear.next = new Node<T>(values[i], null);14 rear = rear.next;15 }16 }1718public boolean isEmpty() {19return this.head.next == null;20 }2122public T get(int i) {23 Node<T> p = this.head.next;24for (int j = 0; p != null && j < i; j++) {25 p = p.next;26 }27return (i >= 0 && p != null) ? p.data : null;28 }2930public void set(int i, T x) {31if (i < 0 || i > size())32throw new IndexOutOfBoundsException(i + "");33if (x == null)34throw new NullPointerException("x==null");35 Node<T> p = this.head.next;36for (int j = 0; p != null && j < i; j++) {37 p = p.next;38 }39 p.data = x;4041 }4243public int size() {44int len = 0;45 Node<T> p = this.head.next;46if (p == null)47return -1;48while (p != null) {49 len++;50 p = p.next;5152 }53return len;54 }5556public Node<T> insert(int i, T x) {57if (x == null)58throw new NullPointerException("x==null");59 Node<T> front = this.head;60for (int j = 0; front.next != null && j < i; j++) {61 front = front.next;62 }63 front.next = new Node<T>(x, front.next);64return front.next;6566 }6768public Node<T> insert(T t) {69return insert(Integer.MAX_VALUE, t);70 }7172public T remove(int i) {73 Node<T> front = this.head;74for (int j = 0; front.next != null && j < i; j++) {75 front = front.next;76 }77if (i >= 0 && front.next != null) {78 T old = front.next.data;79 front.next = front.next.next;80return old;81 }82return null;8384 }8586public void clear() {87this.head.next = null;88 }8990 }91// 排序单链表，对于⼀些结点可以实现按顺序插⼊排序92public class SortedSinglyList<T extends Comparable<? super T>> extends93 SinglyList<T> {94public SortedSinglyList() {95super();96 }9798public SortedSinglyList(T[] values) { // values的数组中的对象按值插⼊99super();100for (int i = 0; i < values.length; i++) {101this.insert(values[i]);102 }103 }104105public SortedSinglyList(SinglyList<T> list) { // 单链表的深拷贝106super();107for (Node<T> p = list.head.next; p != null; p = p.next)108this.insert(p.data);109 }110111public Node<T> insert(T x) { // 覆盖⽗类的insert⽅法112 Node<T> front = this.head, p = front.next;113while (p != null && pareTo(p.data) > 0) {114 front = p;115 p = p.next;116 }117 front.next = new Node<T>(x, p); // 在front之后，p之前插⼊x节点118return front.next;119 }120121 }122123//可相加接⼝124public interface Addible<T> {125public void add(T t); // 两元素相加126127public boolean removable(); // 删除元素128129 }130//⽐较⼤⼩接⼝131public interface Comparable<T> {132int compareTo(T obj);133134 }135136/*137 * ⼀元多项式节点类存储多项式的系数(coefficient)和指数(exponential)138*/139public class PolyNode implements Comparable<PolyNode>, Addible<PolyNode> { 140private int coef;// 系数141private int expo;// 指数142143protected PolyNode next;144145public PolyNode() {146this(0, 0);147 }148149public PolyNode(int coef, int expo) { // 带参数的构造函数150151this.coef = coef;153// this.next = null;154 }155156public PolyNode(PolyNode po) { // 拷贝构造函数157this(po.coef, po.expo);158 }159160public boolean equals(Object obj) // ⽐较两项是否相等161 {162if (this == obj)163return true;164if (!(obj instanceof PolyNode))165return false;166 PolyNode term = (PolyNode) obj;167return this.coef == term.coef && this.expo == term.expo;168 }169170public PolyNode(String str) { // 参数为⼀个项时，得到项的系数和指数171if (str.charAt(0) == '+')172 str = str.substring(1); // 去掉‘+’号173int i = str.indexOf('x');174if (i == -1) {175this.coef = Integer.parseInt(str); // 没有x,指数就为0176this.expo = 0;177 } else {178if (i == 0) { // x在开头，系数为1179this.coef = 1;180 } else {181 String str1 = str.substring(0, i);// 截取x符号之前的系数182if (str1.equals("-")) { // 为‘-’，系数为-1183this.coef = -1;184 } else {185this.coef = Integer.parseInt(str1);186 }187 i = str.indexOf('^');// 找^符号188if (i == -1)189this.expo = 1;190else191this.expo = Integer.parseInt(str.substring(i + 1));192 }193 }194 }195196public String toString() { // 显⽰多项式的样式197 String sy = this.coef > 0 ? "+" : "-";198if (this.expo == 0 || this.expo > 0 && this.coef != 1199 && this.coef != -1) {200 sy += Math.abs(this.coef); // 系数绝对值，系数为-1或1不能显⽰201 }202if (this.expo > 0)203 sy += "x";// 指数为0不能输出x204if (this.expo > 1)205 sy += "^" + this.expo;// 指数为1不能输出^206return sy;207 }208209public int compareTo(PolyNode a) { // ⽐较两项的⼤⼩210return (this.expo < a.expo ? -1 : (this.expo == a.expo ? 0 : 1)); 211 }212213public void add(PolyNode po) { // 相加214if (pareTo(po) == 0)215this.coef += po.coef;216217 }218219public boolean removable() { // 删除220return this.coef == 0;221 }222223public int getCoef() {224return coef;225 }226227public void setCoef(int coef) {228this.coef = coef;229 }230231public int getExpo() {232return expo;233 }234235public void setExpo(int expo) {237 }238239 }240/*241 * ⼀元多项式排序链表类，提供排序单链表的多项式相加运算；242*/243public class PolySort<T extends Comparable<? super T> & Addible<T>> extends244 SortedSinglyList<T> {245246public PolySort() {247super(); // 构造空单链表248 }249250public PolySort(T value[]) { // 构造⽅法，项的组来指定各项的值251super(value);252 }253254public PolySort(PolySort<T> list) {// 调⽤⽗类的深拷贝函数，复制所有结点255super(list);256 }257258// 多项式相加函数259public void addAll(PolySort<T> list) {260 Node<T> front = this.head, p = front.next;261 Node<T> q = list.head.next;262while (p != null && q != null) {263if (pareTo(q.data) == 0) { // 两项⼤⼩相同264 p.data.add(q.data);265if (p.data.removable()) { // 删除系数为0的结点266 front.next = p.next;267 p = front.next;268 } else {269 front = p;270 p = p.next;271272 }273 q = q.next;274 } else if (pareTo(q.data) < 0) {275 front = p;276 p = p.next;277 } else {278 front.next = new Node<T>(q.data, p);279 q = q.next;280 }281 }282while (q != null) // 将list单链表中剩余结点复制并插⼊到当前链表尾283 {284 front.next = new Node<T>(q.data, null);285 front = front.next;286 q = q.next;287 }288 }289290 }291// 多项式类，使⽤多项式排序单链表类作为成员变量，提供多项式相加运算292public class Polynomial {293private PolySort<PolyNode> list; // 多项式排序单链表294295public Polynomial() // 构造⽅法296 {297this.list = new PolySort<PolyNode>(); // 创建空单链表，执⾏排序单链表默认构造⽅法298 }299300public Polynomial(PolyNode terms[]) // 构造⽅法，由项数组指定多项式各项值301 {302this.list = new PolySort<PolyNode>(terms);303 }304305public Polynomial(String polystr) // 构造⽅法，参数指定多项式表达式字符串306 {307this();308if (polystr == null || polystr.length() == 0)309return;310 Node<PolyNode> rear = this.list.head;311int start = 0, end = 0; // 序号start～end的⼦串为⼀项312while (start < polystr.length() && end < polystr.length()) {313int i = polystr.indexOf('+', end + 1); // 返回字符+在字符串中从end+1开始的序号314if (i == -1) // 未找到指定字符315 i = polystr.length();316int j = polystr.indexOf('-', end + 1);317if (j == -1)318 j = polystr.length();319 end = i < j ? i : j; // end为下⼀个+或-号的序号320 rear.next = new Node<PolyNode>(new PolyNode(polystr.substring(321 start, end)), null);322// 尾插⼊，以序号start～end的⼦串作为⼀项，创建结点，创建元素对象323 rear = rear.next;324 start = end;325 }326 }327328public Polynomial(Polynomial poly) // 深度拷贝构造⽅法，复制所有结点和对象329 {330this(); // 创建空单链表，只有头结点331 Node<PolyNode> rear = this.list.head;332for (Node<PolyNode> p = poly.list.head.next; p != null; p = p.next) // p遍历poly单链表333 {334 rear.next = new Node<PolyNode>(new PolyNode(p.data), null);// 复制结点，复制对象335 rear = rear.next;336 }337 }338339public String toString() // 返回多项式的描述字符串340 {341 String str = "";342for (Node<PolyNode> p = this.list.head.next; p != null; p = p.next)343 str += p.data.toString();344return str;345 }346347public void addAll(Polynomial poly) // 多项式相加，this＋=poly348 {349this.list.addAll(poly.list);350 }351352public Polynomial union(Polynomial poly) // 加法＋，C=this＋poly353 {354 Polynomial polyc = new Polynomial(this); // 深度拷贝，复制所有结点和对象355 polyc.addAll(poly); // polyc＋=poly356return polyc; // 返回对象引⽤357 }358359public boolean equals(Object obj) // ⽐较两个多项式是否相等360 {361return this == obj || obj instanceof Polynomial362 && this.list.equals(((Polynomial) obj).list);363// ⽐较两条单链表是否相等364 }365 }366// 测试类，完成多项式的相加结果并显⽰367public class Poly extends PolySort {368369public static void main(String[] args) {370371 System.out.println("//⼀元多项式");372 PolyNode aterms[] = { new PolyNode(-7, 9), new PolyNode(2, 7),373new PolyNode(-9, 4), new PolyNode(1, 2), new PolyNode(-1, 1),374new PolyNode(2, 0) };375 Polynomial apoly = new Polynomial(aterms);376377 PolyNode bterms[] = { new PolyNode(9, 11), new PolyNode(5, 10),378new PolyNode(-3, 8), new PolyNode(10, 4), new PolyNode(-1, 2),379new PolyNode(1, 1), new PolyNode(-1, 0) };380 Polynomial bpoly = new Polynomial(bterms);381382// Polynomial bpoly = new Polynomial("-1+x-x^2+10x^4-3x^8+5x^10+9x^11");383 System.out.println("A=" + apoly.toString() + "\nB=" + bpoly.toString());384385 Polynomial cpoly = apoly.union(bpoly);386 System.out.println("C=A+B，C=" + cpoly.toString());387 apoly.addAll(bpoly);388 System.out.println("A+=B，A=" + apoly.toString());389390 }391 }。
通信韩若冰222010315220106实验项目：线性表及其应用实验内容：用单链表存储多项式；实现多项式的输出显示、相加、相乘、求导、求值运算。
算法设计与程序实现：由于存储多项式需要存储系数和指数，且其指数变化范围可能很大如果用顺序表就会浪费很大的空间，用单链表存取指针域，和数据域（系数和指数）就会节省很大空间。
要想实现多项式的显示，相加，相乘，求导，求值运算，首先得创建函数以实现上述功能，然后再在主函数中调用上述函数以得到运行结果。
算法描述：（实验内容的核心算法）创建链表：首先创建空表，然后将每个结点用尾插法依次插入。
每一项多项式的组成部分（系数和指数）输出程序：此程序需要遍历整个链表，通过判断p->next的系数的正负来确定输出“+”还是“-”很容易出现错误。
多项式相加：这个程序需要按照幂的排列顺序依次遍历寻找一个多项式与另一个多项式指数相同的，将其系数相加比较简单。
该程序写成升幂比较，其中可能出现如A多项式的前几项都比B中的指数小，那么以一个pre为头结点的链表先将其穿起来，找到相等的进行运算再串起来，最后可能会有链表剩余的指数更大的项不能和另一个相加再将剩余的串起来。
（第一项要先串起来，因为第一项之前没有多项式不用判断+ —号）多项式相乘：此程序需要循环语句，即将一个多项式的每一项分别和另一个多项式相乘，依次调用多项式相加的程序叠加起来。
多项式求导：需要依次将多项式的每一项的系数和指数相乘，指数减1，形成一个链表多项式求值：需要有x的幂次的表示，C语言不能识别“^”，所以需要用一个循环实现x^exp相乘的结果，容易出错核心程序：运行结果：实验总结：本次试验做了很长时间，也出现了很多错误。
总起来说有以下几种错误：1.输入错误：中英文状态下输入错误，其中还有运行时在中文状态下输入数据回车后就不能输了，应在英文状态下输入data , data↙2.多项式表示需要判断下一个多项式系数是正还是负然后分别写+, —（fabs），但是第一项必须先输出,因为第一项不需要写+ —号3.多项式相加，要注意写的程序是怎么比较的，升幂的话则p->exp < q->exp 则把p结点指数小的先穿起来。
