单链表-使用单链表实现两个非负大整数求和

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

一、题目说明

1. 将用户输入的十进制整数字符串转换为带头结点的单链表，每个节点存储一个数字位。

2. 实现两个整数链表相加，并生成结果链表。

二、解题思路概述

本题通过带头结点的单链表结构实现对超长非负整数的存储与加法运算。将大整数按位拆分，采用前插法将其存入链表中，使得低位在前、高位在后，便于后续从个位开始进行逐位相加操作。加法过程模拟手工竖式计算方式：从链表头部开始遍历，对应位相加并处理进位，使用尾插法构建结果链表以保持“低位在前”的结构。最终借助递归回溯机制倒序输出链表内容，还原为常规的高位在前显示格式。该方法有效解决了超出基本数据类型范围的大整数运算问题。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*  超长非负整数的存储结构  */
typedef struct Node{
	int data;
	struct Node *next;
}BINode, *BILinkList;

/*  创建超长非负整数   */
BILinkList CreateBigInteger(){
	BINode *p;
	
	char *num = (char *)malloc(sizeof(char)*100);
	printf("\n请输入大整数：");
	//从键盘输入大整数字符串num
	scanf("%s", num);
	//获取大整数字符串的长度len
	int len = strlen(num);
	
	//创建大整数带头结点单链表
	//1.初始化链表
	BILinkList L = (BILinkList)malloc(sizeof(BINode));
	L->next = NULL;
	
	for(int i=0;i<len;i++){
		p=(BINode *)malloc(sizeof(BINode));
		p->data = num[i]-'0';
		//前插法，将当前结点插入头结点之后
		/******** begin *******/
		p->next=L->next;
		L->next=p;
		/******** end *******/      
	}	
	
	return L;
}

/*  显示超长非负整数, 采用递归算法倒序显示链表结点的值  */
void DispBigInteger(BILinkList L){
	/******** begin *******/
	if(L->next != NULL){
		// 阶段1：递归深入（先执行）—— 一直调用到最后一层，此阶段不打印
		DispBigInteger(L->next);  
		// 阶段2：回溯打印（后执行）—— 只有深入到底后，才从下往上执行这行
		printf("%d", L->next->data);  
	}
	/******** end *******/
}

/*  超长非负整数求和  */
BILinkList AddBigInteger(BILinkList bia, BILinkList bib){
	int s=0; //进位值
	
	//初始化结果链表
	BILinkList ls = (BILinkList)malloc(sizeof(BINode));
	ls->next = NULL;
	
	BINode *pa=bia->next, *pb=bib->next, *pc=ls, *q;  //pc为结果单链表ls的尾结点指针,初始化时指向头结点，q为临时结点
	
	/**两个整数对应位求和。由于整数存放时，低位在单链表的前面，高位在后面，所以只需逐结点求和，并将和作为结点采用尾插法插入结果链表。*/
	while(pa && pb){
		/******** begin *******/
		q=(BINode *)malloc(sizeof(BINode));
		q->data=pa->data+pb->data+s;
		if(q->data>9){
			s=q->data/10;
			q->data=q->data%10;
		}else{
			s=0;
		}
		q->next=pc->next;
		pc->next=q;
		pa=pa->next;
		pb=pb->next;
		pc=pc->next;
		/******** end *******/
	}
	
	//两个整数不一样长时，将更长的整数的其余部分与进位相加后放入结果整数中
	BINode *p = pa ? pa :pb;
	while(p){  
		/******** begin *******/
		q=(BINode *)malloc(sizeof(BINode));
		q->data=p->data+s;
		if(q->data>9){
			s=q->data/10;
			q->data=q->data%10;
		}else{
			s=0;
		}
		q->next=pc->next;
		pc->next=q;
		p=p->next;
		pc=pc->next;
		/******** end *******/
	}
	
	//仍有进位时，创建最高位的结点并放入结果链表
	if(s){  
		/******** begin *******/
		q=(BINode *)malloc(sizeof(BINode));
		q->data=s;
		q->next=pc->next;
		pc->next=q;
		pc=pc->next;
		/******** end *******/
	}
	pc->next = NULL;  //尾插法，尾元结点的next置为NULL
	return ls;
}

/** 释放单链表 */
void destroyBigInteger(BILinkList *bi){
	/******** begin *******/
	BINode *p,*p1;
	p=*bi;
	while(p!=NULL){
		p1=p;
		p=p->next;
		free(p1);
	}
	*bi=NULL;
	/******** end *******/
}
/*  测试程序的主函数，不要修改  */
int main(int argc, char** argv) {
	BILinkList bia = CreateBigInteger();
	DispBigInteger(bia);
	printf("\n");
	BILinkList bib = CreateBigInteger();
	DispBigInteger(bib);
	printf("\n");
	BILinkList bic = AddBigInteger(bia,bib); 
	DispBigInteger(bic);
	
	destroyBigInteger(&bia);
	destroyBigInteger(&bib);
	destroyBigInteger(&bic);	
	return 0;
}

三、测试用例展示

（一）测试案例一

键盘输入：
123
456

输出结果：579

（二）测试案例二

键盘输入：
9999
1

输出结果：10000

四、核心知识点分析

（一）数据结构设计 —— 带头结点的单链表

