数据结构2-2线性表的顺序表示和实现

1、2.2 线性表的顺序表示和实现线性表的顺序表示和实现用一组地址连续的存储单元依次存储。用一组地址连续的存储单元依次存储。例：例：（34, 23, 67, 43）34236743 4存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素2.2 线性表的顺序表示和实现线性表的顺序表示和实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743存储空间的起始位置存储空间的起始位置 4用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的

2、当前长度顺序表的当前长度2.2 线性表的顺序表示和实现线性表的顺序表示和实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743 4如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组逻辑相邻逻辑相邻位置相邻位置相邻如何求得任意元素的存储地址？如何求得任意元素的存储地址？ 0 i-2 i-1 n-1 Listsize-1 a1 ai-1 ai an 空闲空闲 长度长度2.2 线性表的顺序表示和实现线性表的顺序表示和实现顺序表顺序表一般情况下，一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储

3、：的顺序存储：cLoc(ai)Loc(a1) 0 i-2 i-1 n-1 Listsize-1 a1 ai-1 ai an 空闲空闲 长度长度Loc(ai)=Loc(a1) + (i - -1)l随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素2.2 线性表的顺序表示和实现线性表的顺序表示和实现顺序表顺序表一般情况下，一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)C语言中用语言中用一维数组一维数组来表示顺序表：来表示顺序表：2.2 线性表的顺序表示和实现线性表的顺序表示和实现#define LISTINCRE

4、MENT 10 /存储空间的分配增量存储空间的分配增量typedef struct ElemType *elem; /存储空间基址存储空间基址 int length; /线性表当前的大小线性表当前的大小 int listsize; /当前分配的存储容量当前分配的存储容量SqList;#define LIST_INIT_SIZE 100 /线性表初始分配量线性表初始分配量线性表的初始化：线性表的初始化：2.2 线性表的顺序表示和实现线性表的顺序表示和实现Status InitList_Sq (SqList &L) L.elem=(ElemType *) malloc (LIST_INIT_SIZ

5、E * sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; 8 82.2 线性表的顺序表示和实现线性表的顺序表示和实现0a111a222a33 i-1aii n-1ann89 9顺序表的特点顺序表的特点n关系线性化关系线性化n结点顺序存结点顺序存91010n插入插入n删除删除n查找查找n线性表的合并线性表的合并101111定义：定义：在第在第i（1 i n）个元素前插入一个新的数据元素个元素前插入一个新的数据元素e，使长度为使长度为n的线性表的线性表(a1

6、 ， a2 ， ai-1 ， ai ， an)变成长度为变成长度为n+1的线性表的线性表(a1 ， a2 ， ai-1 ，e， ai ， an)111212插入前：插入前：(a1, , ai-1, ai, , an)插入后：插入后：(a1, , ai-1, e , ai, , an)n 顺序表的实现顺序表的实现插入插入ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化12131333例：例：（35，12，24，42），），在在a2的位置上插入的位置上插入33。表满：表满：L

7、.lengthL.listsize合理的插入位置：合理的插入位置：1iL.length（i指的是元素的序号）指的是元素的序号） 435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件n5. 顺序表的实现顺序表的实现插入插入1314141. 如果元素的插入位置不合理，则插入如果元素的插入位置不合理，则插入位置位置非法非法;2. 如果表满了，则如果表满了，则上溢上溢;3. 将最后一个元素至第将最后一个元素至第i个元素分别向后移动一个位置；个元素分别向后移动一个位置；4. 将元素将元素 e 填入位置填入位置i处；处；5. 表长

