专升本数据结构试题解析(5)
时间:2025-07-11
时间:2025-07-11
第2部分 习题解析 亱店↘打烊oO
new=(LinkList*)malloc(sizeof(LNode));
new->data=b;
if(i==1)
{/*插入在链表头部*/
New->next=*L;
*L=new;
}
else
{ /*插入在第i个元素的位置*/
p=*L;
while(--i>1) p=p->next;
new->next=p->next;p->next=new;
}
}/*Insert */
5.已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试设计一个高效的算法,删除表中所有值大于 mink且小于 maxk的元素(若表中存在这样的元素),同时释放被删结点空间(注意:mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同,也可以不同)。
【算法分析】
1)查找最后一个不大于mink的元素结点,由指针p指向;
2)如果还有比mink更大的元素,查找第一个不小于maxk的元素,由指针q指向;
3)p->next=q,即删除表中所有值大于 mink且小于 maxk的元素。
【算法源代码】
void Delete_Between(LinkList *L,int mink,int maxk)
{
p=*L;
while(p->next->data<=mink) p=p->next; /*p是最后一个不大于mink的元素*/
if(p->next) /*如果还有比mink更大的元素*/
{
q=p->next;
while(q->data<maxk) q=q->next; /*q是第一个不小于maxk的元素*/
p->next=q;
}
}/*Delete_Between */
6.已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试设计一个高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同),同时释放被删结点空间。
【算法分析】
1)初始化指针p和q,分别指向链表中相邻的两个元素;
2)当p->next不为空时,做如下处理:
①若相邻两元素不相等时,p和q都向后推一步;
②否则,当相邻元素相等时,删除多余元素。
【算法源代码】
void Delete_Equal(LinkList *L)
{
p=(*L)->next;q=p->next; /*p和q指向相邻的两个元素*/
while(p->next)
{
if(p->data!=q->data) /*若相邻两元素不相等时,p和q都向后推一步*/
{
p=p->next;
q=p->next;
}
else
{
while(q->data==p->data) /*当相邻元素相等时删除多余元素*/
{