创建查找删除功能的单向链表

在文章最后我会附上源代码。

数组一旦确立以后，在运行时我们无法改变它的大小（C99中可以用变量来确定数组大小），假如我们的程序一开始不知道要存放多少数据，一种很无奈的办法就是一开始把数组定义的很大，但是这样有可能会浪费内存，还有可能在程序运行时才发现，数组定义的还不够大，不足以容纳数据，这就很麻烦。解决的方法我们可以用链表。

什么是链表？

链表是由有多个带着数据的结点离散分配而成，结点由两部分组成，一部分数据域，用来存数据，另一部分是指针域，用来指向下一个结点。

我们先来看下，结点的定义：

这是链表的结构，我们把它定义成一个结构体，里面有两个结构成员，一个是int类型的data，用来存放数据。一个是struct _node类型的指针*next，用来指向下一个结点。

在开始写一个链表程序前，我们先来了解，看下链表具体包含什么：

我们知道一个结点分为两部分，一个是数据，一个是指针。在链表的最后一个结点我们要把它的指针指向NULL。我们还需要一个指针指向第一个结点的“头”（head）。来表示一个链表。

接下来我们看一下程序怎么写，我们先试着写出一个链表的代码，最后再把它放到自己定义的函数里面去。第一步我们要往这个链表里输入数据，比如我们要往程序里读入很多数字，直到输入-1为止结束：

程序可以这么写，用一个do-while循环，里面每次输入一个数，条件当number=-1时就退出。

在每次读到这个数字后，我们要把它加到结构体里的data中去，也就是链表中的某个结点中去。接下来程序要这么写：

在第11行我们定义一个Node *head=NULL，作为链表的头。接下来在函数中我们要做出一个node的结构体出来，因为每输入一个数我们就要做一个Node的结构体来存放它，所以在程序第16行我们定义一个Node *p指针，指向用malloc的方式申请一块内存，之后第17行我们把指针P所指东西做个初始化，p所指的data指向输入的number，把P所指的那个指针next指向NULL，作为一个结点。接下来，当我们输入下一个数时，就要把这个新结点接上去。怎么做？这里先说一个要注意的小细节：作为链表的开始，第一次第一个结点我们要怎么处理？

我们现在要做的事情是说，因为每输入一个数据，作为一个结点，我们都要把这个新结点放到链表的最后，所以每次我们都要找到最后那个结点，然后把新结点接上去。我们可以这样做：就是让这个Node *last从head开始，从头开始，遍历，找出最后一个结点。while（last->next），也就是这个last所指的next是有东西的话，那就说它不是最后一个结点，然后进循环里，做last=last->next；一直到最后知道last->next等于NULL了，就证明这个结点是链表的最后一个结点，我们就把last->next=p，把这个结点接上去。我们先根据思路看下代码可不可以写成这样：

不过代码这样写其实是错的，错在漏了一些东西。我们要看第19行，第一次我们把Node *last=head，这样last->next=NULL，这是错的，这样是无法进入while循环，因为这个while循环while（last->next）只有当last所指的next有东西时才会循环。所以在这前面我们应该加点东西：

第20行用个if做个判断，当last不等于0，才做while循环里的东西，这是为了针对链表第一个结点的情况，看第25行else，如果last=NULL，就应该把p赋值给head，这样从第二次开始，每次的head都是用户上一次输入的数据，当有新数据输入时，我们把head赋值给last，然后进入while中，让last->next指向用户输入的最后一次p，再把head指向p。为下一次连接结点时，作为连接的末尾。这样，一个单向链表的代码我们就写出来了.

接下来要做的就是把写的代码抽出来，做成一个函数，我们先来看下程序的第16到第27行是我们需要做成函数的，因为这部分代码做的事情是把新输入的结点接到链表的末尾。我们看下这个函数需要的参数有什么？有一个head，还有一个用户输入的number。所以函数我们可不可以这样写呢？把16到27行抽出来后（25-39行）：

程序这样写还是有问题的，问题是，我们看下第37行，我们的head是会被修改的，至少第一次是这样，但是这个函数每次做完后，对于外面的那个head其实是没做修改的，主函数里的head一直等于NULL，所以第二次传入add函数的Node *head仍然等于NULL，导致Node *last等于那个head等于NULL，这样程序就出问题了。

