資源描述:
《線性表的順序存儲(chǔ).doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、線性表的順序存儲(chǔ)將線性表中的所有數(shù)據(jù)元素按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)內(nèi)存儲(chǔ)器中指定存儲(chǔ)位置開始的一塊連續(xù)的存儲(chǔ)區(qū)域中。數(shù)據(jù)元素之間的邏輯關(guān)系通過數(shù)據(jù)元素的存儲(chǔ)位置直接反映。定義3:動(dòng)態(tài)存儲(chǔ)#defineLIST_Init_Size100(線性表存儲(chǔ)空間的初始分配量)#defineLISTINCREMENT10(線性表存儲(chǔ)空間的分配增量)TypedefStruct{ElemType*elem;//存儲(chǔ)區(qū)域基地址intlength;//當(dāng)前有效長度intlistsize;//當(dāng)前分配的存儲(chǔ)容量}SqList,*PSqList;SqListL;//定義順序表PSqListPL
2、=&L;插入數(shù)據(jù)元素ListInsert(L,i,e)intListInsert(PSqListPL,inti,ElemTypee)//在順序表L中第i個(gè)元素前插入數(shù)據(jù)元素e{if(i<1
3、
4、i>PL->length+1)returnERROR;//i值不合法if(PL->Length>=PL->Listsize){//當(dāng)前分配已滿,增加空間newbase=(ElemType*)realloc(PL->elem,(PL->Listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗
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;}刪除數(shù)據(jù)元素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;}(算法)將兩個(gè)有序(從小到大)的順序表合并成一個(gè)有序的順序表。(1)初始化一個(gè)線性表Lc;(2)分別取La和Lb的當(dāng)前數(shù)據(jù)元素ai和bj;(3)若ai≤bj,則將ai插入到Lc,i++;否則將bj插入到Lc中,j++。(4)重復(fù)第(2)和(3)步直到其中一個(gè)表的數(shù)據(jù)元素取完為止。(5)將未取完的表中所剩數(shù)據(jù)元素,全部復(fù)制到Lc中。voidSqListmerge(SqListp,SqLi
9、stq,PSqListPr){i=j=k=0;InitList(Pr);while(i
elem[k]=p.elem[i];i++;k++;}else{Pr->elem[k]=q.elem[j];j++;k++;}}//endof(ielem[k]=p.elem[i];i++;k++;}while(j10、{Pr->elem[k]=q.elem[j];j++;k++;}Pr->length=k;//或p.length+q.length}順序表應(yīng)用實(shí)例例1設(shè)計(jì)一個(gè)算法,將x插入到一個(gè)有序(從小到大排序)的順序表中,并保持順序表的有序性。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個(gè)位置}PL->length++;}例2已知長度為n的順序表A,設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法,刪除A中所有值為item的數(shù)據(jù)元素。A=(10,15,16,18,19,23,16,17,25,2710151618192316172527voiddelnode(PSqListPA,ElemTypeitem){i=0;while(ilength){if(PA->elem[i]==item){fo