第二章线性表.ppt

东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 本章主要内容 线性表 顺序表 单链表 线性表的变形 双向链表 循环链表 多项式及其运算 * 线性表 定义：n个数据元素的有限序列，记为(a1,a2,…,an) ai是线性表中的数据元素 n是线性表的长度 线性表的性质 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 * a1 an 线性表 线性表的一些基本操作 查找 插入 删除 ?????? 线性表的存储方式 基于数组 (顺序表) 基于链表 (链表) 基于散列 (散列表) …… * 顺序表 顺序表是线性表基于数组的存储表示 * a1 a2 ??? ai ai+1 ??? an ??? 0 1 n-1 i i-1 存储空间 下标 SIZE-1 顺序表 顺序表的查找操作 * Search(Type x) { for(i=0; in; i++) if(a[i] == x) return i+1; return 0; } 平均比较次数 假设每个值查找概率相同 ??? 0 1 4 3 2 5 6 25 34 57 16 48 09 63 查找16 顺序表 顺序表的插入操作 * ??? 0 1 4 3 2 5 6 7 25 34 57 16 48 09 63 50 平均移动次数： 插入 顺序表大小加1 顺序表 顺序表的删除操作 * ??? 0 1 4 3 2 5 6 25 34 57 16 48 09 63 平均移动次数： 删除16 顺序表大小减1 顺序表 顺序表的优点 无需保存与逻辑关系相关的信息 给定下标时，存取速度快 顺序表的缺点 插入删除操作移动开销大 需要固定的存储空间 * 单链表 单链表也是线性表的一种存储表示 * data link 单链表的一个结点： a1 first a2 a3 an null ??? 单链表结构： struct LinkNode { Type data; LinkNode *link; }; LinkNode *first = null; 单链表 单链表的查找操作 * 查找a3 a1 first a2 a3 an ??? null p = first; while (p!=null) { if(p-data == a3)　{ return p; } p = p-link; } return null; p p p 单链表 单链表的插入操作 在非空表头部或空表插入 * first a1 a2 ??? pnew-link = first; first = pnew; anew pnew null 单链表 单链表的插入操作 在非空表头部或空表插入 在非空表中部或尾部插入 * ai ai+1 ??? pnew-link = p-link; p-link = pnew; anew p null pnew ??? 单链表 单链表的删除操作 在单链表头部删除 * first a1 a2 ??? p = first; first = first-link; delete p; p 单链表 单链表的删除操作 在单链表头部删除 在单链表中部或尾部删除 * ai ai+1 ??? p temp = p-link; p-link = temp-link; delete temp; ??? ai+2 temp 单链表 单链表的删除操作 在单链表头部删除 在单链表中部或尾部删除 空链表删除：无结点删除 * 带附加头结点的单链表 附加头结点 * struct LinkNode { Type data; LinkNode *link; }; 带附加头结点时头指针初始化： LinkNode *first = new LinkNode; first-link = null; 不带附加头结点头指针初始化： LinkNode *first = null; a1 first a2 a3 an null ??? 不带附加头结点单链表结构： a1 first a2 a3 an null ??? 带附加头结点单链表结构： 带附加头结点的单链表 附加头结点 插入操作(空表、表头、中部、尾部操作相同) * a1 first a2 a3 an null ??? ax pnew null 带附加头结点的单链表 附加头结点 插入操作(空表、表头、中部、尾部操作相同) 删除操作(表头、中部、尾部操作相同) * a1 first