DS第二章课后习题答案.docx
《DS第二章课后习题答案.docx》由会员分享,可在线阅读,更多相关《DS第二章课后习题答案.docx(13页珍藏版)》请在冰点文库上搜索。
DS第二章课后习题答案
第二章线性表
2.1填空题
(1)一半插入或删除的位置
(2)静态动态
(3)一定不一定
(4)头指针头结点的next前一个元素的next
2.2选择题
(1)A
(2)DAGKHDAELIAFIFA(IDA)
(3)D(4)D(5)D
2.3
头指针:
在带头结点的链表中,头指针存储头结点的地址;在不带头结点的链表中,头指针存放第一个元素结点的地址;
头结点:
为了操作方便,在第一个元素结点前申请一个结点,其指针域存放第一个元素结点的地址,数据域可以什么都不放;
首元素结点:
第一个元素的结点。
2.4已知顺序表L递增有序,写一算法,将X插入到线性表的适当位置上,以保持线性表的有序性。
voidInserList(SeqList*L,ElemTypex)
{
inti=L->last;
if(L->last>=MAXSIZE-1)returnFALSE;//顺序表已满
while(i>=0&&L->elem[i]>x)
L->elem[i+1]=L->elem[i];
i--;
}
L->elem[i+1]=x;
L->last++;
2.5删除顺序表中从i开始的k个元素
intDelList(SeqList*L,inti,intk)
intj,l;
if(i<=0||i>L->last){printf("TheInitialPositionisError!
");return0;}
if(k<=0)return1;/*NoNeedtoDelete*/
if(i+k-2>=L->last)L->last=L->last-k;/*modifythelength*/
for(j=i-1,l=i+k-1;llast;j++,l++)
L->elem[j]=L->elem[l];
L->last=L->last-k;
return1;
2.6已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O
(1)的算法,删除线性表中所有值为item的数据元素。
[算法1]
voidDeleteItem(SeqList*L,ElemTypeitem)
inti=0,j=L->last;
while(i{while(ielem[i]!=item)i++;while(ielem[i]==item)j--;if(ielem[i]=L->elem[j];i++;j--;}}L->last=i-1;}[算法2]voidDeleteItem(SeqList*L,ElemTypee){inti,j;i=j=0;while(L->elem[i]!=e&&i<=L->last)i++;j=i+1;while(j<=L->last){while(L->elem[j]==e&&j<=L->last)j++;if(j<=L->last){L->elem[i]=L->elem[j];i++;j++;}}L->last=i-1;}2.7编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。voidDeleteRepeatItem(SeqList*L){inti=0,j=1;while(j<=L->last){if(L->elem[i]==L->elem[j])j++;else{L->elem[i+1]==L->elem[j];i++;j++;}}L->last=i;}2.8已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素),分析你的算法的时间复杂度。voidDelData(LinkListL,ElemTypemink,ElemTypemaxk){Node*p=L->next,*pre=L;while(!p&&p->data<=mink)//寻找开始删除的位置{pre=p;p=p->next;}while(p){if(p->data>maxk)break;else{pre->next=p->next;free(p);p=pre->next;}}}T(n)=O(n);2.9试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1,a2...,an)逆置为(an,an-1,...,a1)。(1)以一维数组作存储结构。(2)以单链表作存储结构。(略)(1)voidReverseArray(ElemTypea[],intn){inti=0,j=n-1;ElemTypet;while(i{t=a[i];a[i]=a[j];a[j]=t;}}(2)voidReverseList(LinkListL){p=L->next;L->next=NULL;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;}}2.10已知一个带有表头结点的单链表,假设链表只给出了头指针L。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,至返回0。(提示:设置两个指针,步长为k)intSearchNode(LinkListL,intk){Node*p=L,*q;inti=0;while(i{i++;p=p->next;}if(p==NULL)return0;//不存在倒数第k个元素q=L->next;while(p->next!=NULL)//p到终点时,q所指结点为倒数第k个{q=q->next;p=p->next;}printf("%d",q->data);return1;}2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。(头插法)LinkListReverseMerge(LinkList*A,LinkList*B){LinkListC;Node*pa=A->next,*pb=B->next;//pa和pb分别指向A,B的当前元素A->next=NULL;C=A;while(pa!=NULL&&pb!=NULL){if(pa->datadata)/*将pa的元素前插到pc表*/{temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}else{temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将pb的元素前插到pc表*/}while(pb!=NULL){temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}/*将剩余pa的元素前插到pc表*/while(pb!=NULL){temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将剩余pb的元素前插到pc表*/returnhc;}2.12一单链表,以第一个元素为基准,将小于该元素的结点全部放到前面,大于该结点的元素全部放到后面。时间复杂度要求为O(n),不能申请新空间。voidAdjustList(LinkListL){Node*pFlag=L->next,*q=L->next->next,*temp=NULL;pflag->next=NULL;while(q!=NULL){if(q->datadata)//插到链表首端{temp=q->next;q->next=L->next;L->next=q;q=temp;}Else//插到pFlag结点后面{temp=q->next;q->next=pFlag->next;pFlag->next=q;q=temp;}}}2.13假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。voidDelPreNode(Node*s){Node*p=s;while(p->next->next!=s)p=p->next;free(p->next);p->next=s;}2.14已知由单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其他字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。//L为待拆分链表//Lch为拆分后的字母链;Lnum为拆分后的数字链,Loth为拆分后的其他字符链//Lch,Lnum,Loth均已被初始化为带头结点的单循环链表,采用头插法voidsplitLinkList(LinkListL,LinkListLch,LinkListLnum,LinkListLoth){Node*p=L->next;while(p!=NULL){if((p->data>='a'&&p->data<='z')||(p->data>='A'&&p->data<='Z')){temp=p->next;p->next=Lch->next;Lch->next=p;p=temp;}elseif(p->data>='0'&&p->data<='9'){temp=p->next;p->next=Lnum->next;Lnum->next=p;p=temp;}else{temp=p->next;p->next=Loth->next;Loth->next=p;p=temp;}}}2.15设线性表A=(a1,a2,…,am),B=(b1,b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得:C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时;或者C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。//将A和B合并为C,C已经被初始化为空单链表voidMergeLinkList(LinkListA,LinkListB,LinkListC){Node*pa=A->next,*pb=B->next,*pc=C;inttag=1; while(pa&&pb){if(tag){pc->next=pa->next;pc=pc->next;pa=pa->next;tag=1;}else{pc->next=pb->next;pc=pc->next;pb=pb->next;tag=0;}}if(pa)pc->next=pa->next;elsepc->next=pb->next;s}2.16将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。//A为循环单链表,表示某多项式;将A拆分为B和C//其中B只含奇次项,C只含偶次项;奇偶按照幂次区分//B,C均已被初始化为带头结点的单链表voidSplitPolyList(PolyListA,PolyListB,PolyListC){PolyNode*pa=A->next,*rb=B,*rc=C;while(pa){if(pa->exp%2==0)//偶次项{rc->next=pa->next;rc=rc->next;pa=pa->next;}else//奇次项{rb->next=pa->next;rb=rb->next;pa=pa->next;}}rb->next=NULL;rc->next=NULL;}2.17建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。voidBinAdd(LinkListl)/*用带头结点的单链表L存储二进制数,实现加1运算*/{Node*q,*r,*s;q=l->next;r=l;while(q!=NULL)/*查找最后一个值域为0的结点*/{if(q->data==0)r=q;q=q->next;}if(r!=l)r->data=1;/*将最后一个值域为0的结点的值域赋为1*/else/*未找到值域为0的结点*/{s=(Node*)malloc(sizeof(Node));/*申请新结点存放最高进位*/s->data=1;/*值域赋为1*/s->next=L->next;L->next=s;/*插入到头结点之后*/r=s;}r=r->next;while(r!=NULL)/*将后面的所有结点的值域赋为0*/{r->data=0;r=r->next;}}2.18多项式P(x)采用书中所述链接方法存储。写一算法,对给定的x值,求P(x)的值。doubleCompute(PolyListPL,doublex){doublesum=0;PolyNode*p=PL->next;while(p){sum=sum+p->coef*pow(x,p->exp);p=p->next;}returnsum;}
while(ielem[i]!
=item)i++;
while(ielem[i]==item)j--;
if(ielem[i]=L->elem[j];i++;j--;}
L->last=i-1;
[算法2]
voidDeleteItem(SeqList*L,ElemTypee)
inti,j;
i=j=0;
while(L->elem[i]!
=e&&i<=L->last)
i++;
j=i+1;
while(j<=L->last)
while(L->elem[j]==e&&j<=L->last)
j++;
if(j<=L->last)
L->elem[i]=L->elem[j];
i++;j++;
2.7编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。
要求时间复杂度为O(n),空间复杂度为O
(1)。
voidDeleteRepeatItem(SeqList*L)
inti=0,j=1;
if(L->elem[i]==L->elem[j])
else
L->elem[i+1]==L->elem[j];
L->last=i;
2.8已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。
试写一高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素),分析你的算法的时间复杂度。
voidDelData(LinkListL,ElemTypemink,ElemTypemaxk)
Node*p=L->next,*pre=L;
while(!
p&&p->data<=mink)//寻找开始删除的位置
{pre=p;p=p->next;}
while(p)
if(p->data>maxk)
break;
pre->next=p->next;
free(p);
p=pre->next;
T(n)=O(n);
2.9试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1,a2...,an)逆置为(an,an-1,...,a1)。
(1)以一维数组作存储结构。
(2)以单链表作存储结构。
(略)
(1)
voidReverseArray(ElemTypea[],intn)
inti=0,j=n-1;
ElemTypet;
while(i{t=a[i];a[i]=a[j];a[j]=t;}}(2)voidReverseList(LinkListL){p=L->next;L->next=NULL;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;}}2.10已知一个带有表头结点的单链表,假设链表只给出了头指针L。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,至返回0。(提示:设置两个指针,步长为k)intSearchNode(LinkListL,intk){Node*p=L,*q;inti=0;while(i{i++;p=p->next;}if(p==NULL)return0;//不存在倒数第k个元素q=L->next;while(p->next!=NULL)//p到终点时,q所指结点为倒数第k个{q=q->next;p=p->next;}printf("%d",q->data);return1;}2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。(头插法)LinkListReverseMerge(LinkList*A,LinkList*B){LinkListC;Node*pa=A->next,*pb=B->next;//pa和pb分别指向A,B的当前元素A->next=NULL;C=A;while(pa!=NULL&&pb!=NULL){if(pa->datadata)/*将pa的元素前插到pc表*/{temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}else{temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将pb的元素前插到pc表*/}while(pb!=NULL){temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}/*将剩余pa的元素前插到pc表*/while(pb!=NULL){temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将剩余pb的元素前插到pc表*/returnhc;}2.12一单链表,以第一个元素为基准,将小于该元素的结点全部放到前面,大于该结点的元素全部放到后面。时间复杂度要求为O(n),不能申请新空间。voidAdjustList(LinkListL){Node*pFlag=L->next,*q=L->next->next,*temp=NULL;pflag->next=NULL;while(q!=NULL){if(q->datadata)//插到链表首端{temp=q->next;q->next=L->next;L->next=q;q=temp;}Else//插到pFlag结点后面{temp=q->next;q->next=pFlag->next;pFlag->next=q;q=temp;}}}2.13假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。voidDelPreNode(Node*s){Node*p=s;while(p->next->next!=s)p=p->next;free(p->next);p->next=s;}2.14已知由单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其他字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。//L为待拆分链表//Lch为拆分后的字母链;Lnum为拆分后的数字链,Loth为拆分后的其他字符链//Lch,Lnum,Loth均已被初始化为带头结点的单循环链表,采用头插法voidsplitLinkList(LinkListL,LinkListLch,LinkListLnum,LinkListLoth){Node*p=L->next;while(p!=NULL){if((p->data>='a'&&p->data<='z')||(p->data>='A'&&p->data<='Z')){temp=p->next;p->next=Lch->next;Lch->next=p;p=temp;}elseif(p->data>='0'&&p->data<='9'){temp=p->next;p->next=Lnum->next;Lnum->next=p;p=temp;}else{temp=p->next;p->next=Loth->next;Loth->next=p;p=temp;}}}2.15设线性表A=(a1,a2,…,am),B=(b1,b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得:C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时;或者C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。//将A和B合并为C,C已经被初始化为空单链表voidMergeLinkList(LinkListA,LinkListB,LinkListC){Node*pa=A->next,*pb=B->next,*pc=C;inttag=1; while(pa&&pb){if(tag){pc->next=pa->next;pc=pc->next;pa=pa->next;tag=1;}else{pc->next=pb->next;pc=pc->next;pb=pb->next;tag=0;}}if(pa)pc->next=pa->next;elsepc->next=pb->next;s}2.16将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。//A为循环单链表,表示某多项式;将A拆分为B和C//其中B只含奇次项,C只含偶次项;奇偶按照幂次区分//B,C均已被初始化为带头结点的单链表voidSplitPolyList(PolyListA,PolyListB,PolyListC){PolyNode*pa=A->next,*rb=B,*rc=C;while(pa){if(pa->exp%2==0)//偶次项{rc->next=pa->next;rc=rc->next;pa=pa->next;}else//奇次项{rb->next=pa->next;rb=rb->next;pa=pa->next;}}rb->next=NULL;rc->next=NULL;}2.17建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。voidBinAdd(LinkListl)/*用带头结点的单链表L存储二进制数,实现加1运算*/{Node*q,*r,*s;q=l->next;r=l;while(q!=NULL)/*查找最后一个值域为0的结点*/{if(q->data==0)r=q;q=q->next;}if(r!=l)r->data=1;/*将最后一个值域为0的结点的值域赋为1*/else/*未找到值域为0的结点*/{s=(Node*)malloc(sizeof(Node));/*申请新结点存放最高进位*/s->data=1;/*值域赋为1*/s->next=L->next;L->next=s;/*插入到头结点之后*/r=s;}r=r->next;while(r!=NULL)/*将后面的所有结点的值域赋为0*/{r->data=0;r=r->next;}}2.18多项式P(x)采用书中所述链接方法存储。写一算法,对给定的x值,求P(x)的值。doubleCompute(PolyListPL,doublex){doublesum=0;PolyNode*p=PL->next;while(p){sum=sum+p->coef*pow(x,p->exp);p=p->next;}returnsum;}
{t=a[i];a[i]=a[j];a[j]=t;}
(2)
voidReverseList(LinkListL)
p=L->next;
L->next=NULL;
while(p!
=NULL)
q=p->next;
p->next=L->next;
L->next=p;
p=q;
2.10已知一个带有表头结点的单链表,假设链表只给出了头指针L。
在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。
若查找成功,算法输出该结点的data域的值,并返回1;否则,至返回0。
(提示:
设置两个指针,步长为k)
intSearchNode(LinkListL,intk)
Node*p=L,*q;
inti=0;
while(i{i++;p=p->next;}if(p==NULL)return0;//不存在倒数第k个元素q=L->next;while(p->next!=NULL)//p到终点时,q所指结点为倒数第k个{q=q->next;p=p->next;}printf("%d",q->data);return1;}2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。(头插法)LinkListReverseMerge(LinkList*A,LinkList*B){LinkListC;Node*pa=A->next,*pb=B->next;//pa和pb分别指向A,B的当前元素A->next=NULL;C=A;while(pa!=NULL&&pb!=NULL){if(pa->datadata)/*将pa的元素前插到pc表*/{temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}else{temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将pb的元素前插到pc表*/}while(pb!=NULL){temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}/*将剩余pa的元素前插到pc表*/while(pb!=NULL){temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将剩余pb的元素前插到pc表*/returnhc;}2.12一单链表,以第一个元素为基准,将小于该元素的结点全部放到前面,大于该结点的元素全部放到后面。时间复杂度要求为O(n),不能申请新空间。voidAdjustList(LinkListL){Node*pFlag=L->next,*q=L->next->next,*temp=NULL;pflag->next=NULL;while(q!=NULL){if(q->datadata)//插到链表首端{temp=q->next;q->next=L->next;L->next=q;q=temp;}Else//插到pFlag结点后面{temp=q->next;q->next=pFlag->next;pFlag->next=q;q=temp;}}}2.13假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。voidDelPreNode(Node*s){Node*p=s;while(p->next->next!=s)p=p->next;free(p->next);p->next=s;}2.14已知由单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其他字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。//L为待拆分链表//Lch为拆分后的字母链;Lnum为拆分后的数字链,Loth为拆分后的其他字符链//Lch,Lnum,Loth均已被初始化为带头结点的单循环链表,采用头插法voidsplitLinkList(LinkListL,LinkListLch,LinkListLnum,LinkListLoth){Node*p=L->next;while(p!=NULL){if((p->data>='a'&&p->data<='z')||(p->data>='A'&&p->data<='Z')){temp=p->next;p->next=Lch->next;Lch->next=p;p=temp;}elseif(p->data>='0'&&p->data<='9'){temp=p->next;p->next=Lnum->next;Lnum->next=p;p=temp;}else{temp=p->next;p->next=Loth->next;Loth->next=p;p=temp;}}}2.15设线性表A=(a1,a2,…,am),B=(b1,b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得:C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时;或者C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。//将A和B合并为C,C已经被初始化为空单链表voidMergeLinkList(LinkListA,LinkListB,LinkListC){Node*pa=A->next,*pb=B->next,*pc=C;inttag=1; while(pa&&pb){if(tag){pc->next=pa->next;pc=pc->next;pa=pa->next;tag=1;}else{pc->next=pb->next;pc=pc->next;pb=pb->next;tag=0;}}if(pa)pc->next=pa->next;elsepc->next=pb->next;s}2.16将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。//A为循环单链表,表示某多项式;将A拆分为B和C//其中B只含奇次项,C只含偶次项;奇偶按照幂次区分//B,C均已被初始化为带头结点的单链表voidSplitPolyList(PolyListA,PolyListB,PolyListC){PolyNode*pa=A->next,*rb=B,*rc=C;while(pa){if(pa->exp%2==0)//偶次项{rc->next=pa->next;rc=rc->next;pa=pa->next;}else//奇次项{rb->next=pa->next;rb=rb->next;pa=pa->next;}}rb->next=NULL;rc->next=NULL;}2.17建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。voidBinAdd(LinkListl)/*用带头结点的单链表L存储二进制数,实现加1运算*/{Node*q,*r,*s;q=l->next;r=l;while(q!=NULL)/*查找最后一个值域为0的结点*/{if(q->data==0)r=q;q=q->next;}if(r!=l)r->data=1;/*将最后一个值域为0的结点的值域赋为1*/else/*未找到值域为0的结点*/{s=(Node*)malloc(sizeof(Node));/*申请新结点存放最高进位*/s->data=1;/*值域赋为1*/s->next=L->next;L->next=s;/*插入到头结点之后*/r=s;}r=r->next;while(r!=NULL)/*将后面的所有结点的值域赋为0*/{r->data=0;r=r->next;}}2.18多项式P(x)采用书中所述链接方法存储。写一算法,对给定的x值,求P(x)的值。doubleCompute(PolyListPL,doublex){doublesum=0;PolyNode*p=PL->next;while(p){sum=sum+p->coef*pow(x,p->exp);p=p->next;}returnsum;}
{i++;p=p->next;}
if(p==NULL)return0;//不存在倒数第k个元素
q=L->next;
while(p->next!
=NULL)//p到终点时,q所指结点为倒数第k个
{q=q->next;p=p->next;}
printf("%d",q->data);
2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。
(头插法)
LinkListReverseMerge(LinkList*A,LinkList*B)
{LinkListC;
Node*pa=A->next,*pb=B->next;//pa和pb分别指向A,B的当前元素
A->next=NULL;C=A;
while(pa!
=NULL&&pb!
if(pa->datadata)/*将pa的元素前插到pc表*/
{temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}
{temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将pb的元素前插到pc表*/
while(pb!
{temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}/*将剩余pa的元素前插到pc表*/
{temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将剩余pb的元素前插到pc表*/
returnhc;
2.12一单链表,以第一个元素为基准,将小于该元素的结点全部放到前面,大于该结点的元素全部放到后面。
时间复杂度要求为O(n),不能申请新空间。
voidAdjustList(LinkListL)
Node*pFlag=L->next,*q=L->next->next,*temp=NULL;
pflag->next=NULL;
while(q!
if(q->datadata)//插到链表首端
temp=q->next;q->next=L->next;
L->next=q;q=temp;
Else//插到pFlag结点后面
temp=q->next;q->next=pFlag->next;
pFlag->next=q;q=temp;
2.13假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。
已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。
voidDelPreNode(Node*s)
Node*p=s;
while(p->next->next!
=s)p=p->next;
free(p->next);
p->next=s;
2.14已知由单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其他字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。
//L为待拆分链表
//Lch为拆分后的字母链;Lnum为拆分后的数字链,Loth为拆分后的其他字符链
//Lch,Lnum,Loth均已被初始化为带头结点的单循环链表,采用头插法
voidsplitLinkList(LinkListL,LinkListLch,LinkListLnum,LinkListLoth)
Node*p=L->next;
if((p->data>='a'&&p->data<='z')||(p->data>='A'&&p->data<='Z'))
{temp=p->next;p->next=Lch->next;Lch->next=p;p=temp;}
elseif(p->data>='0'&&p->data<='9')
{temp=p->next;p->next=Lnum->next;Lnum->next=p;p=temp;}
{temp=p->next;p->next=Loth->next;Loth->next=p;p=temp;}
2.15设线性表A=(a1,a2,…,am),B=(b1,b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得:
C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时;
或者
C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。
线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。
注意:
单链表的长度值m和n均未显式存储。
//将A和B合并为C,C已经被初始化为空单链表
voidMergeLinkList(LinkListA,LinkListB,LinkListC)
Node*pa=A->next,*pb=B->next,*pc=C;
inttag=1;
while(pa&&pb)
if(tag)
{pc->next=pa->next;pc=pc->next;pa=pa->next;tag=1;}
{pc->next=pb->next;pc=pc->next;pb=pb->next;tag=0;}
if(pa)pc->next=pa->next;
elsepc->next=pb->next;s
2.16将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。
//A为循环单链表,表示某多项式;将A拆分为B和C
//其中B只含奇次项,C只含偶次项;奇偶按照幂次区分
//B,C均已被初始化为带头结点的单链表
voidSplitPolyList(PolyListA,PolyListB,PolyListC)
PolyNode*pa=A->next,*rb=B,*rc=C;
while(pa)
if(pa->exp%2==0)//偶次项
{rc->next=pa->next;rc=rc->next;pa=pa->next;}
else//奇次项
{rb->next=pa->next;rb=rb->next;pa=pa->next;}
rb->next=NULL;rc->next=NULL;
2.17建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。
并在此链表上实现对二进制数加1的运算。
voidBinAdd(LinkListl)/*用带头结点的单链表L存储二进制数,实现加1运算*/
Node*q,*r,*s;
q=l->next;
r=l;
=NULL)/*查找最后一个值域为0的结点*/
if(q->data==0)
r=q;
q=q->next;
if(r!
=l)
r->data=1;/*将最后一个值域为0的结点的值域赋为1*/
else/*未找到值域为0的结点*/
s=(Node*)malloc(sizeof(Node));/*申请新结点存放最高进位*/
s->data=1;/*值域赋为1*/
s->next=L->next;
L->next=s;/*插入到头结点之后*/
r=s;
r=r->next;
while(r!
=NULL)/*将后面的所有结点的值域赋为0*/
r->data=0;
2.18多项式P(x)采用书中所述链接方法存储。
写一算法,对给定的x值,求P(x)的值。
doubleCompute(PolyListPL,doublex)
doublesum=0;
PolyNode*p=PL->next;
sum=sum+p->coef*pow(x,p->exp);
p=p->next;
returnsum;
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2