数据结构-链表

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博客

建议画图理解！！！