链表 原文：http://canlynet.blog.163.com/blog/static/2550136520091120101712136/

===========================================================================

链表存在的意义：

1、不需要事先准备足够大的内存空间。

2、每次加入新数据时，之需要将位置确定在比前面数据大/小，比后面数据小/大的地方，插入数据即可。

3、删除数据只需要将该数据之前的那个数据指针指向该数据后面的数据首地址即可。

两个好处：内存空间随需要而分配；插入数据、删除数据方便且一次成型，无需数据挪动（与数组相比）。

===========================================================================

★链表一定有一个头指针，不然链表位置无法确定！所以在定义链表结构体的数据结构以后，首先做的事情就是定义一个链表头指针Head_pointer，类型为Linklist（指向链表的指针），赋值NULL，加入第一个数据时，第一个数据的p->next = *Head_pointer;而链表头指针Head指向新加入这个节点*Head_pointer = p;★

【单链表】（节点指针域存储的知识后继元素的地址）：

一、定义结构体：

typedef struct node

{

        elemtype data; //数据域

        struct node *next; //指针域

} Node, *LinkList; //定义两个类型，Node为节点类型，LinkList为指向节点的指针类型。

#define OVER_FLOW    -1 //内存分配失败返回值

#define OK                      0 //操作成功返回值。

二、构造一个空链表：

LinkList Head;

void Init_LinkList(LinkList *Head_pointer)

{

    * Head_pointer = NULL;

}

调用语句：Init_LinkList (&Head);即可

三、插入一个元素（头插）：

int Insert_First (LinkList *Head_pointer, ElemType x)

{

    Node *p

    p = (LinkList) malloc (sizeof (Node)); // 为节点分配空间

    if (p == NULL) //错误处理

        return OverFlow;

    p->data = x; //数据域赋值

    p->next = *Head_pointer; //新节点指针域指向原来的头结点（头结点可以有数据域而且一般推荐存放数据，但指针域为NULL——单链表）

    *Head_pointer = p;

    return OK;

}

使用如下语句调用Insert_First函数：

    if (Insert_First (&Head, x) != OK)

        printf("Insert failed\n");

=====================================================================

总结：插入数据的步骤（任何位置插入都实用）：

一、为新节点分配内存空间；

二、定义一个该节点类型的指针变量p，p指向新节点；

三、新节点data赋值；

四、新节点的next指针指向插入位置的后面那个节点，即用前面节点的next为这个节点的next赋值；

五、前一个节点的next用p赋值（即指向新节点）。

=====================================================================

四、查找指定元素：

LinkList Location_LinkList(Linklist Head, ElemType x)

{

    LinkList p; //定义节点指针类型变量p

    p = Head; //p指向头结点

    while （p != NULL)

    {

        if (p->data == x) break; //找到数据就跳出循环，返回p，就得到该数据的位置啦。

        p = p->next;

    }

    return p; //注意如果没找到数据的时候，p会指向NULL（就是最后一个数据的next指针的值）

}