C语言结构体、共用体与链表基础

用 typedef 说明一个新类型

是为已存在的数据类型起别名。

作用是为一种数据类型（基本类型或自定义数据类型）定义一个新名字，不能创建新类型。

与 #define 不同，typedef 仅限于数据类型，而不是能使表达式或具体的值。

#define 发生在预处理，typedef 发生在编译阶段。

结构体类型数据的定义和成员的引用

概述

数组：描述一组具有相同类型数据的有序集合，用于处理大量相同类型的数据运算。

有时我们需要将不同类型的数据组合成一个有机的整体，如：一个学生有学号、姓名、性别、年龄、地址等属性，显然单独定义以上变量比较繁琐，数据不便于管理。

C 语言中给出了一种构造数据类型——结构体。

struct stu { int num; char name[20]; char sex; int age; char addr[30]; } student;

结构体是一种可以有我们自己定义的数据类型。

定义结构体类型不分配存储空间。

定义结构体变量才分配存储空间。

结构体成员之间顺序存储。

直接引用（直接访问）：结构体指针->成员。

间接引用（间接访问）：结构体变量。成员 或 (*指针名).成员名。

共用体（联合体）

联合 union 是一个能在同一个存储空间存储不同类型数据的类型。

联合体所占的内存空间长度等于其最长成员的长度倍数，也有叫做共用体。

同一内存段可以用来存放几种不同类型的成员，但每一瞬时只有一种起作用。

共用体变量中起作用的成员是最后一次存放的成员，在存入一个新的成员后原有的成员的值会被覆盖。

共用体变量的值和它的各成员的地址是同一地址。

链表

链表是一种存放数据的方式。

链表中的数据，在内存可以不用连续（数组中存放的数据时连续的）。

链表是一种常见而又重要的数据结构。

链表是由一个个结点构成的，结点的存储单元是动态分配的。

每个节点包含两部分：数据和下一个节点的地址（称为数据域和指针域）。

数据域用来保存用户数据，指针域保存下一个节点的地址。

链表在指定位置插入和删除不需要移动元素，只需要修改指针即可，相对于数组查找效率低一些，多了指针空间开销。

拿到链表的第一个节点，就相当于拿到整个链表了。

头节点不保存任何数据。

动态链表结点存储空间是动态分配的，需要使用动态分配函数：malloc。

malloc 函数的原型：需要包含头文件 stdlib.h。

void *malloc(unsigned size) // 返回值为 (void*) 型指针

因为 malloc 是一个通用的内存分配函数，所以返回地址类型没有指定。

动态分配返回首地址，肯定要赋值指针。

数组与链表的区别

数组：一次性分配一块连续的存储区域。

• 优点：随机访问元素效率高。
• 缺点：
  1. 需要分配一块连续的存储空间（很大区域，有可能分配失败）。
  2. 删除和插入某个元素效率低。

链表：无需一次性分配一块连续的存储区域，只需分配 n 块节点存储区域，通过指针建立关系。

• 优点：
  1. 不需要一块连续的存储区域。
  2. 删除和插入某个元素效率高。
• 缺点：随机访问元素效率低。

链表分类

1. 静态链表、动态链表。
2. 单向链表、双向链表、单向循环链表、双向循环链表。

静态链表

#include <stdio.h>
// 链表节点类型定义
struct LinkNode {
    int data;
    struct LinkNode *next;
};

void test() {
    struct LinkNode node1 = { 10, NULL };
    struct LinkNode node2 = { 20, NULL };
    struct LinkNode node3 = { 30, NULL };
    struct LinkNode node4 = { 40, NULL };
    struct LinkNode node5 = { 50, NULL };
    struct LinkNode node6 = { 60, NULL };

    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    node5.next = &node6;

    // 如何遍历链表？
    // 先定义一个辅助指针变量
    struct LinkNode *pCurrent = &node1;
    while (pCurrent != NULL) {
        printf("%d ", pCurrent->data);
        // 指针移动到下一个元素的首地址
        pCurrent = pCurrent->next;
    }
}

动态链表

