目录

  链表概述

  链表，别名链式存储结构或单链表js创建节点，用于存储逻辑关系为 一对一的 同类型 的数据。 与顺序表不同，链表不限制数据的物理存储状态，物理存储空间可以不连续。换句话说，链表存储的数据元素，其物理存储位置是随机的分散的，由其指针域指向后续节点的地址来连接形成线性表的一种存储方式，像用链子把不同的物体连接在一起一样。

  链表创建

  链表一般为单链表，由于需要同时记录数据和地址，故需要用到结构体来进行链表节点的数据类型定义。

  节点的定义

   //节点的定义

    struct Node{
        int data;    //数据域
        struct Node *next;    //指针域
    };
    //struct 关键词

  此时我们已经定义了数据类型，此类型用于创建链表的节点使用。

  头节点的创建

   //主函数

    int main(){
        
        //定义节点类型的指针head，申请节点类型的空间大小，用作头节点。
        struct Node *head = (struct Node *)malloc(sizeof(struct Node));
        //此时只存在头节点，所以他的指针域指向为空。
        head->next = NULL;
        
        return 0;

  头节点数据域大部分情况下不做数据的存储，故不向其数据域存储内容。

  后续节点的创建并连接形成链表——头插法

   //创建链表————头插法

    void fun(struct Node *head) {
        
        //传参传的是头节点的地址，所以用指针接收地址
        if(head == NULL){
            printf("头指针未指向头节点");
            return;
        }
        
        printf("请输入链表长度");
        int len;
        scanf("%d",&len);
        //指针p指向头节点
        struct Node *p=head;
        struct Node *q;//临时节点
        for(int i=0; idata);
            q->next=p->next;//新节点q指向p的地址
            p->next=q;//p指向q
        }

  创建的新节点连接在头节点后一个位置

  导致链表内容被倒置

  如 录入数据域内容： 1 2 3 4 5

  输出数据域内容： 5 4 3 2 1

  后续节点的创建并连接形成链表——尾插法

   //创建链表————尾插法

    void fun2(struct Node *head) {
        
        //传参传的是头节点的地址，所以用指针接收地址
        if(head == NULL){
            printf("头指针未指向头节点");
            return;
        }
        
        //指针p指向头节点
        struct Node *p=head;
        struct Node *q;//临时节点
        
        printf("请输入链表长度");
        int len;
        scanf("%d",&len);
        for(int i=0; idata);
            q->next=NULL;//新节点q指针域指向空
            p->next=q;//p指向新节点q
            p=q;//p位置更新到q位置
        }

  创建的新节点永远在链表的最后一位

  输入顺序就是输出顺序

  如 录入数据域内容： 1 2 3 4 5

  输出数据域内容： 1 2 3 4 5

  链表的遍历——输出链表数据域内容

   //遍历链表

    void shuchu(struct Node *head) {
        
        //传参传的是头节点的地址，所以用指针接收地址
        if(head == NULL){
            printf("头指针未指向头节点");
            return;
        }
        struct Node *p=head->next;    //结构体指针指向头节点的第一个节点
        //指针不为空进行循环
        while(p) {    //等价于 p != NULL;
            printf("%d  ",p->data);    //输出数据域内容
            p=p->next;    //指针后移指向下一个节点
        }

  由于头节点的数据域不进行内容存储

  故指针p直接指向头节点的下一个节点js创建节点，即首元节点

  2023年3月20日

  持续更新