海淀区企业网站建设,购物商城网站的运营,网站开发需要掌握哪些知识,wordpress分页目录编辑文章目录 主要内容一.链表练习题1.设计一个递归算法#xff0c;删除不带头结点的单链表 L 中所有值为 X 的结点代码如下#xff08;示例#xff09;: 2.设 L为带头结点的单链表#xff0c;编写算法实现从尾到头反向输出每个结点的值代码如下#xff08;示例#xff09;: … 文章目录 主要内容一.链表练习题1.设计一个递归算法删除不带头结点的单链表 L 中所有值为 X 的结点代码如下示例: 2.设 L为带头结点的单链表编写算法实现从尾到头反向输出每个结点的值代码如下示例: 3.试编写算法将带头结点的单链表就地逆置所谓“就地”是指辅助空间复杂度为 O(1).代码如下示例: 4.有一个带头结点的单链表 L设计一个算法使其元素递增有序。代码如下示例: 5.设计一个算法用于判断带头结点的循环双链表是否对称代码如下示例: 6.有两个循环单链表链表头指针分别为 h1和h2编写一个函数将链表 h2 链接到链表h1 之后要求链接后的链表仍保持循环链表形式代码如下示例: 总结 主要内容
链表基础练习题
一.链表练习题 1.设计一个递归算法删除不带头结点的单链表 L 中所有值为 X 的结点
代码如下示例:
设 f(L,x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点
显然有f(L-next,x)的功能是删除以L-next 为首结点指针的单链表中所有值等于x 的结点。
由此可以推出递归模型如下。
终止条件:f(Lx)不做任何事情; 若L为空表
递归主体:f(L,x)删除*L结点;f(L-next,x); 若L-dataxf(L,x)f(L-next,x); 其他情况void Del_X_3(Linklist L,ElemType x){//递归实现在单链表L中删除值为x的结点LNode *p; //p指向待删除结点if(LNULL) //递归出口return;if(L-datax){ //若L所指结点的值为XpL; //删除*L并LL-next;free(p);Del_X_3(L,x); //递归调用}else //若L所指结点的值不为XDel_X_3(L-next,x); //递归调用
}
2.设 L为带头结点的单链表编写算法实现从尾到头反向输出每个结点的值
代码如下示例:
void R Print(LinkList L){
//从尾到头输出单链表L中每个结点的值if(L-next!NULL){ //递归R_Print(L-next);) //ifif(L!NULL) print(L-data); //输出函数
}
void R_Ignore_Head(LinkList L){
if(L-next!NULL) R_Print(L-next);
}3.试编写算法将带头结点的单链表就地逆置所谓“就地”是指辅助空间复杂度为 O(1).
代码如下示例:
假设 pre、p和r指向3个相邻的结点如下图所示。假设经过若干操作后*pre 之前的结点的指针都已调整完毕它们的 next 都指向其原前驱结点。现在令*p 结点的 next 域指向pre 结点注意到一旦调整指针的指向*p 的后继结点的链就会断开为此需要用r 来指向原*p 的后继结点。处理时需要注意两点:一是在处理第一个结点时应将其 next 域置为 NULL而不是指向头结点(因为它将作为新表的尾结点);二是在处理完最后一个结点后需要将头结点的指针指向它 LinkList Reverse(LinkList L){
//依次遍历线性表 L并将结点指针反转INode *pre*pL-next*rp-next;p-nextNULL; //处理第一个结点while(r!NULL){ //r为空则说明p为最后一个结点prep; //依次继续遍历pr;rr-next;p-nextpre; //指针反转}L-nextp; //处理最后一个结点return L;
}4.有一个带头结点的单链表 L设计一个算法使其元素递增有序。
代码如下示例:
算法思想:采用直接插入排序算法的思想先构成只含一个数据结点的有序单链表然后依次扫描单链表中剩下的结点*p (直至 pNULL 为止)在有序表中通过比较查找插入*p 的前驱结点*pre然后将*p 插入到*pre 之后如下图所示。void Sort(LinkList L)(
//本算法实现将单链表L的结点重排使其递增有序LNode *pL-next,*pre;LNode *rp-next; //r保持*p后继结点指针以保证不断链微p-nextNULL; //构造只含一个数据结点的有序表pr;while(p!NULL)(rp-next; //保存*p的后继结点指针preL;while(pre-next!NULLpre-next-datap-data)prepre-next; //在有序表中查找插入*p的前驱结点*prep-nextpre-next; //将*p插入到*pre之后pre-nextp;pr; //扫描原单链表中剩下的结点}
}5.设计一个算法用于判断带头结点的循环双链表是否对称
代码如下示例:
算法思想:让 p从左向右扫描 从右向左扫描直到它们指向同一结点(pg当循环双链表中结点个数为奇数时)或相邻(p-nextg或g-priorp
当循环双链表中结点个数为偶数时)为止若它们所指结点值相同则继续进行下去否则返回 0。若比较全部相等则返回1。int Symmetry(DLinkList L){
//本算法从两头扫描循环双链表以判断链表是否对称DNode *pL-next*qL-prior; //两头工作指针while(p!qp-next!g) //循环跳出条件if(p-dataq-data){ //所指结点值相同则继续比较pp-next;qq-prior;}else //否则返回0return 0;return 1; //比较结束后返回1
}
6.有两个循环单链表链表头指针分别为 h1和h2编写一个函数将链表 h2 链接到链表h1 之后要求链接后的链表仍保持循环链表形式
代码如下示例:
算法思想:先找到两个链表的尾指针将第一个链表的尾指针与第二个链表的头结点链接起来再使之成为循环的。LinkList Link(linklist hl,LinkList ah2){
//将循环链表h2链接到循环链表h1之后使之仍保持循环链表的形式LNode *p*q; //分别指向两个链表的尾结点ph1;while(p-next!h1) //寻找h1的尾结点pp-next;qh2;while(q-next!h2) //寻找h2的尾结点qq-next;p-nexth2; //将h2链接到h1之后q-nexth1; //令h2的尾结点指向 h1return hl;
}总结
以上是今天要讲的内容练习了链表相关习题。
