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

2.2线性表的顺序表示和实现用一组地址连续的存储单元依次存储。例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素2.2线性表的顺序表示和实现顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度2.2线性表的顺序表示和实现顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434如何实现顺序表的内存分配？顺序表一维数组逻辑相邻位置相邻如何求得任意元素的存储地址？0…i-2i-1…n-1Listsize-1a1…ai-1ai…an空闲长度2.2线性表的顺序表示和实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)0…i-2i-1…n-1Listsize-1a1…ai-1ai…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线性表的顺序表示和实现#defineLISTINCREMENT10//存储空间的分配增量typedefstruct{

ElemType*elem;

//存储空间基址

intlength;

//线性表当前的大小intlistsize;//当前分配的存储容量}SqList;#defineLIST_INIT_SIZE100

//线性表初始分配量线性表的初始化：2.2线性表的顺序表示和实现StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}

882.2线性表的顺序表示和实现数组下标结点内容线性表中位序0a111a222a33∶∶∶i-1aii∶∶∶n-1ann899顺序表的特点关系线性化结点顺序存91010顺序表的操作实现插入删除查找线性表的合并101111插入运算定义：在第i（1in）个元素前插入一个新的数据元素e，使长度为n的线性表(a1

，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)顺序表的实现——插入ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化12131333例：（35，12，24，42），在a2的位置上插入33。表满：L.length>L.listsize合理的插入位置：1≤i≤L.length（i指的是元素的序号）435122442a1a2a3a401234422412335什么时候不能插入？注意边界条件5.顺序表的实现——插入1314141.

如果元素的插入位置不合理，则插入位置非法;2.如果表满了，则上溢;3.将最后一个元素至第i个元素分别向后移动一个位置；4.将元素e填入位置i处；5.表长加1；算法描述——伪代码顺序表的实现——插入141515StatusListInsert_Sq(SqList&L,inti,ElemTypee){If(i<1||i>L.length+1)returnERROR;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;}//ifq=&(L.elem[i-1]);For(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;ReturnOK;}插入算法：在第i个位置前插入e1616最好情况（i=n+1）：基本语句执行0次，时间复杂度为O(1)。最坏情况（i=1）：基本语句执行n次，时间复杂度为O(n)。平均情况（1≤i≤n+1）：时间复杂度为O(n)。时间性能分析:å+-+=11)=1(niiinpå+-++=11)=1(11niinn2n=O(n)161717运算时间复杂度分析设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的期望值（平均次数）为：171818结点删除运算定义：使长度为n的线性表(a1

，a2

，……，ai-1

，ai

，……，an)变成长度为n-1的线性表(a1

，a2

，……，ai-1

，ai+1

，……，an)算法分析：删除第i（1≤i≤n）个元素，需将从第i+1个元素至第n个元素依次向前移动一个位置。181919删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)

顺序表的实现——删除ai-1和ai+1之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化192020例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出伪代码和C语言描述的算法；3.分析时间复杂度。535a1a2a3a401234422412334a5122442顺序表的实现——删除202121删除运算：删除顺序表中第i个位置元素eStatusListDelete_Sq(SqList&L,inti,ElemType&e){If(i<1||i>L.length)returnERROR;p=&(L.elem[i-1]);//删除位置e=*p;q=L.elem+L.length-1;//表尾位置for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}212222算法时间复杂度：设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的(期望值）平均次数为：222323顺序表的实现——按值查找535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系232424查找运算：在顺序表中查找第一个与e满足compare（）的元素位置intLocateElem_Sq(SqListL,ElemTypee,Status(*compare(ElemType,ElemType))){i=1;p=L.elem;//p为第一个元素位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}242525查找算法分析：252n+1å=1=*niiipå=1=1niin=O(n)2626合并运算：合并成一个有序表voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;262727合并运算：while(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顺序存储结构的特点

顺序表的优点：⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；⑵随机存取：可以快速地存取表中任一位置的元素。

顺序表的缺点：⑴插入和删除操作需要移动大量元素；⑵表的容量难以确定，表的容量难以扩充；⑶造成存