2.19.c

来自「数据结构习题及答案」· C语言 代码 · 共 38 行

◆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<=mink)
        {
         p=q;q=q->next;}
        else
        {
         p->next=q->next;
         free(q);
         q=p->next;}
       }   
}