头歌平台——C语言之链表练习题

第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 <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关：单链表逆置 

任务描述

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

相关知识

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

头插法

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

举例：

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 <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;  
}