前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构 | 每日一练(67)

数据结构 | 每日一练(67)

作者头像
小林C语言
发布2019-06-05 15:29:20
1.1K0
发布2019-06-05 15:29:20
举报
文章被收录于专栏:C语言入门到精通

数据结构

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

——老子

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的数可能有,也可能多个,也可能没有)。之后,计数据的第一次出现,同时删去偶数。

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-05-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 C语言入门到精通 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档