插入算法执行时间 元素总个数为n,各个位置插入 的概率相等为p=1/n 平均移动元素次数为 ∑1/n°(m-1)≈ 12 0 ■总时间开销估计为O(n) back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 11
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 back next 插入算法执行时间 元素总个数为n，各个位置插入 的概率相等为p＝1/n 平均移动元素次数为 总时间开销估计为O（n） n-1 i 0 1/ ( - ) 2n n ni =∑ • ≈
删除算法时间代价 与插入操作相似,Omn) 顺序表存取元素方便,时间代价 为O(1) 但插入、删除操作则付出时间代 价O(m) back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 12
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 back next 删除算法时间代价 与插入操作相似，O(n) 顺序表存取元素方便，时间代价 为O(1) 但插入、删除操作则付出时间代 价O(n)
23链表( linked list) 令单链表 令双链表 令循环链表 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 13
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 back next 2.3 链表(linked list) 单链表 双链表 循环链表
first指向特殊的头结点 引入头结点有利于特殊情况的处理 空链表 链表头 ■i按照c/C++数组下标编号的规则 从0到n-1 链表的第0个结点为frst>ink back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 14
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 back next first指向特殊的头结点 引入头结点有利于特殊情况的处理 空链表 链表头 i按照C/C++数组下标编号的规则 从0到n-1 链表的第0个结点为first->link
单链表的存储结构 单链表 first- last 空的单链表 first data字段 last link字段 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 15
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 back next 单链表的存储结构 first a0 a1 a2 an-1 last 单链表 空的单链表 first last data字段 link字段