第2章线性表 2.2顺序表的实现《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第二章 线性表 2.2.2 顺序表的实现（或操作） 回忆：数据结构基本运算操作有： 插入、删除、查找、排序、修改 1)插入 在线性表的第i个位置插入一个元素 实现步骤： 移动元素（ 哪些元素？移动方向？移动次序？） 将第n至第i 位的元素依次向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? 长度为n的线性表变为长度为n+1的线性表 （a1,a2,…,ai-1,ai,…,an） （a1,a2,…,ai-1,x,ai,…,an） 程序： int INSERT(sequenlist *L, datatype x, int i) { int j; if(((*L).last)>=MAXSIZE-1) return(NULL); if ((i<1)||(i>((*L).last)+2)) return(NULL); for(j=(*L).last; j>=i-1; j--) (*L).data[j+1]= (*L).data[j]; (*L).data[i-1]=x; (*L).last ++; return(1); } 实现步骤： 移动元素（ 哪些元素？移动方向？移动次序？） 将第i +1至第n 位的元素依次向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 2)删除 删除线性表的第i个位置上的元素 使：长度为n的线性表变为长度为n-1的线性表。（a1,a2,…,ai-1,ai,ai+1,…,an） （a1,a2,…,ai-1,ai+1,…,an） int DELETE(sequenlist *L，int i) { int j; if ((i<1) ||(i>(*L).last+1)) return NULL; for(j=i; j<=(*L).last; j++) (*L).data[j-1]=(*L).data[j]; (*L).last--; return(1); } 2.2.3 顺序表的运算效率分析 时间效率分析: 插入算法花费的时间，主要在于循环中元素的后移（其它语句花费的时间可以省去），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移动，需n次移动，当i=n＋1时，不需移动元素，故在i位置插入时移动次数为n-i+1 删除算法花费的时间，主要在于循环中元素的前移（其它语句花费的时间可以省去），即从删除位置到最后位置的所有元素都要前移一位.但是，删除的位置是不固定的，当删除位置i=1时，全部元素都得移动，需n-1次移动，当i=n时，不需移动元素，故在i位置删除时移动次数为n-i 假定在表中任意位置插入、删除元素都是等概率的， 插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n ，则： 插入操作时间效率（平均移动次数） 删除操作时间效率（平均移动次数） 显然，顺序表的空间复杂度S(n)=O(1) （没有占用辅助空间） 本节小结 线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑。 缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先分配空间需按最大空间分配，利用不充分;表容量难以扩充。 为克服这一缺点，我们引入另一种存储形式： 链式存储结构 见2.3节 2.3 线性表的链式表示和实现 2.3.1 链表的表示 2.3.2 链表的实现 2.3.3 链表的运算效率分析 2.3.1 链表的表示 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 数据域 指针域 结点 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 43 13 1 NULL 37 7 19 25 数据域 指针域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存储地址 1 7 13 19 25 31 37 43 31 H 头指针 与链式存储有关的术语： 1、结点：数据元素的存储映像。由数据域和指针域两部分组成； 2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。