数据结构2-1b.pdf

数据结构 主讲：胡圣荣 线性表是最简单、最 常见的一种数据结构。线 性表的知识也是栈、队列、 串等数据结构的基础。 2.1 线性表的概念 2.2 顺序表 2.3 链表 2.4 顺序表与链表的比较 一、定义 线性表(Linear List)：n(n0)个数据元素a , a , …, 1 2 a 组成的有限序列，一般记作L=(a , a , …, a )。 n 1 2 n 其中， L为线性表的名字。 数据元素的个数n定义为表的长度。 当n=0时称为 空表，记作( )或Φ。 例1 数列 (11, 13, 15, 17, 19, 21)。 例2 英文字母表 (A, B, C, D, E, …, Z)。 例3 电话号码表 姓 名 电话号码 蔡 颖 陈 红 刘建平 王小林 张 力 … 例3 电话号码表 姓 名 电话号码 注意有序排列 蔡 颖 陈 红 不是无序集合 刘建平 {11,13,15,17} 王小林 张 力 … 二、逻辑结构 线性：第一个元素无前趋，最后一 个元素无后继，其它每个元素有且 仅有一个直接前趋和一个直接后继。 三、基本运算 1. 初始化INITIATE(L)： 建一空表。之后其它操作才能进行。 2. 求表长LENGTH(L) ： 3. 读表元 (按序号找)GET(L, i) ： 得到值或地址。 三、基本运算 4. 定位 (按值找)LOCATE(L, x) ： 得到序号或地址。 5. 插入INSERT(L, x, i) ： 6. 删除DELETE(L, i) ： 7. 排序* 三、基本运算 实际问题中基本运算的种类和个数可能不同。 非基本运算：修改第i个元素SET(L, i, x)、求 前趋PRIOR(L, x)和后继NEXT(L, x)、判空EMPTY(