线性结构是最简单且最常用的数据结构。线性表是一种典型的线性结构。 ; |3 O7 I5 }/ G& @% ~
d) w9 V# [% C% F/ u线性表的逻辑定义
+ \+ a6 Q4 b. g! {3 O% n- Z; f& R" J) C& i) x- G" p* I
线性表(linear list)是由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。5 Q9 d; ?; z9 r% z
① 数据元素的个数n定义为表的长度(n=0时称为空表)。% e$ z) u/ g1 j. s+ a& }5 G8 r
% ]0 j6 `) s8 G: k) P
② 将非空的线性表(n>0)记作:(a1,a2,…,an)
+ e! X: J0 ?5 c/ @2 n+ O ③ 数据元素ai(1≤i≤n)只是个抽象符号,其具体含义在不同情况下可以不同。
0 C" j8 y) y3 t5 d7 f8 V 【例1】英文字母表(a,b,…,z)是线性表,表中每个字母是一个数据元素(结点)
+ W. j2 Z% n! } n7 M$ G 【例2】一副扑克牌的点数(2,3,…,10,j,q,k,a)也是一个线性表,其中数据元素是每张牌的点数
5 t, O# o2 {) H3 G9 T 【例3】学生成绩表(见概论中表1.1)中,每个学生及其成绩是一个数据元素,其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。, J/ }+ V y0 g% u, t. T. b
3 |0 }: l. g# x& W% K/ U( O
线性表的逻辑结构特征: k3 n- I9 {: [" D. j# L, c9 ?+ r
# A0 K' F7 s, o
对于非空的线性表:- C0 Z# |. h* T/ M6 s- _
① 有且仅有一个开始结点a1,没有直接前趋,有且仅有一个直接后继a2;
) K% r p% T! b; D; M. U4 I1 G( u ② 有且仅有一个终结结点an,没有直接后继,有且仅有一个直接前趋an-1;; K$ r1 p! p0 e: t# t8 l
③ 其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个ai+1。" K4 W! V2 e& l1 `: L6 }# z! a
常见的线性表的基本运算7 I! a9 R- e7 D+ ^6 @7 c' g! u1 v
8 @2 b1 k7 K) F0 D! {1. initlist(l)
2 p% a5 C+ |# j' @. F% V 构造一个空的线性表l,即表的初始化。
( c9 Y3 b& w2 I" }2. listlength(l) 2 t, `, C5 @) y) k. a/ C6 A! m
求线性表l中的结点个数,即求表长。$ _7 U7 v7 Y8 Z# T \ Q
3. getnode(l,i) P, P7 U2 y- V
取线性表l中的第i个结点,这里要求1≤i≤listlength(l)% ~/ U- l" O7 _7 g+ }+ d6 O* U
4. locatenode(l,x) * n% ~ F) Z: D& I
在l中查找值为x 的结点,并返回该结点在l中的位置。若l中有多个结点的值和x 相同,则返回首次找到的结点位置;若l中没有结点的值为x ,则返回一个特殊值表示查找失败。
( f% Q5 g5 J/ a, g8 @ z, G5. insertlist(l,x,i) 6 u) J& D7 i; |1 c
在线性表l的第i个位置上插入一个值为x 的新结点,使得原编号为i,i+1,…,n的结点变为编号为i+1,i+2,…,n+1的结点。这里1≤i≤n+1,而n是原表l的长度。插入后,表l的长度加1。* ~# [0 {( L7 V$ k* F8 h" [: Z
6. deletelist(l,i) 2 ~; O$ O# ]7 Y% H9 u
删除线性表l的第i个结点,使得原编号为i+1,i+2,…,n的结点变成编号为i,i+1,…,n-1的结点。这里1≤i≤n,而n是原表l的长度。删除后表l的长度减1。
; v" ?" a; i. M% U8 D- P) u" A* N+ Y8 p% L2 M
注意:
) Y* q/ d& ~4 z K9 ^& x 以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么",至于"如何做"等实现细节,只有待确定了存储结构之后才考虑。) z6 H1 J3 } k
- k7 y, u6 u& ^$ H
组合基本运算,实现复杂运算 ' v& ?& b4 T8 P b4 m8 {( c
9 m6 L3 Y% E% z, U
对于实际问题中涉及的其它更为复杂的运算,可以用基本运算的组合来实现。 |