【数据结构】线性表的链式表示之单链表

微信公众号:程序员周同学 关注可了解更多的教程及编程技巧。问题或建议,请公众号留言; 如果你觉得对你有帮助,欢迎点赞

内容目录

线性表的链式表示之单链表单链表的特点单链表的储存结构单链表的结点单链表的储存结构

线性表的链式表示之单链表

顺序表的链式表示其实就是我们所“熟知”的链表,链表分为:

  • 单向链表---今天讲这个
  • 双向链表
  • 循环链表

单链表的特点

单链表作为线性表的一种,首先肯定是具备线性表的两种特点的:

  1. 除了首尾两个元素之外,每个元素的前面和后面只有一个数据元素
  2. 可以在任意位置插入元素和删除元素
    • 单链表中,删除和插入元素不需要移动其他元素
    • 单链表执行查找元素操作时,平均效率是O(n)

    同样在这篇文章中主要讲插入删除元素,因为另外两个操作都可以基于删除操作演变而来,所以两个操作只给出代码。

单链表的储存结构

C语言的链表可能是很多人的噩梦,因为要频繁用到指针操作。在顺序表中我们了解到,顺序表的每个元素的内存空间是连续的,而链表每个数据元素的内存空间是不连续的,所以必须要使用指针将所有的结点连接起来。如果有一个结点没有连接,那你就再也找不到他了。

单链表的结点

单链表的结点结构

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;//定义DataType类型
struct linkedList{
    DataType data;//结构体数据域
    struct linkedList *next;//结构体指针域
}

单链表的储存结构

单链表的储存结构

    //创建结构体指针,head,node,end用于创建链表,traverse用于遍历链表,此处无用
    //明天将创建链表封装成函数
    struct linkedList *head,*node,*end,*traverse;
    int data;
    head = NULL;
    int n;
    scanf("%d",&n);
    for (int i = ; i < n; i++) {
        scanf("%d",&data);
        //malloc是stdlib.h中的函数,所以必须导入头文件
        //为node指针分配一个struct linkedList大小的空间
        node = (struct linkedList*)malloc(sizeof(struct linkedList));
        //将node的数据域赋值为data
        node->data = data;
        //将node的指针域赋值为NULL,即:指向空内存
        node->next = NULL;
        //如果头结点为空,则把node赋值给head
        if (head == NULL)
            head = node;
        //如果不为空,则将end的指针域指向node
        else
            end->next = node;
        //将node赋值给end
        end = node;
    }

每一个结点通过next结构体指针指向下一个结点,直到最后一个结点指向NULL,即空内存。 以下是创建链表的图示:

本文分享自微信公众号 - 程序员周同学(jay-ztx)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京宏哥

Appium+python自动化(十三)- 输入中文 - 一次填坑记(超详解)

无论你在哪里,在做什么都会遇到很多坑,这些坑有些事别人挖的,有些是自己挖的。别人挖的叫坑人,自己挖的叫自杀,儿子挖的叫坑爹。因此在做app自动化道路上也...

46030
来自专栏风吹杨柳

实习杂记(21):LocalBroadcastManager的使用、优点在哪里?

       它来自Android 的support包,类名是android.support.v4.content.LocalBroadcastManager...

10130
来自专栏机器学习与python集中营

使用python+tkinter开发一个简单的学生管理系统

57520
来自专栏机器学习与python集中营

深入剖析Mean Shift聚类算法原理

Mean Shift在计算机视觉领域的应用非常广,如图像分割,聚类和视频跟踪,小编曾经用Mean Shift实现目标跟踪,效果还不错。本文详细的总结了Mean ...

58710
来自专栏风吹杨柳

opencv 8 --背景减除 -- BackgroundSubtractorMOG2

例如顾客统计,使用一个静态摄像头来记录进入和离开房间的人数;或者是交通摄像头,需要提取交通工具的信息等。

45430
来自专栏机器学习与python集中营

深度学习中常用的损失函数loss有哪些?

这是专栏《AI初识境》的第11篇文章。所谓初识,就是对相关技术有基本了解,掌握了基本的使用方法。

2.7K20
来自专栏风吹杨柳

实习杂记(27):android中关于横竖屏切换的那些事

关于Android中Activity的横竖屏切换问题可以通过AndroidManifest.xml文件中的Activity来配置:

10530
来自专栏风吹杨柳

opencv 9 -- 轮廓 层次结构

使用函数 cv2.findContours 来查找轮廓, 我们需要传入一个参数:轮廓提取模式(Contour_Retrieval_Mode)。 我们总是...

14020
来自专栏侯哥的Python分享

python算法与数据结构-栈(43)

  栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹...

10220
来自专栏北京宏哥

Appium+python自动化(十二)- Android UIAutomator终极定位凶器(超详解)

乍眼一看,小伙伴们觉得这部分其实在异性兄弟那里就做过介绍和分享了,其实不然,上次介绍和分享的大哥是uiautomatorviewer,是一款定位工具...

22130

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励