数据结构之顺序表.ppt

SCIE UniversityofElectronicScienceandTechnologyofChina 1 第二章线性结构 线性表堆栈队列串二维数组 SCIE UniversityofElectronicScienceandTechnologyofChina 2 2 1线性表 线性表的定义线性表是n个相同类型数据元素的有限线性序列 通常记为 a1 a2 a3 an 线性表特点 各元素数据类型必须相同数据ai可以是数字 字符和记录等例1 1 1 2 3 5 8 13 例2 Sun Mon The wed Thu Fri Sat 例3学生成绩表 SCIE UniversityofElectronicScienceandTechnologyofChina 3 2 1线性表 逻辑结构 元素及元素之间的关系为线性 1 有且仅有一个开始节点 该节点只有一个直接后继节点 没有直接前趋节点 2 有且仅有一个结束节点 该节点只有一个直接前趋节点 没有直接后继节点 3 其余节点有且仅有一个直接前趋和一个直接后继 SCIE UniversityofElectronicScienceandTechnologyofChina 4 2 1线性表 线性表不同的实现方式 2 1 1顺序表数组存储顺序表定义顺序表基本操作 遍历 插入 删除顺序表算法分析2 1 2单链表2 1 3双向链表链接存储2 1 4循环链表 SCIE UniversityofElectronicScienceandTechnologyofChina 5 2 1 1顺序表 一 定义采用顺序存储结构的线性表通常称为顺序表用一组地址连续的存储单元依次存储线性表的数据元素 内存 存储地址 元素序号 12in 特点 实现逻辑上相邻 物理地址相邻随机存取 Loc a1 Loc a1 k Loc a1 i 1 k Loc a1 n 1 k SCIE UniversityofElectronicScienceandTechnologyofChina 6 2 1 1顺序表 可以借助于高级程序设计语言中的数组来表示 数组的下标与元素在线性表中的序号相对应 顺序表说明 typedefstructlist type elemtypedata MAXNUM intlength list type list typelist 问题 如何获得第i的数据元素 list data i 0 i length SCIE UniversityofElectronicScienceandTechnologyofChina 7 2 1 1顺序表 二 顺序表的基本操作遍历 查询 插入删除 SCIE UniversityofElectronicScienceandTechnologyofChina 8 2 1 1顺序表 遍历运算问题描述在第1个元素到第length个元素依次取值 a1a2 ai an SCIE UniversityofElectronicScienceandTechnologyofChina 9 2 1 1顺序表 for i 0 i table length i typedefstructlist type elemtypedata MAXNUM intlength list type list typetable table data i SCIE UniversityofElectronicScienceandTechnologyofChina 10 2 1 1顺序表 插入运算问题描述在第i个元素前插入一个新元素new node a1 a2 ai 1 ai an a1 a2 ai 1 newnode ai 1 逐个向后挪动 SCIE UniversityofElectronicScienceandTechnologyofChina 11 2 1 1顺序表 从ai开始逐个向后 每个元素向后移动从an开始逐个向前 每个元素向后移一格 a1 a2 ai 1 ai ai 1 an ai ai ai ai a1 a2 ai 1 ai ai 1 an an ai 1 ai for j i j table length j table data j 1 table data j for j table length j i j table data j 1 table data j newnode SCIE UniversityofElectronicScienceandTechnologyofChina 12 2 1 1顺序表 算法输入 table 指向线性表的指针new node 需要插入的元素location 插入的位置 在其之前插入输出table 线性表指针 voidinsert table new node location SCIE UniversityofElectronicScienceandTechnologyofChina 13 2 1 1顺序表 算法 搬动节点 腾空位置 在腾空的位置处 放入新的元素 数组长度因为增加了一个新元素而加一 voidinsert table new node location SCIE UniversityofElectronicScienceandTechnologyofChina 14 2 1 1顺序表 voidinsert table new node location for j table length 1 j location j table data j 1 table data j table data location new node table length table length 1 if table length MAXNUM error 1 else if locationtable length error 2 else location location 1 SCIE UniversityofElectronicScienceandTechnologyofChina 15 2 1 1顺序表 voiderror intnumber switch number case1 printf thetableisfull break case2 printf can tinsertatlocation break default printf unknownerror SCIE UniversityofElectronicScienceandTechnologyofChina 16 2 1 1顺序表 an ai 删除运算问题描述 删除第i个元素算法实现分析 a1 a2 ai an ai 1 a1 a2 ai 1 ai 1 删除算法是否与插入算法一样有个方向和过程的问题 SCIE UniversityofElectronicScienceandTechnologyofChina 17 2 1 1顺序表 for j i j table length j table data j table data j 1 for j table length j i j table data j 1 table data j 关键技术分析从an开始逐个向前 每个元素向前移动从ai 1开始逐个向后 每个元素向前移动 a1 a2 ai 1 ai an ai 1 an an an for j table length 1 j i j table data j 1 table data j a1 a2 ai 1 ai ai 1 an for j i j table length 1 j table data j table data j 1 SCIE UniversityofElectronicScienceandTechnologyofChina 18 2 1 1顺序表 算法输入table 线性表指针location 需要删除的节点位置输出table 线性表指针 voiddelete table location SCIE UniversityofElectronicScienceandTechnologyofChina 19 2 1 1顺序表 算法 1 从ai节点开始 向后逐个向前搬动节点 挤掉第i个元素 2 数组长度因为减少了一个新元素而减一 voiddelete table location SCIE UniversityofElectronicScienceandTechnologyofChina 20 2 1 1顺序表 voiddelete table location for j location jlength 1 j table length table length 1 if table length 1 error 3 else if locationtable length error 4 else location location 1 table data j table data j 1 SCIE UniversityofElectronicScienceandTechnologyofChina 21 2 1 1顺序表 voiderror intnumber switch number case1 printf thetableisfull break case2 printf can tinsertatlocation break case3 printf thetableisempty break default printf unknownerror SCIE UniversityofElectronicScienceandTechnologyofChina 22 2 1 1顺序表 编写算法的一般步骤 1 分析问题描述输入 输出及模块功能等2 分析算法实现的总体框架 关键问题的突破方法3 核心算法的实现4 算法补充完善 如 增加算法有效性的保护措施 越界判断等 SCIE UniversityofElectronicScienceandTechnologyofChina 23 2 1 1顺序表 数组顺序存储结构的特点元素随机获取特性 存取时间短 存取时间与位置无关算法效率 时间复杂度 元素更动的搬移性平均N 2次的搬移算法效率 O 1 O n SCIE UniversityofElectronicScienceandTechnologyofChina 24 2 1 1顺序表 例 设线性表的元素个数为N 请计算插入一个节点需要移动的节点的平均个数 观察 在表首插入一个节点 需要搬移的节点个数为 在ai处插入一个节点 则需要搬移