- 链表是一种常用的数据结构，它通过指针将一些列数据结点，连接成一个数据链。相对于数组，链表具有更好的动态性（非顺序存储）。
- 数据域用来存储数据，指针域用于建立与下一个结点的联系。
- 建立链表时无需预先知道数据总量的，可以随机的分配空间，可以高效的在链表中的任意位置实时插入或删除数据。
- 链表的开销，主要是访问顺序性和组织链的空间损失。
链表的相关概念
1）有关结构体的自身引用
1 #include <stdlib.h>
2 #include <string.h>
3 #include <stdio.h>
4
5 //结构体嵌套结构体指针(√) 结构体指针的分配内存确定（32位4字节，64位8字节）
6 typedef struct Teacher
7 {
8 char name[64];
9 int id;
10 struct Teacher *teacher;
11 } teacher_t;
12
13
14 //数据类型本质：固定大小内存块的别名
15
16 //结构体中套一个结构体(X)
17 typedef struct Student
18 {
19 char name[64];
20 int id;
21 struct Student student;
22 } student_t;
23 //在自己类型大小 还没有确定的情况下 引用自己类型的元素 是不正确的
24 //结构体不能嵌套定义 （确定不了数据类型的内存大小，分配不了内存）
25
26
27 int main(void)
28 {
29 teacher_t t1;
30 student_t s1;
31
32 return 0;
33 }
2） data域和指针域
1 typedef struct node *link;
2
3 struct node {
4 unsigned char item; //data域
5 link next; //链表域
6 };
链表分类
1）动态链表和静态链表
静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。
所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。
所谓动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。
2）带头链表和不带头链表
3）单向链表、双向链表、循环链表等
链表基本操作
(1)建立带有头结点的单向链表
编写函数SList_Creat，建立带有头结点的单向链表。循环创建结点，结点数据域中的数值从键盘输入，以-1作为输入结束标志。链表的头结点地址由函数值返回。
(2)顺序访问链表中各结点的数据域
编写函数SList_Print，顺序输出单向链表各项结点数据域中的内容。
(3)在单向链表中插入节点
编写函数SList_NodeInsert，功能：在值为x的结点前，插入值为y的结点；若值为x的结点不存在，则插在表尾。
(4)删除单向链表中的结点
编写函数SList_NodeDel，删除值为x的结点。
指针函数和函数指针
(1) 指针函数（返回指针值的函数）
一个函数可以带回一个整型值、字符值、实型值等，也可以带回指针型的数据，即地址。
这种带回指针值的函数，一般定义形式为：
类型名 *函数名（参数表列）;
例如：
1 int *a(int x, int y);
(2) 函数指针（指向函数的指针）
一个函数在编译时被分配一个入口地址，这个地址就称为函数的指针，函数名代表函数的入口地址。
这一点和数组一样，因此我们可以用一个指针变量来存放这个入口地址，然后通过该指针变量调用函数。
1 int max (int x, int y);
2 int c;
3 c = max(a,b);
4 //这是通常用的方法，我们也可以定义一个函数指针，通过指针来调用这个函数。
5
6 int (*p)(int, int); //指向函数指针变量的定义形式
7 p = max; //将函数的入口地址赋给函数指针变量p
8 c = p(a,b); //调用max函数
(3) 回调函数
函数指针变量常见的用途之一是把指针作为参数传递到其他函数，指向函数的指针也可以作为参数，以实现函数地址的传递。
1. 写一个函数A,A里面有一个参数是个函数指针:
1 int funcA(int a, int (*Pcall)(int b));
2 //注意回调函数做形式参数函数名和*号要用括号搞在一起，否则 就会被返回值类型占有.
2. 有个实体函数，那他要指向一个函数B,这个函数的类型应该和A的函数参数类型一样:
int funcB(int c);
3.使用A函数把参数赋值后,A中的形参Pcall函数指针指向了一个函数funB的地址:
funcA(36,funcB);
1 #include <stdio.h>
2
3 int funcB(int b)
4 {
5 printf("in funcB:%d
", b);
6 }
7
8 int funcA(int a,int (*Pcall)(int b))
9 {
10 int PA = 3;
11 int PS = 4;
12 Pcall(a); //调用回调函数,传参数a
13 Pcall(PS); //调用回调函数,传参数PS
14 Pcall(PA); //调用回调函数,传参数PA
15 }
16
17 int main(void)
18 {
19 funcA(3, funcB); //将funcB当做参数传递给funcA
20 funcA(5, funcB);
21
22 return 0;
23 }
(4) 函数类型的别名
1 #include <stdio.h>
2
3 typedef int (*pCall)(int b); //将 int (*)(int b)类型的指针 起别名 pCall
4
5 pCall pCallA; //定义一个函数指针
6 pCall pCallB; //定义一个函数指针
7
8 int funcB(int b)
9 {
10 printf("in funcB:%d
", b);
11 }
12
13 int funcA(int a, pCallA)
14 {
15 int PA = 3;
16 int PS = 4;
17 PcallA(a); //调用回调函数,传参数a
18 PcallA(PS); //调用回调函数,传参数PS
19 PcallA(PA); //调用回调函数,传参数PA
20 }
21
22 int main(void)
23 {
24 funcA(3, funcB); //将funcB当做参数传递给funcA
25 funcB(5, funcB);
26
27 return 0;
28 }
奇葩的变量笔试题
给定以下类型的变量a的定义式：
a) 一个整型（An integer）
b) 一个指向整型的指针（A pointer to an integer）
c) 一个指向指向整型的指针（A pointer to a pointer to an integer）
d) 一个10个存放整型的数组（An array of 10 integers）
e) 一个10个存放指向整型指针的数组
（An array of 10 pointers to integers）
f) 一个指向存放10个整型数组的指针
（A pointer to an array of 10 integers）
g) 一个指向 需要一个整型参数并且返回值是一个整型函数的指针
（A pointer to a function that takes an integer as an argument and returns an integer）
h) 一个存放10个 指向 需要一个整型参数并且返回值是一个整型函数的指针的数组