C语言之链表练习题_c语言链表练习题

第3关：单链表逆置

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

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

头插法

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

就地逆置法

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

编程要求

• 按程序提示输入并创建一个单链表，带有头结点；

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

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

效果如下： 输入：

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>
#include <malloc.h>
typedef struct node {
    int data;
    struct node *next;
}NODE,* PNODE;
//函数声明
PNODE CreateList();
PNODE ReverseList(PNODE phead);
//CreateList函数创建链表
PNODE CreateList(){//先用尾插法创建一个链表
    //创建一个头节点
    PNODE phead=(PNODE)malloc(sizeof(NODE));
    phead->next=NULL;
 
    int len=0,i,val;
    PNODE p=phead;//p指向头指针phead
    scanf("%d",&len);//输入的链表长度len
    for(i=0;i<len;i++){
        scanf("%d",&val);
        PNODE pNew=(PNODE)malloc(sizeof(NODE));//动态分配一个新节点pNew
        p->next = pNew;
        pNew->data = val;
 
        p=pNew;
    }
    p->next=NULL;
    return phead;
}
//将单链表逆置的ReverseList函数
PNODE ReverseList(PNODE phead){
    PNODE pHEAD=(PNODE)malloc(sizeof(NODE));//新建一个头节点pHEAD,然后依次读入phead中的每一个数据，并用头插法创建一个以pHEAD为头指针的新链表
    pHEAD->next=NULL;
    PNODE p = pHEAD->next;
    int val;
    PNODE q=phead->next;//p指向头指针phead
    while(q!=NULL){
        val = q->data;
        q= q->next;
        PNODE pNew=(PNODE)malloc(sizeof(NODE));//动态分配一个新节点pNew
        pHEAD->next = pNew;
        pNew->data = val;
        pNew->next = p;
        p=pNew;
    }
    //p=pHead;
    return pHEAD;
 
}
void ShowList(PNODE phead){//遍历链表
    PNODE p = phead->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return;
}
int main(void)
{
    PNODE phead;
    phead = CreateList();
    printf("链表逆置前的数据:\n");
    ShowList(phead);
    
    phead = ReverseList(phead);
    printf("链表逆置后的数据:\n");
    ShowList(phead);
    return 0;
}

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

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

相关知识

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

编程要求

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

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

效果如下：

输入：

8

12367802

输出：

12367802

8

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct node {
    int data;
    struct node *next;
}NODE,*PNODE;
 
int length_list(PNODE phead){
    int cnt=0;
    PNODE p = phead;
    while(p->next!=NULL){
        cnt++;
        p=p->next;
    }
 
    return cnt;
 
}
PNODE CreatList(){
    //创建头节点
    PNODE phead = (PNODE)malloc(sizeof(NODE));
    phead->next = NULL;
 
    int i,len;
    scanf("%d",&len);
    PNODE p = phead;
    for(i=0;i<len;i++){
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        scanf("%d",&pNew->data);
        p->next = pNew;
        pNew->next = NULL;
        p=pNew;
    }
    return phead;
}
void ShowList(PNODE phead){
    PNODE p = phead->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return;
}
int main(void)
{
    PNODE phead;
    phead = CreatList();
    ShowList(phead);
    printf("%d", length_list(phead));
    return 0;
}

第1关：建单向链表

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

相关知识

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

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

编程要求

请仔细阅读右侧代码，根据方法内的提示，在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,* PNODE;
 
PNODE CreateList(){
    //创建一个头节点
    PNODE phead=(PNODE)malloc(sizeof(NODE));
    phead->next=NULL;
 
    int len=0,i,val;
    PNODE p=phead;//p指向头指针phead
    scanf("%d",&len);//输入的链表长度len
    for(i=0;i<len;i++){
        scanf("%d",&val);
        PNODE pNew=(PNODE)malloc(sizeof(NODE));//动态分配一个新节点pNew
        p->next = pNew;
        pNew->data = val;
        pNew->next = NULL;
        p=pNew;
    }
    //p=pHead;
    return phead;
}
 
void ShowList(PNODE phead){//遍历链表
    PNODE p = phead->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    return;
}
int main(void)
{
    PNODE phead;
    phead = CreateList();
    ShowList(phead);
    return 0;
}

如果文章对你有用的话，可不可以点一个赞鼓励我呢^o^