8、加表长加1；算法描述算法描述伪代码伪代码n 顺序表的实现顺序表的实现插入插入141515Status ListInsert_Sq (SqList &L, int i, ElemType e) If( iL.length +1 ) return ERROR; If(L.length=L.listsize) newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); If(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCRE

9、MENT; /if q=&(L.elemi-1); For(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; Return OK;在第在第i个位置前插入个位置前插入e1616最好最好情况（情况（ i=n+1）：）： 基本语句执行基本语句执行0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（ i=1）：）： 基本语句执行基本语句执行n次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：）： 时间复杂度为时间复杂度为O(n)。时间性能分析时间性能分析: + +- -+ += =11)=1(nii

10、inp + +- -+ + += =11)=1(11niinn2n=O(n)161717 设设Pi是在第是在第i个元素之前插入一个元素个元素之前插入一个元素的的概率，则在概率，则在长度为长度为n的线性表中插入一个元素时，所需移动的元素的线性表中插入一个元素时，所需移动的元素次数的次数的期望值期望值（平均次数平均次数）为：为：+=+-=11)1(niiinPEis nOnTninnEisnPnii=+-+=+=+=112)1(1111则若认为171818定义：定义：使长度为使长度为n的线性表的线性表(a1 ， a2 ， ai-1 ， ai ， an)变成长度为变成长度为n-1的线性表的线性表(a

11、1 ， a2 ， ai-1 ，ai+1 ， an)算法分析：算法分析：删除第删除第i（1i n）个元素，需将从第）个元素，需将从第i+1个元素至第个元素至第n个个元素依次向前移动一个位置。元素依次向前移动一个位置。181919删除前：删除前：( (a1, , ai- -1, ,ai, ,ai+1, , ,an) )删除后：删除后：( (a1, , ,ai- -1, ,ai+1, , ,an) ) 顺序表的实现顺序表的实现删删 除除ai-1和和ai+1之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反

12、映这个变化192020例：（例：（35, 33, 12, 24, 42），），删除删除i=2的数据元素。的数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1. 分析边界条件；分析边界条件；2. 分别给出伪代码和分别给出伪代码和C语言描述的算法；语言描述的算法；3. 分析时间复杂度。分析时间复杂度。 535a1a2a3a40 1 2 3 4422412334a5122442顺序表的实现顺序表的实现删删 除除202121删除顺序表中第删除顺序表中第i个位置元素个位置元素eStatus ListDelete_Sq(SqList &L, int i, ElemType &e)If(i

13、L.length) return ERROR;p=&(L.elemi-1); /删除位置删除位置e=*p;q=L.elem+L.length-1; /表尾位置表尾位置for(+p;p=q;+p) *(p-1)=*p;-L.length;return OK;212222算法时间复杂度：算法时间复杂度：n设设Qi是删除第是删除第i个元素的概率，则在长度为个元素的概率，则在长度为n的线性的线性表中删除一个元素所需移动的元素次数的表中删除一个元素所需移动的元素次数的(期望值）期望值）平均次数为：平均次数为：=-=niideinQE1)( nOnTninnEnQnidei=-=-=121)(11则若认为

14、222323顺序表的实现顺序表的实现按值查找按值查找 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35, 33, 12, 24, 42） 中查找值为中查找值为12的元素，的元素，返回在表中的序号。返回在表中的序号。iii注意序号和下标之间的关系注意序号和下标之间的关系232424在顺序表中查找第一个与在顺序表中查找第一个与e满足满足compare（）的元素位置（）的元素位置int LocateElem_Sq(SqList L, ElemType e,Status (*compare(ElemType, ElemType) i=1;p=L.elem; /p为第一个

15、元素位置为第一个元素位置while(i=L.length &!(*compare)(*p+,e) +i;if(i=L.length) return i;else return 0;242525252n+1 = =1=*niiip = =1=1niin=O(n)2626void MergeList_Sq( SqList La, SqList Lb, SqList &Lc)pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType *) malloc( Lc.listsize * siz

16、eof(ElemType);if(!Lc.elem) exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;262727while(pa=pa_last & pb=pb_last) if(*pa= *pb) *pc+=*pa+; else *pc+=*pb+; while(pa=pa_last) *pc+=*pa+;while(pb=pb_last) *pc+=*pb+; 272828顺序存储结构的特点顺序存储结构的特点 顺序表的优点：顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的无需为表示表中元素之间的逻辑关系而增加额外的存储空间；存储空间； 随机存取：可以快速地存取表中任一位置的元素。随机存取：可以快速地存取表中任一位置的元素。 顺序表的缺点：顺序表的缺点： 插入和删除操作需要移动大量元素；插入和删除操作需要移动大量元素； 表的容量难以确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充； 造成存储空间的造成存储空间的碎片碎片。 282929n 线性表线性表 逻辑结构逻辑结构n顺序顺序表表 存储结构存储结构293030算法练习算法练习n设线性表设线性表La中的数据元素递增有序，试中的数据元素递增有序，试写一算法，将写一算法，将e插入到顺序表的适当位插入到顺序表的适当位