c语言编程:用单链表实现两个无限大的两个数的加法和乘法,并将两个数从低位到高位(如:100输出00
// 本程序主要由三个文件构成:
// BigInteger.h 包涵了对节点的结构定义,以及类BigInteger的定义.
// BigInteger.cpp 包涵了BigInteger类里面成员函数的具体内容.
// main.cpp 主函数…
/*********************************************************/
//BigInteger.h
struct Node //定义了节点的结构
{
char Num;
Node *Prev,*Next;
};
class BigInteger //定义BigInteger 类
{
Node *Head,*End,*TempNode;
void AddHead(char Num);
void AddEnd(char Num);
public:
BigInteger();
BigInteger(const BigInteger BigNum);
void GetNumber();
void disp();
BigInteger operator + (const BigInteger BigNum);
BigInteger operator * (const BigInteger BigNum);
BigInteger operator = (const BigInteger BigNum);
~BigInteger();
};
//BigInteger.cpp
#include iostream.h
#include stdio.h
#include “BigInteger.h”
BigInteger::BigInteger() //构造函数,将每个节点置空.
{
Head=End=TempNode=NULL;
}
BigInteger::BigInteger(const BigInteger BigNum) //拷贝构造
{
Node *p;
Head=End=TempNode=NULL;
p=BigNum.Head;
while(p)
{
AddEnd(p-Num);
p=p-Next;
}
}
BigInteger::~BigInteger() //析构
{
Node *NextNode;
if(Head==NULL)
return;
TempNode=Head;
while(TempNode)
{
NextNode=TempNode-Next;
delete TempNode;
TempNode=NextNode;
}
Head=NULL;
End=NULL;
TempNode=NULL;
}
void BigInteger::AddHead(char Num) //在链表头插入节点的操作
{
TempNode=new Node;
TempNode-Num=Num;
TempNode-Prev=NULL;
if(!Head)
{
Head=End=TempNode;
TempNode-Next=NULL;
}
else
{
TempNode-Next=Head;
Head-Prev=TempNode;
Head=TempNode;
}
}
void BigInteger::AddEnd(char Num) //在链表尾插入节点的操作
{
TempNode=new Node;
TempNode-Num=Num;
TempNode-Next=NULL;
if(!Head)
{
Head=End=TempNode;
TempNode-Prev=NULL;
}
else
{
TempNode-Prev=End;
End-Next=TempNode;
End=TempNode;
}
}
void BigInteger::GetNumber() //输入部分
{
char key;
int count=0,num=0;
while((key=getchar())!=10) //判断输入的是否是回车,不是的话将内容从后到前放到链表中.
{
if(key=’0′ key=’9′)
{
num=key-‘0’;
AddEnd(num);
num=0;
}
}
}
BigInteger BigInteger::operator + (const BigInteger BigNum2) //重载”+”
{
BigInteger BigNum1=*this,result;
Node *temp1,*temp2;
int TempNum,rest=0;
temp1=BigNum1.End; //将临时链表首地址放置到输入链表的尾部
temp2=BigNum2.End;
while(temp1 temp2)
{
TempNum=int(temp1-Num)+int(temp2-Num)+rest; //节点内元素相加并加上进位rest
if(TempNum9) //判断相加结果是否会产生进位.
{
TempNum=TempNum-10;
rest=1;
}
else
rest=0;
result.AddHead(char(TempNum)); //将结果放置到最终结果链表里
temp1=temp1-Prev;
temp2=temp2-Prev;
}
if(temp2)temp1=temp2;
while(temp1)
{
int(TempNum)=int(temp1-Num)+rest; //节点内元素加上进位rest
if(TempNum9)
{
TempNum=TempNum-10;
rest=1;
}
else
rest=0;
result.AddHead(char(TempNum)); //将结果放置到最终结果链表里
temp1=temp1-Prev;
}
if(rest)
result.AddHead(char(rest)); //考虑最后的进位是否存在,如果存在则存入链表的首部.
return result;
}
BigInteger BigInteger::operator * (const BigInteger BigNum2) //对*进行重载
{
BigInteger BigNum1=*this,temp,result;
Node *temp1,*temp2,*tempa,*tempb;
int TempNum,rest,i=0,rest2;
temp1=BigNum1.End;
temp2=BigNum2.End;
while(temp2) //由乘数的存在与否判断是否去乘被乘数的每个位
{
rest=0;
while(temp1!=NULL)
{
TempNum=int(temp1-Num)*int(temp2-Num)+rest;
if(TempNum9)
{
rest=TempNum/10; //进位由相乘结果与10做商求得
TempNum=TempNum%10; //由相乘结果与10求模取个位
}
else
rest=0;
temp.AddHead(char(TempNum)); //存入临时链表
temp1=temp1-Prev;
}
if(rest!=0)temp.AddHead(char(rest));
for(int k=i;k=1;k–)temp.AddEnd(char(0)); //判断应该在链表后面补几个0
i++; //每次乘完后计数,用来下一次的补0
temp1=BigNum1.End; //把被乘数重新置到尾,用来让乘数下一次去乘每个元素
temp2=temp2-Prev; //将乘数取出链表的前驱
tempa=result.End; //下面进行的是将每次乘数与被乘数的相乘结果累加放到最终链表里等待输出
if(result.Head!=NULL) //下面过程与”+”重载基本一样,只是多了对临时链表的置空,所以不在做详细的注释.
{
result.End=temp.Head;
result.Head=NULL;
}
tempb=temp.End;
rest2=0;
while(tempa!=NULL tempb!=NULL)
{
TempNum=int(tempa-Num)+int(tempb-Num)+rest2;
if(TempNum9)
{
TempNum=TempNum-10;
rest2=1;
}
else
rest2=0;
result.AddHead(char(TempNum));
tempa=tempa-Prev;
tempb=tempb-Prev;
}
if(tempb)tempa=tempb;
while(tempa)
{
int(TempNum)=int(tempa-Num)+rest2;
if(TempNum9)
{
TempNum=TempNum-10;
rest2=1;
}
else
rest2=0;
result.AddHead(char(TempNum));
tempa=tempa-Prev;
}
if(rest2)
result.AddHead(char(rest2));
if(temp.Head!=NULL)
{
temp.End=temp.Head;
temp.Head=NULL;
}
tempb=NULL;
}
return result;
}
BigInteger BigInteger::operator = (const BigInteger BigNum) //对=号进行重载
{
if(this==BigNum)
return *this;
Node *p;
TempNode=Head=End=NULL;
p=BigNum.Head;
while(p)
{
AddEnd(p-Num);
p=p-Next;
}
return *this;
}
void BigInteger::disp() //输出链表
{
if(Head)
{
coutint(Head-Num);
TempNode=Head-Next;
}
else return;
while(TempNode)
{
coutint(TempNode-Num);
TempNode=TempNode-Next;
}
coutendl;
}
//main.cpp
#include iostream.h
#include “BigInteger.h”
void main()
{
BigInteger BigNum1,BigNum2,BigNum3;
int c;
cout”选择你要进行的操作:”endl;
cout”1.大整数加法运算”endl;
cout”2.大整数乘法运算”endl;
cout”选择你需要进行的运算:”endl;
cinc;
switch(c)
{
case 1:
{
cout”A:”endl;
BigNum1.GetNumber();
cout”B:”endl;
BigNum2.GetNumber();
BigNum3=BigNum1+BigNum2;
cout”相加的结果是:”endl;
BigNum3.disp();
}break;
case 2:
{
cout”A:”endl;
BigNum1.GetNumber();
cout”B:”endl;
BigNum2.GetNumber();
BigNum3=BigNum1*BigNum2;
cout”相乘的结果是:”endl;
BigNum3.disp();
}break;
default:break;
}
}
用c语言编写基于链表的长整数的加减乘除法运算的程序
#include “iostream.h”
void main()
{
int x,y;
cout”请输入两个整数,整数之间用空格隔开:”endl;
cinxy;
int he=x+y;
int ji=x*y;
int jian=x-y;
double chu=x/y;
couthejijianchu;
}
C语言数据结构题目 用链表 问题描述:设计一个实现任意长的整数进行加法运算的演示程序。基本要求:利
试描述头指针、头结点、开始结点的区别,并说明头指针和头结点的作用。头指针:存放链表首地址的指针变量。头结点:链表的开始结点之前的一个同类型结点。开始结点:链表的第一个元素所在的结点。头指针的作用:用于确定链表的地址。头结点的作用:方便于处理开始结点的操作和处理其它结点的操作保持一致,也方便于处理空表的操作和处理非空表的操作保持一致。2.2有哪些链表可由一个尾指针来唯一确定?即从尾指针出发能访问链表上任何一个结点。单循环链表,双链表,双循环链表★2.3设线性表存放在向量A[arrsize]的前elenum个分量中,且递增有序。试写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性。并且分析算法的时间复杂度。#definearrsize100intInsertOrder(intA[],intelenum,intx){inti=elenum-1;if(elenum==arrsize)//在顺序表上进行插入操作必须先判满{printf(“full”);return0;}while(i=0A[i]x){A[i+1]=A[i];i–;}//从后往前进行比较,比较的同时完成移动A[i+1]=x;elenum++;returnelenum;//返回变化之后的表长}//本题也可以先进行比较,比较的结果就是找到了插入的合适位置,然后再完成插入操作。但这样做比较耗时。假设n=elenum,则时间复杂度:最坏O(n),最好O(1),平均O(n)★2.4用向量作存储结构,试设计一个算法,仅用一个辅助结点,实现将线性表中的结点循环右移k位的运算,并且分析算法的时间复杂度。voidMoveKList(inta[],intn,intk){inti,j,temp;for(i=1;i=0;j–)a[j+1]=a[j];//内层for循环完成一次整体右移一位a[0]=temp;//把原来的表尾元素移至表头}}时间复杂度T(n)=k*n=O(n)★2.5已知带头结点的动态单链表L中的结点是按整数值递增排列的,试写一算法将值为x的结点插入表L中,使L仍然有序。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;//linklist结构体类型描述voidInsertListOrder(linklist*L,datetypex){linklist*p=L;//对寻位指针p初始化linklist*s=(linklist*)malloc(sizeof(linklist));//使用强制类型转换将新结点的地址赋给指针ss-data=x;while((p-next)(p-next-datanext;//后移寻位指针s-next=p-next;p-next=s;}//本题也可以采用两个寻位指针p和q,让q始终跟随p的后移而后移。★2.6设计一算法,逆置带头结点的动态单链表L。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;voidReverse(linklist*L){linklist*p,*q;p=L-next;q=L-next;L-next=NULL;while(q){q=q-next;p-next=L-next;L-next=p;p=q;}}//用指针q遍历结点,指针p跟随指针q,使用头插法把当前结点*p插入到修改之后的单链表中。2.7试编写在带头结点的动态单链表和静态单链表上实现线性表操作Length(L)的算法,并将长度写入头结点的数据域中。★(1)typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;voidLength1(linklist*L){linklist*p=L-next;inti=0;while(p){i++;p=p-next;}L-data=i;//按照题目要求,将表长写入头结点的数据域中。}(2)#definemaxsize1024typedefintdatatype;typedefstruct{datatypedata;intnext;}node;nodenodepool[maxsize];voidLength2(intL){inti=0,p=nodepool[L].next;while(p){i++;p=nodepool[p].next;}nodepool[L].data=i;}2.8假设有两个按元素值递增有序排列的线性表A和B,均以单链表①作存储结构,试编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许值相同)排列的线性表C,并要求利用原表(即A表和B表)的结点空间存放表C。①今后若不特别指明,链表均是指动态链表,且可以带头结点。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;linklist*Connect(linklist*A,linklist*B){linklist*C,*p,*q,*r;C=A;//C为最后返回的链表头指针p=A-next;//p总是指向链表A中当前正在比较的结点q=B-next;//q总是指向链表B中当前正在比较的结点C-next=NULL;//置空链表Cwhile(pq)//当链表A和链表B中还有没比较的结点时{if(p-datadata){r=p;p=p-next;}else{r=q;q=q-next;}//r总是指向*p和*q二者中数据较小的结点r-next=C-next;C-next=r;//将*r按照头插法插入到链表C中}if(!p)//如果链表A中所有结点都链接到链表C中后,链表B中还有结点,while(q)//将链表B中剩余的未比较过的结点全部按照头插法插入到链表C中{r=q;q=q-next;r-next=C-next;C-next=r;}else//如果链表B中所有结点都链接到链表C中后,链表A中还有结点,while(p)//将链表A中剩余的未比较过的结点全部按照头插法插入到链表C中{r=p;p=p-next;r-next=C-next;C-next=r;}free(B);//释放链表B的头结点returnC;}2.9假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前趋结点。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;voidDeleteBefore(linklist*s){linklist*p=s;while(p-next-next!=s)p=p-next;free(p-next);p-next=s;}2.10已知,由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符、数字字符和其它字符),试编写算法构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;//L为等待分解的单链表,最后得到的包含字母字符的链表的首地址作为该函数的返回值被返回,得到的包含数字字符的链表的首地址被参数*LB带回,得到的包含其它字符的链表的首地址被参数*LC带回。linklist*Decompose(linklist*L,linklist**LB,linklist**LC){linklist*A,*B,*C,*pa,*pb,*pc,*p;//A,B,C分别用于保存分解之后得到的三个循环链表的首地址//pa,pb,pc分别指向三个循环链表当前的尾结点//p总是指向原单链表L中当前正在判断类型,正在等待处理的结点A=L;B=(linklist*)malloc(sizeof(linklist));C=(linklist*)malloc(sizeof(linklist));pa=A;pb=B;pc=C;p=A-next;while(p)//只要p不为空,就意味着原单链表L中仍然有未处理的结点{if(((’a’data)(p-datadata)(p-datanext=p;pa=p;p=p-next;}//将*p链接到链表A的终端,然后p后移elseif((’0’data)(p-datanext=p;pb=p;p=p-next;}//将*p链接到链表B的终端,然后p后移else{pc-next=p;pc=p;p=p-next;}//将*p链接到链表C的终端,然后p后移}pa-next=A;pb-next=B;pc-next=C;//让链表A、B、C都循环起来*LB=B;//通过指针类型的变量LB带回循环链表B的首地址*LC=C;//通过指针类型的变量LC带回循环链表C的首地址returnA;//通过函数返回值带回循环链表A的首地址}2.11设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个访问频度域freq,在链表被起用之前,其值均初始化为零。每当在链表进行一次Locate(L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度递减的顺序排列,以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的Locate运算的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*prior,*next;intfreq;}dlinklist;//创建符合题意的结点类型dlinklist*Locate(dlinklist*L,datatypex){dlinklist*p=L-next;//指针p用于查找第一个data域等于x的结点dlinklist*q;while(p(p-data!=x))p=p-next;if(!p)returnNULL;//p为空,意味着没有找到data域等于x的结点else{p-freq++;//将找到的data域等于x的结点的访问频度值加1q=p-prior;//指针q用于查找在*p的前面结点中第一个freq域不小于当前p所指结点的freq域的结点while((q!=L)(q-freq)freq))q=q-prior;if(q!=p-prior)//如果q发生了前移,才有必要移动*p{p-prior-next=p-next;if(p-next)p-next-prior=p-prior;//如果*p不是终端结点,才有必要修改*p的后继结点的prior域p-prior=q;p-next=q-next;q-next=p;p-next-prior=p;//将*p插入到*q的后边}returnp;}}
C语言用链表实现一元多项式的相加
C语言代码:
#include “stdio.h”
#include “malloc.h”
/* 链表结点结构 */
typedef struct LNode{
double coef; /* 系数 */
int exp; /* 指数 */
struct LNode *next;
}LNode;
/* 初始化链表 */
LNode *Init()
{
LNode *head = (LNode*)malloc(sizeof(LNode));
head-next = NULL;
return head;
}
/* 将值为data的结点插入到head链表的最后 */
void AddNode(LNode *head, double coef, int exp)
{
LNode *pre = head-next;
LNode *temp;
temp = (LNode*)malloc(sizeof(LNode));
temp-coef = coef;
temp-exp = exp;
temp-next = NULL;
if(pre == NULL)
{
head-next = temp;
return;
}
for(; pre-next!=NULL; pre=pre-next);
pre-next = temp;
}
/* 输出head链表的所有结点的值 */
void List(LNode *head)
{
LNode *curr;
printf(“All nodes : “);
for(curr=head-next; curr!=NULL; curr=curr-next)
{
printf(“(%lf, %d)\t”, curr-coef, curr-exp);
}
printf(“\n”);
}
/* 返回head链表的所有结点的数量 */
int Size(LNode *head)
{
int len = 0;
LNode *curr;
for(curr=head-next; curr!=NULL; curr=curr-next,len++);
return len;
}
LNode *Add(LNode *headA, LNode *headB)
{
LNode *currA, *currB, *headC;
double sum;
currA = headA-next;
currB = headB-next;
headC = Init();
while(currA!=NULL currB!=NULL)
{
if(currA-exp currB-exp)
{
AddNode(headC, currA-coef, currA-exp);
currA = currA-next;
}
else if(currA-exp currB-exp)
{
AddNode(headC, currB-coef, currB-exp);
currB = currB-next;
}
else
{
sum = currA-coef + currB-coef;
if(sum != 0)
{
AddNode(headC, sum, currA-exp);
}
currA = currA-next;
currB = currB-next;
}
}
while(currA != NULL)
{
AddNode(headC, currA-coef, currA-exp);
currA = currA-next;
}
while(currB != NULL)
{
AddNode(headC, currB-coef, currB-exp);
currB = currB-next;
}
return headC;
}
void main()
{
LNode *headA, *headB, *headC;
headA = Init();
headB = Init();
AddNode(headA, 1.0, 5);
AddNode(headA, -1.0, 3);
AddNode(headA, 1, 0);
AddNode(headB, 0.5, 5);
AddNode(headB, 1.0, 4);
AddNode(headB, 1.0, 3);
List(headA);
List(headB);
headC = Add(headA, headB);
List(headC);
}
运行测试:
c语言,如何实现将两个链表相加
#includestdlib.h
#includestdio.h
#includemalloc.h
typedef struct datas
{
int num;
struct datas *next;
}DATAS;
DATAS *newData(int len);//创建1条数据链表 参数:节点数量 返回首节点
DATAS *addData(DATAS *datasHead1,DATAS *datasHead2);//你要的两链表相加,结构返回在新的链表中(链表节点数据对应相加,节点数量不一致,按少的算)
int main()
{
//创建3个链表头节点指针
DATAS *datasHead1;DATAS *datasHead2;DATAS *datasHead3;
datasHead1=newData(3);//测试每个链表3个节点数据,需要自己加
datasHead2=newData(3);//测试每个链表3个节点数据,需要自己加
datasHead3=addData(datasHead1,datasHead2);//测试每个链表3个节点数据,需要自己加
printf(“两链表相加后,新的链表数据为:”);
while(datasHead3-next!=NULL)
{
printf(“%d “,datasHead3-next-num);
datasHead3=datasHead3-next;
}
return 0;
}
DATAS * newData(int len)//创建1条数据链表 参数:节点数量 返回首节点
{
int i;
DATAS *datasHead=(DATAS *)malloc(sizeof(DATAS));
DATAS *datasTail=NULL;
datasHead-next=NULL;
printf(“输入%d个数 生成链表:”,len);
for(i=0;ilen;i++)
{
DATAS *datasNew=(DATAS *)malloc(sizeof(DATAS));
scanf(“%d”,(datasNew-num));
datasNew-next=NULL;
if(datasHead-next==NULL)
datasHead-next=datasNew;
else
datasTail-next=datasNew;
datasTail=datasNew;
}
return datasHead;
}
DATAS *addData(DATAS *datasHead1,DATAS *datasHead2)
{
DATAS *datasHead=(DATAS *)malloc(sizeof(DATAS));
DATAS *datasTail=NULL;
datasHead-next=NULL;
while(datasHead1-next!=NULL datasHead2-next!=NULL)
{
DATAS *datasNew=(DATAS *)malloc(sizeof(DATAS));
datasNew-next=NULL;
datasNew-num=datasHead1-next-num+datasHead2-next-num;
if(datasHead-next==NULL)
datasHead-next=datasNew;
else
datasTail-next=datasNew;
datasTail=datasNew;
datasHead1=datasHead1-next;
datasHead2=datasHead2-next;
}
return datasHead;
}
c语言大数加法,乘法,阶乘!
#include stdio.h
void fac(int n)
{
double i,j=1;
for(i=1;i=n;i++)
j*=i;
printf(“%d!=%d\n”,n,j);
}
void add(double n,double m)
{
}
void mult(double n,double m)
{
}
void main()
{
char a[200];
double i,j,k=0,t=1;
int p;
for(i=0;i200;i++)
a[i]=’*’
scanf(“%s”,a);
for(i=0;i200;i++)
if(a[i]==’+’||a[i]==’-‘||a[i]==’*’)
break;
p=i;
if(a[i–]==’*’)
{
if(i0) k=a[1]*10+a[0];
else k=a[0];
fac(k);
}
if(a[i–]==’+’)
{
}
if(a[i–]==’-‘)
{
}
}
//是这样吗?到底是求阶乘还是求加减?题目清楚些?·