数据结构与算法关于单链表

Question

数据结构与算法中要求利用单链表基本操作实现两个大数相加的计算。

Answer 1

【以下回答由 GPT 生成】

#include<iostream>
#include<list>
using namespace std;

// 定义单链表节点结构
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 实现单链表的基本操作
class LinkedList{
public:
    // 头插法插入节点
    static void insert_node(ListNode* &head, int val){
        ListNode* node = new ListNode(val);
        node->next = head;
        head = node;
    }
    // 尾插法插入节点
    static void append_node(ListNode* &head, int val){
        ListNode* node = new ListNode(val);
        if(head == NULL){
            head = node;
        }
        else{
            ListNode* cur = head;
            while(cur->next != NULL){
                cur = cur->next;
            }
            cur->next = node;
        }
    }
    // 打印单链表
    static void print_list(ListNode* head){
        ListNode* cur = head;
        while(cur != NULL){
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};

// 实现两个大数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点
    ListNode* cur = dummy;
    int carry = 0; // 进位标志

    while(l1 || l2){
        int sum = carry;
        if(l1){
            sum += l1->val;
            l1 = l1->next;
        }
        if(l2){
            sum += l2->val;
            l2 = l2->next;
        }
        carry = sum / 10; // 计算进位
        cur->next = new ListNode(sum % 10); // 计算当前节点的值
        cur = cur->next;
    }
    if(carry){
        cur->next = new ListNode(carry); // 若最高位有进位，需新增节点
    }

    return dummy->next;
}

int main(){
    // 从键盘接收两个数，生成两个单链表
    int num1, num2;
    cout << "请输入第一个大数: ";
    cin >> num1;
    cout << "请输入第二个大数: ";
    cin >> num2;

    ListNode* list1 = NULL;
    ListNode* list2 = NULL;

    // 从高位到低位插入节点
    while(num1 > 0){
        int digit = num1 % 10;
        LinkedList::insert_node(list1, digit);
        num1 /= 10;
    }
    while(num2 > 0){
        int digit = num2 % 10;
        LinkedList::insert_node(list2, digit);
        num2 /= 10;
    }

    // 输出原始的单链表
    cout << "第一个大数: ";
    LinkedList::print_list(list1);
    cout << "第二个大数: ";
    LinkedList::print_list(list2);

    // 求两个大数的和
    ListNode* result = addTwoNumbers(list1, list2);

    // 输出结果
    cout << "两个大数的和: ";
    LinkedList::print_list(result);

    return 0;
}

【相关推荐】

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7676570
• 这篇博客你也可以参考下：【数据结构与算法】八大排序（中）快速排序 快排居然还能这么优化？快排的非递归该如何写？
• 您还可以看一下 刘建萍老师的人工智能系列课程零基础讲解知识点和实例应用线性回归梯度下降逻辑回归课程中的 讲解机器学中会涉及到的有关数学方面的知识储备有哪些小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【数据结构与算法】顺序表的基本操作实现中的 顺序表的按位查找 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^