数据结构 | 每日一练（67）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间）

(1) 确 定 在 序 列 中 比 正 整 数 x 大 的 数 有 几 个 （ 相 同 的 数 只 计 算 一 次 ， 如 序 列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比 10 大的数有 5 个）；

(2) 在单链表将比正整数 x 小的数按递减次序排列；

(3) 将正整数（比）x 大的偶数从单链表中删除。

正确答案

ps：||代表注释

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

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结束

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

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