尾插法建立链表详解

尾插法建立链表详解

引用

CSDN

1.

https://blog.csdn.net/qq_40741513/article/details/107243817

尾插法，顾名思义，就是把新加入的节点插入到上一个节点的尾部（头插法是把新加入的节点插入到上一个节点的头部），next存储下一个节点位置的地址，开始时，初始化定义头节点

head -> next = NULL;  

表示头节点的下一个节点为空，就是该链表只有一个头节点，图形化表示为

由于头插法要把每一个新加入的节点插入到上一个节点的尾部，所以需要定义一个指针，记录每次插入变换后的最后一个节点的指针域信息

r = head;

将头节点赋值给r,r记录每次插入变换后尾部的信息

申请一个节点A1,将A1按照尾插法插入到链表当中，实现代码为

r -> next = p;
r = p;  

第一句代码 r -> next = p的意思是将 r (当前还是代表头节点的地址)的下一个节点指向p,图像表示形式为

第二句代码 r = p的意思是将原本表示头部节点地址的指针赋值为新插入的A1,也就是说 r 当前表示为节点A1

当插入节点A2时，依然执行这两行代码，由于r是上一个新插入的节点，所以A2插入到了A1的尾部

插入后同样将r赋值给当前插入节点的地址

不断地执行上述过程，把新来的节点插入到上一个尾部，把最后一个节点的next值赋为空，实现尾插法代码的实现

完整代码如下

#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
//结构体的定义
struct LNode{
    Elemtype data;//数据域，存储数据
    struct LNode *next;//指针域，存储指针,存放后继节点信息
};
typedef struct LNode* LNodePtr;//定义结构体指针型变量，将结构体指针等价于Linklist
typedef struct LNode LNode1;
//尾插法建立链表
LNodePtr CreateListTail(int n){
    struct LNode l1;
    LNodePtr p;
    LNodePtr r;
    int i;
    struct LNode* L = (struct LNode*)malloc(sizeof(struct LNode));
    L->next = NULL;
    L->data = 0;
    r = L;
    for(i = 0; i < n; i ++){
        p = (struct LNode*)malloc(sizeof(struct LNode));//每次动态申请一个结构体空间存储
        p->data = i;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return L;
}
//链表的遍历输出
void TraverseList(LNodePtr L){
    LNodePtr p, q;
    p = L;//将头指针赋值给p
    while(p->next != NULL){
        q = p->next;
        printf("%d\n", q->data);
        p = p->next;
    }
}
int main()
{
    LNodePtr l1 = CreateListTail(5);
    TraverseList(l1);
    return 0;
}