数据结构考研分类复习真题 第二章 答案[33]

．[题目分析] 在单链表中删除自第i个元素起的共len个元素应从第个元素起开始计数记到第i个时开始数len个然后将第i个元素的后继指针指向第i+len个结点实现了在A链表中删除自第i个起的len个结点这时应继续查到A的尾结点得到删除元素后的A链表再查B链表的第j个元素将A链表插入之插入和删除中应注意前驱后继关系不能使链表断链另外算法中应判断ilen和j的合法性

LinkedList DelInsert(LinkedList headaheadbint ijlen)∥heada和headb均是带头结点的单链表本算法删除heada链表中自第i个元素起的共len个元素然后将单链表heada插入到headb的第j个元素之前

{if(i< || len< || j<){printf(参数错误\n);exit();}∥参数错退出算法

p=heada;∥p为链表A的工作指针初始化为A的头指针查到第i个元素时p指向第i个元素

k=;∥计数

while(p!=null && k<i)∥查找第i个结点

{k++;p=p>next;}

if(p==null){printf(给的%d太大\ni);exit();}∥i太大退出算法

q=p>next;∥q为工作指针初始指向A链表第一个被删结点

k=;

while(q!=null && k<len){k++;u=qq=q>next;free(u);}∥删除结点后移指针

if(k<len){printf(给的%d太大\nlen);exit();}

p>next=q;∥A链表删除了len个元素

if (heada>next!=null)∥heada>next=null说明链表中结点均已删除无需往B表插入

{while(p>next!=null)p= p>next;∥找A的尾结点

q=headb;∥q为链表B的工作指针

k=;∥计数

while(q!=null && k<j)∥查找第j个结点

{k++;q= q>next;}∥查找成功时q指向第j个结点

if(q==null){printf(给的%d太大\nj);exit();}

p>next=q>next;∥将A链表链入

q>next=heada>next;∥A的第一元素结点链在B的第j个结点之后

}//if

free(heada);∥释放A表头结点

}∥算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []