VB公共基础 第1讲 - 算法与数据结构 - 图文(5)

1.3.1 线性表的基本概念线性表：由n(n≥0)个相同类型数据元素构成的有限序列：(a1,a2,?,ai,?an)n定义为线性表的表长；n=0 时的线性表被称为空表。称i为在线性表中的位序。例如：?英文大写字母表（A，B，C，D，E，F，…X，Y，Z）?同一花色的13张扑克牌?(2,3,4,5,6,7,8,9,10,J,Q,K,A)211.3.1 线性表的基本概念线性表的结构特征?数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；?对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的存储结构?顺序存储?链式存储221.3.2 线性表的顺序存储结构两个基本特点：?线性表中所有元素所占的存储空间是连续的。?线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。存储示意图逻辑地址数据元素…12a1a2物理地址Loc(a1)Loc(a1)+k…iaiLoc(a1)+(i-1)k…nanLoc(a1)+(n-1)k…Loc(ai)?Loc(a1)?(i?1)*k231.3.3 顺序表的插入运算1832345678910V(1..10)19305562382136671212345678910V(1..10)19833055623821366712345678910V(1..10)198330556238123621673667(a)长度为8的线性表(b)插入83后，长度变为9(c)插入12后，长度变为10241.3.4 顺序表的删除运算12345678910V(1..10)193055623821366712345678910V(1..10)3030555562623838212136366712345678910V(1..10)305562382167(a)长度为8的线性表(b)删除19后，长度变为7(c)删除36后，长度变为625