2.11.2 建立动态单向链表
建立链表首先要定义一个包含数据域和指针域的的结构类型，然后建立指向表头节点的头指针head，最后通过malloc函数动态申请一块内存作为表头节点。
- typedef struct node
- {
- int data; /*信息*/
- struct node *link; /*指针*/
- }NODE； /*定义节点*/
- NODE *head; /*定义头指针head */
定义结构类型和头节点之后，我们要建立不包含数据的表头节点，可以按下列语句进行操作。
- NODE *p; /*说明一个指向节点的指针变量p */
- p=(NODE*) malloc(sizeof(NODE)); /*申请表头节点*/
- p->link = NULL; /*将表头节点的link置为NULL */
- head=p; /*head指向表头节点p*/
此时链表的状态如图2.12 所示，由于此时链表中只有一个表头节点，没有数据节点，所以称为空链表。
 |
| 图 2.12 空链表 |
为了在链表中保存数据，可以从表头位置将数据节点插入到链表中，例如，插入一个数据节点：
- p=(NODE*) malloc(sizeof(NODE)); /*申请一个数据节点*/
- gets(p ->data); /*输入一个新的数据*/
- p->link=head->link; /*建立链接关系。将表头节点的link存入p 的link中*/
- head->link=p; /*将数据节点插在表头节点之后成为第一个数据节点*/
插入第一个数据节点后链表如图2.13 所示，然后继续插入下一个数据节点。
 |
| 图2.13 插入一个节点后的链表 |
根据上面的链表建立过程，可以写出函数create建立有n个数据节点的链表，如下所示：
- create(NODE *head,int n)
- {
- NODE *p;
- for(; n>0;n--)
- {
- p=(NODE*) malloc(sizeof(NODE));
- if(p==NULL)
- exit(0);
- gets(p->data);
- p->link = head->link;
- head->link = p;
- }
- }