I am trying to implement addition of polynomials using linked list. The program adds the power 0 coefficients successfully but after the first traversal it panics. Here is the code I have written so far. after initializing temp1!= nil the loop iterates over else but doesn't enter if loop when powers are different and goes into panic state
package main
import (
"fmt"
)
type Node struct {
coefficient int
power int
next *Node
}
type list struct {
head *Node
count int
}
func main() {
list1 := &list{}
list1.addVariable(5, 2)
list1.addVariable(4, 1)
list1.addVariable(3, 0)
list1.print()
list2 := &list{}
list2.addVariable(4, 1)
list2.addVariable(2, 0)
list2.print()
list4 := addLists(list1, list2)
list4.print()
}
func (lst *list) print() {
temp := lst.head
for temp != nil {
fmt.Print(temp.coefficient, "x", "^", temp.power, "+")
temp = temp.next
}
fmt.Println("\n")
}
func (lst *list) addVariable(coefficient int, power int) {
lst.head = &Node{coefficient, power, lst.head}
lst.count++
}
func addLists(list1 *list, list2 *list) *list {
list3 := &list{}
temp1 := list1.head
temp2 := list2.head
fmt.Println("reached") // for debugging purposes
if list1.count > list2.count {
fmt.Println("\nreached 2") // for debugging purposes
for temp1 != nil {
fmt.Println("reached3") // for debugging purposes
if temp1.power != temp2.power {
fmt.Println("reached4") // for debugging purposes
list3.normalAdd(temp1, temp2)
temp1 = temp1.next
} else {
fmt.Println("reached5") // for debugging purposes
node4 := add(temp1, temp2)
list3.exlusiveAdd(node4)
temp1 = temp1.next
temp2 = temp2.next
}
}
}
return list3
}
func (lst *list) normalAdd(node6 *Node, node7 *Node) {
node6.next = lst.head
lst.head = node6
node7.next = lst.head
lst.head = node7
lst.count += 2
}
func (lst *list) exlusiveAdd(node5 *Node) {
node5.next = lst.head
lst.head = node5
lst.count++
}
func add(node1, node2 *Node) *Node {
node3 := &Node{}
node3.coefficient = node1.coefficient + node2.coefficient
node3.power = node1.power
return node3
}
Output when the program is run:
3x^0+4x^1+5x^2+
2x^0+4x^1+
reached
reached 2
reached3
reached5
reached3
reached5
reached3
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0xffffffff addr=0x0 pc=0xd48e6]
goroutine 1 [running]:
main.addLists(0x41c7a8, 0x41c7a0, 0x40c120, 0x1d)
/tmp/sandbox520212269/main.go:56 +0x186
main.main()
/tmp/sandbox520212269/main.go:28 +0x220
playground here
Update: Thanks for the solution but I have successfully written the code for above problem. here it is. package main
import (
"fmt"
)
type Node struct {
coefficient int
power int
next *Node
}
type list struct {
head *Node
count int
}
func main() {
list1 := &list{}
list1.addVariable(5, 2)
list1.addVariable(4, 1)
list1.addVariable(3, 0)
list1.print()
list2 := &list{}
list2.addVariable(4, 1)
list2.addVariable(2, 0)
list2.print()
poly := addPoly(list1, list2)
poly.print()
}
func (lst *list) print() {
temp := lst.head
for temp != nil {
fmt.Print(temp.coefficient, "x", "^", temp.power, "+")
temp = temp.next
}
fmt.Println("\n")
}
func (lst *list) addVariable(coefficient int, power int) {
lst.head = &Node{coefficient, power, lst.head}
lst.count++
}
func addPoly(list_1 *list, list_2 *list) *list {
list_3 := &list{}
temp_1 := list_1.head
temp_2 := list_2.head
if list_1.count > list_2.count {
for temp_1 != nil && temp_2 != nil {
if temp_1.power == temp_2.power {
new_coefficient := temp_1.coefficient + temp_2.coefficient
new_power := temp_1.power
list_3.addVariable(new_coefficient, new_power)
temp_1 = temp_1.next
temp_2 = temp_2.next
} else if temp_1.power != temp_2.power {
list_3.addVariable(temp_1.coefficient, temp_1.power)
list_3.addVariable(temp_2.coefficient, temp_2.power)
temp_1 = temp_1.next
temp_2 = temp_2.next
}
}
}
for temp_1 != nil {
list_3.addVariable(temp_1.coefficient, temp_1.power)
temp_1 = temp_1.next
}
return list_3
}
The error occur because you tried to access .power
property from nil
object in code below. Both temp1
and temp2
are nil
.
if temp1.power != temp2.power {
// ...
}
The .head
property on list
struct has pointer data type. The zero value of pointer data type is nil
. In your code, both list1
and list2
has nil
value on its .head
property.
What you need to do: initialise the value of .head
property explicitly during creation of both list1
and list2
. Then the panic error will disappear and your code will work properly.
list1 := &list{head: new(Node)}
// ...
list2 := &list{head: new(Node)}
// ...
Playground: https://play.golang.org/p/vPK3pYKht3E
You have a lot of mistakes in your code like the first answer posted. Also, why is there a need to keep track of the number of terms? I would suggest you take a simpler approach.
type Node struct {
Coeff int
Power int
next *Node
}
// Add coeff^power to a polynomial
func (n *Node) AddTerm(coeff int, power int) {
for t := n; t != nil; t = t.next {
if t.Power == power {
t.Coeff += coeff
return
}
}
n.next = &Node{coeff, power, n.next}
}
// Add a polynomial m to the polynomial
func (n *Node) AddPolynomial(m *Node) {
for t := m; t != nil; t = t.next {
n.AddTerm(t.Coeff, t.Power)
}
}
// The string representation of the polynomial
func (n *Node) String() string {
buff := strings.Builder{}
for t := n; t != nil; t = t.next {
fmt.Fprintf(&buff, " + %d^%d", t.Coeff, t.Power)
}
return buff.String()[3:]
}
// Add two polynomials together creating a new one
func Add(a *Node, b *Node) *Node {
c := &Node{}
c.AddPolynomial(a)
c.AddPolynomial(b)
return c
}
func main() {
p1 := &Node{}
p1.AddTerm(5, 2)
p1.AddTerm(4, 1)
p1.AddTerm(3, 0)
fmt.Println(p1)
p2 := &Node{}
p2.AddTerm(4, 1)
p2.AddTerm(2, 0)
fmt.Println(p2)
p3 := Add(p1, p2)
fmt.Println(p3)
}
Just check your libraries. There are some redundant ones.
User contributions licensed under CC BY-SA 3.0