数据结构-链表

1.链表

定义： 链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

链表节点分为两个域

数据域：存放各种实际的数据，如：num、score等

指针域：存放下一节点的首地址，如：next等.

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

2.链表创建

1. 创建链表（创建一个表头表示整个链表）

   //表头
   struct Node *createList()
   {
       struct Node *head = (struct Node*)malloc(sizeof (struct Node));
       //head成为了结构体变量
       head->next = NULL;
       return head;
   }
   

2. 创建结点

   //创建结点
   struct Node* createNode(int data)
   {
       struct Node *node = (struct Node*)malloc(sizeof (struct Node));
       node->data = data;
       node->next = NULL;
       return node;
   }
   

3. 插入结点

   //头部插入结点
   void insertNodeHead(struct Node *head, int data)
   {
       //创建插入的结点
       struct Node *new = createNode(data);
   
       new->next = head->next;
       head->next = new;
   }
   

4. 删除结点

   //指定位置删除
   void deleteNode(struct Node *head, int index)
   {
       struct Node *pos = head->next;
       struct Node *posFront = head;
       if (pos == NULL)
           return;     //链表为空
       while(pos ->data != index)
       {
           posFront = pos;
           pos = pos->next;
           if (pos == NULL)  //表尾
               return;
       }
       posFront->next = pos->next;
       free(pos);
   }
   

   注意：链表的每一个结点都是动态开辟(malloc)出来的，删除结点后需要释放掉。

5. 打印遍历链表

   void printList(struct Node *node)
   {
       struct Node *p = node->next;
       while(p->next != NULL)
       {
           printf("%d ", p->data);
           p = p->next;
       }
       printf("\n");
   }
   

3.测试代码

#include "stdio.h"

struct  Node
{
    int data;
    struct Node *next;
};

struct Node *createList()
{
    struct Node *head = (struct Node*)malloc(sizeof (struct Node));
    //head成为了结构体变量
    head->next = NULL;
    return head;
}

struct Node* createNode(int data)
{
    struct Node *node = (struct Node*)malloc(sizeof (struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

void printList(struct Node *node)
{
    struct Node *p = node->next;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
//头部插入节点
void insertNodeHead(struct Node *head, int data)
{
    //创建插入的节点
    struct Node *new = createNode(data);

    new->next = head->next;
    head->next = new;
}

//指定位置删除
void deleteNode(struct Node *head, int index)
{
    struct Node *pos = head->next;
    struct Node *posFront = head;
    if (pos == NULL)
        return;     //链表为空
    while(pos ->data != index)
    {
        posFront = pos;
        pos = pos->next;
        if (pos == NULL)  //表尾
            return;
    }
    posFront->next = pos->next;
    free(pos);
}

int main()
{
    struct node *list = createList();
    insertNodeHead(list,1);
    insertNodeHead(list,2);
    insertNodeHead(list,3);
    insertNodeHead(list,4);
    printList(list);
    deleteNode(list,2);
    printList(list);
    //printf("Hello World!\n");
    return 0;
}

参考来源：

【1个小时学会单链表，C语言数据结构专题】https://www.bilibili.com/video/BV1Rb411F738?vd_source=3075951c704cf80b7df7522fbb58214d

链表基础知识详解（非常详细简单易懂）-CSDN博客

建议画图理解！！！