要怎么解决这个问题，有一种方法是：我们把add函数的类型改为Node *，然后在函数最后我们返回这个head，所以在调用函数那一行我们还要改成head=add（head，number）：

注意第18，25和39行。这是一种方法。

不过，我们还有一种更好的方法，就是传入的不是Node *head，而是传入指针。我们先看下程序怎么写，然后再做解释：

我们新定义一个结构体（9-11行），里面就放一个指针，然后在主函数里定义一个结构体变量list，当然还要给它做初始化list.head=NULL（18、19行，17行的就可以删掉了），在第24行我们就不是传入head了，而是传入list的指针。函数里所有的head都改为list->head，最后当然也就不用return了，函数的类型也可以改为void了。

这种做法的好处是：我们把指针放在了一个结构体中，在以后的修改里我们可以做些扩充，比如再加些指针进这个结构体中，有什么用？举个例子：我们看下程序的37到39行，我们每次增加一个新结点后，都要从头开始从第一个结点开始找一直找到最后一个结点，再接上新的结点，这样做很浪费时间。

为了更好解释那句“在以后的修改里我们可以做些扩充，比如再加些指针进这个结构体中。”和解决“我们每次增加一个新结点后，都要从头开始从第一个结点开始找一直找到最后一个结点，再接上新的结点，这样做很浪费时间。”这个问题。接下来我们再说第三种改进方法。

就是我们可以在结构体中新定义一个指针比如Node *tail，让每次接完新结点后，让这个指针指向最后的这个结点，下一次接新结点时，直接从这个指针tail指向的链表中的最后一个结点的后面连接，这样做的很节约时间了：

在第11行结构体里我们新加入一个指针tail，当然定义完后别忘了初始化，初始化在第20行我们让它也等于NULL。接着进入函数中，同样一开始让last指向head，head=NULL，所以else里我们把list->head指向p，同时加多一句list->tail也指向p，（因为第一次输入数据时，p就是最后一个结点，所以让tail指向p）。完了以后第二次读入数据时就会进到if里，if里面我们让list->tail->next=p，也就是有新结点进来后，要把它放在最后，就要让上一次的最后一个结点（也就是tail指向的那个结点）的next指向p，然后list->tail=p，把tail又等于了最后一个结点，为下次接入新结点做准备。

我认为用第三种方法是最好，对于如果是一些大程序来说，这样用结构体和指针方式创建链表，更为合理。

最后附上源代码：

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


typedef struct _node {
int value;
struct _node *next;
} Node;


typedef struct _list {
Node* head; 
Node* tail; 
} List;


void add(List* pList, int number);
void myprint(List *pList);


int main(int argc,char const *argv[])
{
//Node *head=NULL;
List list; //定义一个List结构的变量； 
list.head=list.tail=NULL;
int number;
do {
scanf("%d", &number);
if (number!=-1) {
   add(&list, number); //接入新结点； 
}
} while (number!=-1);
printf("\n链表:\n");
myprint(&list); //输出链表； 
printf("请输入要查找的数字:");
scanf("%d", &number);
Node *p;
int isFound=0;
for (p=list.head; p; p=p->next) {
if (p->value==number) {
printf("找到了!\n");
isFound=1;
break;
}
} 
if (!isFound) {
printf("没找到.\n"); 
} 
Node *q;
for (q=NULL,p=list.head; p; q=p,p=p->next) {
   if (p->value==number) {
if (q) {
q->next=p->next;
} else { //当要删除的是第一个时，q为NULL，应让head指向下一个; 
list.head=p->next;
}
free(p);
p=q;
}
}
printf("删除后:\n"); 
myprint(&list);

for (p=list.head; p; p=q) {
q=p->next;
free(p);
}

return 0;
}
void add(List* pList, int number) //读入数据函数 
{
Node *p=(Node*)malloc(sizeof(Node)); //每读入一个数就做一个Node的结构体来存这个数，才能通过*next接起来； 
p->value=number;
p->next=NULL; //每次读入一个新的，把它当作最后一个;
Node *last=pList->head;
//pList->tail=pList->head;
if (last) {
  pList->tail->next=p; 
  pList->tail=p; 
} else {
  pList->head=p;
  pList->tail=p;
}
//printf("%d", &pList->tail->value);
}


void myprint(List *pList) //输出整个链表函数 
{
Node *p;
for (p=pList->head; p; p=p->next) {
printf("%d\t", p->value);
}
printf("\n");
}