东北大学2001年研究生试题的两种解法 (转载)

设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）
(1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；
(2) 在单链表将比正整数x小的数按递减次序排列；
(3) 将正整数（比）x大的偶数从单链表中删除。【东北大学 2001 二 (17分)】
[题目分析] 在由正整数序列组成的有序单链表中，数据递增有序，允许相等整数存在。确定比正整数x大的数有几个属于计数问题，相同数只计一次，要求记住前驱，前驱和后继值不同时移动前驱指针，进行计数。将比正整数x小的数按递减排序，属于单链表的逆置问题。比正整数x大的偶数从表中删除，属于单链表中结点的删除，必须记住其前驱，以使链表不断链。算法结束时，链表中结点的排列是：小于x的数按递减排列，接着是x（若有的话），最后是大于x的奇数。
[算法讨论] 本题“要求用最少的时间和最小的空间”。本算法中“最少的时间”体现在链表指针不回溯，最小空间是利用了几个变量。在查比x大的数时，必须找到第一个比x大的数所在结点（因等于x的数可能有，也可能多个，也可能没有）。之后，计数据的第一次出现，同时删去偶数。总的来说下面第二个算法是优秀的算法。
顺便指出，题目设有“按递增次序”的“有序单链表”，所给例子序列与题目的论述并不一致。
法（1）
void exam（LinkedList la，int x）
∥la是递增有序单链表，数据域为正整数。本算法确定比x大的数有几个；将比x小的数按递减排序，并将比x大的偶数从链表中删除。）
{p=la->next；q=p;∥p为工作指针 q指向最小值元素，其可能的后继将是>=x的第一个元素。
pre=la；        ∥pre为p的前驱结点指针。
k=0；           ∥计数（比x大的数）。
la->next=null；∥置空单链表表头结点。
while（p && p->data<x）     ∥先解决比x小的数按递减次序排列
{r=p->next；        ∥暂存后继
   p->next=la->next；∥逆置
   la->next=p；
   p=r；∥恢复当前指针。退出循环时，r指向值>=x的结点。
}
q->next=p; pre=q;   ∥pre指向结点的前驱结点
    while（p->data==x）{pre=p; p=p->next;} ∥从小于x到大于x可能经过等于x
      while（p）            ∥以下结点的数据域的值均大于x
        {k++; x=p->data;    ∥下面仍用x表示数据域的值，计数
         if（x % 2==0）     ∥删偶数
{while (p->data==x)
{u=p；p=p->next；free(u)；}
pre->next=p; ∥拉上链
}
        else               ∥处理奇数
while (p->data==x)∥相同数只记一次
{pre->next=p；pre=p；p=p->next；}
         }∥while(p)
       printf（“比值%d大的数有%d个\n”，x，k）；
   }∥算法exam结束
   
法（2）
Compare(int x,Node *L)
{
int count=0,comp=0;
int status=0;//当当前指针所指向的值>=x时，status=0，否则为1
Node *p,*t,*pre;
Node *end,*work=NULL;//work在逆置时指向逆置元素
p=L->next;
pre=L;
end=pre;
while(p)
{
if(p->data<x)
status=1;
if(comp!=p->data&&status==0)
{
count++;
comp=p->data;
}
if(status==0)
{
if(p==L&&(p->data)%2==0)
{
t=p;
L->next=p->next;
free(t);
p=L->next;
}
else if(p!=L&&(p->data)%2==0)
{
t=p;
pre->next=p->next;
free(t);
p=pre->next;
}
else
{
pre=p;
p=p->next;
}
end=pre;//最后end记录的是链表中最后一个大于x的值
}
if(status==1)
{
t=pre->next;
pre->next=work;
work=p;
p=t;
}
}
end->next=work;
}