专栏首页机器学习和数学[数据结构与算法] 线性表总结

[数据结构与算法] 线性表总结

线性表也是基本的数据结构之一,Python里面的list和tuple,就是线性表的一种实现。

首先什么是表呢,其实很简单,比如【元素1,元素2,。。。,元素n】,这样的一种数据的组织方式就是表,一个表里可以包含0个或者多个元素,只有0个元素的表,叫做空表。1,2,。。。,n叫做下标,元素的个数叫做表的长度。表元素之间的关系叫做下一个关系,比如元素2是元素1的下一个元素,这是一种顺序关系。

前驱元素和后继元素

在一个表中,存在唯一一个首元素和尾元素。就是元素1和元素n,除了元素1以外,每个元素都有唯一一个前驱元素;除了元素n以外,每一个元素都有唯一一个后继元素。这个也比较好理解,显而易见的道理。

对于一个线性表来说,需要提供哪些操作呢,也就是说我们应该如何使用一个表来为我们编程服务。

首先,应该知道如何创建一个表;创建表有2种情况,一种是创建一个空表,一种是创建部分元素,并且提供创建这部分元素的方法。

然后,创建表以后,需要对他的各种信息进行提取,比如长度,判断某个元素是否在创建的表里面等。

其次,有时候我们创建的表需要增加或者删除一些元素,比如我们的公司名单表,肯定经常有人入职和离职,也就是说员工表示一个动态变化的表,所以我们就应该实现如何增加和删除元素这个功能。另外,如果和顺序有关,那我们必须实现在指定位置上插入或者删除元素的功能。

还有,如果是对2个表的操作,就需要一些组合操作。比如合并表,或者根据一个表的数据,产生另外一个表,满足某种数学关系。

线性表的实现问题

上面讲了一些线性表的基本概念以及一些性质,下面就要考虑如何用计算机语言来实现这种数据结构。换句话说,就是要开发一段程序,来满足线性表的各种操作需求。根据实现方式的不同,线性表分为顺序表和链表。

顺序表:将表中元素顺序的存放在一大块连续的存储区内。

链表:讲表元素存放在通过链接构造起来的一系列存储块中。

首先我们仔细学习一下顺序表的实现问题。

创建和访问操作

创建空表:创建空表时,需要分配一块元素存储,记录表的容量并将元素计数值设置为0. 创建空表的时候,应明确告诉这个表的元素个数和表的长度。

简单判断操作:判断一个表是否为空或者为满,只要看表中元素个数是否为0,或者是否为表的长度,这个长度就是创建的时候,事先定义好的。

访问给定下标i的元素: 这个操作首先要做异常处理,分析i是否合法,就是说i是否在0到表长度这个范围内,这个也比较好理解吧,如果不在范围内,肯定就找不到,在Python中,这时候就会报IndexError。当位置合法时,需要计算出元素的的实际位置。知道了实际位置,自然想要找的元素也就找到了。

遍历操作:要顺序访问表中的元素,只需要遍历过程中用一个整数变量记录遍历达到的位置,因为位置是唯一的,如果之前访问过这个位置,那么下次就不再访问。

查找给定元素d的位置(首次出现):这种操作也叫查找操作。上一次说过用python实现二分查找,就是这个操作。

增加元素:增加元素包括两种情况,一种是在顺序表的尾端插入,实现较简单;一种是在指定位置插入,实现较复杂。首先看下尾端插入,尾端插入需要判断表是否已经满了,如果满了就插入不进去了,如果没满直接存入元素,并更新表的长度。在指定位置插入元素也有2中情况,一种是将元素插入到指定位置以后,不用保持原有数据的顺序关系,那么只要把相应位置的元素取出,存到别的任意位置即可。另一种是需要保持原有数据的顺序关系,那么就需要将数据存入以后,将后面的元素依次向后移动一位。

删除元素:和增加元素是一样的,也包括尾端或者首端删除和删除指定位置元素。在指定位置删除时,如果有保证顺序的要求,那么在删除之后,就需要将后面的元素依次向上移动一位。如果没有保证顺序的要求,只需要讲尾元素复制到指定位置,并覆盖原来的元素。

下面我们用Python实现一个类似自带的list的顺序表的数据结构,可以感受一下

