链表

对于确定长度的同类型数据，之前学习了如何用数组存储。对于长度不确定的、经常要改变的数据，我们则会选择构造一个被称为 链表（linked list） 的结构。

链表

链表由一系列存储了数据的节点和他们之间的指向关系构成。从第一个节点（链表头）开始，每一个节点都会指向下一个节点，直到链表末端的一个节点为止。

C 语言通常会定义一个结构体，来对链表节点进行实现。在这结构体中，有一系列数据，同时还有一个指向这一结构体类型的指针。

在这种定义下，我们就可以通过将第二个节点的地址保存在第一个节点的指针变量中的方式实现节点之间的指向了。

相对于数组来说，链表有一定的优势和劣势。

• 优势

存储的元素数不固定，数据结构所需的内存空间无需一开始就说明。
只要改变指针指向就可以动态地在两个节点之间插入数据。

• 劣势

在内存中不连续，查询效率没有数组高，需要从链表头开始沿着指针方向依次访问每一个节点才能到达目标节点。

通过链表节点构造一个链表

在这里，我们没有太深入地对链表进行操作，但是可以想一下如果我们要删除一个节点、插入一个节点分别应该怎么办。

删除一个节点，我们需要从head开始，沿着->next逐一地到达目标节点。将目标节点的前一节点的->next改为目标节点当前的->next内保存的值。使用free将目标节点对应的内存空间释放。

插入一个节点则需要创建一个新的节点，将链表目标位置前的一个节点的->next修改为新的节点的地址，并将新的节点的->next插入目标位置前的一个节点的原->next取值。

值得注意的是，在这一课的代码中，我们在堆区内存上开了空间，但是没有释放。从内存安全的角度出发，我们应该还要在链表被使用完毕后释放所有开辟给链表节点的堆区上内存喔。

如果我们将链表的头尾相连，我们还可以得到一个环形的链表，被称为“循环链表”。

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} Node;

链表的性质（判断）：

image.png

问题：约瑟夫环

学习链表结构后，需要用链表解决一个稍有改动的“约瑟夫环（Josephus problem）”问题：
有N个同学围成一圈，顺序编号（分别为 1,2,3...n），从编号为 K的人开始报 1，他之后（顺初始数字增长方向计算序号）的人报 2，数到某个数字 M 的人出列。出列同学的下一人又从 1继续报，数到某个数 M 的人出列。重复直到所有人出列。

现需要根据同学人数 N和给出的 K 和 M 计算出同学的正确出列顺序。

• 输入格式
  输入为一行，包括三个被空格分隔开的符合描述的正整数 N、K和 M
  （1≤K≤N≤1000，1≤M≤2000）。
• 输出格式
  输出为一行，包含 N个整数，为依次顺序出列的学生编号，由空格分隔开。

样例输入1

9 1 1

样例输出1

1 2 3 4 5 6 7 8 9

样例输入2

8 5 2

样例输出2

6 8 2 4 7 3 1 5

思路：在删除循环链表节点的过程中，一般是先设置临时指针，然后对临时指针循环一圈，让 临时指针 在 当前的头指针 的前面，具体原理：链表修改的原理，临时指针的next越过下节点，指向下下节点。同时将删除的节点元素的内存释放出来。
遇到的坑主要有置空以后又引用，引起的段错误。
代码如下：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int data;
    struct node *next;
} Node;                //构造链表结构体

Node *circle_create(int n);  //创建环的函数
void count_off(Node *head, int n, int k, int m);  //约瑟夫环出列函数

int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    Node *head = circle_create(n);
    count_off(head, n, k, m);
    return 0;
}

