|
线性结构是最简单且最常用的数据结构线性表是一种典型的线性结构 线性表的逻辑定义 线性表(Linear List)是由n(n≥)个数据元素(结点)a a …a n 组成的有限序列 ① 数据元素的个数n定义为表的长度(n=时称为空表) ② 将非空的线性表(n>)记作(a a …a n ) ③ 数据元素a i (≤i≤n)只是个抽象符号其具体含义在不同情况下可以不同 【例】英文字母表(AB…Z)是线性表表中每个字母是一个数据元素(结点) 【例】一副扑克牌的点数(…JQKA)也是一个线性表其中数据元素是每张牌的点数 【例】学生成绩表(见概论中表)中每个学生及其成绩是一个数据元素其中数据元素由学号姓名各科成绩及平均成绩等数据 项组成 线性表的逻辑结构特征 对于非空的线性表: ① 有且仅有一个开始结点a 没有直接前趋有且仅有一个直接后继a ; ② 有且仅有一个终结结点a n 没有直接后继有且仅有一个直接前趋a n ; ③ 其余的内部结点a i (≤i≤n)都有且仅有一个直接前趋a i 和一个a i+ 常见的线性表的基本运算 InitList(L) 构造一个空的线性表L即表的初始化 ListLength(L) 求线性表L中的结点个数即求表长 GetNode(Li) 取线性表L中的第i个结点这里要求≤i≤ListLength(L) LocateNode(Lx) 在L中查找值为x 的结点并返回该结点在L中的位置若L中有多个结点的值和x 相同则返回首次找到的结点位置;若L中没有结点的值为x 则返回一个特殊值表示查找失败 InsertList(Lxi) 在线性表L的第i个位置上插入一个值为x 的新结点使得原编号为ii+…n的结点变为编号为i+i+…n+的结点这里 ≤i≤n+而n是原表L的长度插入后表L的长度加 DeleteList(Li) 删除线性表L的第i个结点使得原编号为i+i+…n的结点变成编号为ii+…n的结点这里≤i≤n而n是原表L的长度删 除后表L的长度减 注意 以上所提及的运算是逻辑结构上定义的运算只要给出这些运算的功能是做什么至于如何做等实现细节只有待确定了存储结构之后 才考虑 组合基本运算实现复杂运算 对于实际问题中涉及的其它更为复杂的运算可以用基本运算的组合来实现 |
