chap002_线性表.ppt

  1. 1、本文档共70页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
chap002_线性表

(a1, …, ai-1, ai, …, an) 改变为 (a1, …, ai-1, e, ai, …, an) a1 a2 … ai-1 ai … an a1 a2 … ai-1 … ai e an ai-1, ai ai-1, e, e, ai 表的长度增加 插入操作ListInsert_Sq(L, i, e) 内存 a1 a2 ai ai+1 an 0 1 i-1 数组下标 n-1 i n 1 2 i 位序 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 数组下标 n-1 i n 1 2 i 位序 i+1 n n+1 an-1 e q p For( p; p=q;--p) (L.elem[i-1]) (L.elem[L.length-1]) *(p+1)=*p *q=e; ++L.length; q 内存 a1 a2 ai ai+1 an 0 1 i-1 数组下标 n-1 i n 1 2 i 位序 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 数组下标 n-1 i n 1 2 i 位序 i+1 n n+1 an-1 e q p For( p; p=q;--p) =(L.elem[i-1]) =(L.elem[L.length-1]) *(p+1)=*p *q=e; ++L.length; q Status ListInsert_Sq(SqList L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1 } // ListInsert_Sq q = (L.elem[i-1]); // q 指示插入位置 for (p = (L.elem[L.length-1]); p = q; --p) *(p+1) = *p; *q = e; // 插入e ++L.length; // 表长增1 return OK; …… 算法时间复杂度为: O( ListLength(L) ) if (L.length = L.listsize) { // 当前存储空间已满,增加分配 newbase = (ElemType *) realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) exit(OVERFLOW); // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } if (i 1 || i L.length+1) return ERROR; // 插入位置不合法 算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率,则在长度为n的线性表中插入一个元素时,所需移动的元素次数的平均次数为: 21 18 30 75 42 56 87 21 18 30 75 例如:ListInsert_Sq(L, 5, 66) L.length-1 0 p p p q 87 56 42 66 p q = (L.elem[i-1]); // q 指示插入位置 for (p = (L.elem[L.length-1]); p = q; --p) *(p+1) = *p; (a1, …, ai-1, ai, ai+1, …, an) 改变为 (a1, …, ai-1, ai+1, …, an) ai+1 … an ai-1, ai, ai, ai+1 ai-1, ai+1 表的长度减少 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 删除操作ListDelete(L, i, e) 内存 a1 a2 ai ai+1 an 0 1 i-1 数组下标 n-1 i n 1 2 i

文档评论(0)

erfg4eg + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档