王道考研"/>
2024 王道考研
第二章 线性表算法题(线性表的链式存储)
二、综合应用题
1.设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点。
设f(L,x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点,显然有f(L->next,x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。因此,可以推递归模型如下。
终止主体:f(L,x)=不做任何事情; 若L为空表
递归主体:f(L,x)=删除*L结点;f(L->next,x); 若L->data==x;
f(L,x)=f(L->next,x); 其他情况
void Del_X_3(LinkList &L,ELemtype x)
{LNode *p;//p指向待删除结点 if(L==NULL)//递归出口 return;if(L->data==x)//若L所指结点的值为x {p=L;//删除*L,并让L指向下一个结点 L=L->next;free(p);Del_X_3(L,x);//递归调用 }else//若L所指结点的值不为x {Del_X_3(L->next,x);//递归调用 }
}
2.在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法以实现上述操作。
算法思想:用p从头至尾扫描单链表,pre指向*p结点的前驱。若p所指结点的值为x,则删除,并让p移向下一个结点,否则让pre、p指针同步后移一个结点。
void Del_X_1(LinkList &L,ElemType x)
{LNode *p=L->next,*pre=L,*q;//置p和pre的初始值 while(p!=NULL){if(p->data==x){q=p;//q指向被删结点 p=p->next;pre->next=p;//将*q结点从链表中断开 free(q);//释放*q结点的空间 }else//否则,pre和p同步后移 {pre=p;p=p->next; } }
}
3.设L为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值。
void R_Print(LinkList L)
{if(L->next!=NULL){R_Print(L->next);//递归 }if(L!=NULL)print(L->data);//输出函数
}
void R_Ignore_Head(LinkList L)
{if(L->next!=NULL)R_Print(L->next);
}
4.试编写在头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。
算法思想:用p从头至尾扫描单链表,pre指向*p结点的前驱,用minp保存值最小的结点指针(初值为p),minpre指向*minp结点的前驱(初值为pre)。一边扫描,一边比较,若p->data小于minp->data,则将p、pre分别赋值给minp、minpre。当p扫描完毕时,minp指向最小值结点,minpre指向最小值结点的前驱结点,再将minp所指结点删除即可。
LinkList Delete_Min(LinkList &L)
{LNode *pre=L,*p=pre->next;//p为工作指针,pre指向其前驱LNode *minpre=pre,*minp=p;//保存最小值结点及其前驱 while(p!=NULL){if(p->data<minp->data){minp=p;//找到比之前找到的最小值结点更小的结点 minpre=pre; }pre=p;//继续扫描下一个结点 p=p->next; }minpre->next=minp->next;//删除最小值结点 free(minp);return L;
}
5.试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为O(1)。
算法思想:将头结点摘下,然后从第一结点开始,依次插入到头结点的后面(头插法建立单链表),直到最后一个结点为止,这样就实现了链表的逆置。
LinkList Reverse(LinkList L)
{LNode *p,*r;//p为工作指针,r为p的后继,以防断链 p=L->next;//从第一个元素结点开始 L->next=NULL;//先将头结点L的next域值为NULL while(p!=NULL)//依次将元素结点摘下 {r=p->next;//暂存p的后继 p->next=L->next;//将p结点插入到头结点之后 L->next=p;p=r;}return L;
}
6.有一个带头结点的单链表L,设计一个算法使其元素递增有序。
算法思想:采用直接插入排序算法的思想,先构成只含一个数据结点的有序单链表,然后依次扫描单链表中剩下的结点*p(直至p==NULL为止),在有序表中通过比较查找插入*p的前驱结点*pre,然后将*p插入到*pre之后。
7.设在一个带表头结点的单链表中所有元素结点的数据值无序,试编写一个函数,删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)。
8.给定两个单链表,编写算法找出两个链表的公共结点。
更多推荐
2024 王道考研
发布评论