C语言之链表

数组：方便访问，不方便插入删除
链表：不必连续，定义链表，节点定义，结构体构造，生成链表和动态机制，进行链表的三个操作（增删改）
（1）链表概述
链表是一种数据结构，它采用动态分配存储单元方式。它能够有效地节省存储空间（同数组比较）。
链表都有一个“头指针”变量（head），它用于指向链表中第一个元素（即用于存放链表中第一个元素的地址）。链表中的元素称为“结点”，链表中的所有结点都是结构体类型，且同一结点都是同一结构体类型。每个结点都应包括数据部分和下个节点的地址两部分内容。链表的最后一个元素（结点）称为链尾，它不再指向其他结点（即该结点的指针成员值为NULL）。
链表的访问都是通过指针变量从头结点开始。
由于链表中的节点是一个结构体类型，并且节点中有一个成员用于指向下一个结点。所以定义作为结点的格式：

struct 结构体名
{定义数据成员；
struct 结构体名*指针变量名；
}；
例如：
struct student
{int num；float score；
struct student *next；
}；
struct student a，*p；
//出现指向自身的指针是链表中的节点

（2）动态存储分配函数<stdlib.h>
1.malloc（）函数

格式：malloc（size）

malloc()返回值是void类型，必须进行强制类型转换！！！
作用是在内存的动态存储区中分配一个长度为size个字节的连续空间
，函数返回值为一个指向分配域起始地址的指针若分配失败则返回NULL。
例如：开辟一个用于存放struct student数据的内存空间，并让p指向该空间：

struct student*p=（struct student*）malloc（sizeof（struct student

2.free（）函数

格式：free（p）；

作用是释放用malloc（）分配的内存。
3.链表操作
（1）建立动态链表（假定若输入的成员为0则表示结束）

#include<stdlib.h>
struct node{
    int data;
    struct node *next;
};
int main() {
    struct node *head,*p=(struct node *)malloc(sizeof(struct node)),*q=(struct node *)malloc(sizeof(struct node));
    p->data=10;
    head=p;
    q->data=20;
    q->next=NULL;
    p->next=q;
    return 0;
}

（2）访问链表
求平均数

struct node{
    int data;
    struct node *next;
};
struct node *head,*p=(struct node *)malloc(sizeof(struct node));
int sum=0;
p=head;
while(p!=NULL)
{sum+=p->data;
p=p->next;
}
sum/=3;//随便敲der

（3）链表结点的删除
如：
a、请将结点b从链表中删除。
b、请将结点d从链表中删除。
c、请将结点a从链表中删除并让head重新指向链表的第一个结点。
删除中间节点：必须要拿到要删除的节点的钱一个节点的地址

q->next=p->next;free(p);
p=q->next;q->next=q->next->next;free(p);
删除头节点：p=head;head=head->next；free(p);
删除尾节点：知道尾节点前一个节点q
p=q->next;q->next=NULL;free(p)

（4）增加结点
如：
a、请将结点c插入结点之间，形成新链表
b、请将结点c插到已有链表的末尾
c、请将结点c插到已有链表的前面

在中间插入节点q后插入s：先连后改指向,s->next=q->next;q->next=s;
在头部插入节点s：s->next=head;head=s；
尾部s：s->next=NULL;q->next=s;