学习笔记——C语言基本概念&链表——（12）

在介绍链表之前先介绍一下数据结构的分类：

线性结构：数组，链表，栈，队列

顺序结构：数组

链式结构：链表

非线性结构：树，二叉树

1、链表

特点：利用碎片化空间。

链表组成：由节点组成

节点组成：

数据域--真正要存放的数据

指针域--下一个节点的地址

节点的定义：

第一种： 直接定义

struct NODE
{
    char name[32];
    int id;
    float score;
    struct NODE *addr； //下一个节点的地址
}；

第二种：
先定义数据域， 再定义节点

//定义数据域
struct Stu
{
    char name[32];
    int id;
    float score;
}；
//定义指针域
struct NODE
{
    struct Stu stu； //数据域
    struct NODE *addr;//指针域， 下一个节点的地址
}

回顾一下指针的定义：

1>int *p = NULL；
2>int num = 100; int *p=#
3>char buf[32]={0}; char *p=buf;
4>char *p = “hello”;

由链表的引入又有了新的指针定义：
1》 malloc函数 -- 开辟空间

头文件：#include <stdlib.h>

void *malloc(size_t size);
形参： size -- 要开辟空间的大小
返回值：
成功： 返回开辟好的空间的首地址， void * -- 万能指针， 可以随意的强转为你想要的
类型
失败： NULL
int *p = (int *)malloc(sizeof(int));

2》 void free(void *ptr);
        形参： 要释放的空间的首地址；
        返回值： void -- 无返

3》 memset -- 内存清理函数
        #include <string.h>
        void *memset(void *s, int c, size_t n);
        形参： s -- 你要清理的空间的首地址
        c -- 0
        n -- 清多大， sizeof
        返回值： 就是第一个参数

2、双向链表

组成：节点--数据域和指针域（存放上一个和下一个节点的地址）

定义格式：

struct Stu
{
    char name[32];
    int id;
    float score;
}；
struct NODE
{
    struct Stu stu； //数据域
    struct NODE *front； //指针域， 上一个节点的地址
    struct NODE *next; //指针域， 下一个节点的地址
}

图示：

循环链表：
单向循环
双向循环