当前位置 博文首页 > jtwqwq的博客：翁恺老师C语言程序设计网课(17)
每次长大，都可能会重新申请新的内存空间。
实际上的解决方法是每一块都分为两部分，前一块是数据，后一块是指针，指向下一块。然后还需要指向开头的head，以及结尾不指向任何东西(NULL)。这就是链表（linked-list）。每个块就是结点。
typedef struct _node{
int value;
struct _node *next;
}Node;
第一个例子：像可变数组一样，不停读入数字直到-1为止。
这件事回想起来，从平均数就开始做了。一开始我们不需要记录每一个数，只需要求平均数即可。后来讲到数组，需要输出比平均数大的数，就需要记录输入的每一个数，用到数组了。不过数组大小需要用户事先告诉我们。但现在是不知道会读入多少个数。
do{
scanf("%d",&number);
if(number!=-1)//add to linked-list
}while(number!=-1);
首先我们需要有head开头的指针。一开始head指针是NULL，不停往后挂结点
Node *head=NULL;
Node *p=(Node*)malloc(sizeof(Node));
p->value=number;
p->next=NULL;
//find the last, attach
Node *last=head;
if(last)//判断head是否为空
{
while(last->next)last=last->next;
last->next=p;
}else head=p;//即：p就是第一个结点
上面的这些操作（把新的结点挂到上一个结尾）尝试拿出来单独写成一个add函数。
函数的参数应该有什么？head头指针，以及每次要传入的数据data。
错误的方案1：
void add(Node *head,int number);
每次新定义一个临时结点p，p->last=number，p->next=NULL;然后我们把这个结点挂在链表的末尾。
有两种情况：1、p是链表的第一个元素，即head=NULL，那直接令head=p完事。
2、p不是第一个元素，我们现在只知道链表头是head，我们要先找到last链表的结尾结点，然后把p挂在结尾。
last=head;
while(last->next)last=last->next;//找到结尾last结点
last->next=p;
但是head=p是有问题的，head的值并没有得到修改。如果想不通，可以阅读作者的另一篇文章，里面有写作者自己的一些理解。
如果我们把head放在外面作为一个全局变量？不好，在全局变量时讲过，不要用head做全局变量。因为add只能对这个链表的head起作用，如果程序中出现其他链表，不能再做操作。
方案2：如果add函数返回指针，然后return 理想的head指针，在函数中令head=add函数呢？不错。
方案3：传给add的参数不再是head，而是head的地址。我们知道通过指针可以直接修改该地址中的值。
方案4：我们定义一个结构list，其中包含*head。在原函数中定义list，list.head=NULL；然后把list的指针&list传入add函数，add的参数是list的指针，在函数中就可以对list->head进行修改。
方案4的好处在于我们用自己定义的list结构来代表整个链表。除了定义的这个head，还可以有tail指向结尾，这样每次last不用遍历整个链表才能找到结尾；等等。
这里讲的比较细，是因为链表的放入东西、插入东西都是比较简单的。对于工程化的东西，我们要深究。
输出链表中读到的所有东西
node *p;
for(p=list.head;p;p=p->next)printf("%d\t",p->value);//遍历
则这一段可以单独拿出来写作函数，称之为print，参数为list的指针。
可见for循环不一定非要是++。
然后进一步，我们希望能实现搜索的功能：输入一个数字，在链表中寻找这个数字，如果找到了就将其删除。
for(p=list.head;p;p=p->next)
{
if(p->value==number)printf("找到了！");
}
删除某个值，我们要做两件事。
第一，前面的指针指向他后面的值。
第二，free it.
也就是说，如果前面的指针是q，我们要删除的部分指针是p，则要q=p,p=p->next。
怎么考虑到边界情况？
一个很重要的思想：
判断出现在arrow箭头左边的指针变量是否是NULL。如图中for循环内出现了p->next，p->value，q->next.因为在for循环中判断了p会不会是空指针，所以p->是安全的。但是q->next就不安全了，没有判断q是否是NULL。
也就是说当要删除的节点p是第一个时，q=NULL，这就是边界情况。这时可以让head等于所指的next。
最后别忘记free(p).
所有节点都是malloc出来的，所以最后都要清除干净。
可以这样做：令p=head，q=p->next
每次free(p)，p=q把最开头的清除，直到p=NULL时就清除完成了。
for(p=head;p;p=q)
{
q=p->next;
free(p);
}
链表这里只是简单地介绍了一下。在之后的数据结构等还会深入研究。这门课就到这里~
cs