单链表的建立 | 廖家龙的博客网站

如果给你很多个数据元素，要把它们存到一个空单链表里？

尾插法(带头结点)，时间复杂度为O(n)：将数据元素一个一个的插入到单链表的尾部

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

typedef struct LNode{  //LNode:结点
    int data;  //数据域：每个结点存放一个数据元素
    struct LNode *next;  //指针域：指针指向下一个结点
}LNode,*LinkList;  //typedef struct LNode *LinkList;  要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点

//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
    (*L)=(LNode *)malloc(sizeof(LNode));  //分配一个头结点,并使得头指针*L指向这个头结点
    if((*L) == NULL){  //内存不足，分配失败
        return false;
    }
    (*L)->data=0;  //头结点不存储数据
    (*L)->next=NULL;  //头结点之后暂时还没有结点
    return true;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList *L){
    int x;

    LNode *s,*r=*L;  //r为表尾指针
    scanf("%d\n",&x);  //输入结点的值
    
    while(x != 9999){  //输入9999表示结束
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;  //r指向新的表尾结点，永远保持r指向最后一个结点
        scanf("%d\n",&x);
    }
    r->next=NULL;  //尾结点指针置空
    return *L;
}

int main(){
    
    LinkList L;  //等价于LNode *L;  声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
    InitList(&L);  //初始化一个空表
    
    LinkList a=List_TailInsert(&L);
    
    //...后续代码
}

头插法(带头结点)：将数据元素一个一个的插入到头结点之后(逆向建立单链表)，注意是每一个数据元素都放到头结点后一个的位置

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

typedef struct LNode{  //LNode:结点
    int data;  //数据域：每个结点存放一个数据元素
    struct LNode *next;  //指针域：指针指向下一个结点
}LNode,*LinkList;  //typedef struct LNode *LinkList;  要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点

//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
    (*L)=(LNode *)malloc(sizeof(LNode));  //分配一个头结点,并使得头指针*L指向这个头结点
    if((*L) == NULL){  //内存不足，分配失败
        return false;
    }
    (*L)->data=0;  //头结点不存储数据
    (*L)->next=NULL;  //头结点之后暂时还没有结点
    return true;
}

//头插法建立单链表
LinkList List_HeadInsert(LinkList *L){
    int x;

    LNode *s;
    scanf("%d\n",&x);  //输入结点的值
    
    while(x != 9999){  //输入9999表示结束
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=(*L)->next;  //s->next指向NULL
        (*L)->next=s;  //将新结点插入表中，L为头指针
        scanf("%d\n",&x);
    }
    return *L;
}

int main(){
    
    LinkList L;  //等价于LNode *L;  声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
    InitList(&L);  //初始化一个空表
    
    LinkList a=List_HeadInsert(&L);
    
    //...后续代码
}