数据结构 线性表

星期六, 8月 3, 2019 | 3分钟阅读 | 更新于 星期二, 3月 14, 2023

@

一、定义

线性表:零个或多个数据元素的有限序列,是逻辑结构呈线性的数据结构。元素之间是有顺序的,元素的前一个元素称为前驱元素,后一个元素称为后继元素。一般表示为:

L = (a1, a2, …, an)

基本操作包括:

  • 初始化空的线性表
  • 清空线性表
  • 获取线性表指定位置元素的值
  • 在指定位置插入元素
  • 删除指定位置的元素
  • 返回线性表的元素个数

二、存储结构

1、顺序存储

可利用数组来实现,按逻辑顺序依次存放到数组a中,a[0]放第一个元素,a[1]放第二个元素,依次类推。

  • 直接访问指定位置的元素(索引访问)
  • 插入:插入新结点,之后结点后移
  • 删除:删除节点,之后结点前移

2、链式存储

可利用链表来实现,数据域存放数据元素,指针域指向前驱和后继结点。

  • 通过指针域递归查找访问元素
  • 插入:修改前后结点的指针域
  • 删除:连接前后结点的指针域,释放删除结点所占存储空间 根据指针域的不同,可分为:
  • 单向链表(简称:单链表):指针域为后继结点地址
  • 双向链表:指针域包括前驱和后继结点地址
  • 循环链表:头结点作为尾结点的后继结点
  • 静态链表:把指针转化为游标,和数据元素一起存放到数组中

静态链表存储空间虽然是连续的,但存储的元素是没有顺序的,所以属于链式存储

三、栈

1、定义

限定仅在一端进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈,从一个栈删除元素称作出栈或退栈。没有元素的栈称为空栈,栈元素总是后进先出,一般用数组实现 栈.png 基本操作包括:

  • 入栈:把新元素放到栈顶元素的上面,使之成为新的栈顶元素
  • 出栈:取出栈顶元素,使其相邻的元素成为新的栈顶元素

2、分类

按存储方式的不同可分为两类:

  • 顺序存储栈:顺序存储结构,用数组存储元素,数组最后一个元素为栈顶
  • 链栈:链式存储结构,插入和删除操作仅限制在链头位置上进行,栈顶指针就是链表的头指针

四、队列

1、定义

限定在一端进行插入和另一端进行删除的线性表。插入的这端被称为队尾,删除的这端称为队头。向一个队列插入新元素称作入队,从一个队列删除元素称作出队。没有元素的队列称为空队列,队列元素总是先进先出

基本操作包括:

  • 入队:把新元素放到队尾的后面,使之成为新的队尾
  • 出队:取出队头元素,使下一个的元素成为新的队头

2、分类

按存储方式的不同可分为两类:

  • 循环队列:顺序存储结构,
  • 链队列:链式存储结构,在表尾插入新的元素,在表头进行删除操作

五、串

1、定义

串是零个或多个字符组成的有限序列,又称为字符串,是数据元素为字符的线性表。线性表关注的是单个元素的操作,比如增删查一个元素,而串通常以整体作为操作对象,如在串中查找某个子串、求取一个子串等等。由于字符串的特殊性,一般直接使用数组存储。

2、基本操作

  • 求串长:获取字符串长度

  • 串连接:把两个字符串拼接成一个字符串

  • 求子串:从指定位置截取N个字符作为新的字符串

  • 子串查找:查找指定字串第一次出现的位置

  • 串插入:在指定位置插入字符串

  • 串删除:从指定位置删除N个字符

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~