Chinaunix首页 | 论坛 | 博客
  • 博客访问: 166891
  • 博文数量: 38
  • 博客积分: 2431
  • 博客等级: 少校
  • 技术积分: 470
  • 用 户 组: 普通用户
  • 注册时间: 2006-12-20 09:49
文章分类

全部博文(38)

文章存档

2011年(2)

2010年(14)

2009年(10)

2008年(12)

我的朋友

分类: C/C++

2010-03-11 15:41:08

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

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

示例,创建链表:
 /* 功能: 创建链表 */
#include
#include

/* 创建一个 结构, 数据域仅有一个名字字段,指针域为结构指针 */
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);
}


阅读(897) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~