理解链表

时间：2010-03-11 来源：liaosnet

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向明上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。
--以上来自wiki: http://zh.wikipedia.org/zh-cn/链表
链表是结构的扩展，是在结构的基本上增加了指针域，然后通过指针域的指针指向下一个相同结构的结构，以此循环（单链表最后一个结构的指针域指向NULL），并最终形成一个链表。如图所示：

使用指针head（地址1000）指示一个链表。当head的地址为NULL时，表明是个空链表。指针域存储的是结构的指针，指向下次一相同结构的地址（如果所示，1000地址上的结构中的指针域的指针的值为1004，指向地址是1004的结构）。

示例，创建链表：

/* 功能: 创建链表 */
#include <stdio.h>
#include <string.h>

/* 创建一个结构, 数据域仅有一个名字字段,指针域为结构指针 */
struct stu
{
    char    name[20];
    struct stu *next;
};

/* 创建链表的函数 create */
struct stu *create(int n)
{
    struct stu *head ; /* 链表头地址指针, 即通过此访问链表   */
    struct stu *pthis ; /* 链表当前地址指针, 当前访问的结构   */
    struct stu *ptemp ; /* 临时交换地址指针, 保存当前地址, 当前指针移到下一节点时就是前一节点的地址 */

    int i ; /* 自变循环变量 */
    for (i = 0; i < n; i++)
    {
        pthis = (struct stu *)malloc(sizeof(struct stu)) ;
        printf("请输入姓名: ") ;
        scanf("%s",pthis->name) ;

        /* 当i==0时,表示当前第一个节点 */
        if (i == 0)
        {
            head = pthis ;
            ptemp = pthis ;
        /* 第一个节点后,pthis指向了第二个节点,此时ptemp指向的地址仍然是第一个节点, 将pthis的地址赋于ptemp的指针域指针next, 以此类推 */
        } else {
            ptemp->next = pthis ;
        }

        /* 由于数据输入仅赋值给数据域, 指针域也需要赋值, 此时可以暂时赋值NULL(最后一个节点的指针域也是指向NULL) */
        pthis->next = NULL ;
        /* 将当前的地址指针pthis的值赋于临时交换地址指针ptemp, 然后将执行循环对pthis重新赋值 */
        ptemp = pthis ;
    }

    /* 返回链表的头地址 */
    return(head);
}

/* 创建打印链表函数lprint, 输入为链表的首地址 */
void lprint(struct stu *p)
{
    if (p == NULL)
    {
        printf("\n空链表.\n");
    } else {
        printf("姓名\n");
        while(p)
        {
              /* p = p->next 是while的循环条件,当p 地址节点存在时,打印数据库 */
            printf("%s\n", p->name);
            p = p->next ;
        }
    }
}

/* 主函数调用create创建链表, 然后调用lprinf打印 */
main()
{
    struct stu *p ;
    int num ;
    printf("请输入欲创建链表的节点数: ");
    scanf("%d",&num);

    p = create(num);

    lprint(p);
}