1. 链表节点定义

通过自定义结构体实现链表节点，其中包含一个整型数据域和指向下一节点的指针域。

typedef struct Node{
    int data;          // 存储单个数字位（0-9）
    struct Node *next; // 指向下一结点的指针
}BINode, *BILinkList;

定义指向节点的指针类型作为链表头指针；

引入头结点：其本身不存储有效数值，仅用于统一空链表与非空链表的操作逻辑，避免频繁判空。

BILinkList

2. 关键操作及其实现方式

操作	实现方式	关键知识点
创建链表（Create）	前插法	从字符串末尾逐位提取数字，利用头插法插入链表，形成低位在前的存储顺序，适配竖式加法流程
显示链表（Disp）	递归算法	利用递归深入至链尾后再逐层回溯输出，实现倒序打印，弥补“低位在前”带来的显示异常
链表求和（Add）	尾插法	逐位相加结合进位处理，使用尾插法构造结果链表，确保结果仍满足“低位在前”结构
释放链表（destroy）	遍历释放	迭代遍历所有节点，逐一释放内存空间，防止内存泄漏，最后将头指针置为空

（二）算法设计核心

1. 超长整数的存储与计算逻辑

• 存储适配性：由于普通整型或长整型无法容纳极长数字，因此采用链表按“位”存储，每位占据一个节点。
• 低位在前结构：链表从头到尾对应数字从低位到高位。例如，数字

123

被存储为

3→2→1

这种结构天然契合竖式加法“从个位起算”的规则。

2. 加法规则详解

• 每一位执行：两操作数对应位 + 进位值；若和 ≥10，则保留个位，进位1；
• 处理长度不同情况：当较短链表遍历完毕后，剩余部分继续与进位值相加；
• 最高位处理：若全部位处理完成后仍有进位，则新增一个节点保存该进位。

3. 递归显示机制

链表以“低位在前”方式存储，直接正向输出会呈现逆序。为此采用递归方式进行输出：

void DispBigInteger(BILinkList L){
    if(L->next != NULL){
        DispBigInteger(L->next);  // 递归深入：先走到链表尾部（数字高位）
        printf("%d", L->next->data); // 回溯打印：从高位到低位输出
    }
}

• 终止条件：

L->next == NULL

（即当前节点为空，到达链尾）；
• 递归策略：“先深入到底，再回溯输出”，从而实现逆序访问链表元素。

4. 链表插入方式对比

插入方式	核心代码	适用场景
头插法	p->next = L->next; L->next = p;	用于创建链表时快速逆序存储输入数字（如将 "123" 存为 3→2→1）
尾插法	pc->next = q; pc = q;	适用于求和结果构建，保证新节点始终接在末尾，维持正确顺序

（三）C语言语法要点

1. 动态内存管理

链表节点和缓冲区均需动态分配内存：

malloc

—— 分配空间；

free

—— 使用完毕后及时释放，防止内存泄漏。

注意：释放链表时必须逐个释放所有节点，不能只释放头结点。

2. 字符串处理技巧

• 获取字符串长度：

strlen

（确定数字位数）；
• 字符转数字：

num[i] - '0'

（利用 '0'~'9' 的ASCII码差值转换为 0~9 的整数）；
• 读取字符串函数：

scanf("%s", num)

（可读取任意长度字符串，实际应用中建议优化为

fgets

以提升安全性。

3. 指针操作细节

• 链表遍历依赖头指针与工作指针的移动：

pa = pa->next

• 函数参数传递：

destroyBigInteger(&bi)

（传指针的地址，允许函数修改原始指针值）；
• 三目运算符简化判断：

BINode *p = pa ? pa : pb;

（常用于处理两链表长度不一致的情况）。

4. 函数设计原则

• 返回值设计：多数功能函数返回链表头指针，如

CreateBigInteger

和

AddBigInteger

• 参数传递方式：根据需求选择传头指针

DispBigInteger

或传指针的指针

destroyBigInteger

• 主函数职责清晰：

main

仅负责调用各模块函数完成测试任务，体现“高内聚、低耦合”的模块化编程思想。

（四）程序设计思想提炼

• 问题适配：针对基本类型无法表示超长整数的问题，采用链表实现按位存储；
• 算法贴合：加法流程完全模拟人工竖式计算，存储顺序与运算顺序高度匹配；
• 内存安全：所有动态内存均在程序结束前通过

destroyBigInteger

显式释放，杜绝内存泄漏；
• 代码复用性强：将链表的创建、显示、相加、销毁封装为独立函数，主函数仅做集成测试，符合良好软件工程规范。

（五）常见错误与重点注意事项

• 头结点作用不可忽视：它统一了空链表与非空链表的处理逻辑，使插入、删除等操作更加简洁；
• 进位处理需全面覆盖：包括三个阶段：对应位相加、较长链表剩余位处理、最终进位判断，都必须跟踪进位变量

s

• 递归终止条件必须明确：在递归输出函数中，若遗漏

L->next != NULL

判断，会导致无限递归甚至栈溢出；
• 尾插法中的尾指针维护：在构建结果链表时，尾指针

pc

必须始终指向最后一个节点，否则会造成链表断裂或连接错误。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Integer include Create struct RETURN