线性表的顺序存储.doc

《线性表的顺序存储.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性表的顺序存储将线性表中的所有数据元素按照其逻辑顺序依次存储到从计算机内存储器中指定存储位置开始的一块连续的存储区域中。数据元素之间的逻辑关系通过数据元素的存储位置直接反映。定义3：动态存储#defineLIST_Init_Size100(线性表存储空间的初始分配量)#defineLISTINCREMENT10(线性表存储空间的分配增量)TypedefStruct{ElemType*elem;//存储区域基地址intlength;//当前有效长度intlistsize；//当前分配的存储容量}SqList,*PSqList;SqListL;//定义顺序表PSqListPL

2、=&L;插入数据元素ListInsert(L,i,e)intListInsert(PSqListPL,inti,ElemTypee)//在顺序表L中第i个元素前插入数据元素e{if(i<1

3、

4、i>PL->length+1)returnERROR;//i值不合法if(PL->Length>=PL->Listsize){//当前分配已满，增加空间newbase=(ElemType*)realloc(PL->elem,(PL->Listsize+LISTINCREMENT）*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败

5、PL->elem=newbase;PL->listsize+=LISTINCREMENT;}q=&(PL->elem[i-1]);//q为插入位置for(p=&(PL->elem[L.length-1];p>=q;--p)*(p+1)=*p;//元素后移*q=e;++PL->length//顺序表长度增1returnOK;}删除数据元素ListDelete(L,i,e)intListDelete(PSqListPL,inti,ElemTypee){if(i<1

6、

7、i>PL->length)returnERROR;p=&(PL->elem[i-1]);e=*p;q=PL->e

8、lem+PL->length-1;//表尾的位置for(++p;p<=q;++p)*(p-1)=*p;//被删位置以后的元素前移--PL->length;//顺序表长度减1returnOk;}(算法)将两个有序(从小到大)的顺序表合并成一个有序的顺序表。（1）初始化一个线性表Lc；（2）分别取La和Lb的当前数据元素ai和bj；（3）若ai≤bj，则将ai插入到Lc，i++；否则将bj插入到Lc中，j++。（4）重复第（2）和（3）步直到其中一个表的数据元素取完为止。（5）将未取完的表中所剩数据元素，全部复制到Lc中。voidSqListmerge(SqListp,SqLi

9、stq，PSqListPr){i=j=k=0;InitList(Pr);while(ielem[k]=p.elem[i];i++;k++;}else{Pr->elem[k]=q.elem[j];j++;k++;}}//endof(ielem[k]=p.elem[i];i++;k++;}while(j

10、{Pr->elem[k]=q.elem[j];j++;k++;}Pr->length=k;//或p.length+q.length}顺序表应用实例例1设计一个算法,将x插入到一个有序(从小到大排序)的顺序表中,并保持顺序表的有序性。voidInsertList(PSqListPL,ElemTypex){i=0;if(x>=PL->elem[PL->length-1])PL->elem[PL->length]=x;//插入表尾else{while(ilength&&PL->elem[i]<=x)i++;for(j=PL->length-1;j>=i;j--)PL->

11、elem[j+1]=PL->elem[j];PL->elem[i]=x;//插入到表的第i个位置}PL->length++;}例2已知长度为n的顺序表A,设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法,删除A中所有值为item的数据元素。A=(10,15,16,18,19,23,16,17,25,2710151618192316172527voiddelnode(PSqListPA,ElemTypeitem){i=0;while(ilength){if(PA->elem[i]==item){fo