線性表的順序存儲(chǔ).doc

ID:59296738

大?。?9.00 KB

頁數(shù):8頁

時(shí)間:2020-09-06

線性表的順序存儲(chǔ).doc_第1頁
線性表的順序存儲(chǔ).doc_第2頁
線性表的順序存儲(chǔ).doc_第3頁
線性表的順序存儲(chǔ).doc_第4頁
線性表的順序存儲(chǔ).doc_第5頁
資源描述:

《線性表的順序存儲(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(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}順序表應(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

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