《数据结构》第六篇、线性表概述

玩命快递.jpg

前面5篇文章我们讲解了数据结构和算法的一些概述,我们应该对数据结构和算法有了一定的认识了,本篇文章将会带着大家学习最简单的一个数据结构,即如题所述:

线性表

线性表,顾名思义是像线一样性质的表,他的用处多不胜数,是常用且最简单的一种数据结构。

例如,一串英文字母,一队手拉手的小朋友,一份学生成绩单等都可以用线性表来表示。

线性表的存储结构有

顺序存储

链式存储

两种,本文章先介绍线性表的一些特性,会在后两篇文章中介绍常用的几个线性表。

什么是线性表?

线性表是具有相同特性的数据元素组成的一个有限序列。例如,定义一个线性表来存储本班学生的学生编号,可表示为如下形式:

(001,002,003,004,....,050)

这就是一个线性表。线性表也可以用一个标识符来命名,如

A=(001,002,003,004,....,050)。线性表中的元素个数为线性表的长度,当元素个数为0时,称这个线性表为空表。

线性表中的元素可以为整数、字符等简单数据,也可以由数个数据项组成,我的数据结构第一篇文章

https://www.jianshu.com/p/2a5b8bda7b84

中的学生信息表也是一个线性表,描述的是新学期入学学生的信息,其中每一个元素都是由几个数据项组成的,在这种情况下,常把一个元素称为一条记录。

线性表的特征

特征

每一种数据结构都有它自己的特征,线性表作为一种最简单的数据结构,它有如下几个特征:

(1)线性表中有且只有一个开始结点(头结点),这个开始结点没有前驱结点。

(2)线性表中有且只有一个末尾结点(尾结点),这个末尾结点没有后继结点。

(3)除去开始结点和末尾结点,其他结点都有一个前驱结点和后继结点。

线性表这种结构使元素逐个排列开来,如手拉手的小朋友,如此呈现给人们的数据形式就比较清晰明了。

结构特点

线性表在存储结构上有顺序存储和链式存储两种,但不管哪种存储方式,他们的结构都有如下特点:

(1)均匀性。虽然不同数据表的数据元素可以是各种各样的,但对于同一个线性表来说,数据元素必须具有相同的数据类型和长度。

(2)有序性。各数据元素在线性表中的位置只取决于他们的序号,数据元素之间的相对位置是线性的,即存在唯一的“第一个”和“最后一个”数据元素。除了第一个数据元素和最后一个数据元素外,其他元素前面均只有一个数据元素,即直接前驱,后面均只有一个数据元素即直接后继。

对于线性表的基本操作方式

线性表是一种比较灵活的数据结构,他的长度可以根据需要增减,它也可以进行插入和删除等操作。对线性表的基本操作大概包括下方这些:

创建——Create():创建一个新的线性表

初始化——Init():初始化操作,将新创建的线性表初始化为空

获取长度——GetLength():获取线性表的长度

判断表是否为空——IsEmpty():判断线性表是否为空

获取元素——Get():获取线性表某一位置上的元素

插入——Insert():在线性表某一位置插入元素

删除——Delete():删除某一位置上的元素

清空表——Clear():清空线性表,将线性表置为空

等等其他操作

上方概括的这些仅仅是基础的操作,有时我们可能需要为这个线性表提供排序、合并、元素替换、复制新表等等操作,这就需要为数据结构提供一些算法了。

ok,总结下啦~

可以说,线性表是应用最广泛的一种数据结构了,我们在用的时候,都知道“链表”、"栈"、“队列”等等数据结构,但是线性表还有很多推广应用,如时间表、排序表等。这些大家根据自己的工作需要去深究吧,这里仅仅介绍基础的线性表,达到一个中级开发工程需要具备的数据结构知识。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180424G15NXM00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券