从数组到链表

在传统的情况下，使用数组可以很方便的进行数据的管理。但是，在多数情况下，数组由于空间大小，元素数量固定，会导致数组的大小在不同的情况下可能会太大，导致空间浪费，也可能太小，导致数据放不下，数组越界。所以，我们需要一种方法，能够让我们不确定地添加数据，或者说直到用完所有的可用内存为止。而不是提前指定要输入多少数据，或者让程序分配冗余的内存空间。

malloc()函数

使用malloc()函数可以分配一块内存空间，供后续的使用。具体的语法如下：

#include <stdlib.h>
/* 以上头文件含有malloc()函数 */
int main(){
	malloc(申请内存空间的大小); //分配一块指定大小的内存空间
  /* ... */
	}

注意: 连续使用malloc()分配的地址空间不一定是连续的。也就是说，我们申请的空间会由操作系统分配一块随机的内存地址。所以，我们并不能简单的通过指针的移动来访问我们申请的内存地址。

使用指针寻址

正因为malloc()分配的地址空间不一定连续，所以我们需要一个指针，来记录我们申请到的内存空间的地址，以便于我们进行访问。这样虽然多用了一些空间用来储存指针变量，但是，这点内存开销有时候是远小于声明额外的结构数组所占用的空间的。也就是说这样我们就可以节省大量未使用的内存空间，并且可以让我们动态确定输入的数据的上限。

所以，我们可以使用如下的方式声明一个结构体来应用这个特性:

struct student {
    string name;
    int id; //学号
    int score[6];//对应6个科目的成绩
    bool sex;//0:男，1:女
    struct film * next,* prev;  //next指向下个结构体的指针,prev指向上个结构体的指针
};
struct film * head; //指向第一个结构体的指针，指向链表中的第一项。

这样，我们就创建好了一个链表的基本结构。

使用链表

创建链表

创建链表涉及下面3步：（1）使用malloc()为结构分配足够的空间；（2）储存结构的地址；（3）把当前信息拷贝到结构中。

使用malloc()为结构分配足够的空间

首先，接受用户的输入，并将用户的输入放入一个临时的内存变量。然后申请一块内存空间。然后接受用户的输入。

输入部分:

//结构体声明部分参考上文
struct student * current,head;
while (cin >> temp,cin.good())
{
  current = (struct student *) malloc(sizeof(struct student));
  if (head == NULL) /* 第1个结构*/
  {
    head = current;  
  }
  else
    	prev->next = current; //指向上次分配的结构
  current->next = NULL;
  /* 这里开始对结构体进行赋值 */
  current->name = temp;
	/* 省略其他的输入部分 */
  prev = current;
  /* 本次输入结束 */
}

释放链表

释放malloc()分配的空间

当我们使用完malloc()所分配的空间之后，这些空间不再被需要。这时就需要释放掉这些内存。虽然大多数情况下，这些内存会被自动释放。但是，我们最好也还是成对的使用malloc()和free()函数来保证内存能被正确的释放。避免内存被塞满。

current = head;
while (current　!=　NULL)
{
	current　=　head;
	head　=　current->next;
	free(current);
}

显示（输出）链表

显示部分就比较简单了。从链表的第一个指针开始访问就行了。

current = head;
cout<<"学生姓名:"<<current->name/*省略其他的输出部分*/<<endl;
while(current != NULL)
{
  cout<<"学生姓名:"<<current->name/*省略其他的输出部分*/<<endl;
  current　=　current->next; //指向下一个部分
}

这样就可以依次输出里面的数据了。

不足

上面的程序并没有检查malloc()分配内存是否成功，也无法直接删除链表中的一个项，

这种用特定方法解决特定问题，并且在需要时才添加相关功能的编程方式通常不是最好的解决方案。另一方面，通常都无法预料程序要完成的所有任务。随着编程项目越来越大，一个程序员或编程团队事先计划好一切模式，越来越不现实。很多成功的大型程序都是由成功的小型程序逐步发展而来。