头歌平台——C语言之链表练习题
第1关：建单向链表
任务描述
本关需要你建立一个带头结点的单向链表。
相关知识
什么是链表？链表和二叉树是C语言数据结构的基础和核心。
链表有多种形式，它可以是单链接的或者双链接的，可以是已排序的或未排序的，可以是循环的或非循环的。
本关让我们来学习单链表。
单链表
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始，链表是使用指针进行构造的列表，又称为结点列表，因为链表是由一个个结点组装起来的，其中每个结点都有指针成员变量指向列表中的下一个结点。
列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。
一个简单结点的结构体表示为：
struct note{int data； /*数据成员可以是多个不同类型的数据*/struct note *next； /*指针变量成员只能是-个*/}；
让我们来看个简单的单向链表的图示：
-
链表是结构、指针相结合的一种应用,它是由头、中间、尾多个链环组成的单方向可伸缩的链表,链表上的链环我们称之为结点；
-
每个结点的数据可用一个结构体表示,该结构体由两部分成员组成：数据成员与结构指针变量成员；
-
数据成员存放用户所需数据,而结构指针变量成员则用来连接(指向)下一个结点,由于每一个结构指针变量成员都指向相同的结构体,所以该指针变量称为结构指针变量；
-
链表的长度是动态的,当需要建立一个结点,就向系统申请动态分配一个存储空间,如此不断地有新结点产生,直到结构指针变量指向为空(
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 <stdio.h>
#include <stdlib.h>
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;i<n;i++)
{
newone=(Node*)malloc(sizeof(Node));
if(T==1)
{
head=newone;
T--;
}
else end->next=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 <stdio.h>
#include <stdlib.h>
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;i<n;i++)
{
newone=(Node*)malloc(sizeof(Node));
if(T==1)
{
head=newone;
T--;
}
else end->next=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关：单链表逆置
任务描述
本关需要你设计一个程序，实现单链表的逆置。
相关知识
单链表的逆置分为两种方法：头插法和就地逆置法，这两种方法虽然都能够达到逆置的效果，但还是有着不小的差别。
头插法
逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。
举例：
void converse(LinkList *head){LinkList *p,*q;p=head->next;head->next=NULL;while(p){/*向后挪动一个位置*/q=p;p=p->next;/*头插*/q->next=head->next;head->next=q;}}
就地逆置法
先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。利用这个函数对问题进行求解：将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时，直接返回这个节点。
举例：
LinkList* converse(LinkList *head){LinkList *newHead;if(head==NULL||head->next==NULL)return head;/*递归*/newHead=converse(head->next);/*回溯：将当前表头结点链接到逆序链表的尾部*/head->next->next=head;head->next=null;return newHead;}
编程要求
-
按程序提示输入并创建一个单链表，带有头结点；
-
可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式；
-
实现单链表的逆置，直观地输出结果。
效果如下： 输入：
6 1 212 7 8 0 2
输出：
链表逆置前的数据: 1 212 7 8 0 2 链表逆置后的数据: 2 0 8 7 212 1
测试说明
平台会对您的代码进行运行测试，如果实际输出与预期输出相同，则算通关。
#include <stdio.h>
#include <stdlib.h>
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;i<n;i++)
{
newone=(Node*)malloc(sizeof(Node));
if(T==1)
{
head=newone;
T--;
}
else end->next=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;
}