返回介绍

3.9 单链表的整表创建

发布于 2024-08-19 23:28:45 字数 2727 浏览 0 评论 0 收藏 0

回顾一下,顺序存储结构的创建,其实就是一个数组的初始化,即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样,它不像顺序存储结构这么集中,它可以很散,是一种动态结构。对于每个链表来说,它所占用空间的大小和位置是不需要预先分配划定的,可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。

单链表整表创建的算法思路:

1.声明一指针p和计数器变量i;
2.初始化一空链表L;
3.让L的头结点的指针指向NULL,即建立一个带头结点的单链表;
4.循环:

  • 生成一新结点赋值给p;
  • 随机生成一数字赋值给p的数据域p->data;
  • 将p插入到头结点与前一新结点之间。

实现代码算法如下:

/* 随机产生n个元素的值,建立带表头结点的单链
   线性表L(头插法) */
void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;
    /* 初始化随机数种子 */
    srand(time(0));                            
    *L = (LinkList)malloc(sizeof(Node));
    /* 先建立一个带头结点的单链表 */
    (*L)->next = NULL;                         
    for (i = 0; i < n; i++)
    {
        /* 生成新结点 */
        p = (LinkList)malloc(sizeof(Node));    
        /* 随机生成100以内的数字 */
        p->data = rand() % 100 + 1;            
        p->next = (*L)->next;
        /* 插入到表头 */
        (*L)->next = p;                        
    }
}

这段算法代码里,我们其实用的是插队的办法,就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法,如图3-9-1所示。

图3-9-1

可事实上,我们还是可以不这样干,为什么不把新结点都放到最后呢,这才是排队时的正常思维,所谓的先来后到。我们把每次新结点都插在终端结点的后面,这种算法称之为尾插法。

实现代码算法如下:

/* 随机产生n个元素的值,建立带表头结点的单链
线性表L(尾插法) */
void CreateListTail(LinkList *L, int n)
{
    LinkList p,r;
    int i;
    /* 初始化随机数种子 */
    srand(time(0));                         
    /* 为整个线性表 */
    *L = (LinkList)malloc(sizeof(Node));    
    /* r为指向尾部的结点 */
    r = *L;                                 
    for (i = 0; i < n; i++)
    {
        /* 生成新结点 */
        p = (Node *)malloc(sizeof(Node));   
        /* 随机生成100以内的数字 */
        p->data = rand() % 100 + 1;         
        /* 将表尾终端结点的指针指向新结点 */
        r->next = p;                        
        /* 将当前的新结点定义为表尾终端结点 */
        r = p;                              
    }
    /* 表示当前链表结束 */
    r->next = NULL;                         
}

注意L与r的关系,L是指整个单链表,而r是指向尾结点的变量,r会随着循环不断地变化结点,而L则是随着循环增长为一个多结点的链表。

这里需解释一下,r->next=p;的意思,其实就是将刚才的表尾终端结点r的指针指向新结点p,如图3-9-2所示,当中①位置的连线就是表示这个意思。

图3-9-2

r->next=p;这一句应该还好理解,我以前很多学生不理解的就是后面这一句r=p;是什么意思?请看图3-9-3。

图3-9-3

它的意思,就是本来r是在ai-1元素的结点,可现在它已经不是最后的结点了,现在最后的结点是ai,所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。

循环结束后,那么应该让这个节点的指针域置空,因此有了“r->next=NULL;”,以便以后遍历时可以确认其是尾部。

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文