第二章 线性表(16)

48

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

若该数值是偶数，则将其直接后继结点删除。【东北大学 2000 二 (15分)】 [题目分析]在无序的单链表上，查找最小值结点，要查遍整个链表，初始假定第一结点是最小值结点。当找到最小值结点后，判断数据域的值是否是奇数，若是，则“与其后继结点的值相交换”，即仅仅交换数据域的值，用三个赋值语句即可完成。若与后继结点交换位置，则需交换指针，这时应知道最小值结点的前驱。至于删除后继结点，则通过修改最小值结点的指针域即可。 void MiniValue（LinkedList la）

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

∥若最小值结点的数值是奇数，则与后继结点值交换；否则，就删除其直接后继结点

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

pre=p； ∥pre指向最小值结点，初始假定首元结点值最小 while（p!=null） ∥p是待比较的当前结点 {if（p->datadata）pre=p； 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）；} ∥释放后继结点空间 30．已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的时间和最少的空间） 【东北大学 2002 三(15分)】

[题目分析]将一个结点数据域为字符的单链表，分解成含有字母字符、数字字符和其它字符的三个循环链表，首先要构造分别含有这三类字符的表头结点。然后从原链表第一个结点开始，根据结点数据域是字母字符、数字字符和其它字符而分别插入到三个链表之一的链表。注意不要因结点插入新建链表而使原链表断链。另外，题目并未要求链表有序，插入采用“前插法”，每次插入的结点均成为所插入链表的第一元素的结点即可。

void OneToThree（LinkedList L，la，ld，lo）

∥本算法将无头结点数据域为字符的链表L分成字母字符、数字字符和其它字符的三个循环链表

{la=（LinkedList）malloc（sizeof（LNode））； ∥建立三个链表的头结点 ld=（LinkedList）malloc（sizeof（LNode））； lo=（LinkedList）malloc（sizeof（LNode））；

la->next=la；ld->next=ld；lo->next=lo； ∥置三个循环链表为空表 while（L!=null） ∥分解原链表

49

{r=L; L=L->next; ∥L指向待处理结点的后继

if（r->data>=‘a’&& r->data<=‘z’|| r->data>=‘A’&& r->data<=‘Z’）

{r->next=la->next； la->next=r；} ∥处理字母字符 else if（r->data>=‘0’&& r->data<=‘9’） {r->next=ld->next；ld->next=r；} ∥处理数字字符

else {r->next=lo->next；lo->next=r；} ∥处理其它符号 }∥结束while（L!=null） }∥算法结束

[算法讨论] 算法中对L链表中每个结点只处理一次，时间复杂度O（n），只增加了必须的三个表头结点，符合题目“用最少的时间和最少的空间”的要求。 31．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间）

(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的奇数。 void exam（LinkedList la，int x） ∥本算法确定比x大的数有几个；将比x小的数按递减排序，并将比x大的偶数从链表中删除

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

pre=la； ∥pre为p的前驱结点指针 k=0； ∥计数（比x大的数） la->next=null； ∥置空单链表表头结点

while（p && p->datanext； ∥暂存后继 p->next=la->next； ∥逆置 la->next=p；

p=r；∥恢复当前指针。退出循环时，r指向值>=x的结点 }

q->next=p; pre=q; ∥pre指向结点的前驱结点

while（p && p->data==x）{pre=p; p=p->next;} ∥从小于x到大于x可能经过等于x

while（p） ∥以下结点的数据域的值均大于题目中的x {k++; y=p->data; ∥下面用y表示数据域的值，计数

50