java双循环链表长整数运算
时间: 2023-11-18 09:54:38 浏览: 43
Java双循环链表长整数运算是一种利用双向循环链表来实现对长整数的存储和运算的方法。每个节点只存储四位十进制数字,即不超过9999的非负整数。双向链表有头指针,它的data值存储长整数的符号,1为正,-1为负,0代表长整数为0;它的over值存储除头节点外节点的个数。在实现长整数的加减法时,需要将两个长整数分别存储在两个双向循环链表中,然后按照加减法的规则进行运算,最后将结果存储在一个新的双向循环链表中。具体实现过程中,需要注意进位和借位的处理,以及对于结果中前导0的处理。
下面是一个简单的Java双循环链表长整数加法的实现代码:
```
public class LongIntAddition {
public static void main(String[] args) {
String s1 = "123456789";
String s2 = "987654321";
Node head1 = createList(s1);
Node head2 = createList(s2);
Node result = add(head1, head2);
printList(result);
}
public static Node createList(String s) {
Node head = new Node(0, 0);
Node tail = head;
int len = s.length();
int sign = 1;
if (s.charAt(0) == '-') {
sign = -1;
len--;
}
int count = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
if (c == '-') {
break;
}
int digit = c - '0';
tail.next = new Node(digit * sign, count++);
tail.next.prev = tail;
tail = tail.next;
}
head.over = count;
return head;
}
public static Node add(Node head1, Node head2) {
Node p = head1.next;
Node q = head2.next;
Node result = new Node(0, 0);
Node tail = result;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.data : 0;
int y = (q != null) ? q.data : 0;
int sum = x + y + carry;
carry = sum / 10000;
sum = sum % 10000;
tail.next = new Node(sum, tail.over++);
tail.next.prev = tail;
tail = tail.next;
if (p != null) {
p = p.next;
}
if (q != null) {
q = q.next;
}
}
if (carry > 0) {
tail.next = new Node(carry, tail.over++);
tail.next.prev = tail;
}
result.over = tail.over;
return result;
}
public static void printList(Node head) {
if (head.next == null) {
System.out.println("0");
return;
}
if (head.next.data < 0) {
System.out.print("-");
}
Node p = head.next;
while (p != null) {
int digit = Math.abs(p.data);
if (p.over == 0) {
System.out.print(digit);
} else {
System.out.printf("%04d", digit);
}
if (p.next != null) {
System.out.print(",");
}
p = p.next;
}
System.out.println();
}
}
class Node {
int data;
int over;
Node prev;
Node next;
public Node(int data, int over) {
this.data = data;
this.over = over;
}
}
```