Recently ENCOUNTERED such a topic, using a linked list to realize the addition of two polynomials, at the beginning I thought it should be relatively simple, but maybe I did not have a solid foundation, which is also stepping on a lot of pit ah, finally successful, hereby write a blog record.
First, the question requirements
Use a linked list to achieve the addition of two polynomials, output the final sum of the polynomial. By default, polynomials increase in order by exponential (power). When input, coefficients and exponents of each term will be input in turn. Data between two polynomials end with two consecutive zeros to input a polynomial, and finally output the polynomial result of the addition of two polynomials. Such as:
B: X^1 + 2 * X^2 + 3 * X^3Copy the codeInput:
1 1 2 2 3 3 0 0 1 2 2 3 3 0 0Copy the codeOutput:
2 * X^1 + 4 * X^2 + 6 * X^3
Copy the codeAbove is the requirement of the title, let’s begin the formal analysis.
Second, topic analysis
The first problem we’re going to solve is the storage of polynomials, the way they’re represented in the computer, and obviously we just need to store the coefficients and exponents of polynomials to start adding. Here we have two types of storage, one is linear storage, and the other is chain storage.
Linear storage, for example, we use an array to store the data, theory is possible, but as a result of our polynomial number is uncertain, but an array must be must be given at the beginning of an initial size, we not sure, this initial size distribution, can’t store all polynomials, distribution is much, will cause the waste of space, So here we use a linked list to store polynomials. Each time we input a polynomial node, we allocate a linked list node, which can reasonably save space.
Next we look at the concrete implementation steps, which I have broken down into three steps:
Step 1: Take input from the user console and generate a linked list representation of the corresponding two polynomials.
Each of our linked list nodes has three fields. The first two fields are data fields, representing coefficients and exponents of polynomials in turn, and the third field is pointer field, pointing to the next node. In order to facilitate subsequent processing, we add a head node to each edge. As shown below:
Step 2: Add the data in the two lists in turn
This step is our key step, which will be explained in the way of combination of pictures and texts below:
As shown in the figure, we have prepared two linked lists A and B
2 * X^1 + (-2 * X^2) + 2 * X^3 Linked list C is our final sumCopy the codeHere we proceed as follows:
1. We specify three header Pointers to each of the three linked lists, and then three move Pointers to the node being processed in the current three linked lists
2. Let the moving Pointers of A, B, and C also start at the position of the head pointer. Then, we compare the exponents in the first node of A with the exponents in the first node of B.
In case A. the current node index in a < the current node index in B —— we insert the current node in A into C, and then move the Pointers of A and C backwards (because the current node in A has been processed)
The index of the current node in A > the index of the current node in b —— We insert the current node in B into C, and then move the Pointers of B and C backwards (because the current node in B has been processed) i.e. the case of ⑧ in the figure.
In case C. the index of the current node in A > the index of the current node in B —— in this case, the index of the current node in A and B are the same, and the coefficients can be added. In this case, two situations will also occur:
Case 1. The sum of coefficients is not 0 —— At this time we put the coefficient of the sum in A coefficient of the current node in the domain, and then insert the node of A C, and then move back C pointer (remember that we have here is not to create A new node, but directly change the coefficient of A domain, and then insert A current node C), namely in the diagram (1) and (2) (3) process.
Case 2. The sum of coefficients is 0 —— At this point we can’t put coefficient and zero items in A list in C, theory we don’t have to do anything, but there is A small problem, because 1, according to the situation when we coefficient and is not zero is A node directly into the C, we assume that we do nothing after coefficient and 0, continue to deal with subsequent nodes, in A later met A coefficient and is not zero In this case, we insert the node with a non-zero coefficient into C, and we insert the previous node with a zero coefficient into C, assuming that the node with a zero coefficient is always connected to the other nodes. So we now have to remove the current node from A when the sum of the coefficients is 0. That is, ④ and ⑤ in the figure produce ⑥.
Regardless of case 1 or case 2, we’re dealing with both nodes A and B, so we need to move the pointer to both nodes A and B backwards.
There is also A situation, we can A and B chain table length is not consistent, so it is possible to one of the chain table pointer has moved to the end, so at this point, we won’t need to continue to move, we just need to another list of unprocessed data directly in the current production of C the back of the list.
Step 3: Print out the final calculated and linked list expression
Three, code implementation
After the above analysis, we respectively use C language and Java to achieve the above ideas, there are detailed annotations in the code, the following is only a simple explanation.
C language implementation:
#include<stdio.h>
#include<malloc.h>
typedef struct node{
float coef;
int expn;
node *next;
}Lnode, * Dxs;
Dxs create();
Dxs add_dxs(Dxs firsta, Dxs firstb);
void printDxs(Dxs h);
void deleteNode(Dxs h, Dxs p);
int main(){
Dxs ha, hb, hc;
printf("Please enter the coefficients and exponents \n of the first polynomial in turn.");
ha = create();
printf("Please enter the coefficients and exponents \n of the second polynomial in turn.");
hb = create();
printf("The first polynomial input is:");
printDxs(ha->next);
printf("The second polynomial input is:");
printDxs(hb->next);
hc = add_dxs(ha, hb);
printf("The sum of two polynomials is:");
printDxs(hc->next);
return0; } // create a linked list (read data ends with 0 0) Dxscreate() {float coef;
int expn;
Dxs first, qa, s;
first = (Dxs)malloc(sizeof(Lnode));
first->coef = -1;
first->expn = -1;
first->next = NULL;
qa = first;
while(1){
scanf("%f", &coef);
scanf("%d", &expn);
if(coef == 0 && expn == 0){
break;
}
s = (Dxs)malloc(sizeof(Lnode));
s->coef = coef;
s->expn = expn;
s->next = NULL;
qa->next = s;
qa = s;
}
returnfirst; } Dxs add_dxs(Dxs firsta, Dxs firstb){Dxs firstc, ha, hb, PC, s; int a, b;float sum;
firstc = (Dxs)malloc(sizeof(Lnode));
firstc->coef = -1;
firstc->expn = -1;
firstc->next = NULL;
pc = firstc;
ha = firsta->next;
hb = firstb->next;
while(ha! = NULL && hb ! = NULL){ a = ha->expn; b = hb->expn;if(a < b){// add a to c, move a and C pointer PC ->next = ha; pc = pc->next; ha = ha->next; }else if(a > b){// add b to c, move b and c pointer PC ->next = hb; pc = pc->next; hb = hb->next; }else{
sum = ha->coef + hb->coef;
if(sum ! = 0.0){// add sum to a, add sum to c, add sum to c, add sum to c, add sum to c, add sum to c; pc->next = ha; pc = pc->next; }else{// select firsta from A where the sum of the coefficients is 0;while(s ! = ha){ s = s->next; } s->next = ha->next; } // we are done with ab, and we are done with ha = ha->next; hb = hb->next; }} // Add the rest after cif(ha ! = NULL){ pc->next = ha; }if(hb ! = NULL){ pc->next = hb; }returnfirstc; } // iterate over the list voidprintDxs(Dxs h){
while(h ! = NULL){printf("% 0.2 f * X ^ % d +", h->coef, h->expn);
h=h->next;
}
printf("\n");
}
Copy the codeJava language description:
package cn.codekong; import java.util.Scanner; /** ** list class * @author SZH ** / public class MyLink {/** * list Node class * @author SZH ** / class Node{// coefficient of the list privatefloat coef;
//多项式的指数
private int expn;
//指向下级节点
public Node next = null;
public Node(floatcoef, int expn){ this.coef = coef; this.expn = expn; }} /** * Create a linked list class * to read data continuously from the console, ending with (0 0) * @returnCreate the first list Node */ public NodecreateLink(){// Access the coefficients and exponents read from the consolefloatCoef f = 0.0; int expn = 0; // Node head, tail; head= new Node(-1, -1); head.next = null; tail = head; Scanner scanner = new Scanner(System.in);while(true){ String res = scanner.nextLine(); String[] resArray = res.split("\\s+");
coef = Float.parseFloat(resArray[0]);
expn = Integer.parseInt(resArray[1]);
if(coef == 0 && expn == 0.0f){
break;
}
Node node = new Node(coef, expn);
node.next = null;
tail.next = node;
tail = tail.next;
}
returnhead; } /** * print the list * @param head */ public voidprintLink(Node head){
while(head ! = null){ System.out.format("%.2f*X^%d + ", head.coef, head.expn); head = head.next; } System.out.println(); } /** * computes the sum of two linked lists * @param nodeA * @param nodeB * @return*/ public Node addLink(Node nodeA, Node nodeB){Node nodeC = new Node(-1, -1); nodeC.next = null; Nodepa = nodea. next, pB = nodeb. next, pC = nodeC; Int valueAExpn = 0, valueBExpn = 0;while(pA ! = null && pB ! = null){ valueAExpn = pA.expn; valueBExpn = pB.expn;if(valueAExpn < valueBExpn){// Add A to C and move A and C to the next element pc. next = pA; pC = pC.next; pA = pA.next; }else if(valueAExpn > valueBExpn){// Add the node in B to C, and move the pointer of B and C to the next element pc. next = pB; pC = pC.next; pB = pB.next; }else{// The two nodes have the same index // Now add the coefficients to the coefficients of node A, and then add node A to Cfloat sum = pA.coef + pB.coef;
if(sum ! = 0.0f){// the sum of the coefficients of A node is not 0, and the sum of the coefficients of A node is not 0, and the sum of the coefficients of A node is not 0. pC.next = pA; pC = pC.next; }else{// if the sum of the coefficients is 0, the Node in the list must be removed from the list. If only the pointer is moved, the item will also be output.while(s ! = pA){ s = s.next; } // delete the node. Next = pa.next; } // In the case of the same coefficient,A and B Pointers are moved back pA = pa.next; pB = pB.next; }}if(pA ! = null){ pC.next = pA; }if(pB ! = null){ pC.next = pB; }returnnodeC; }}Copy the codepackage cn.codekong;
import cn.codekong.MyLink.Node;
public class MyTest {
public static void main(String[] args) {
MyLink myLink = new MyLink();
System.out.println("Please enter the coefficients and exponents of the first polynomial in turn.");
Node nodea = myLink.createLink();
System.out.println("Please enter the coefficients and exponents of the second polynomial in turn.");
Node nodeb = myLink.createLink();
System.out.println("The first polynomial input is:");
myLink.printLink(nodea.next);
System.out.println("The second polynomial input is:");
myLink.printLink(nodeb.next);
Node nodec = myLink.addLink(nodea, nodeb);
System.out.println("The sum of two polynomials is:"); myLink.printLink(nodec.next); }}Copy the codeIn fact, Java linked list implementation and C language is very similar, except in C language, the node is the definition structure, but here we use an inner class to define each node of the linked list, in C language Pointers are actually Java references, our life Java objects are stored in the heap, and object references are stored in the stack.
To keep Java and C inputs consistent on the console above, I read a line using Scanner and then split coefficients and exponents with regular expressions for subsequent processing.
Four, code operation verification
C language running results:
Java runtime results:
