C语言中的链表
一、引子
我们前面讲数组的时候，提到了创建数组的三种方法，一种是创建静态数组，一个是创建动态数组，以及使用malloc创建动态数组。然后我们可能会有一个场景，就是我们并不知道我们实际需要多大的内存，我们需要可以不确定的添加数据，这个时候，我们可能回想，这个无所谓的，直接malloc就可以了。然后这个时候就有两个方式了，一个是说我们一来就定义好300个内存空间，还有一种是我们用的时候在调用malloc。然后第一种方法就造成了两种情况的发生，如果我们所需内存少于300，就浪费了，要是所需内存多余300，就不够了。第二种方法会出现一个问题，就是我们一个数据，可能所需内存太大了，使得一个malloc存不下。然后我们想到了一个新的思路，就是我们能不能这样，就是我们每次使用的时候，就进行malloc一次，然后这个malloc正好满足我们所需的内存大小，然后我们在该内存的的一部分空间内存放一个指针，指向上一个内存的地址，这样就像火车那样连接成了一串。
例子：
#include<stdio.h>#include<stdlib.h>#include<string.h> #define TSIZE 45 structfilm {chartitle[TSIZE];intrating;struct film*next;
};char* s_gets(char* st, intn);int main(void)
{struct film* head =NULL;struct film* prev, *current;charinput[TSIZE];
puts("Enter first movie title:");while (s_gets(input, TSIZE) != NULL && input[0] != '\0')
{
current= (struct film*)malloc(sizeof(structfilm));if (head ==NULL)
head=current;elseprev->next =current;
current->next =NULL;
strcpy(current->title, input);
puts("Enter your rating<0-10>:");
scanf("%d", ¤t->rating);while (getchar() != '\n')continue;
puts("Enter next movie title (empty line to stop)");
prev=current;
}if (head ==NULL)
printf("No data entered");elseprintf("HERE is the movie lists:\n");
current=head;while (current !=NULL)
{
printf("Movie :%d rating:%d", current->title, current->rating);
current= current->next;
}
current=head;while (current !=NULL)
{free(current);
head= current->next;
}
printf("BYE\n");return 0;
}char* s_gets(char* st, intn)
{char*ret_val;char*find;
ret_val=fgets(st, n, stdin);if(ret_val)
{
find= strchr(st, '\n');if(find)*find = '\0';else while (getchar() != '\n')continue;
}returnret_val;
}