知识分享 – 数据结构 | 每日一练(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-

正文完