数据结构之线性表

leoperfect 发布于2019-07-30 18:46 / 1807人阅读

摘要：线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。链表之单链表线性表的定义，它是一些元素的序列，维持着元素之间的一种线性关系。

线性表学习笔记，python语言描述-2019-1-14

线性表简介

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：

顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
链表，将元素存放在通过链接构造起来的一系列存储块中。

顺序表

2.1、顺序表的基本形式

图a表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：

Loc(ei) = Loc(e0) + c*i

故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。

如果元素的大小不统一，则须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

图b这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。

2.2、顺序表的基本实现
顺序表的基本实现方式：表中元素顺序存放在一片足够大的连续存储区里，首元素存入存储区的开始位置，其余元素依次顺序存放。元素之间的逻辑顺序关系通过元素在存储区的物理地址表示。

顺序表最常见的一种基本实现方式是一个表里保存的元素类型相同，因此存储每个表元素所需的存储量相同，可以在表里等距安排相同大小的存储位置。如下图，一个顺序表，存放的元素是整型的数据类型，整型在32位的操作系统中，一个整型数字占用内存的空间大小是4Byte,因此，内存中连续存放几个整型数字，每个存放元素的空间的地址值之间是等距。其中Li变量指向的通常是顺序表的表头元素的地址值，也就是0x23。

链表之单链表

线性表的定义，它是一些元素的序列，维持着元素之间的一种线性关系。实现线性表的基本需要是：

能够找到表中的首元素

从表中的任一元素出发，都能找到它的下一个元素

实现它除了连续存储的顺序表之外，链表也能做到。

链表是用链接关系显示表示元素之间的顺序关系，基本实现方式如下:

把表中的元素分别存储在一批独立的存储块里

保证从组成表结构中的任一结点可找到与其相关的下一个结点

在前一结点用链接的方式显示地记录与下一结点的关联。

单链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

表元素域elem用来存放具体的数据。

链接域next用来存放下一个节点的位置（python中的标识）

变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

而表示一条链表的结束，只需要将最后一个结点的链接域设置为None。
节点的实现

一个链表的最基本组成是一个结点，一个结点的实现如下：

class SingleNode(object):
    """单链表的结点"""
    def __init__(self,item):
        # _item存放数据元素
        self.item = item
        # _next是下一个节点的标识
        self.next = None

单链表的操作

is_empty() 链表是否为空

length() 链表长度

travel() 遍历整个链表

add(item) 链表头部添加元素

append(item) 链表尾部添加元素

insert(pos, item) 指定位置添加元素

remove(item) 删除节点

search(item) 查找节点是否存在

python中单链表的实现

class SingleLinkList(object):
    """单链表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None

    def length(self):
        """链表长度"""
        # cur初始时指向头节点
        cur = self._head
        count = 0
        # 尾节点指向None，当未到达尾部时
        while cur != None:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""

私有云超融合服务器线性表的存储结构分别建立包含10个数据元素的顺序线性表和链式线性表 c语言线性表删除数据线性表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43018.html

数据结构之线性表（手绘版）

摘要：就可以称之为线性表。这种可以根据位序得到数据元素也是一种很重要的线性表操作。瀏除线性表中第个位置元素并用返回其值。线性表的长度是线性表中数据元素的个数随着线性表插入和删除操作的进行这个量是变化的。目录一，写在前面二，线性表的定义三，线性表的抽象数据类型四，线性表的顺序存储结构 4....

Maxiye 2021-09-22 10:01 评论0 收藏0
新学期预习吗？保姆级讲解数据结构之顺序表的9个方法+手撕代码

摘要：顺序表是一种使用数组存取的线性表。给位置的元素设为更新位置不合法删除第一次出现的关键字如下图，当前顺序表元素出现了两次，需要删除第一次出现的。数据结构之顺序表 ...

selfimpr 2021-09-04 16:45 评论0 收藏0
数据结构与算法的Python实现（二）——线性表之顺序表

摘要：文章首发于公众号一件风衣在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基础，在中，和就可以看作是线性表的实现。文章首发于公众号一件风衣（ID：yijianfengyi）在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基...

TerryCai 2019-07-30 16:53 评论0 收藏0
数据结构与算法之顺序表

摘要：前面的话本篇文章带大家认识数据结构与算法基础，顺序表动态，所谓的顺序表本质就是数组，它的特点是物理结构与逻辑结构都是连续的，最大的优点就是能够随机访问，最大的缺点是空间有限，就算扩容，也有可能存在大量的内存浪费。 ...

roundstones 2021-11-11 16:54 评论0 收藏0
图解几种常见的线性表

摘要：下面来看一下，有哪些数据结构属于线性表吧栈特性先进后出只有唯一的一个出入口介绍栈又名堆栈，它是一种运算受限的线性表。原文是在我自己博客中，小伙伴也可以点阅读原文进行跳转查看，还有好听的背景音乐噢背景音乐已取消~ 2333333 线性表什么是线性表？就是一种连续或间断存储的数组，这里的连续和间断是针对物理内存空间中线性表元素之间是否连续，其中连续数组对应内置数组的实现方式，间断数组对...

wawor4827 2019-07-01 10:01 评论0 收藏0