第二章_线性表课1.ppt

2.插入：在线性表的第i个位置前插入一个元素， 并保持数据的大小顺序。 实现步骤： 找到需要插入的位置i，将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? （a1,a2,…,ai-1,ai,…,an） （a1,a2,…,ai-1,x,ai,…,an） 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 插入算法C语言描述如下： Status ListInsert_Sq(SqList L, int i, ElemType e) { //在顺序表L中第i个位置之前插入新元素e if (i1||iL.length+1) return ERROR; //非法的位置 if (L.length=L.listsize) { //当前空间已满，增加分配： 　 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)) ; * 2.2 线性表的顺序表示和实现 if (!newbase) exit (OVERFLOW); L.elem = newbase; //新基址 L.listsize+=LISTINCREMENT; //增加存储容量 } q=(L.elem[i-1]); //定位位置i，对应数组下标为i-1 for (p=(L.elem[L.length-1]), p=q; --p) *(p+1)=*p; // 插入位置及之后的元素后移一个单元 *q=e; //e插入位置i L.length++; // 表长增1 return OK; }//ListInsert_Sq 算法结果演示..\数据结构-光盘\DS-Algo-VC * 实现步骤： 将第i +1至第n 位的元素向前移动一个位置； 表长减1。 注意： 事先需要判断，删除位置i 是否合法? 如果要删除学号为2的学生记录，如何进行？线性表的其它功能如何实现才可以方便使用？ 3.删除：删除线性表的第i个位置上的元素，使长度为n的线性表变为长度为n-1的线性表。 （a1,a2,…,ai-1,ai,ai+1,…,an） （a1,a2,…,ai-1,ai+1,…,an） 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 线性表的删除操作算法C语言描述如下： Status ListDelete_Sq(SqList L, int i, ElemType e) { //删除L中第i个元素，后面的元素前移 if (i1 || iL.length) return ERROR; // i值不合法 p = (L.elem[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p=q; ++p) *(p-1) = *p; // 被删除元素之后元素左移 --L.length; // 表长减1 return OK; } // ListDelete_Sq 算法结果演示：..\数据结构-光盘\DS-Algo-VC * 2.2 线性表的顺序表示和实现 /102 时间效率分析: 插入算法花费的时间，主要在于循环中元素的后移。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移动，需n次移动，当i=n时，不需移动元素，故在i位置插入时移动次数为n-i+1。 删除算法花费的时间，主要在于循环中元素的前移.但是，删除的位置是不固定的，当删除位置i=1时，全部元素都得移动，需n-1次移动，当i=n时，不需移动元素，故在i位置删除时移动次数为n-i-1. 假定在表中任意位置插入、删除元素都是等概率的， 插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n ，则： 插入操作时间效率（平均移动次数） 删除操作时间效率（平均移动次数） 显然，顺序表的空间复杂度S(n)=O(1) （没有占用辅助空间） 本节小结 线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑 缺点：在插入，删除某一元素时