// 定义节点数据类型
struct LinkNode {
    int data;
    struct LinkNode *next;
};

// 初始化链表
struct LinkNode *Init_LinkList();

// 在值为 oldval 的位置插入新的数据 newval
void InsertByValue_LinkList(struct LinkNode *header, int oldval, int newval);

// 删除值为 val 的节点
void RemoveByValue_LinkList(struct LinkNode *header, int delValue);

// 遍历
void Foreach_LinkList(struct LinkNode *header);

// 销毁
void Destroy_LinkList(struct LinkNode *header);

// 清空
void Clear_LinkList(struct LinkNode *header);

// 初始化链表
struct LinkNode *Init_LinkList() {
    // 创建头节点
    struct LinkNode *header = malloc(sizeof(struct LinkNode));
    header->data = -1;
    header->next = NULL;

    // 尾部指针
    struct LinkNode *pRear = header;
    int val = -1;
    while(1) {
        printf("输入插入的数据：\n");
        scanf("%d", &val);
        if(val == -1) {
            break;
        }
        // 先创建新节点
        struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
        newnode->data = val;
        newnode->next = NULL;
        // 新节点插入到链表中
        pRear->next = newnode;
        pRear = newnode;
    }
    return header;
}

// 在值为 oldval 的位置插入新的数据 newval
void InsertByValue_LinkList(struct LinkNode *header, int oldval, int newval) {
    if(header == NULL) {
        return;
    }
    // 两个辅助指针变量
    struct LinkNode *pPrev = header;
    struct LinkNode *pCurrent = pPrev->next;
    while(pCurrent != NULL) {
        if(pCurrent->data == oldval) {
            break;
        }
        pPrev = pCurrent;
        pCurrent = pCurrent->next;
    }
    // 如果 pCurrent 为 NULL，说明链表中不存在值为 oldval 的节点
    if(pCurrent == NULL) {
        return;
    }
    // 先创建新节点
    struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
    newnode->data = newval;
    newnode->next = NULL;
    // 新节点插入到链表中
    newnode->next = pCurrent;
    pPrev->next = newnode;
}

// 删除值为 val 的节点
void RemoveByValue_LinkList(struct LinkNode *header, int delValue) {
    if(header == NULL) {
        return;
    }
    // 两个辅助指针变量
    struct LinkNode *pPrev = header;
    struct LinkNode *pCurrent = pPrev->next;
    while(pCurrent != NULL) {
        if(pCurrent->data == delValue) {
            break;
        }
        // 移动两个辅助指针
        pPrev = pCurrent;
        pCurrent = pCurrent->next;
    }
    if(NULL == pCurrent) {
        return;
    }
    // 重新建立待删除的节点的前驱和后继节点关系
    pPrev->next = pCurrent->next;
    // 释放删除节点内存
    free(pCurrent);
    pCurrent = NULL;
}

// 遍历
void Foreach_LinkList(struct LinkNode *header) {
    if(header == NULL) {
        return;
    }
    // 辅助指针变量
    struct LinkNode *pCurrent = header->next;
    while (pCurrent != NULL) {
        printf("%d ", pCurrent->data);
        pCurrent = pCurrent->next;
    }
}

// 销毁
void Destroy_LinkList(struct LinkNode *header) {
    if(header == NULL) {
        return;
    }
    struct LinkNode *pCurrent = header;
    while(pCurrent != NULL) {
        // 先保存下当前节点的下一个节点地址
        struct LinkNode *pNext = pCurrent->next;
        // 释放当前节点内存
        free(pCurrent);
        // 指针向后移动
        pCurrent = pNext;
    }
}

// 清空
void Clear_LinkList(struct LinkNode *header) {
    if(header == NULL) {
        return;
    }
    // 辅助指针变量
    struct LinkNode *pCurrent = header->next;
    while(pCurrent != NULL) {
        // 先保存下当前节点的下一个节点地址
        struct LinkNode *pNext = pCurrent->next;
        // 释放当前节点内存
        free(pCurrent);
        // pCurrent 指向下一个节点
        pCurrent = pNext;
    }
    header->next = NULL;
}