【C】链表

链表【重点，难点】

1. 链表结构概述

类似于火车的结构，每一个车厢之后有固定的链接方式，但是每一个车厢相互独立，可以任意组合，任意调节。

车头类型和中间的车厢不一样

车厢的相对尺寸一致，同时链接方式和其他车厢一致

车厢内部设计结构存在不同。

2. 链表结构核心数据设计

2.1 链表头结点

链表头结点主要存储链表中的相关数据和链表第一个结点，和链表最后一个结点的地址。

typedef struct linked_head
{
  	Node * first; // 链表结构中，第一个 Node 结点首地址
    Node * last;  // 链表结构中，最后一个 Node 结点首地址
    size_t size;  // 整个链表中的 Node 结点个数
} Linked_Head;

2.2 元素 Node 结点

Node 结点主要存储数据内容，和当前结点上一个 Node 地址，和下一个 Node 地址

typedef struct node
{
    struct node * prev; // 当前 Node 结点的上一个结点地址
    struct node * next; // 当前 Node 结点的下一个结点地址
    void * data;        // 当前 Node 结点中存储的数据在内存空间首地址
} Node;

01-项目目录结构

3. Student 结构体实现

student.h

#ifndef _STUDENT_
#define _STUDENT_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * student 结构体类型，利用 typedef 将当前数据类型
 * struct student 简化为 Student 类型。
 */
typedef struct student
{
    char name[32];
    int id;
    short age;
    char gender;
} Student;

/**
 * 动态内存申请空间，创建一个 Student 结构体数据所需内存，将参数中的数据赋值
 * 给结构体成员变量，同时返回值是当前结构体在内存堆区空间的首地址。【需要使用
 * malloc 或者 calloc】，后续需要【free】操作
 *
 * @param id     赋值给成员变量 id 的 int 类型实际参数
 * @param name   赋值成员变量 name 对应的 char * 字符串实际参数
 * @param age    赋值成员变量 age 对应的 short 类型数据
 * @param gender 赋值成员变量 gender 对应的 char 类型数据
 * @return 返回值类型为 Student *， 对应当前结构体在内存堆区空间的首地址.
 */
Student *create_new_student(int id, char *name, short age, char gender);

/**
 * 释放 Student 结构体在占用的内存堆区空间，需要提供 Student 结构体
 * 在内存堆区的空间首地址
 *
 * @param stu 要求进行释放操作 Student 结构体堆区内存首地址
 */
void release_student(Student *stu);

/**
 * 展示当前 Student 结构体中的数据内容，需要提供给函数的实际参数
 * 是结构体在内存堆区的空间首地址
 */
void show_student_data(Student *stu);

#endif

student.c

#include "../h/student.h"

Student *create_new_student(int id, char *name, short age, char gender)
{
    // 1. 利用 malloc 申请必要的内存空间，空间大小为 sizeof(Student)
    Student *new_student = (Student *)malloc(sizeof(Student));

    // 2. 根据参数列表对 new_student 进行成员变量赋值操作
    new_student->id = id;
    strcpy(new_student->name, name);
    new_student->age = age;
    new_student->gender = gender;

    // 3. return 返回当前 malloc 申请内存地址
    return new_student;
}

void release_student(Student *stu)
{
    // 利用 free 函数对当前使用的内存空间进行释放操作
    free(stu);
}

void show_student_data(Student *stu)
{
    printf("ID : %d, Name : %s, Age : %d, Gender : %c\n",
           stu->id, stu->name, stu->age, stu->gender);
}

main_project.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "./h/student.h"

int main(int argc, char const *argv[])
{
    Student * new_student = create_new_student(1, "James", 40, 'M');

    show_student_data(new_student);

    release_student(new_student);

    return 0;
}

4. Node 结构体实现

node.h

#ifndef _NODE_
#define _NODE_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "student.h"

/*
Node 结点结构体类型定义
*/
typedef struct node
{
    struct node *prev; // 当前结点的前一个结点
    struct node *next; // 当前结点的下一个结点
    Student *data;     // 存储的 Student 类型结构体数据内存地址
} Node;

/**
 * 创建一个 Node 结点数据，如果代码中需要提供一个 Node 结点，明确存储一个
 * Student 结构体数据，要求当前 Node 结点创建所需参数为 Student 结构体数据类型
 *
 * @param stu Student 结构体数据在内存堆区的首地址
 * @return 返回值是当前 Node 在内存堆区的首地址
 */
Node *create_new_node(Student *stu);

/**
 * 释放 Node 结点占用的内存堆区空间，需要注意，在 Node 结点
 * 中存储的有对应 Student 结构体地址，首先需要对 Student 占用
 * 的内存空间进行释放操作，之后再释放 Node 占用内存
 *
 * @param node 需要释放的 Node 结点在内存堆区空间首地址
 */
void release_node(Node *node);

/**
 * 展示当前 Node 结点中存储的 Student 数据
 * 
 * @param node 参数是需要进行展示的 Node 结点地址
 */
void show_node_data(Node *node);

#endif

node.c

#include "../h/node.h"

Node *create_new_node(Student *stu)
{   
    /*
    利用 calloc 申请内存空间，calloc 会对当前内存中所有的二进制数据进行
    初始化为 0 操作，对于当前指针相关数据，对外的数据形式为 NULL
    */
    Node * new_node = (Node *)calloc(1, sizeof(Node)); 

    /*
    将参数 Student * 赋值给 Node 中 data 存储
    */
    new_node->data = stu;    

    return new_node;
}

void release_node(Node *node)
{
    release_student(node->data);
    free(node);
}

void show_node_data(Node *node)
{
    show_student_data(node->data);
}

main_project.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "./h/student.h"
#include "./h/node.h"

int main(int argc, char const *argv[])
{
#if 0
    Student * new_student = create_new_student(1, "James", 40, 'M');

    show_student_data(new_student);

    release_student(new_student);
#endif

    Student *new_student = create_new_student(2, "昌昌", 360, 'M');
    Node *new_node = create_new_node(new_student);

    show_node_data(new_node);
    release_node(new_node);

    return 0;
}