版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
2.2線性表的順序表示和實現(xiàn)用一組地址連續(xù)的存儲單元依次存儲。例:(34,23,67,43)342367434存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素2.2線性表的順序表示和實現(xiàn)順序表——線性表的順序存儲結構例:(34,23,67,43)34236743存儲空間的起始位置4用什么屬性來描述順序表?順序表的容量(最大長度)順序表的當前長度2.2線性表的順序表示和實現(xiàn)順序表——線性表的順序存儲結構例:(34,23,67,43)342367434如何實現(xiàn)順序表的內存分配?順序表一維數(shù)組邏輯相鄰位置相鄰如何求得任意元素的存儲地址?0…i-2i-1…n-1Listsize-1a1…ai-1ai…an空閑長度2.2線性表的順序表示和實現(xiàn)順序表一般情況下,(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隨機存?。涸贠(1)時間內存取數(shù)據(jù)元素2.2線性表的順序表示和實現(xiàn)順序表一般情況下,(a1,a2,…,ai-1,ai,…,an)的順序存儲:cLoc(ai)Loc(a1)C語言中用一維數(shù)組來表示順序表:2.2線性表的順序表示和實現(xiàn)#defineLISTINCREMENT10//存儲空間的分配增量typedefstruct{
ElemType*elem;
//存儲空間基址
intlength;
//線性表當前的大小intlistsize;//當前分配的存儲容量}SqList;#defineLIST_INIT_SIZE100
//線性表初始分配量線性表的初始化:2.2線性表的順序表示和實現(xiàn)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線性表的順序表示和實現(xiàn)數(shù)組下標結點內容線性表中位序0a111a222a33∶∶∶i-1aii∶∶∶n-1ann899順序表的特點關系線性化結點順序存91010順序表的操作實現(xiàn)插入刪除查找線性表的合并101111插入運算定義:在第i(1in)個元素前插入一個新的數(shù)據(jù)元素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)順序表的實現(xiàn)——插入ai-1和ai之間的邏輯關系發(fā)生了變化順序存儲要求存儲位置反映邏輯關系存儲位置要反映這個變化12131333例:(35,12,24,42),在a2的位置上插入33。表滿:L.length>L.listsize合理的插入位置:1≤i≤L.length(i指的是元素的序號)435122442a1a2a3a401234422412335什么時候不能插入?注意邊界條件5.順序表的實現(xiàn)——插入1314141.
如果元素的插入位置不合理,則插入位置非法;2.如果表滿了,則上溢;3.將最后一個元素至第i個元素分別向后移動一個位置;4.將元素e填入位置i處;5.表長加1;算法描述——偽代碼順序表的實現(xiàn)——插入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):基本語句執(zhí)行0次,時間復雜度為O(1)。最壞情況(i=1):基本語句執(zhí)行n次,時間復雜度為O(n)。平均情況(1≤i≤n+1):時間復雜度為O(n)。時間性能分析:?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)161717運算時間復雜度分析設Pi是在第i個元素之前插入一個元素的概率,則在長度為n的線性表中插入一個元素時,所需移動的元素次數(shù)的期望值(平均次數(shù))為: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)
順序表的實現(xiàn)——刪除ai-1和ai+1之間的邏輯關系發(fā)生了變化順序存儲要求存儲位置反映邏輯關系存儲位置要反映這個變化192020例:(35,33,12,24,42),刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作,完成:1.分析邊界條件;2.分別給出偽代碼和C語言描述的算法;3.分析時間復雜度。535a1a2a3a401234422412334a5122442順序表的實現(xiàn)——刪除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的線性表中刪除一個元素所需移動的元素次數(shù)的(期望值)平均次數(shù)為:222323順序表的實現(xiàn)——按值查找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順序存儲結構的特點
順序表的優(yōu)點:⑴無需為表示表中元素之間的邏輯關系而增加額外的存儲空間;⑵隨機存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑亍?/p>
順序表的缺點:⑴插入和刪除操作需要移動大量元素;⑵表的容量難以確定,表的容量難以擴充;⑶造成存
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 餐飲公司員工培訓
- 食堂大灶點火規(guī)范培訓
- 廣東省佛山市禪城區(qū)2023-2024學年四年級上學期月考英語試卷(12月份)
- 廣東省江門市蓬江區(qū)省實學校2023-2024學年高一上學期期中考試 化學試題(無答案)
- 信息技術(第2版)(拓展模塊) 教案 項目3、4 DHCP服務器的配置與管理;4 物聯(lián)網(wǎng)
- T-ZFDSA 10-2024 沙棘面制作標準
- Windows Server網(wǎng)絡管理項目教程(Windows Server 2022)(微課版)課件 易月娥 項目5、6 Web和FTP服務器的配置與管理、證書服務器的配置與管理
- 高中語文第1章寫作的多樣性與獨特性第2節(jié)聯(lián)想與想象課件新人教版選修文章寫作與修改
- 骨盆臨床解剖
- 環(huán)保行動未來在手-共筑綠色生活守護地球家園
- 發(fā)給客戶ap82-sdk包-卡拉mvkaraoke dsp應用簡要說明
- 2023年山東省高中物理合格考真題
- 通力電梯技能培訓教材系列:《KCE控制系統(tǒng)課程》
- 社區(qū)衛(wèi)生服務中心安全生產工作計劃
- English-Drama英語戲劇寫作及表演技巧課件
- 模板-偵查階段第二次會見筆錄
- 2023年全科醫(yī)師轉崗培訓理論考試試題及答案
- 2023年惠州仲愷城市發(fā)展集團有限公司招聘筆試題庫及答案解析
- 衛(wèi)生協(xié)管員培訓考試題附答案
- 小學語文學習情況評價表
- 坐井觀天(動畫)課件
評論
0/150
提交評論