Question

C语言数据结构题目 用链表 问题描述:设计一个实现任意长的整数进行加法运算的演示程序。基本要求:利

C语言数据结构题目 用链表
问题描述:设计一个实现任意长的整数进行加法运算的演示程序。基本要求:利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -215 - 1 215 - 1。输入和输出形式:按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据:(1)0;0;应输出“0” 。(2)-23456789;-76543211;应输出“-100000000” 。(3)-99999999;1000000000000;应输出“999(4)100010001;-100010001;应输出“0”。(5)100010001;-100010000;应输出“1” 。(6)-999999999999;-999999999999;应输出“1999999999998” 。(7)1000099999999;1;应输出“1000100000000”。实现提示:(1)每个结点中可以存放的最大整数为 32767，才能保证两数相加不会溢出，但若这样存放，即相当于按 32768 进制存放，在十进制与 32768 进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的 4 位，即不超过 9999 的非负整数，整个链表表示为万进制。(2)可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。选做内容实现长整数的四则运算。

Answer 1

试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。头指针：存放链表首地址的指针变量。头结点：链表的开始结点之前的一个同类型结点。开始结点：链表的第一个元素所在的结点。头指针的作用：用于确定链表的地址。头结点的作用：方便于处理开始结点的操作和处理其它结点的操作保持一致，也方便于处理空表的操作和处理非空表的操作保持一致。2.2有哪些链表可由一个尾指针来唯一确定？即从尾指针出发能访问链表上任何一个结点。单循环链表，双链表，双循环链表★2.3设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。#definearrsize100intInsertOrder(intA[],intelenum,intx){inti=elenum-1;if(elenum==arrsize)//在顺序表上进行插入操作必须先判满{printf(“full”);return0;}while(i>=0&&A[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(p&&q)//当链表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;}}