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

数据结构

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

——老子

1

每日一练

1．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：

（1）找出最小值结点，且打印该数值；

（2）若该数值是奇数，则将其与直接后继结点的数值交换；

（3）若该数值是偶数，则将其直接后继结点删除。

正确答案

ps：||代表注释

[题目分析] 在无序的单链表上，查找最小值结点，要查遍整个链表，初始假定第一结点是最小值结点。当找到最小值结点后，判断数据域的值是否是奇数，若是，则“与其后继结点的值相交换”即仅仅交换数据域的值，用三个赋值语句即可交换。若与后继结点交换位置，则需交换指针，这时应知道最小值结点的前驱。至于删除后继结点，则通过修改最小值结点的指针域即可。

[算法设计]

void MiniValue（LinkedList la）

∥la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印。若最小值结点的数值是奇数，则与后

继结点值交换；否则，就删除其直接后继结点。

{p=la->next； ∥设la是头结点的头指针，p为工作指针。

pre=p； ∥pre指向最小值结点，初始假定首元结点值最小。

while（p->next!=null） ∥p->next是待比较的当前结点。

{ if（p->next->data<pre->data）pre=p->next；

p=p->next； ∥后移指针

}

printf（“最小值=%d\n”，pre->data）；

if（pre->data%2!=0） ∥处理奇数

if（pre->next!=null）∥若该结点没有后继，则不必交换

{t= pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕

else∥处理偶数情况

if（pre->next!=null）∥若最小值结点是最后一个结点，则无后继

{u=pre->next；pre->next=u->next；free（u）；} ∥释放后继结点空间

-end-