我这是第二次，至于为什么有第二次，自然是第一次没有学好。第一次失败的学习中，链表就给我留下了比较深的印象。当时第一次看到链表几十行源代码的心情，我现在觉得有点幼稚。经过这第二次系统，全面的学习c语言之后，才发现链表的虚有其表。不过是个结构体的一种用法，居然唬住了我一年半
链表这个东西，按我自己现在的理解，就是以单个的结构体为基本组成单位的集合。而之所以能被叫做链表，是因为每一个组成链表的结构体中都包含有一个指针，这个指针指向当前结构体的下一个结构体。这些指针将结构体“串”成一条，就形成了链表。
介绍完我理解的链表，再来说说链表和数组的对比。同样是存放一堆数据，链表和数组相比更灵活。对链表中数据的增删改查相对数组来的更容易，更简便，具体的操作后面我会介绍。但数组并不是一无是处的，与链表相比，数组的优势在于创建数组远比创建链表简单，只需要定义出来就可以了。所以在存放一些简单的数据时，选择数组更加明智。
下面就来进行一些代码实操，认识一下链表。
#includestruct Test { int data; struct Test *next; }; int main(){ struct Test t1 = {1,NULL}; struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL}; t1.next = &t2; t2.next = &t3; printf("%d %d %dn",t1.data,t1.next->data,t1.next->next->data); return 0; }
定义一个结构体模板，里面包含一个整形变量和一个结构体指针变量。在主函数中，定义出三个结构体t1，t2，t3，并对他们进行初始化。这里要注意，在初始化结构体的时候，结构体中的结构体指针要先定义为“NULL”。如果我们直接将t1中的结构体指针指向还未定义的结构体t2，会引起报错。因此，先把所以的结构体指针全部定义为“NULL”，再在初始化完毕结构体之后统一让结构体指针指向下一个结构体的地址。一番操作之后，我们完成了一个简单链表的初始化，然后我们通过printf来验证一下。printf时要注意“.”号跟“->”的使用。
然后我们加入一点函数的知识，把这个简单的链表优化一下。
#includestruct Test { int data; struct Test *next; }; void printLink(struct Test *head) { struct Test *point; point = head; while(point != NULL){ printf("%d ",point->data); point = point->next; } putchar('n'); } int main(){ struct Test t1 = {1,NULL}; struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL}; struct Test t4 = {4,NULL}; struct Test t5 = {5,NULL}; struct Test t6 = {6,NULL}; t1.next = &t2; t2.next = &t3; t3.next = &t4; t4.next = &t5; t5.next = &t6; printLink(&t1); return 0; }
我们定义了一个printfLink函数，通过循环的方式让它输入链表中每一个结构体中的整形变量。在主函数中，我们定义了更多的结构体来组成这个链表。
初步熟悉链表之后，我们来学学链表的增删改查中的查。
查找的基本思想很简单，通过循环让链表中每一个结构体中的变量与查找的目标变量相比较。把这个功能打包成函数，可以通过返回“0”或“1”来表示查找的结果。接下来就把它实现出来。
#includestruct Test { int data; struct Test *next; }; void printLink(struct Test *head) { struct Test *point; point = head; while(point != NULL){ printf("%d ",point->data); point = point->next; } putchar('n'); } int getNumberFromLink(struct Test *heat,int data) { while(heat != NULL){ if(heat->data == data){ return 1; } heat = heat->next; } return 0; } int main(){ struct Test t1 = {1,NULL}; struct Test t2 = {2,NULL}; struct Test t3 = {3,NULL}; struct Test t4 = {4,NULL}; struct Test t5 = {5,NULL}; struct Test t6 = {6,NULL}; t1.next = &t2; t2.next = &t3; t3.next = &t4; t4.next = &t5; t5.next = &t6; printLink(&t1); int tem; tem = getNumberFromLink(&t1,3); if(tem == 1){ printf("have 3n"); }else{ printf("no 3n"); } tem = getNumberFromLink(&t1,9); if(tem == 1){ printf("have 9n"); }else{ printf("no 9n"); } return 0; }
上面我的“getNumberFromLink”就是按照循环加比较的思路来完成查找的功能的，在查找完之后，也只是简单的返回“0”或“1”。这个函数其实还有改进空间，比如可以添加scanf来实现不同需求的查找，又或者是将printf加入到函数中，直接将查找的结果在函数中输出来。我这里因为重点是将我想到的查找变量的思路实现，就不做进一步的完善。
“查”讲完了，接下来就是进一步的“改”。改的思路也比较简单，在循环查找的基础上，对找到的变量进行替换就可以了。
void insertLink(struct Test *head,int data,struct Test *pnew)
{
while(head != NULL){
if(head->data == data){
pnew->next = head->next;
head->next = pnew;
}
head = head->next;
}
}
这里我就只将“改”这一个函数进行展示，思路简单，打出来也很简单。跟“查”函数一样，我们也没有进行进一步的完善，它只要能通过查找和替换实现“改”就可以了。
搞完了“查”和“改”，是不是觉得这跟数组比不能说一模一样，也能说是十分相似。那么下面的“增”和“删”就会体现链表的好处。
“增”的方法有两种：一种叫前插法，是在目标结构体的前面增加一个结构体；还有一种就叫后插法，是在目标结构体后面增加一个结构体。先还是说一下思路，前插法的思路是先通过循环找到目标结构体，然后将目标结构体前面的那个结构体中的指针指向新的结构体，将新的结构体中的指针指向目标结构体。当目标结构体是链表头也就是第一个结构体时，就只需要将新的结构体的指针指向目标结构体就可以了。
struct Test* insertLinkBefore(struct Test *head,int data,struct Test *new)
{
struct Test *p = head;
if(p->data == data){
new->next = head;
return new;
}
while(p->next != NULL){
if(p->next->data == data){
new->next = p->next;
p->next = new;
printf("insert Yesn");
return head;
}p = p->next;
}printf("insert Non");
return head;
}
这里要实现“增”函数推荐使用指针函数，返回进行“增”之后的链表头。这里要注意定义一个结构体指针来保存传递进来的链表头地址，因为在后面“增”的操作中，肯定是会发生指针偏移的，提前保存一个以便最后的返回。
前插法达成后，来了解一下后插法。后插法的思路是通过循环找到目标结构体，将目标结构体中的指针指向新结构体，再将新结构体中的指针指向目标结构体后面的那个结构体。
void insertLinkBehind(struct Test *head,int data,struct Test *pnew)
{
while(head != NULL){
if(head->data == data){
pnew->next = head->next;
head->next = pnew;
}
head = head->next;
}
}
后插法因为是在目标结构体的后面增加新结构体，所以新结构体不会作为链表头，就不用想前插法那样额外加一条if判断。
“增”实现了之后，就剩下“删”了。删除链表中的目标结构体的思路也是比较简单的：循环查找到目标变量，将目标结构体前面那个结构体中的指针指向目标结构体后面的结构体，并将目标结构体所占用的空间释放掉（如果还有其他用处则可以将目标结构体的地址用指针保留下来）。然后我们用代码实现一下。
struct Test* deleteLink(struct Test *head,int data)
{
struct Test *p = head;
if(head->data == data){
head = head->next;
free(p);
return head;
}
while(p->next != NULL){
if(p->next->data == data){
struct Test *tem = p->next;
p->next = p->next->next;
free(tem);
return head;
}
p = p->next;
}
return head;
}
”删“的时候要注意一下，如果目标结构体是链表头，那么只需要将它释放掉并将表示链表头的指针指向第二个结构体就可以了。在函数的最开始还是要定义一个结构体指针来备份链表头地址，以便后面的返回。
学会了链表的增删改查，就差不多掌握链表了。至于更深一步的动态创建链表，增删改查的优化等等我这里就不多介绍了，有思路有基础，想要实现都是很简单的。