Node *circle_create(int n) {
    Node *temp, *new_node, *head;
    int i;

    // 创建第一个链表节点并加数据
    temp = (Node *) malloc(sizeof(Node));  //临时申请空间
    head = temp;                                          //申请到的空间赋给头元素
    head->data = 1;

    // 创建第 2 到第 n 个链表节点并加数据
    for(i = 2; i <= n; i++) {              //”创指针“不断开辟新空间，利用temp指针进行跟随
        new_node = (Node *) malloc(sizeof(Node));   //”创指针“申请临时空间
        new_node->data = i;              
        temp->next = new_node;                      //临时节点节点指向”创指针“
        temp = new_node;                                //”创指针“赋给临时节点
    }

    // 最后一个节点指向头部构成循环链表
    temp->next = head;
    return head;
}

void count_off(Node *head, int n, int k, int m) {
Node *temp;
    temp = head;
    int i = 1;
    while(i<=n){
        temp = head;
        head = head->next;
        i++;         
    }                                            //置temp到head前一位
    i = 1;
    while(i<k){
        temp = head;
        head = head->next;
        i++;
    }                                        //head移到k号位置，temp移到k-1号位
    i = 1;
    while (1){
        while(i< m){
            temp = head;
            head = head->next;           //报m号，m号为head，temp则在head前一位
            i++;
        }
        i = 1;
        if (temp!= head){
            printf("%d ",head->data);                //输出m号，即head节点内容
            temp->next = head->next;              //这里把temp指向下下个节点
            free(head);                                      //输出完了释放head的内存
            head = temp->next;                       //现在head就得是刚才head的下一位了
        }else {
            printf("%d",head->data);
            free(head);
            break;                               //实际上还应该置野指针为NULL
        }
    }
    return;
}

共用体

它看起来和结构体很像的东西，称为 共用体（union）。
结构体特性解决了一系列不同类型的变量可以怎么被放在一起组织的问题；
而共用体，则使多种不会同时出现的变量共用同一块内存，十分方便。

共用体初始化：

定义共用体的关键字是union，一个共用体可以包括多个合法的类型描述成员，例如：

union register {
    struct {
        unsigned char byte1;
        unsigned char byte2;
        unsigned char byte3;
        unsigned char byte4;
    } bytes;
    unsigned int number;
};

这共用体所占用的内存空间是被公用的，可通过struct类型的bytes和unsigned int类型的number两种不同的类型描述成员进行访问。

无论我们通过哪一种描述成员访问这一共用体，我们访问的都会是同一块内存空间。

image.png

如果用这个union register类型声明一个变量reg。我们将可以通过reg.bytes按字节访问或者通过reg.number整体访问两种不同的方式获得或修改同一片内存。

共用体在涉及到直接操作内存的嵌入式编程、需要极度节省空间的通信协议设计中都会有它的优势。

在之前的内容中，我们看到了一种通过共用体实现的可以整体修改，也可以按字节修改的类型。类似的，我们也可以定义一个既可以按位访问，也可以按字节访问的类型：

union {
    struct {
        unsigned char b1:1;
        unsigned char b2:1;
        unsigned char b3:1;
        unsigned char b4:1;
        unsigned char reserved:4;
    } bits;
    unsigned char byte;
}

这里有一个冒号是用来定义变量使用内存的“位长”的。这里:1、:4表示冒号前的变量只需要占 1 个和 4 个二进制位，而不按照char类型默认的字节数占用内存。这样，用这个类型生成的变量就可以被我们就按字节或者按位进行访问和使用了（这个概念被称为 位域（bit field），在其它场景下也可以被使用）。

再举一个被设计出来专门储存IP地址的共用体结构。使用了它的变量，既可以存储 IPv4 的 IP 地址，也可以存储 IPv6 的 IP 地址，这些地址既可以作为一个整体被操作，也可以分几个部分分别操作。

union {
    // IPv4 地址
    union {
        struct {
            unsigned char _reserved[12];
            unsigned char _ip_bytes[4];
        } _raw;
        struct {
            unsigned char _reserved[12];
            unsigned char _o1;
            unsigned char _o2;
            unsigned char _o3;
            unsigned char _o4;    
        } _octet;    
    } _IPv4;

