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

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

数据结构

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

——老子

1

每日一练

1. 请写一个算法将顺序存储结构的线性表(a 1 ...a n )逆置为(a n ...a 1 )。

类似本题的另外叙述有:

(1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.

(2) 设有一个带头结点的单向链表,数据项递减有序。写一算法,重新排列链表,使数据项递增有序,要求算法时间复杂度为 O(n)。(注:用程序实现)

(3) 试编写求倒排循环链表元素的算法。

(4) 请设计算法将不带头结点的单链表就地逆置。

(5) 试编写算法 ,将不设表头结点的、不循环的单向链表就地逆转。

(6) 有一个单链表 L(至少有 1 个结点),其头结点指针为 head,编写一个过程将 L 逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。

正确答案

ps:||代表注释

1.[题目分析] 顺序存储结构的线性表的逆置,只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。

void SeqInvert(ElemType a[ ], int n)∥a是具有n个元素用一维数组存储的线性表,本算法将其逆置。

{ for(i=0;i<=(n-1)/2;i++)

{t=a[i];a[i]= a[n-1-i];a[n-1-i]=t;}

}∥算法结束

[算法讨论] 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始,第n个元素的下标是n-1。因为首尾对称交换,所以控制变量的终值是线性表长度的一半。当n为偶数,“一半”恰好是线性表长度的二分之一;若n是奇数,“一半”是小于n/2的最大整数,这时取大于1/2的最小整数的位置上的元素,恰是线性表中间位置的元素,不需要逆置。另外,由于pascal数组通常从下标1开始,所以,上下界处理上略有不同。这点请读者注意。

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

这一组又选了6个题,都是单链表(包括单循环链表)的逆置。链表逆置的通常作法是:将工作指针指向第一个元素结点,将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点,依次前插至头结点后,使最后插入的结点成为链表的第一结点,第一个插入的结点成为链表的最后结点。

(1)要求编程实现带头结点的单链表的逆置。首先建立一单链表,然后逆置。

typedef struct node

{ int data;∥假定结点数据域为整型。

struct node *next;

}node,*LinkedList;

LinkedList creat( )

{LinkedList head,p

int x;

head=(LinkedList)malloc( sizeof(node));

head->next=null; /*设置头结点*/

scanf(“%d”,&x);

while(x!=9999) /*约定输入9999时退出本函数*/

{p=(LinkedList)malloc( sizeof(node));

p->data=x;

p->next=head->next;/* 将新结点链入链表*/

head->next=p;

scanf(“%d”,&x);

}

return(head);

}∥结束creat函数。

LinkedList invert1(LinkedList head)

/*逆置单链表*/

{LinkedList p=head->next; /*p为工作指针*/

head->next=null;

while(p!=null)

{r=p->next; /*暂存p的后继*/

p->next=head->next;

head->next=p;

p=r;

}

return(head);

}/*结束invert1函数*/

main()

{LinkedList la;

la=creat( ); /*生成单链表*/

la=invert1(la);/*逆置单链表*/

}

(2)本题要求将数据项递减有序的单链表重新排序,使数据项递增有序,要求算法复杂度为O(n)。虽没说要求将链表逆置,这只是叙述不同,本质上是将单链表逆置,现编写如下:

LinkedList invert2(LinkedList la)∥la是带头结点且数据项递减有序的单链表,本算法将其排列成数据项递增有序的单链表。

{p=la->next; /*p为工作指针*/

la->next=null;

while(p!=null)

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

p->next=la->next;/*将p结点前插入头结点后。*/

la->next=p;p=r;

}

}∥结束算法

(3)本题要求倒排循环链表,与上面倒排单链表处理不同之处有二:一是初始化成循环链表而不是空链表;二是判断链表尾不用空指针而用是否是链表头指针。算法中语句片段如下:

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

la->next=la; ∥初始化成空循环链表。

while(p!=la) ∥当p=la时循环结束。

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

p->next=la->next;∥逆置

la->next=p; p=r;

}

(4)不带头结点的单链表逆置比较复杂,解决方法可以给加上头结点:

la=(LinkedList)malloc( sizeof(node));

la->next=L;

之后进行如上面(2)那样的逆置,最后再删去头结点:

L=la->next; ∥L是不带头结点的链表的指针。

free(la); ∥释放头结点。

若不增加头结点,可用如下语句片段:

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

L->next=null;∥第一结点成为尾结点。

while(p!=null)

{r=p->next;

p->next=L;∥将p结点插到L结点前面。

L=p; ∥L指向新的链表“第一”元素结点。

p=r;

}

(5)同(4),只是叙述有异。

(6)同(2),差别仅在于叙述不同。

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

-end-

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    ——老子

    C语言入门到精通
  • C语言 | 建立链表,输出各结点中的数据

    例42:C语言实现一个简单链表,它由3个学生数据的结点组成,要求输出各结点中的数据。

    C语言入门到精通
  • 数据结构 | 每日一练(21)

    ——老子

    C语言入门到精通
  • 单链表的C++实现(采用模板类)

    采用模板类实现的好处是,不用拘泥于特定的数据类型。就像活字印刷术,制定好模板,就可以批量印刷,比手抄要强多少倍! 此处不具体介绍泛型编程,还是着重叙述链表的定义...

    静默虚空
  • 数据结构—线性表

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

    张俊红
  • 数据结构 | 每日一练(61)

    ——老子

    C语言入门到精通
  • 数据结构 | 每日一练(21)

    ——老子

    C语言入门到精通
  • 【数据结构系列】双向链表

    上一篇文章中我们说到单链表,然后最后有一道习题,不知道大家有没有做出来,为了照顾一些还不太会的同学,这里专门对这道题进行一个简单的讲解,先来看看原题内容:

    wangweijun
  • 地平线余凯:自动驾驶处理器的“三国时代”| 清华人工智能研习社

    大数据文摘
  • 数据结构 第4-2讲 双向链表

    链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?

    rainchxy

扫码关注云+社区

领取腾讯云代金券