◆2.19③ 已知线性表中的元素以值递增有序排列,并以
单链表作存储结构。试写一高效的算法,删除表中所有值
大于mink且小于maxk的元素(若表中存在这样的元素)同时
释放被删结点空间,并分析你的算法的时间复杂度(注意:
mink和maxk是给定的两个参变量,它们的值可以和表中的
元素相同,也可以不同)。
实现下列函数:
void DeleteSome(LinkList &L, ElemType mink, ElemType maxk);
/* Delete all the elements which value is between mink and */
/* maxk from the single sorted LinkList with head pointer L.*/
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
void DeleteSome(LinkList &L, ElemType mink, ElemType maxk)
/* Delete all the elements which value is between mink and */
/* maxk from the single sorted LinkList with head pointer L.*/
{
LinkList p,q;
p=L;q=L->next;
while(q)
{
if(q->data>=maxk) break;
else if(q->data {
p=q;q=q->next;}
else
{
p->next=q->next;
free(q);
q=p->next;}
}
}