1、大秦帝国的连坐
孙皓晖先生在《大秦帝国（第一部）》中讲到：
烈酒下喉，卫鞅精神为之一振，“《治秦九论》乃卫鞅谋划的变法大纲。其一《田论》，立定废井田、开阡陌、田得买卖之法令……其五《郡县论》，将秦国旧世族的自治封地一律取缔，设郡县两级官府，直辖于国府之下，使全国治权一统，如臂使指。其六《连坐论》，县下设里、村、甲三级小吏。民以十户为一甲，一人犯罪，十户连坐，使民众怯于私斗犯罪而勇于公战立功。”
大秦帝国
连坐制就是一条隐形的绳子，把“乡里乡亲”们串联起来。
（连坐制确实在特定的历史条件下发挥了巨大的作用，之后一系列的制度安排又将大秦帝国拖入了深渊。）
连坐制本身就像一个链表（Linked list ），一个个的人串联起来，形成一种独特的结构。
2、链表的由来和表示
存储数据的时候我们通常用的是数组，数组最大的特点就是可以通过下标快速查找，也就是便于检索。
但对于线性表（数组和链表都属于线性表）常见的插入操作，数组就有些力不从心了。
插入操作
为了在数组中插入一个数据，需要移动后面所有的数据！
链表正是为了快速插入的问题。
链表每一个节点都由数据域和指向下一个节点的指针构成；
多个节点首尾相连，构成线性表。
链表的插入
上一节《第二节、算法中的公平——队列》我们讲到了结构体，忘记结构体的定义的同学可以出门左转，查看上一节。
这里，我们就使用结构体表示链表，struct list_node就是链表的一个节点，包含一个数据域和一个指向下一个节点的指针。
typedef struct list_node {
int data ; //数据域，用于存储数据
struct list_node *next ; //指向下一个节点的指针
}single_list;
这里的struct list_node的用法与上一节的不同，使用typedef，大括号后面也有single_list。
这样以后在定义struct list_node变量的时候就不用写一大长串了，直接single_list就可以了。
//下面两种方式等价
struct list_node node;
single_list node;
3、链表的基本用法
与此同时，为了实现便于插入数据的要求，链表的长度必须是可变的，否则可能没有空间插入！
所以，链表的初始化以及插入操作需要申请存储空间，函数为malloc()函数，用来分配存储空间。对应的有释放存储空间，使用free()函数。
由于项目运行结束后会自动回收存储空间，所以对于小项目而言，可以不手动回收，有兴趣可以搜索free()函数的用法。
下面的代码生成了一个最开始的一个节点，数据data存储的是5，因为接下来没有数据，所以next指针指向空NULL。
#include <stdlib.h> //malloc函数需要使用这个头文件
single_list *node = NULL; //1、定义头指针
node = (single_list *)malloc(sizeof(single_list)); //2、分配内存空间
node->data = 5; //3、给链表节点的数据赋值
node->next = NULL; //4、将链表的指针域指向空
初始化
我们可以printf打印数据，查看结果。
完整代码:
/*
输出：5
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct list_node
{
int data;
struct list_node *next;
}single_list;
int main()
{
single_list *node = NULL; //1、定义一个头指针
node = (single_list *)malloc(sizeof(single_list)); //2、分配内存空间
node->data = 5; //3、给链表节点的数据赋值
node->next = NULL; //4、将链表的指针域指向空
printf("%d\n", node->data);
getchar();getchar();
return 0;
}
这里我们使用了->这个运算符，叫做结构体指针运算符，用来表示结构体内部的指针指向空间存储的数据，比较拗口，看个例子就知道了。
//两者等价，省了个括号！程序员都是偷懒的！
node->data = 5;
(*node).data=5;
4、小结
这一小节介绍的新知识比较多，吃多了难以消化，所以就不介绍更多了。简单回顾下：
- 链表，就是节点连在一起
- 每一个节点包含一个数据域和指向下一个节点的指针
- 链表最大的好处是插入数据快
- 为了实现插入数据快的功能，链表长度可变，要手动分配空间
链表的插入、删除、遍历操作，我们下一节再见！
网友评论