    // IPv6 地址
    union {
        struct {
            unsigned char _IpBytes[16];
        } _raw;
        struct {
            unsigned short _w1;
            unsigned short _w2;
            unsigned short _w3;
            unsigned short _w4;
            unsigned short _w5;
            unsigned short _w6;
            unsigned short _w7;
            unsigned short _w8;   
        } _word;
    } _IPv6;
} _IP;

共用体其实也可以被视为一种特殊的结构体，但是一般的结构体中的成员会在内存中对齐排列（如果你对这块有兴趣可以在互联网上通过搜索多了解一些，我们在这里不做过多介绍），而共用体则都选择以同一位置作为起点，共用同一开始地址的内存。

• 共用体类型的变量占用内存的大小将会和他所有成员中占用内存的最大的一致。
• 类型别名在共用体类型上的使用方式与在其他类型上相同,没有区别。
• 和其他类型一样,共用体类型也可以被用于结构体类型定义。
• 和其他类型一样,共用体类型也可以被用于结构体类型定义。

验证共用体类型的变量取出的内存地址是不是完全一致

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

typedef union type_x {
    char a;
    int b;
    float c;
} Type_x;

typedef struct type_y {
    char a;
    int b;
    float c;
} Type_y;

int main() {
    Type_x x;
    Type_y y;
    printf("%p %p %p\n", &(x.a),&(x.b),&(x.c));
    printf("%p %p %p\n", &(y.a),&(y.b),&(y.c));
    return 0;
}

可能的运行结果：

0x7ffd44294e40 0x7ffd44294e40 0x7ffd44294e40                                  
0x7ffd44294e50 0x7ffd44294e54 0x7ffd44294e58 

枚举

C 语言提供了一种数据类型叫 枚举（enumeration）。由一系列整数成员组成，表示这一数据类型的变量可以取的所有可能值；但这些值都不直接以字面量形式存在，每一个值都被单独给予了一个名字。例如：

enum week {
SUNDAY,
MONDAY,
TUESDAY,
WEDNESDAY,
THURSDAY,
FRIDAY,
SATURDAY
};
这种方式定义了一个与周相关的枚举类型，其中每一个成员都会对应一个编号。

• 当像上面例子这样没有对它们进行显性的编号时，系统默认编号会从 0开始。也就是如果直接使用SUNDAY，将和使用0一样，而使用MONDAY则会相当于使用了1，依此类推。

• 也可以给枚举类型成员进行显性的编号。如果我们给SUNDAY编号为1

enum week {
    SUNDAY = 1,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
};

我们使用MONDAY则会相当于使用了2，每一个成员都比之前编号多1

• 也可以给多个枚举类型成员进行显性的编号。

enum week {
    SUNDAY = 1,
    MONDAY,
    TUESDAY,
    WEDNESDAY = 1,
    THURSDAY,
    FRIDAY,
    SATURDAY
};

当将SUNDAY和WEDNESDAY都编号为1的时候，使用MONDAY或者使用THURSDAY则都会相当于使用了2。

不难发现， 其实可以对任何一个枚举成员进行显性的编号，那么：
没有显性编号的其他成员的编号将从它之前一个显性编号的成员开始计算，按顺序依次加一获得。

当一个枚举类型被定义以后，我们可以直接用这一类型声明变量。如：

enum week {
    SUNDAY,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
};
enum week exam_date;

声明了一个enum week类型的变量exam_date，它只能取定义过的枚举类型中的成员名作为值，如exam_date = TUESDAY;。

与struct、union以及其它类型一样，我们也可以给枚举类型通过typedef设置类型别名。

输出枚举类型举例：

#include <stdio.h>
typedef enum week {
    SUNDAY,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
} Week;
int main() {
    Week meeting_date;
    meeting_date = FRIDAY;
    printf("%d\n", meeting_date);
    return 0;
}

• 枚举类型中成员的编号只能是整数。