C语言单链表的入门学习

编程知识更新时间:2023-04-06 20:30:54

C语言单链表的创建与遍历

建立一个链表存放输入的整数。使链表中从链头至链尾的结点排列顺序正好和整数的输入顺序相同（称为先进先出链表或“队列”，即最先建立的结点为链头，最后建立的结点为链尾）。

1.创建结点的结构体类型

typedef struct _node
{
    int num;
    struct _node * next;
}node;

每一个结点包含存放的数据和指向下一结点的指针。
注：结构体本身不能含有同类型的结构，但是它可以含有指向同类型结构的指针。

2.建立一个链表
（1）声明一个头指针head，并使其具有初值NULL，再声明一个暂时保存当前新建结点存储地址的指针p，最后声明一个指向链尾的指针tail，并使其具有初值NULL。

node * head = NULL, *p, *tail = NULL;

（2）为新建的结点分配内存，并使p指向该结点。

p = (node *)malloc(sizeof(node));

（3）判断新建结点p是否为第一个结点（head是否指向NULL），是则使head指向p，否则使当前链尾结点的指针指向p（使当前链尾结点与新建结点链接，生成新的链尾）。

if (head == NULL)
    head = p;
else
    tail->next = p;

（4）将数据存入新建的结点，并使新建的结点称为链表中最后一个结点，即链尾。

p->num = n;
p->next = NULL;

（5）此时已经生成了新的链尾结点，所以使链尾结点tail指向新的链尾结点。

tail = p;

（6）重复步骤（2）到（5）直到结束。

3.遍历链表（逐个读取链表中所有结点的过程）。
（1）使遍历指针p指向链头。
（2）如果链表不为空则输出当前结点存放的数据，否则结束。
（3）每输出一个结点之后使p指向下一个结点。
（4）重复（2）到（3）直到结束。

p = head;
while (p != NULL)
{
    printf("%d ", p->num);
    p = p->next;
}

4.完整代码运行。

#include<stdio.h>
#include<stdlib.h>

typedef struct _node
{
    int num;
    struct _node * next;
}node;

int main(void)
{
    node * head = NULL, *p, *tail = NULL;
    int n;
    while(scanf("%d", &n) == 1)//当输入不为整数时结束
    {
        p = (node *)malloc(sizeof(node));
        
        if(head == NULL)
           head = p;
        else
           tail->next = p;
           
        p->num = n;
        p->next = NULL;
        tail = p;
    }
    
    p = head;
    while (p != NULL)
    {
        printf("%d ", p->num);
        p = p->next;
    }
    printf("\n");
    
    return 0;
}