云南建设厅网站首页,长治市建设局网站,wordpress 插件角色,互诺 网站好吗第二章 线性表算法题(线性表的链式存储) 二、综合应用题
1.设计一个递归算法#xff0c;删除不带头结点的单链表L中所有值为x的结点。
设f(L,x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点#xff0c;显然有f(L-next,x)的功能是删除以L-next为首结点指…第二章 线性表算法题(线性表的链式存储) 二、综合应用题
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-datax; f(L,x)f(L-next,x); 其他情况
void Del_X_3(LinkList L,ELemtype x)
{LNode *p;//p指向待删除结点 if(LNULL)//递归出口 return;if(L-datax)//若L所指结点的值为x {pL;//删除*L,并让L指向下一个结点 LL-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 *pL-next,*preL,*q;//置p和pre的初始值 while(p!NULL){if(p-datax){qp;//q指向被删结点 pp-next;pre-nextp;//将*q结点从链表中断开 free(q);//释放*q结点的空间 }else//否则pre和p同步后移 {prep;pp-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 *preL,*ppre-next;//p为工作指针pre指向其前驱LNode *minprepre,*minpp;//保存最小值结点及其前驱 while(p!NULL){if(p-dataminp-data){minpp;//找到比之前找到的最小值结点更小的结点 minprepre; }prep;//继续扫描下一个结点 pp-next; }minpre-nextminp-next;//删除最小值结点 free(minp);return L;
}
5.试编写算法将带头结点的单链表就地逆置所谓“就地”是指辅助空间复杂度为O(1)。
算法思想将头结点摘下然后从第一结点开始依次插入到头结点的后面头插法建立单链表直到最后一个结点为止这样就实现了链表的逆置。
LinkList Reverse(LinkList L)
{LNode *p,*r;//p为工作指针r为p的后继以防断链 pL-next;//从第一个元素结点开始 L-nextNULL;//先将头结点L的next域值为NULL while(p!NULL)//依次将元素结点摘下 {rp-next;//暂存p的后继 p-nextL-next;//将p结点插入到头结点之后 L-nextp;pr;}return L;
}
6.有一个带头结点的单链表L设计一个算法使其元素递增有序。
算法思想采用直接插入排序算法的思想先构成只含一个数据结点的有序单链表然后依次扫描单链表中剩下的结点*p(直至pNULL为止)在有序表中通过比较查找插入*p的前驱结点*pre,然后将*p插入到*pre之后。
void Sort(LinkList L)
{LNode *pL-next,*pre;//r保持*p后继结点指针以保证不断链 LNode *rp-next;//构造只含一个数据结点的有序表 p-nextNULL;pr;while(p!NULL){rp-next;//保存*p的后继结点指针 preL;while(pre-next!NULLpre-next-datap-data) prepre-next;//在有序表中查找插入*p的前驱结点*pre p-nextpre-next;//将*p插入到*pre之后 pre-nextp;pr;//扫描原单链表中剩下的结点 }
}
7.设在一个带表头结点的单链表中所有元素结点的数据值无序试编写一个函数删除表中所有介于给定的两个值作为函数参数给出之间的元素若存在。
算法思想因为链表是无序的所以只能逐个结点进行检查执行删除。
void RangeDelete(LinkList L,int min,int max)
{LNode *prL,*pL-link;//p是检测指针pr使其前驱 while(p!NULL){if(p-dataminp-datamax)//寻找到被删结点删除 {pr-linkp-link;free(p);ppr-link;}else//否则继续寻找被删结点 {prp;pp-link;}}
}
8.给定两个单链表编写算法找出两个链表的公共结点。
LinkList Search_1st_Common(LinkList L1,LinkList L2)
{int dist;int len1Length(L1),len2Length(L2);//计算两个链表的表长LinkList longList,shortList;//分别指向表长较长和较短的链表if(len1len2)//L1表长较长 {longListL1-next;shortListL2-next;distlen1-len2; //表长之差 } else//L2表长较长{longListL2-next;shortListL1-next;distlen2-len1; //表长之差 } while(dist--)//表长的链表先遍历到第dist个结点然后同步 longListlongList-next;while(longList!NULL)//同步寻找共同结点 {if(longListshortList)//找到第一个公共结点 return longList;else//继续同步寻找 {longListlongList-next;shortListshortList-next;}}return NULL;
}
9.给定一个带表头结点的单链表,设head为头指针结点结构为data,next,data为整型元素next为指针试写出算法按递增次序输出单链表中各结点的数据元素并释放结点所占的存储空间要求不允许使用数组作为辅助空间。
算法思想对链表进行遍历在每次遍历中找出整个链表的最小值元素输出并释放结点所占空间再次查找次小值元素输出并释放空间如此下去直至链表为空最后释放头结点所占存储空间。
void Min_Delete(LinkList head)
{while(head-next!NULL)//循环到仅剩头结点 {LNode *prehead;//pre为元素最小值结点的前驱结点的指针 LNode *ppre-next;//p为工作指针 Lnode *u;//指向被删除结点 while(p-next!NULL){if(p-next-datapre-next-data)prep;//记住当前最小值结点的前驱 pp-next;}print(pre-next-data);//输出元素最小值结点的数据 upre-next;//删除元素值最小的结点释放结点空间 pre-nextu-next;free(u);}free(head);//释放头结点
}
10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B使得A表中含有原表中序号为奇数的元素而B表中含有原表中序号为偶数的元素且保持其相对顺序不变。
算法思想设置一个访问序号变量初值为0,每访问一个结点序号自动加1然后根据序号的奇偶性将结点插入到A表或B表中。重复以上操作直到表尾。
LinkList DisCreat_1(LinkList A)
{int i0;//i记录表A中结点的序号 LinkList B(LinkList)malloc(sizeof(LNode));//创建B表表头 B-nextNULL;//B表的初始化 LNode *raA,*rbB,*p;//ra和rb将分别指向将创建的A表和B表的尾结点 pA-next;//p为链表工作指针指向待分解的结点 A-nextNULL;//置空新的A表 while(p!NULL){i;//序号加1 if(i%20)//处理序号为偶数的链表结点 {rb-nextp;//在B表插入新结点 rbp;//rb指向新的尾结点 }else//处理序号为奇数的链表结点 {ra-nextp;//在A表插入新结点rap;//ra指向新的尾结点 }pp-next;//将p恢复为指向新的待处理结点 }ra-nextNULL;rb-nextNULL;return B;
}
11.设C{a1,b1,a2,b2,...,an,bn}为线性表采用带头结点的单链表存放设计一个就地算法将其拆分为两个线性表使得A{a1,a2,...,an},B{bn,...,b2,b1}。
算法思想采用上题的思路不设序号变量。二者的差别仅在于对B表建立不采用尾插法而是采用头插法。
LinkList DisCreat_2(LinkList A)
{LinkList B(LinkList)malloc(sizeof(LNode));//创建B表表头 B-nextNULL;//B表的初始化 LNode *pA-next,*q;//p为工作指针 LNode *raA;//ra始终指向A的尾结点 while(p!NULL){ra-nextp;rap;//将*p链到A的表尾 pp-next;if(p!NULL){qp-next;//头插后*p将断链因此用q记忆*p的后继 p-nextB-next;//将*p插入到B的前端 B-nextp;pq; } } ra-nextNULL;//A表结点的next域置空 return B;
}
12.在一个递增有序的现行标准中有数值相同的元素存在。若存储方式为单链表设计算法去掉数值相同的元素使表中不再有重复的元素例如7101021304242425170将变为7102130425170。
算法思想由于是有序表所有相同值域的结点都是相邻的。用p扫描递增单链表L,若*p结点等于其后继结点的值域则删除后者否则p移向下一个结点。
void Del_Same(LinkList L)
{LNode *pL-next,*q;//p为扫描工作指针 if(pNULL)return;while(p-next!NULL){qp-next;//q指向*p的后继结点 if(p-dataq-data)//找到重复值的结点 {p-nextq-next;//释放*q结点 free(q);//释放相同元素值的结点 }else{pp-next;}}
}
13.假设有两个按元素值递增次序排列的线性表均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
算法思想两个链表已经按元素值递增次序排序将其合并时均从第一个结点起进行比较将小的结点链入链表中同时后移工作指针。该问题要求结果链表按元素值递减次序排列故新链表的建立应该采用头插法。比较结束后可能会有一个链表为空此时用头插法将剩下的结点依次插入到新链表中即可。
void MergeList(LinkList La,LinkList Lb)
{LNode *r,*paLa-next,*pbLb-next;//分别是表La和Lb的工作指针 La-nextNULL;//La作为结果链表的头指针先将结果链表初始化为空 while(papb)//当两链表均不为空时循环 {if(pa-datapb-data){rpa-next;//r暂存pa的后继结点指针 pa-nextLa-next;La-nextpa;//将pa结点链于结果表中同时逆置(头插法) par;//恢复pa为当前待比较结点 }else{rpb-next;//r暂存pb的后继结点指针pb-nextLa-next;La-nextpb;//将pb结点链于结果表中同时逆置(头插法)pbr;//恢复pb为当前待比较结点 } if(pa)pbpa;//通常情况下会剩一个链表非空处理剩下的部分 while(pb){//处理剩下的一个非空链表 rpb-next;//依次插入到La中(头插法) pb-nextLa-next;La-nextpb;pbr; }free(Lb); }
}
14.设A和B是两个单链表(带头结点)其中元素递增有序。设计一个算法从A和B中的公共元素产生单链表C,要求不破坏A、B的结点。
算法思想表A、B都有序可从第一个元素起依次比较A、B两表的元素若元素值不等则值小的指针往后移若元素值相等则创建一个值等于两结点的元素值的新结点使用尾插法插入到新的链表中并将两个原表指针后移一位直到其中一个链表遍历到表尾。
void Get_Common(LinkList A,LinkList B)
{LNode *pA-next,*qB-next,*r,*s;LinkList C(LinkList)malloc(sizeof(LNode));//建立表CrC;//r始终指向C的尾结点 while(p!NULLq!NULL)//循环跳出条件 {if(p-dataq-data)pp-next;//若A的当前元素较小后移指针 else if(p-dataq-data)qq-next;//若B的当前元素较小后移指针else//找到公共元素结点 {s(LNode *)malloc(sizeof(LNode));s-datap-data;//复制产生结点*s r-nexts;//将*s链接到C上(尾插法) rs;pp-next;//表A和表B继续先后扫描 qq-next; } }r-nextNULL;//置C尾结点指针为空
}
