共有回帖数 0 个
-
线性结构是最简单且最常用的数据结构。线性表是一种典型的线性结构。
线性表的逻辑定义
线性表(Linear List)是由n(n≥0)个数据元素(结点)a 1 ，a 2 ，…，a n 组成的有限序列。
① 数据元素的个数n定义为表的长度(n=0时称为空表)。
② 将非空的线性表(n0)记作：(a 1 ，a 2 ，…，a n )
③ 数据元素a i (1≤i≤n)只是个抽象符号，其具体含义在不同情况下可以不同。
【例1】英文字母表(A，B，…，Z)是线性表，表中每个字母是一个数据元素(结点)
【例2】一副扑克牌的点数(2，3，…，10，J，Q，K，A)也是一个线性表，其中数据元素是每张牌的点数
【例3】学生成绩表(见概论中表1.1)中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据
项组成。
线性表的逻辑结构特征
对于非空的线性表:
① 有且仅有一个开始结点a 1 ，没有直接前趋，有且仅有一个直接后继a 2 ;
② 有且仅有一个终结结点a n ，没有直接后继，有且仅有一个直接前趋a n-1 ;
③ 其余的内部结点a i (2≤i≤n-1)都有且仅有一个直接前趋a i-1 和一个a i+1 。
常见的线性表的基本运算
1. InitList(L)
构造一个空的线性表L，即表的初始化。
2. ListLength(L)
求线性表L中的结点个数，即求表长。
3. GetNode(L，i)
取线性表L中的第i个结点，这里要求1≤i≤ListLength(L)
4. LocateNode(L，x)
在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置;若L中没有结点的值为x
，则返回一个特殊值表示查找失败。
5. InsertList(L，x，i)
在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。这里
1≤i≤n+1，而n是原表L的长度。插入后，表L的长度加1。
6. DeleteList(L，i)
删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。这里1≤i≤n，而n是原表L的长度。删
除后表L的长度减1。
注意：
以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节，只有待确定了存储结构之后
才考虑。
组合基本运算，实现复杂运算
对于实际问题中涉及的其它更为复杂的运算，可以用基本运算的组合来实现。具体请【参见参考书目】
楼主 2016-04-28 11:47 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
