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

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

1

每日一

1.设 Listhead 为一单链表的头指针,单链表的每个结点由一个整数域 DATA 和指针域 NEXT 组成,整数在单链表中是无序的。编一 PASCAL 过程,将 Listhead 链中结点分成一个奇数链和一个偶数链,分别由 P,Q指向,每个链中的数据按由小到大排列。程序中不得使用 NEW 过程申请空间。

类似本题的另外叙述有:

(1)设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C,其中 B 表的结点为 A 表中值小于零的结点,而 C 表的结点为 A 表中值大于零的结点(链表 A 的元素类型为整型,要求 B、C 表利用 A 表的结点)。

(2) 设 L 为一单链表的头指针,单链表的每个结点由一个整数域 data 和指针域 NEXT 组成,整数在单链表中是无序的。设计算法,将链表中结点分成一个奇数链和一个偶数链,分别由 P,Q 指向,每个链中的数据按由小到大排列,算法中不得申请新的结点空间。

(3) 将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B,使得 A 表中含有原表中序号为奇数的元素,而 B 表中含有原表中序号为偶数的元素,且保持其相对顺序不变。

1) 写出其类型定义:

2) 写出算法。

正确答案

ps:||代表注释

1.[题目分析]本题要求将一个链表分解成两个链表,两个链表都要有序,两链表建立过程中不得使用NEW过程申请空间,这就是要利用原链表空间,随着原链表的分解,新建链表随之排序。

PROC discreat(VAR listhead,P,Q:linkedlist)∥listhead是单链表的头指针,链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表listhead分解成奇数链表和偶数链表,分解由P和Q指向,且P和Q链表是有序的。

P:=NIL;Q:=NIL;∥P和Q链表初始化为空表。

s:=listhead;

WHILE(s<>NIL) DO

[r:=s^.NEXT; ∥暂存s的后继。

IF s^.DATA DIV 2=0 ∥处理偶数。

THEN IF P=NIL THEN[P:=s;P^.NEXT:=NIL;] ∥第一个偶数链结点。

ELSE[pre:=P;

IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre;P:=s;∥插入当前最小值结点修改头指针]

ELSE[ WHILE pre^.NEXT<>NIL DO

IF pre^.NEXT^.DATA<s^.DATA THEN pre:=pre^.NEXT;∥查找插入位置。

s^.NEXT:=pre^.NEXT; ∥链入此结点。

pre^.NEXT:=s;

]

]

ELSE∥处理奇数链。

IF Q=NIL THEN[Q:=s;Q^.NEXT:=NIL;] ∥第一奇数链结点。

ELSE[pre:=Q;

IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre; Q:=s; ]∥修改头指针。

ELSE[ WHILE pre^.NEXT<>NIL DO ∥查找插入位置。

IF pre^.NEXT^.DATA<s^.DATA THEN pre:=pre^.NEXT;

s^.NEXT:=pre^.NEXT;∥链入此结点。

pre^.NEXT:=s;

]

]∥结束奇数链结点

s:=r;∥s指向新的待排序结点。

]∥结束“ WHILE(s<>NIL) DO”

ENDP;∥结束整个算法。

[算法讨论]由于算法要求“不得使用NEW过程申请空间,也没明确指出链表具有头结点,所以上述算法复杂些,它可能需要在第一个结点前插入新结点,即链表的头指针会发生变化。如有头结点,算法不必单独处理在第一个结点前插入结点情况,算法会规范统一,下面的(1)是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0(DATA DIV 2=0)判断的。

类似本题的其它题解答如下:

(1)[题目分析]本题基本类似于上面第7题,不同之处有二。一是带头结点,二是分解后的两个链表,一个是数据值小于0,另一个是数据值大于0。由于没明确要求用类PASCAL书写算法,故用C书写如下。

void DisCreat1(LinkedList A)

∥A是带头结点的单链表,链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C,B中结点的数据小于零,C中结点的数据大于零。

{B=A;

C=(LinkedList )malloc( sizeof(LNode));∥为C申请结点空间。

C->next=null ∥C初始化为空表。

p=A->next; ∥p为工作指针。

B->next=null; ∥B表初始化。

while(p!=null)

{r=p->next; ∥暂存p的后继。

if (p->data<0)∥小于0的放入B表。

{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。

else {p->next=C->next; C->next=p; }

p=r;∥p指向新的待处理结点。

}

}∥算法结束。

[算法讨论]因为本题并未要求链表中结点的数据值有序,所以算法中采取最简单方式:将新结点前插到头结点后面(即第一元素之前)。

(2) 本题同上面第7题,除个别叙述不同外,本质上完全相同,故不再另作解答。

(3)[题目分析]本题中的链表有头结点,分解成表A和表B,均带头结点。分解后的A表含有原表中序号为奇数的元素,B表含有原A表中序号为偶数的元素。由于要求分解后两表中元素结点的相对顺序不变,故采用在链表尾插入比较方便,这使用一指向表尾的指针即可方便实现。

void DisCreat3(LinkedList A)

∥A是带头结点的单链表,本算法将其分解成两个带头结点的单链表,A表中含原表中序号为奇数

∥的结点,B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。

{i=0;∥i记链表中结点的序号。

B=(LinkedList)malloc( sizeof(LNode);∥创建B表表头。

B->next=null; ∥B表的初始化。

LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。

ra=A;rb=B;

p=A->next; ∥p为链表工作指针,指向待分解的结点。

A->next=null; ∥置空新的A表

while(p!=null)

{r=p->next; ∥暂存p的后继。

i++;

if(i%2==0) ∥处理原序号为偶数的链表结点。

{p->next=rb->next;∥在B表尾插入新结点;

rb->next=p; rb=p;∥rb指向新的尾结点;

}

else∥处理原序号为奇数的结点。

{p->next=ra->next; ra->next=p; ra=p; }

p=r; ∥将p恢复为指向新的待处理结点。

}∥算法结束

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

-end-

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

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

原始发表时间:2019-05-02

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    ——老子

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

    ——老子

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

    ——老子

    闫小林
  • 极客算法训练笔记(三),链表详细图解,别再逃避了朋友

    上一篇说的是数组,然后现在来说说链表。链表有个经典应用,就是实现LRU缓存淘汰算法,缓存的作用大家肯定都知道,常见的Redis缓存,CPU缓存,数据库缓存,浏览...

    阿甘的码路
  • 「优质题解」出圈

    https://www.dotcpp.com/oj/problem1160.html

    编程范 源代码公司
  • 算法-O(1)时间删除链表的指定结点

    题目:给定一个链表的头指针和一个结点的指针,定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下: struct ListNode { int v...

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

    ——老子

    闫小林
  • 数据结构—线性表

    本篇开始,又会开始一个新的系列,数据结构,数据结构在算法或者是编程中的重要性不言而喻,所以学好数据结构还是很有必要的。本篇主要介绍数据结构的第一个结构——线性表...

    张俊红
  • 2-6 链表逆序

    A -> C -> B -> D -> E -> F -> null #将上面 B后的C 插入到A后面

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

    ——老子

    闫小林

扫码关注云+社区

领取腾讯云代金券