class SeqList(object):
    def __init__(self, max=10):
        self.max = max
        # 默认顺序表最多容纳10个元素
        # 初始化顺序表数组
        self.num = 0
        self.date = [None] * self.max

    def is_empty(self):
        # 判定线性表是否为空
        return self.num is 0

    def is_full(self):
        # 判定线性表是否全满
        return self.num is self.max

    # 获取线性表种某一位置的元素
    def __getitem__(self, i):
        if not isinstance(i, int):
            # 如果i不为int型,则判定输入
            # 有误,即Type错误
            raise TypeError
        if 0 <= i < self.num:
            # 如果位置i满足条件,即
            # 在元素个数的范围内,
            # 则返回相对应的元素值,
            return self.date[i]
        else:
            # 否则,超出索引,
            # 返回IndexError
            raise IndexError

    # 修改线性表种某一位置的元素
    def __setitem__(self, key, value):
        if not isinstance(key, int):
            # 如果key不为int型,则判定输
            # 入有误,即Type错误
            raise TypeError
        if 0 <= key < self.num:
            # 如果位置key满足条件,即在
            # 元素个数的范围内,则返回
            # 相对应的元素值,否则,超出
            # 索引,返回IndexError
            self.date[key] = value
        else:
            raise IndexError

    # 按值查找元素的位置
    def getLoc(self, value):
        n = 0
        for j in range(self.num):
            if self.date[j] == value:
                return j
        if j == self.num:
            return -1
            # 如果遍历顺序表还未找到
            # value值相同的元素,则
            # 返回-1表示顺序表种没有
            # value值的元素

    # 统计线性表中元素的个数
    def Count(self):
        return self.num

    # 表末尾插入操作
    def appendLast(self, value):
        if self.num >= self.max:
            print 'The list is full'
            return
        else:
            self.date[self.num] = value
            self.num += 1

    # 表任意位置插入操作:
    def insert(self, i, value):
        if not isinstance(i, int):
            raise TypeError
        if i < 0 and i > self.num:
            raise IndexError
        for j in range(self.num, i, -1):
            self.date[j] = self.date[j - 1]
        self.date[i] = value
        self.num += 1

    # 删除某一位置的操作
    def remove(self, i):
        if not isinstance(i, int):
            raise TypeError
        if i < 0 and i >= self.num:
            raise IndexError
        for j in range(i, self.num):
            self.date[j] = self.date[j + 1]
        self.num -= 1

    # 输出操作
    def printList(self):
        for i in range(0, self.num):
            print self.date[i]

    # 销毁操作
    def destroy(self):
        self.__init__()


if __name__ == "__main__":
    my_list = SeqList()
    my_list.is_empty()
    my_list.insert(1, [1, 2, 3])
    my_list.printList()
    my_list.insert(1, 20)
    my_list.printList()

本文分享自微信公众号 - 机器学习和数学(ML_And_Maths),作者:Alvin_2580

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

原始发表时间:2017-08-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [数据结构与算法] 链表的其他类型

    单链表是最简单的链表,单链表的一种变形就是循环单链表,其中最后一个结点的next域不用None,而是指向表的第一个结点,这样就形成了一种循环结构,所以叫循环单链...

    用户1622570
  • [编程经验]Python中的Lambda,Map, Reduce小结

    今天要和大家分享的是Python匿名函数(anonymous functions),也叫lambda函数。匿名函数的意思就是说这个函数没有显式的函数名,因为一般...

    用户1622570
  • [数据结构与算法] 链接表总结

    上一次说到了顺序表,链接表和顺序表一样,也是线性表。那为什么有了线性表还要有链接表呢?总之就是当数据过大时,顺序表存在一些存储方面的限制,而链接表比顺序表要更有...

    用户1622570
  • python的paramiko模块

      paramiko是用python语言写的一个模块,遵循SSH2协议,支持以加密和认证的方式,进行远程服务器的连接。

    用户2398817
  • 使用PyTorch进行情侣幸福度测试指南

    计算机视觉--图像和视频数据分析是深度学习目前最火的应用领域之一。因此,在学习深度学习的同时尝试运用某些计算机视觉技术做些有趣的事情会很有意思,也会让你发现些令...

    磐创AI
  • [PYTHON] 核心编程笔记(13.P

    类与实例相互关联,类是对象的定义,而实例是"真正的实物",它存放了类中所定义的对象的具体信息

    用户2398817
  • python数据库-MySQL与python的交互(52)

    2.创建testMySQL.py模块对我们创建的MySQLManager.py模块测试

    Se7eN_HOU
  • PyQt5 输入对话框QInputDialog

    (int, bool ok) QInputDialog.getInt (QWidget parent, QString title, QString labe...

    用户6021899
  • Python与Cisco的事儿之四

       以下代码实现的流程: cdp -->获取相应链接的信息-->自动写进设备相对应的端口--->configure保存-->configure备份到TFTP服...

    用户2398817
  • 强化学习系列之一:马尔科夫决策过程

    文章目录 [隐藏] 1. 马尔科夫决策过程 2. 策略和价值 3. 最优策略存在性和贝尔曼等式 强化学习系列系列文章 机器学习一共有三个分支,有监督...

    AlgorithmDog

扫码关注云+社区

领取腾讯云代金券