一、定义
线性表:零个或多个数据元素的有限序列,是逻辑结构呈线性的数据结构。元素之间是有顺序的,元素的前一个元素称为前驱元素,后一个元素称为后继元素。一般表示为:
L = (a1, a2, …, an)
基本操作包括:
- 初始化空的线性表
- 清空线性表
- 获取线性表指定位置元素的值
- 在指定位置插入元素
- 删除指定位置的元素
- 返回线性表的元素个数
二、存储结构
1、顺序存储
可利用数组来实现,按逻辑顺序依次存放到数组a中,a[0]放第一个元素,a[1]放第二个元素,依次类推。
- 直接访问指定位置的元素(索引访问)
- 插入:插入新结点,之后结点后移
- 删除:删除节点,之后结点前移
2、链式存储
可利用链表来实现,数据域存放数据元素,指针域指向前驱和后继结点。
- 通过指针域递归查找访问元素
- 插入:修改前后结点的指针域
- 删除:连接前后结点的指针域,释放删除结点所占存储空间 根据指针域的不同,可分为:
- 单向链表(简称:单链表):指针域为后继结点地址
- 双向链表:指针域包括前驱和后继结点地址
- 循环链表:头结点作为尾结点的后继结点
- 静态链表:把指针转化为游标,和数据元素一起存放到数组中
静态链表存储空间虽然是连续的,但存储的元素是没有顺序的,所以属于链式存储
三、栈
1、定义
限定仅在一端进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈,从一个栈删除元素称作出栈或退栈。没有元素的栈称为空栈,栈元素总是后进先出,一般用数组实现
基本操作包括:
- 入栈:把新元素放到栈顶元素的上面,使之成为新的栈顶元素
- 出栈:取出栈顶元素,使其相邻的元素成为新的栈顶元素
2、分类
按存储方式的不同可分为两类:
- 顺序存储栈:顺序存储结构,用数组存储元素,数组最后一个元素为栈顶
- 链栈:链式存储结构,插入和删除操作仅限制在链头位置上进行,栈顶指针就是链表的头指针
四、队列
1、定义
限定在一端进行插入和另一端进行删除的线性表。插入的这端被称为队尾,删除的这端称为队头。向一个队列插入新元素称作入队,从一个队列删除元素称作出队。没有元素的队列称为空队列,队列元素总是先进先出
基本操作包括:
- 入队:把新元素放到队尾的后面,使之成为新的队尾
- 出队:取出队头元素,使下一个的元素成为新的队头
2、分类
按存储方式的不同可分为两类:
- 循环队列:顺序存储结构,
- 链队列:链式存储结构,在表尾插入新的元素,在表头进行删除操作
五、串
1、定义
串是零个或多个字符组成的有限序列,又称为字符串,是数据元素为字符的线性表。线性表关注的是单个元素的操作,比如增删查一个元素,而串通常以整体作为操作对象,如在串中查找某个子串、求取一个子串等等。由于字符串的特殊性,一般直接使用数组存储。
2、基本操作
求串长:获取字符串长度
串连接:把两个字符串拼接成一个字符串
求子串:从指定位置截取N个字符作为新的字符串
子串查找:查找指定字串第一次出现的位置
串插入:在指定位置插入字符串
串删除:从指定位置删除N个字符