Question

概论- 线性表的逻辑结构- 逻辑结构

Answer 1

　　线性结构是最简单且最常用的数据结构 线性表是一种典型的线性结构

　　线性表的逻辑定义

　　线性表(Linear List)是由n(n≥ )个数据元素(结点)a a … a n 组成的有限序列

　　① 数据元素的个数n定义为表的长度(n= 时称为空表)

　　② 将非空的线性表(n> )记作 (a a … a n )

　　③ 数据元素a i ( ≤i≤n)只是个抽象符号 其具体含义在不同情况下可以不同

　　【例 】英文字母表(A B … Z)是线性表 表中每个字母是一个数据元素(结点)

　　【例 】一副扑克牌的点数( … J Q K A)也是一个线性表 其中数据元素是每张牌的点数

　　【例 】学生成绩表(见概论中表 )中 每个学生及其成绩是一个数据元素 其中数据元素由学号 姓名 各科成绩及平均成绩等数据

　　项组成

　　线性表的逻辑结构特征

　　对于非空的线性表:

　　① 有且仅有一个开始结点a 没有直接前趋 有且仅有一个直接后继a ;

　　② 有且仅有一个终结结点a n 没有直接后继 有且仅有一个直接前趋a n ;

　　③ 其余的内部结点a i ( ≤i≤n )都有且仅有一个直接前趋a i 和一个a i+

　　常见的线性表的基本运算

　　 InitList(L)

　　构造一个空的线性表L 即表的初始化

　　 ListLength(L)

　　求线性表L中的结点个数 即求表长

　　 GetNode(L i)

　　取线性表L中的第i个结点 这里要求 ≤i≤ListLength(L)

　　 LocateNode(L x)

　　在L中查找值为x 的结点 并返回该结点在L中的位置 若L中有多个结点的值和x 相同 则返回首次找到的结点位置;若L中没有结点的值为x

　　 则返回一个特殊值表示查找失败

　　 InsertList(L x i)

　　在线性表L的第i个位置上插入一个值为x 的新结点 使得原编号为i i+ … n的结点变为编号为i+ i+ … n+ 的结点 这里

　　 ≤i≤n+ 而n是原表L的长度 插入后 表L的长度加

　　 DeleteList(L i)

　　删除线性表L的第i个结点 使得原编号为i+ i+ … n的结点变成编号为i i+ … n 的结点 这里 ≤i≤n 而n是原表L的长度 删

　　除后表L的长度减

　　注意

　　以上所提及的运算是逻辑结构上定义的运算 只要给出这些运算的功能是 做什么 至于 如何做 等实现细节 只有待确定了存储结构之后

　　才考虑

　　组合基本运算 实现复杂运算

lishixinzhi/Article/program/sjjg/201311/23377