第2章+线性表_1_顺序表.ppt

第2章线性表 2 1线性表的定义和运算 一 线性表的定义 1 定义 线性表L是由n个元素a1 a2 an组成的有限序列 记作L a1 a2 an 注 1 n 0为表长 2 n 0时为L空表 记作L 如 字母表 A B C Z 数字表 0 1 2 3 9 同一表中 元素类型相同 2 特点 ai 1 ai ai 1 ai 1称为ai的直接前驱 ai 1称为ai的直接后继 除首元素外每个元素有且仅有一个直接前驱 除尾元素外每个元素有且仅有一个直接后继 二 线性表的基本运算 1 初始化initial list L 建空表 2 求表长list length L 3 按序号取元素get element L i 4 按值查找list locate L x 5 插入list insert L i x 在表中第i个位置上插入元素x 1 i n 1 6 删除list delete L i 删除表中第i个元素 1 i n 2 2顺序表 一 线性表的顺序存储结构 1 定义 假设有一个足够大的连续的存储空间 将线性表中的元素按其逻辑次序依次存储到这一存储空间中 由此方式存储的线性表称为顺序表 顺序表示意图 n 1 2 类型描述 definemaxlen100typedefstruct elementtypedata maxlen intlistlen seqlist 变量定义 如 seqlistL L1 注 a data maxlen 的下标是0到maxlen 1 b listlen是线性表的长度 最后一个元素下标是listlen 1 3 顺序表的特点 逻辑上相邻的元素 其存储地址也相邻 即 可以随机存取元素 二 顺序表运算的实现 1 初始化 建空表 voidinitial list seqlist L L listlen 0 2 求表长 intlist length seqlistL returnL listlen 3 按序号取元素 voidget element seqlistL inti elementtype 4 按值查找 找到则返回其序号 否则返回0 intlist locate seqlistL elementtypex inti for i 0 i L listlen i if L data i x return i 1 return 0 5 插入 分析 首先判断顺序表是否为满 以及i的取值 若可以插入 则执行下列操作 1 将ai an后移一位 2 插入x 3 表长 1 voidlist insert seqlist L inti elementtypex intj if L listlen maxlen error 溢出 elseif iL listlen 1 error 序号错误 else for j L listlen 1 j i 1 j L data j 1 L data j L data i 1 x L listlen 插入算法的时间分析在i 1 2 n 1时 元素移动的次数分为n n 1 0 平均移动次数 等概率情况下 0 1 n n 1 n 2 6 删除 分析 首先判断顺序表是否为空以及i的取值 可以则删除 1 ai 1 an往前移一位 2 表长 1 voidlist delete seqlist L inti intj if L listlenL listlen error 序号错误 else for j i jlistlen 1 j L data j 1 L data j L listlen 删除算法的时间分析 在i 1 2 n时 元素移动的次数分别为n 1 n 2 0 平均移动次数 0 1 n 1 n n 1 2 三 顺序表的应用 已知顺序表L递增有序 设计算法 在L中插入元素x 使得L依然递增有序 例 算法如下 voidinsert se