1、结构的自引用
结构是可以进行自引用的，声明如下：
struct SELF_REF2
{
int a;
struct SELF_REF2 *b;
int c;
}
声明中的b是一个指向结构的指针，编译器在结构的长度确定之前就能够知道指针的长度，所以这个自引用是合法的。
那么，在一个结构的里面包含一个指向该结构本身的指针是不是很奇怪呢？事实上，指针b指向的是同一种类型的不同结构，而非同一个结构。
请警惕下面这个陷阱：
typedef struct
{
int a;
SELF_REF3 *b;
int c;
}SELF_REF3;
这个声明的目的是为这个结构创建类型名为SELF_REF3。但是它失败了，类型名直到声明的最后才被定义，所以在结构声明的内部它尚未被定义。
解决方案是定义一个结构标签来声明b，如下所示：
typedef struct SELF_REF3_TAG
{
int a;
struct SELF_REF3_TAG *b;
int c;
}SELF_REF3;
这样就没有错了。
—— 引用自《C和指针》
2、线性表的链式存储
线性表的的链式存储结构其实就是用一段任意的空间来存储线性表的元素，它们之间的逻辑关系由每个结点中存储的指针来进行关联。所以相比顺序结构而言，链式表每个结点有两个域，一个存储数据元素，称数据域；另一个则存储下一个结点的地址，称指针域。
首先来看单链表的存储结构，代码如下
/* 线性表的单链表存储结构 */
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;// 定义LinkList为指向结构体的指针
#define OK1
#define ERROR0
#define TRUE1
#define FALSE0
typedef int Status;
第二单链表的读取，具体代码如下：
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L, int i, ElemType *e)
{
int j;
LinkList p;// 声明一个指向结构体的指针p
p = L->next;// p指向L的第1个结点
j = 1;
while(p && j < i)// p不为空且计数器j还没有等于i时，循环继续
{
p = p->next;
++j;
}
if(!p || j > i)// 若前方while满足j<i，则这里就不会出现j>i；若j>i,则只能说明前面一开始就跳过了
return ERROR;// while循环，即初始时j>i，即i<1,这个位置自然不存在结点
*e = p->data;// 取第i个结点的数据
return OK;
}
算法描述：
1、声明一个指针p指向链表的第一个结点；
2、初始化变量j = 1；
3、当p不为空且计数器j还没有等于i时，遍历链表，让p指针后移，不断指向下一结点，j累加1；
4、若到链表末尾p为空，或是一开始给出的位置i不合法，报错；
5、把第i个结点的数据赋给e；
6、返回正确。
第三单链表的插入，具体代码如下
/* 操作结果：在L中第i个结点位置之前插入新的数据元素e,L的长度加1 */
Status ListInsert(LinkList *L, int i, ElemType e)// 第一个参数为“一个指向链表根指针的指针”
{
int j;
LinkList p, s;// 定义两个指向结构体的指针
p = *L;// 指向头节点
j = 1;
while(p && j < i)// 寻找第i-1个结点
{
p = p->next;
++j;
}
if(!p || j > i)
return ERROR;
s = (LinkList)malloc(sizeof(Node));// 生成新节点
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
算法描述：
1、声明一个指针p指向链表头结点；
2、初始化变量j = 1；
3、当p不为空且计数器j还没有等于i时，遍历链表，让p指针后移，不断指向下一结点，j累加1；
4、若到了链表末尾p为空或是给出的位置i不合法，则报错；
5、否则查找成功，生成新节点s；
6、把元素值e赋给s的数据域；
7、把p的指针域的值赋给s的指针域；
8、把s赋给p的指针域；
9、返回正确。
注：“LinkList”为一个“指向结构体的指针”类型，故“LinkList * L”表示L类型为“指向一个 指向结构体的指针 的指针”，所以“*L”即为一个指向结构体的指针，这里指向的结构体就是链表的头结点。而“(*L)->next”则指向链表第一个结点。
第四单链表的删除，代码如下
/* 操作结果：删除L的第i个结点，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
while(p->next && j < i)// 遍历寻找第i-1个结点
{
p = p->next;
++j;
}
if(!(p->next) || j > i)
return ERROR;// 第i个结点不存在，解释见前方
q = p->next;
p->next = q->next;
*e = q->data;
free(q);// 让系统回收此结点，释放内存
return OK;
}
算法描述：
1、定义指针p、q，其实p指向链表头结点；
2、初始化变量j = 1；
3、当p不为空且计数器j还没有等于i时，遍历链表，让p指针后移，不断指向下一结点，j累加1；
4、若到链表末尾p为空或是一开始给出的位置i不合法，则报错；
5、否则查找成功，将要删除的结点p->next赋值给q；
6、把q的指针域值赋给p的指针域；
7、把q的数据值赋给e；
8、释放q结点；
9、返回正确。
第五单链表的整表创建，具体代码如下
一、头插法
/* 操作结果：随机产生n个元素的值，建立带表头结点的单链线性表L(头插法) */
void CreateListHead(LinkList *L, int n)
{
LinkList p;// 定义指向结构体的指针p
int i;
srand(time(0));// 初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));//
(*L)->next = NULL;// 先建立一个带头结点的单链表
for(i = 0; i < n; i++)// 循环插入元素
{
p = (LinkList)malloc(sizeof(Node));// 生成新结点
p->data = rand() % 100 + 1;// 随机生成100以内的数字
p->next = (*L)->next;
(*L)->next = p;// 插入到表头
}
}
算法描述：
1、声明指针p与变量i；
2、初始化一空链表L；
3、让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
4、循环：
生成新结点p；
把数据值赋给p的数据域；
将p插入到头结点与前一新结点之间。
二、尾插法
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p, r;
int i;
srand(time(0));// 初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
r = *L;// r此时指向刚刚创建的结点
for(i = 0; i < n; i++)
{
p = (Node *)malloc(sizeof(Node));// 生成新结点
p->data = rand() % 100 + 1;// 随机生成100以内的数字
r->next = p;// 将表尾终端结点的指针指向新结点
r = p;// 将当前的新结点定义为表尾终端结点
}
r->next = NULL;// 表示当前链表结束
}
算法描述：
1、声明指针p、r，变量i；
2、初始化链表L；
3、r指向刚刚创建的结点，也是最后一个结点；
4、循环：
生成新结点并赋给p；
把新数据赋给p的数据域；
把p赋给前一个终端结点r的指针域；
r指向p，即当前链表的终端结点；
5、循环结束后，把r的指针域置空，表示已到表尾，以后遍历时可以通过这点确认其是尾部。
第六单链表的整表删除，具体代码如下
// 操作结果：将L重置为空表
Status ClearList(LinkList *L)
{
LinkList p, q;
p = (*L)->next;// p指向第一个结点
while(p)// 没到表尾
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;// 头结点指针域置空
return OK;
}
算法描述：
1、声明指针p、q，其中p指向第一个结点；
2、循环：
将p的下一结点赋值给q；
释放p；
把q赋给p；
3、循环结束后，把头结点的指针域置空；
4、返回正确。
功能验证：代码如下
void main()
{
int i;
int elem;// 用来存储元素值
int *p = &elem;
LinkList h;// 定义h为指向结构体的指针
// 创建链表
CreateListHead(&h, 5);// 取h的地址作为参数，因为h为指向结构体的指针，所以其地址就为一个指向一个结构体的指针的指针
for(i = 1; i <= 5; i++)
{
GetElem(h, i, p);// 获取元素值
printf("%d ", *p);
}
printf("\n");
// 插入元素
if( ListInsert(&h, 2, 999) )// 在第2个位置插入元素999
printf("已成功插入%d \n", 999);
for(i = 1; i <= 6; i++)
{
GetElem(h, i, p);
printf("%d ", *p);
}
printf("\n");
// 删除元素
ListDelete(&h, 3, p);
printf("已成功删除%d \n", *p);
for(i = 1; i <= 5; i++)
{
GetElem(h, i, p);
printf("%d ", *p);
}
printf("\n");
// 整表删除
if( ClearList(&h) )
printf("All delete over \n");
for(i = 1; i <= 5; i++)
{
//GetElem(h, i, p);
printf("%d ", *p);
}
}
显示如下
总结：
1、若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；若需要频繁插入和删除时，宜采用单链表结构。
2、当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不用考虑存储空间大小的问题；而如果事先知道线性表的大致长度，则用顺序结构效率会高很多。
原创作品
