第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; 
  12. /*头插*/ 
  13. q->next=head->next; 
  14. head->next=q; 
  15. } 
  16. } 
就地逆置法
先假定有一个函数，可以将以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); 
  9. /*回溯：将当前表头结点链接到逆序链表的尾部*/ 
  10. head->next->next=head; 
  11. head->next=null; 
  13. return newHead; 
  14. } 
编程要求
  • 按程序提示输入并创建一个单链表，带有头结点；
  • 可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式；
  • 实现单链表的逆置，直观地输出结果。
效果如下： 输入：
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;}