数据结构考研分类复习真题 第二章 答案[48]

．[题目分析] 在由正整数序列组成的有序单链表中数据递增有序允许相等整数存在确定比正整数x大的数有几个属于计数问题相同数只计一次要求记住前驱前驱和后继值不同时移动前驱指针进行计数将比正整数x小的数按递减排序属于单链表的逆置问题比正整数x大的偶数从表中删除属于单链表中结点的删除必须记住其前驱以使链表不断链算法结束时链表中结点的排列是小于x的数按递减排列接着是x(若有的话)最后是大于x的奇数

void exam(LinkedList laint x)∥la是递增有序单链表数据域为正整数本算法确定比x大的数有几个;将比x小的数按递减排序并将比x大的偶数从链表中删除)

{p=la>next;q=p;∥p为工作指针 q指向最小值元素其可能的后继将是>=x的第一个元素

pre=la;∥pre为p的前驱结点指针

k=;∥计数(比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 % ==)∥删偶数

{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个\nxk);

}∥算法exam结束

[算法讨论] 本题要求用最少的时间和最小的空间本算法中最少的时间体现在链表指针不回溯最小空间是利用了几个变量在查比x大的数时必须找到第一个比x大的数所在结点(因等于x的数可能有也可能多个也可能没有)之后计数据的第一次出现同时删去偶数

顺便指出题目设有按递增次序的有序单链表所给例子序列与题目的论述并不一致

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []