程序设计综合实践课件-线性表的链式存储-双向链表应用举例

4.4双向链表应用举例双向链表的每个结点分别包含指向后继结点和前驱结点两个指针。既可以从链首往链尾方向处理也可以从链尾往链首方向处理注意，采用双向链表存储后，链表的各基本操作需要同时维护好链表结点指针构成的两个方向链。下面以无符号大数的表示和加法运算实现为例介绍双链表处理。12图1.5无符号大数的双向链表表示struct Node{int digit;//数字structNode*next,*prev;//前后结点指针};//无符号大数结构体structUBigNumber{intdigitCount;//位数structNode*pHead,*pTail;//指向头结点，尾结点};3//下列函数返回的大数占用的内存资源由函数调用者负责释放//输入无符号大数structUBigNumberInputUBN();//打印无符号大数voidPrintUBN(structUBigNumberubn);//两个无符号大数相加structUBigNumberAddUBN(structUBigNumber*pA,structUBigNumber*pB);//销毁无符号大数，释放空间voidDestoryUBN(structUBigNumber*pA);4（待续）//下列函数是无符号大数处理辅助函数//建立表示无符号大数用带头结点双链表void_InitUBN(structUBigNumber*pUBN);//无符号大数尾部添加一位数void_AppendDigit(structUBigNumber*pUBN,intdigit);//无符号大数前部添加一位数void_AppendFrontDigit(structUBigNumber*pUBN,intdigit);//无符号大数规范表示，去除高位多余0，至少含一位数字void_Normalize(structUBigNumber*pUBN);//动态分配一个结点，返回结点指针//分配失败时，简化程序，退出运行structNode*_NewNode();5//输入无符号大数structUBigNumberInputUBN(){structUBigNumberresult;_InitUBN(&result);charch;

...//跳过非数字字符while(ch>='0'&&ch<='9'){_AppendDigit(&result,ch-'0');//添加1位ch=getchar();}_Normalize(&result);returnresult;}6//建立表示无符号大数用带头结点双链表void_InitUBN(structUBigNumber*pUBN){structNode*p=_NewNode();pUBN->pHead=pUBN->pTail=p;//建头结点p->next=p->prev=NULL;pUBN->digitCount=0;//位数0}7//无符号大数尾部添加一位数void_AppendDigit(structUBigNumber*pUBN,intdigit){if(pUBN->digitCount==1&&pUBN->pTail->digit==0)//原只有一个高位0{pUBN->pTail->digit=digit;//位数不变，数值为0return;}structNode*p=_NewNode();//申请新结点p->digit=digit;//设置结点数值p->next=NULL;//修改双链表，添加成为新尾部结点p->prev=pUBN->pTail;pUBN->pTail->next=p;pUBN->pTail=p;++pUBN->digitCount;//修改位数}8//无符号大数前添加一位数void_AppendFrontDigit(structUBigNumber*pUBN,intdigit){structNode*p=_NewNode();//申请新结点p->digit=digit;//设置结点数值p->next=pUBN->pHead->next;//修改双链表，添加在头结点后if(p->next!=NULL)p->next->prev=p;p->prev=pUBN->pHead;pUBN->pHead->next=p;if(pUBN->pTail==pUBN->pHead)pUBN->pTail=p;//原先只有头结点时，新结点也是尾结点++pUBN->digitCount;//修改位数}9//无符号大数规范表示，去除高位多余0，至少含一位数字void_Normalize(structUBigNumber*pUBN){if(pUBN->digitCount==0)_AppendDigit(pUBN,0);//去除高位多余的0while(pUBN->digitCount>1&&pUBN->pHead->next->digit==0){structNode*p;p=pUBN->pHead->next;//待删除的结点pUBN->pHead->next=p->next;//正向链表中删除p->next->prev=pUBN->pHead;//反向链表中删除free(p);//释放结点--pUBN->digitCount;//调整位数}}10//打印无符号大数voidPrintUBN(structUBigNumberubn){assert(ubn.digitCount>0&&ubn.pHead->next!=NULL);//断言：至少有1位数字structNode*la=ubn.pHead->next;//头结点无数据，跳过while(la){printf("%d",la->digit);la=la->next;}}11//两个无符号大数相加structUBigNumberAddUBN(structUBigNumber*pA,structUBigNumber*pB){structUBigNumberresult,*pResult=&result;_InitUBN(pResult);intiCarry=0;//进位，初始0structNode*p1,*p2;p1=pA->pTail;p2=pB->pTail;//从低位开始处理while(p1!=pA->pHead&&p2!=pB->pHead)//两数相同位处理{intdigit=p1->digit+p2->digit+iCarry;iCarry=digit/10;digit%=10;//新进位h和当前结果位_AppendFrontDigit(pResult,digit);//添加至结果最高位p1=p1->prev;//准备处理前一位p2=p2->prev;}（待续）

12while(p1!=pA->pHead)//第一大数剩余位处理{intdigit=p1->digit+iCarry;iCarry=digit/10;digit%=10;_AppendFrontDigit(pResult,digit);p1=p1->prev;}while(p2!=pB->pHead)//第二大数剩余位处理{intdigit=p2->digit+iCarry;iCarry=digit/10;digit%=10;_AppendFrontDigit(pResult,digit);p2=p2->prev;}（待续）

13if(iCarry!=0)//最后进位处理_AppendFrontDigit(pResult,iCarry);returnresult;}14//销毁无符号大数，释放空间voidDestoryUBN(structUBigNumber*pUBN){while(pUBN->pHead!=NULL)//清空后应该只剩一个头结点{structNode*p=pUBN->pHead;//待删除结点pUBN->pHead=p->next;//尾指针前移free(p);//释放结点}}15//动态分配一个结点，返回结点指针//分配失败时，简化程序，退出运行structNode*_NewNode(){structNode*p;p=(structNode*)malloc(sizeof(structNode));if(p==NULL)//分配失败{printf("Error:outofmemory\n");exit(-1);//简化程序，退出运行}returnp;}16intmain(){structUBigNumberA,B,C;A=InputUBN();B=InputUBN();//无符号大数输入C=AddUBN(&A,&B);//无符号大数相加PrintUBN(A);printf("+");PrintUBN(B);printf("=");PrintUBN(C);DestoryUBN(&A);//销毁无符号大数DestoryUBN(&B);DestoryUBN(&C);return0;}运行情况如下：21433245327543276473624763245324700342463724567342587325874325874554475143324532754327647362476324532470034+463724567342587325874325874554475=143788257321670234688350650407024509174.5其