第1关:建单向链表

任务描述

本关需要你建立一个带头结点的单向链表。

相关知识

什么是链表?链表和二叉树是C语言数据结构的基础和核心。

链表有多种形式,它可以是单链接的或者双链接的,可以是已排序的或未排序的,可以是循环的或非循环的。

本关让我们来学习单链表。

单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始,链表是使用指针进行构造的列表,又称为结点列表,因为链表是由一个个结点组装起来的,其中每个结点都有指针成员变量指向列表中的下一个结点。

列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。

一个简单结点的结构体表示为:

  1. struct note
  2. {
  3. int data; /*数据成员可以是多个不同类型的数据*/
  4. struct note *next; /*指针变量成员只能是-个*/
  5. };

让我们来看个简单的单向链表的图示:

  • 链表是结构、指针相结合的一种应用,它是由头、中间、尾多个链环组成的单方向可伸缩的链表,链表上的链环我们称之为结点;

  • 每个结点的数据可用一个结构体表示,该结构体由两部分成员组成:数据成员与结构指针变量成员;

  • 数据成员存放用户所需数据,而结构指针变量成员则用来连接(指向)下一个结点,由于每一个结构指针变量成员都指向相同的结构体,所以该指针变量称为结构指针变量;

  • 链表的长度是动态的,当需要建立一个结点,就向系统申请动态分配一个存储空间,如此不断地有新结点产生,直到结构指针变量指向为空(NULL)。

申请动态分配一个存储空间的表示形式为:

(struct note*)malloc(sizeof(struct note))

链表的建立

在链表建立过程中,首先要建立第一个结点,然后不断地在其尾部增加新结点,直到不需再有新结点,即尾指针指向NULL为止。

设有结构指针变量。

struct note *p,*p1,*head;

head:用来标志链表头;

p:在链表建立过程中,p总是不断先接受系统动态分配的新结点地址。

p1->next:存储新结点的地址。

编程要求

请仔细阅读右侧代码,根据方法内的提示,在Begin - End区域内进行代码补充,具体任务如下:

键盘输入一组元素,建立一个带头结点的单向链表(无序)。

要求:

  • 输入整数的长度以及整数;

  • 输出无序的单向链表。

效果如下:

输入: 5 1 23 4 8 9 输出:1 23 4 8 9

测试说明

平台会对您的代码进行运行测试,如果实际输出与预期输出相同,则算通关。

#include #include typedef struct node {int data;struct node *next;}Node; // 请在此添加你的代码/********** Begin **********/Node *CreatList(){Node *head,*newone,*end;int n;int i;int T=1;scanf("%d",&n);for(i=0;inext=newone;end=newone;end->next=NULL;scanf("%d",&end->data);}return head;}void ShowList(Node *head){Node *end=head;for(;end!=NULL;end=end->next){printf("%d ",end->data);}}/**********End**********/int main(void){Node *phead; phead = CreatList();ShowList(phead);return 0;}

第2关:统计单链表中的节点数

任务描述

本小节需要你统计单链表中的节点数。

相关知识

根据上一关我们知道怎么创建单链表了,那么这一关让我们巩固一下单链表的知识。

编程要求

请仔细阅读右侧代码,根据方法内的提示,在Begin - End区域内进行代码补充,具体任务如下:

编写程序,从键盘输入一串整数以及整数的个数,以单链表形式存储起来,计算单链表中结点的个数,输出单链表的数据及结点的个数。

效果如下: 输入: 8 12367802

输出: 12367802 8

测试说明

平台会对您的代码进行运行测试,如果实际输出与预期输出相同,则算通关。

#include #include typedef struct node {int data;struct node *next;}Node; // 请在此添加你的代码/********** Begin *********/Node *CreatList(){Node *head,*newone,*end;int n;int i;int T=1;scanf("%d",&n);for(i=0;inext=newone;end=newone;end->next=NULL;scanf("%d",&end->data);}return head;}void ShowList(Node *head){Node *end=head;for(;end!=NULL;end=end->next){printf("%d ",end->data);}printf("\n");}int Length(Node *phead){int a=0;for(;phead!=NULL;phead=phead->next){a=a+1;}return a;}/**********End**********/int main(void){Node *phead; phead = CreatList();ShowList(phead);printf("%d", Length(phead));return 0;}

第3关:单链表逆置

任务描述

本关需要你设计一个程序,实现单链表的逆置。

相关知识

单链表的逆置分为两种方法:头插法和就地逆置法,这两种方法虽然都能够达到逆置的效果,但还是有着不小的差别。

头插法

逆置链表初始为空,表中节点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空。

举例:

  1. void converse(LinkList *head)
  2. {
  3. LinkList *p,*q;
  4. p=head->next;
  5. head->next=NULL;
  6. while(p)
  7. {
  8. /*向后挪动一个位置*/
  9. q=p;
  10. p=p->next;
  11. /*头插*/
  12. q->next=head->next;
  13. head->next=q;
  14. }
  15. }

就地逆置法

先假定有一个函数,可以将以head为头结点的单链表逆序,并返回新的头结点。利用这个函数对问题进行求解:将链表分为当前表头结点和其余部分,递归的过程就是,先将表头结点从链表中拆出来,然后对其余部分进行逆序,最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时,直接返回这个节点。

举例:

  1. LinkList* converse(LinkList *head)
  2. {
  3. LinkList *newHead;
  4. if(head==NULL||head->next==NULL)
  5. return head;
  6. /*递归*/
  7. newHead=converse(head->next);
  8. /*回溯:将当前表头结点链接到逆序链表的尾部*/
  9. head->next->next=head;
  10. head->next=null;
  11. return newHead;
  12. }
编程要求
  • 按程序提示输入并创建一个单链表,带有头结点;

  • 可自定义链表的长度,可自定义链表储存的数据类型,注意更改相应的输入输出方式;

  • 实现单链表的逆置,直观地输出结果。

效果如下: 输入:

6 1 212 7 8 0 2

输出:

链表逆置前的数据: 1 212 7 8 0 2 链表逆置后的数据: 2 0 8 7 212 1

测试说明

平台会对您的代码进行运行测试,如果实际输出与预期输出相同,则算通关。

#include #include typedef struct node {int data;struct node *next;}Node; // 请在此添加你的代码/********** Begin *********/Node *CreatList(){Node *head,*newone,*end;int n;int i;int T=1;scanf("%d",&n);for(i=0;inext=newone;end=newone;end->next=NULL;scanf("%d",&end->data);}return head;}void ShowList(Node *head){Node *end=head;for(;end!=NULL;end=end->next){printf("%d ",end->data);}printf("\n");}Node *ReverseList(Node *head){Node *newhead;if(head==NULL||head->next==NULL)return head;newhead=ReverseList(head->next);head->next->next=head;head->next=NULL;return newhead;}/**********End**********/int main(void){Node *phead;phead = CreatList();printf("链表逆置前的数据:\n");ShowList(phead);phead = ReverseList(phead);printf("链表逆置后的数据:\n");ShowList(phead);return 0;}