数据结构——第一章线性表:01线性表的逻辑结构
1.线性结构的基本特征:线性结构是一个数据元素的有序集。
(1)集合中必定存在一个唯一的“第一元素”
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。(2)集合中必定存在一个唯一的“最后元素”
(3)除最后一个元素外,集合中的元素均有唯一的前驱元素
(4)除最后一个元素外,集合中的元素均有唯一的后继元素
2.抽象数据类型(ADT)线性表的定义如下:
ADT List
{
数据对象:D = {ai | ai ∈ ElemSet(元素集) , i = 1, 2,...,n,n >= 0}
(n为线性表的表长,当n = 0时线性表为空表)
数据关系:R = {<ai-1,ai>|ai-1,ai ∈ D, i = 2,...,n}
(尖括号代表数据元素具有方向性,ai-1是ai的直接前驱,ai是ai-1的直接后继,称i为ai在线性表中的位序)
基本操作:
(1)结构初始化操作:initList(&L)————构造一个空线性表L
(2)引用型操作:仅使用线性表不对线性表进行修改
①listEmpty(L)————判断线性表L是否为空
②listLength(L)————返回线性表L表长
③preElement(L, currentElem, &preElem)————将线性表L中当前元素的直接前驱元素存入preElem
④nextElement(L, currentElem, &nextElem)————将线性表L中当前元素的直接后继元素存入nextElem
⑤getElem(L, i, &elem)————将线性表L中下标为i的元素存入elem(按下标查找)
⑥locateElem(L, elem, equal())————返回线性表L中与元素elem值相等元素的下标(按值查找)
⑦listTraverse(L, traverse())————遍历线性表L
(3)加工型操作:对线性表进行修改
①clearList(&L)————清空线性表L
②modifyElem(&L, i, elem)————将线性表L中下标为i的元素值修改为elem
③listInsert(&L, i, elem)————在线性表L中下标i处插入元素elem
④listDelete(&L, i)————删除线性表L中下标为i的元素
(4)结构销毁操作:destroyList(&L)——销毁线性表L(前提条件:存在线性表L)
} ADT List
3.有序表:若线性表中的数据元素之间可以比较,并且数据元素值在表中呈非递增或非递减排列,则称该线性表为有序表。