专栏首页C语言入门到精通数据结构 | 每日一练(24)

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

数据结构

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

——老子

1

每日一练

1.已给如下关于单链表的类型说明:

TYPE

list=^node ;

node=RECORD

data: integer; next: list;

END;

以下程序采用链表合并的方法,将两个已排序的单链表合并成一个链表而不改变其排序性(升序),这里两链表的头指针分别为 p 和 q.

PROCEDURE mergelink(VAR p,q:list):

VAR h,r: list;

BEGIN

(1)______

h^.next:= NIL; r:=h;

WHILE((p<>NIL) AND (q<>NIL)) DO

IF (p^.data<=q^.data)

THEN BEGIN (2)___; r:=p; p:=p^.next; END

ELSE BEGIN (3)____; r:=q; q:=q^.next; END;

IF (p=NIL) THEN r^.next:=q;

(4)__;

p:=h^.next; dispose(h);

2.假设链表 p 和链表 q 中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为 max,且链表中其他结点的值都小于 max,在程序中取 max 为 9999。在各个链表中,每个结点的值各不相同,但链表 p 和链表 q 可能有值相同的结点(表头结点除外)。下面的程序将链表 q合并到链表 p 中,使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表,且链表中各个结点的值各不相同。请在划线处填上适当内容,每个框只填一个语句或一个表达式,链表的结点类型如下

TYPE nodeptr=^nodetype;

nodetype=RECORD

data:integer; link:nodeptr;

END;

CONST max=9999;

PROCEDURE merge(VAR p:nodeptr;q:nodeptr);

VAR r,s: nodeptr;

BEGIN

r:=p;

WHILE (A)___ DO

BEGIN

WHILE r^.link^.data<q^.link^.data DO (B)___;

IF r^.link^.data>q^.link^.data

THEN BEGIN s:=(C)_; (D)_:=s^.link; s^.link:=(E)_; (F)_ _:=s; (G)_; END

ELSE BEGIN (H)__; s:=q^.link; (I)__; dispose(s) END

END;

dispose(q)

END;

正确答案

1.

(1)new(h);∥生成头结点,以便于操作。

(2)r^.next:=p; (3) r^.next:=q; (4) IF (q=NIL) THEN r^.next:=p;

2.

A: r^.link^.data<>max AND q^.link^.data<>max

B: r:=r^.link

C: q^.link

D: q^.link

E: r^.link

F: r^.link

G: r:=s(或r:= r^.link)

H: r:=r^.link

I: q^.link:=s^.link

-end-

你学习了么?

文 | 闫小林

本文分享自微信公众号 - C语言入门到精通(yclzl960229)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 | 每日一练(46)

    1.已知不带头结点的线性链表 list,链表中结点构造为(data、link),其中 data 为数据域,link 为指

    闫小林
  • 数据结构 | 每日一练(26)

    ——老子

    闫小林
  • 数据结构 | 每日一练(51)

    1. 已知非空线性链表由 list 指出,链结点的构造为(data,link).请写一算法,将链表中数据域值最小的那个链结点移到链表的最前面。要求:不得额外申请...

    闫小林
  • 数据结构 | 每日一练(46)

    1.已知不带头结点的线性链表 list,链表中结点构造为(data、link),其中 data 为数据域,link 为指

    闫小林
  • 深入理解docker的link机制

    原文地址:https://yq.aliyun.com/articles/55912

    天涯泪小武
  • 请你解释一下hashMap具体如何实现的?

    Hashmap基于数组实现的,通过对key的hashcode & 数组的长度得到在数组中位置,如当前数组有元素,则数组当前元素next指向要插入的元素,这样来解...

    剑走天涯
  • 【每天一道编程系列-2018.2.6】(Ans)

    Merge k sorted linked lists and return it as one sorted list. Analyze and desc...

    yesr
  • Spring 注解概览

    从Java5.0开始,Java开始支持注解。Spring做为Java生态中的领军框架,从2.5版本后也开始支持注解。相比起之前使用xml来配置Spring框架,...

    程序员宝库
  • Spring 最常用的 7 大类注解,史上最强整理!

    随着技术的更新迭代,Java5.0开始支持注解。而作为java中的领军框架spring,自从更新了2.5版本之后也开始慢慢舍弃xml配置,更多使用注解来控制sp...

    Java技术栈
  • Spring 最常用的 7 大类注解,史上最强整理!

    随着技术的更新迭代,Java5.0开始支持注解。而作为java中的领军框架spring,自从更新了2.5版本之后也开始慢慢舍弃xml配置,更多使用注解来控制sp...

    macrozheng

扫码关注云+社区

领取腾讯云代金券