




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
線性表(List)邏輯結(jié)構(gòu)和主要操作順序存儲(chǔ)結(jié)構(gòu)部分操作的實(shí)現(xiàn)小結(jié)和作業(yè)第一頁(yè),共六十頁(yè)。邏輯結(jié)構(gòu)D={a1,
a2,
…,
ai
,an}S={
<ai-1
,ai
>|ai-1
,ai
∈
D,
i=2,...,n
}第二頁(yè),共六十頁(yè)。主要操作InitList(&L)DestroyList(&L)ClearList(&L)ListInsert(&L,
i,
e)ListDelete(&L,
i,
&e)LocateElem(L,
e,
Compare())GetElem(L,
i,
&e)PriorElem(L,
cur_e,
&pre_e)NextElem(L,
cur_e,
&next_e)ListEmpty(L)ListLength(L)第三頁(yè),共六十頁(yè)。順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素a1a2…ai-1ai…
an線性表的起始地址(基地址)第四頁(yè),共六十頁(yè)。定義數(shù)據(jù)類型
SqList#define#definetypedefLIST_INIT_SIZE
100LISTINCREMENT
10struct{ElemTypeintint*elem;length;listsize;}
SqList;第五頁(yè),共六十頁(yè)。使用
SqListSqList
L;Lelemlengthlistsizeint
a;第六頁(yè),共六十頁(yè)?!璭lemlength=6listsize=
100L使用SqList第七頁(yè),共六十頁(yè)。部分操作的實(shí)現(xiàn)InitList(&L)DestroyList(&L)ListInsert(&L,
i,
e)ListDelete(&L,
i,
&e)GetItem(L,
i,
&e)ListMerge(&La,
Lb)ListMerge(La,
Lb,
&Lc)第八頁(yè),共六十頁(yè)。InitList—功能原型:Status
InitList(SqList
&L)作用:給elem,length和listsize賦值過程:1、申請(qǐng)存儲(chǔ)空間,首地址存放到elem2、length=03、listsize=LIST_INIT_SIZE第九頁(yè),共六十頁(yè)。InitList—功能……01
0Lelemlengthlistsize第十頁(yè),共六十頁(yè)。InitList-申請(qǐng)內(nèi)存#include
<malloc.h>elem
=
(ElemType
*)
malloc(LIST_INIT_SIZE
*
sizeof(ElemType))0elem1100elem沒有獲得內(nèi)存,出錯(cuò)第十一頁(yè),共六十頁(yè)。InitListStatus
InitList(SqList
&L){L.elem=(ElemType
*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)
return(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return(OK);}第十二頁(yè),共六十頁(yè)。DestroyList—功能原型:Status
DestroyList(SqList
&L)作用:釋放L以前申請(qǐng)的內(nèi)存過程:1、釋放elem指示的連續(xù)存儲(chǔ)單元2、L.length=03、L.listsize=0第十三頁(yè),共六十頁(yè)。LDestroyList—功能……0610
0第十四頁(yè),共六十頁(yè)。DestroyListStatus
DestroyList(SqList
&L){free(L.elem);L.length=0;L.listsize=0;return(OK);}第十五頁(yè),共六十頁(yè)。GetIem—功能原型:Status
GetItem(SqList
L,int
i,ElemType
&e)作用:取出ai的值過程:1、判斷i的合法性2、e=ai第十六頁(yè),共六十頁(yè)。GetItem—功能L10100a1
a2
a3
a4
a5
a6
a7
a8
a9a10GetItem(L,
6,
e)e第十七頁(yè),共六十頁(yè)。GetIem—合法性判斷線性表中L有l(wèi)ength個(gè)元素a1
a2
a3
...alength數(shù)據(jù)元素的下標(biāo)為1,
2,…,length1≤i≤length第十八頁(yè),共六十頁(yè)。GetItem—ai的位置a1a2
a3
a4a5
a6
a7a8
a9a10數(shù)據(jù)元素elema1
elem
+
0a2
elem
+
1a3elem
+
2ai
elem
+
i
-
1e=*(elem
+
i
–
1)第十九頁(yè),共六十頁(yè)。GetItem—ai的位置a1
a2
a3
a4
a5
a6
a7
a8a9a10數(shù)據(jù)元素a1
elem[0]a2
elem[1]a3elem[2]aielem[
i
–
1]e=elem[
i
–
1]elem[0]
elem[1]elem[9]第二十頁(yè),共六十頁(yè)。GetItemStatus
GetItem(SqList
L,
int
i,
ElemType
&e){if(i<1
||
i>L.length)
return(ERROR);e=L.elem[i
-
1];
//
e=*(L.elem
+
i
–
1)return
(OK)}第二十一頁(yè),共六十頁(yè)。ListInsert—功能原型:Status
ListInsert(SqList
&L,int
i,ElemType
e)作用:把e插入線性表,作為第i個(gè)數(shù)據(jù)元素第二十二頁(yè),共六十頁(yè)。ListInsert—功能邏輯結(jié)構(gòu)的變化(a1,
…,
ai-1,
ai,
…,
an)
→
(a1,
…,
ai-1,
e,
ai,
…,
an)<ai-1,
ai>
→
<ai-1,
e>,
<e,
ai>第二十三頁(yè),共六十頁(yè)。ListInsert—功能存儲(chǔ)結(jié)構(gòu)的變化ListInsert(L,
3,
e)length6a1a2a3a4a5a6length7a1a2ea3a4a5a6第二十四頁(yè),共六十頁(yè)。ListInsert—功能過程:1、判斷i的合法性2、移動(dòng)3、賦值4、length++第二十五頁(yè),共六十頁(yè)。ListInsert—i的合法性L7100a1
a2
a3
a4
a5
a6
a71≤i≤8一般的1≤i≤length+1第二十六頁(yè),共六十頁(yè)。ListInsert—移動(dòng)a1a2a3a4a5a6a1a2ea3a4a5a6length6length7a7
a66a
a5a5
a4a4
a3a
=ak+1
kk=length
→
i第二十七頁(yè),共六十頁(yè)。ListInsert—移動(dòng)L.elem[i-1]=e;ak+1
=
ak方法一:數(shù)組元素k=length
→
ij=L.length-1;While(
j>=i-1){L.elem[j+1]=L.elem[j];j--;}for(int
j=L.length;j>=i;j++)L.elem[j]=
L.elem[j-1];L.elem[i-1]=e;第二十八頁(yè),共六十頁(yè)。ListInsert—移動(dòng)方法二:移動(dòng)指針
q=L.elem+(i-1);p=L.elem+L.length-1while(p>=q){*(p+1)=*p;p--;}q指向了aiP開始時(shí)指向了alength*q=e;k=length
→
iak+1=ak第二十九頁(yè),共六十頁(yè)。ListInsert—移動(dòng)ListInsert(L,
5,
66)q=L.elem
+
(i-1);for(p=L.elem
+
L.length-1;
p>=q;
p--)
*(p+1)=*p;*q=e;L.length-1pp
q21
18
30
75
64620p
p5462
5867
87第三十頁(yè),共六十頁(yè)。ListInsert—移動(dòng)L7a1
a2
a3
a4
a5
a6
a7表滿的條件?length=listsizea1
a2
a3
a4
a5
a6
a7710第三十一頁(yè),共六十頁(yè)。ListInsert—移動(dòng)if(L.length
==
L.listsize){newbase
=
realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)
return(OVERFLOW);L.elem=newbase;L.listsize
+=LISTINCREMENT;}第三十二頁(yè),共六十頁(yè)。ListInsertStatus
ListInsert(SqList
&L,
int
i,
ElemType
e){if(
i<1
||
i>
L.length+1)
return(ERROR);if(
L.length
=
=
L.listsize)
{newbase
=
realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)
return(OVERFLOW);L.elem=newbase;L.listsize
+=LISTINCREMENT;}第三十三頁(yè),共六十頁(yè)。ListInsertq=L.elem
+
(i-1);p=L.elem
+
L.length-1;*q=e;L.length++;return(OK);}移動(dòng)while(
p>=q){
*(p+1)=*p;
p--}賦值長(zhǎng)度增加for(int
j=L.length-1;j>=i-1;j+L.elem[j+1]=
L.elem[j];L.elem[i-1]=e;++L.length;第三十四頁(yè),共六十頁(yè)。ListInsert1、在什么情況下,移動(dòng)次數(shù)最少,最少移動(dòng)次數(shù)是多少?2、在什么情況下,移動(dòng)次數(shù)最多,最多移動(dòng)次數(shù)是多少?3、在插入每個(gè)位置的概率相同的情況下,移動(dòng)次數(shù)的期望值是多少?第三十五頁(yè),共六十頁(yè)。List
Delete—功能原型:Status
ListDelete(SqList
&L,int
i,ElemType
&e)作用:取出線性表L的第i個(gè)數(shù)據(jù)元素的值,并刪除第三十六頁(yè),共六十頁(yè)。ListDelete—功能邏輯結(jié)構(gòu)的變化(a1,
…,
ai-1,
ai,
ai+1…,
an)
→
(a1,
…,
ai-1,
ai+1,
…,
an<ai-1,
ai>
<ai,
ai+1>→
<ai-1,
ai+1>第三十七頁(yè),共六十頁(yè)。ListDelete—功能存儲(chǔ)結(jié)構(gòu)的變化a1
a2
a4
a5
a6a1
a2
a3
a4
a5
a6ListDelete(L,
3,
e)65lengthelength第三十八頁(yè),共六十頁(yè)。List
Delete—功能過程:1、判斷i的合法性2、取值3、移動(dòng)4、length--第三十九頁(yè),共六十頁(yè)。ListDelete—i的合法性L7100a1
a2
a3
a4
a5
a6
a71≤i≤7一般的1≤i≤length第四十頁(yè),共六十頁(yè)。ListDelete—移動(dòng)a3
a44a
a5a5
a6a
=ak-1
kk=i+1
→
lengthlength6a1a2a3a4a5
a6length5a1a2a4a5a6第四十一頁(yè),共六十頁(yè)。ListDelete—移動(dòng)p=L.elem
+
(i-1);e=*p;q=L.elem
+
L.length-1;方法一:移動(dòng)指針p指向了aiq開始時(shí)指向了alengthfor(++p;
p<=q;
p++)
*(p-1)
=*p;p指向了ai+1第四十二頁(yè),共六十頁(yè)。ListDelete—移動(dòng)方法二:數(shù)組元素j=i;while(j<=L.length-1){L.elem[j-1]=L.elem[j];j++;}ak-1=akk=i+1
→
length第四十三頁(yè),共六十頁(yè)。ListDeleteStatus
ListDelete(SqList
&L,
int
i,
ElemType
&e){if(
i<1
||
i>
L.length)
return(ERROR);p=L.elem
+
i
–
1;e=*p;q=L.elem
+
L.length
–
1;for(++p;
p<=q;
p++)
*(p-1)
=*p;L.length--;return(OK);}e=
L.elem[i-1];for(int
j=i;j<=L.length-1;L.elem[j-1]=
L.elem[j];--L.length;第四十四頁(yè),共六十頁(yè)。ListDelete1、在什么情況下,移動(dòng)次數(shù)最少,最少移動(dòng)次數(shù)是多少?2、在什么情況下,移動(dòng)次數(shù)最多,最多移動(dòng)次數(shù)是多少?3、在刪除每個(gè)位置的概率相同的情況下,移動(dòng)次數(shù)的期望值是多少?第四十五頁(yè),共六十頁(yè)。ListMerge—功能原型:Status
ListMerge(SqList
&La,SqList
Lb)作用:把Lb中的數(shù)據(jù)元素添加到La的表尾注意:不破壞Lb表第四十六頁(yè),共六十頁(yè)。ListMerge—功能b1
b2
b3La
a1
a2
a3
a4
a5
a6Lbb1b2
b3第四十七頁(yè),共六十頁(yè)。ListMerge—功能過程:1、取出Lb的一個(gè)數(shù)據(jù)元素bi2、把bi插入到La的表尾3、重復(fù)1-2,使得i=1,2,…,Lb.length第四十八頁(yè),共六十頁(yè)。ListMergeStatus
ListMerge(SqList
&La,
SqList
Lb){for(int
i=1;
i<=Lb.length;
i++){GetItem(Lb,
i,
e);code=ListInsert(La,
La.length+1,
e);if(code
!=
OK)
return(ERROR);}return(OK);}第四十九頁(yè),共六十頁(yè)。ListMergeStatus
ListMerge(SqList
&La,
SqList
Lb){if(
La.listsize<
La.length+Lb.length)
{newbase
=
realloc(L.elem,(La.length+Lb.length)*sizeof(ElemType);if(!newbase)
return(OVERFLOW);L.elem=newbase;L.listsize
=
La.length+Lb.length;}For
(int
i=1;
i<=Lb.length;
i++){La.elem[La.length]=Lb.elem[i-1];
La.length++;}return(OK);}第五十頁(yè),共六十頁(yè)。ListMerge—功能原型:Status
ListMerge(SqList
La,SqList
Lb,SqList
&LcLa:
a1≤
a2
≤a3……
≤amLb:
b1≤
b2
≤b3……
≤bn作用:把有序表La和Lb合并得到一個(gè)新的有序表Lc:
c1≤
c2
≤c3……
≤cm+nci=aj
or
ci=bk第五十一頁(yè),共六十頁(yè)。ListMerge—功能13
6
102
8
9LaLb12
3
6
8
9
10Lc第五十二頁(yè),共六十頁(yè)。ListMerge—分析1
3
6
10
1128
9LaLbLapb123
68910pa
pa
pa
papbpb
pb11pa
pa第五十三頁(yè),共六十頁(yè)。ListMerge—分析分析:1、首先建立空表Lc2、從La和Lb中余下未處理的數(shù)據(jù)元素中選取最小的一個(gè)e3、把e插入表尾4、重復(fù)n+m次2和3第五十四頁(yè),共六十頁(yè)。ListMerge
—分析1、首先建立空表LcInitList(Lc);2、pa和pb分別表示La和Lb中余下未處理的第一個(gè)數(shù)據(jù)元素(初始時(shí)pa=1,pb=1)GetItem(La,
pa,
Ea);
GetItem(Lb,
pb,
Eb);if(Ea<Eb
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 語文-河南金太陽(yáng)2024-2025學(xué)年高二上學(xué)期第二次月考
- 2025年比特幣投資項(xiàng)目建議書
- 2025年吡唑啉酮項(xiàng)目合作計(jì)劃書
- 2025年濕式碾米機(jī)項(xiàng)目建議書
- 加強(qiáng)云服務(wù)與本地?cái)?shù)據(jù)同步策略
- 智能科技服務(wù)合同
- 設(shè)備采購(gòu)申請(qǐng)說明及預(yù)算分析報(bào)告書
- 雷鋒的敬業(yè)精神觀后感
- 智聯(lián)保密協(xié)議
- 8-Iodooctan-1-amine-生命科學(xué)試劑-MCE
- 公路工程節(jié)后復(fù)工安全教育
- 2024.8.1十七個(gè)崗位安全操作規(guī)程手冊(cè)(值得借鑒)
- 小王子-英文原版
- T-CHTS 10021-2020 在役公路隧道長(zhǎng)期監(jiān)測(cè)技術(shù)指南
- 醫(yī)院門診醫(yī)生績(jī)效考核標(biāo)準(zhǔn)及評(píng)分細(xì)則
- 醫(yī)院納入定點(diǎn)后使用醫(yī)療保障基金的預(yù)測(cè)性分析報(bào)告
- 北師大版六年級(jí)下冊(cè)書法練習(xí)指導(dǎo)教案教學(xué)設(shè)計(jì)
- 《企業(yè)經(jīng)營(yíng)統(tǒng)計(jì)學(xué)》課程教學(xué)大綱
- 如何做好健康沙龍
- 交通安全設(shè)施養(yǎng)護(hù)技術(shù).ppt
- 環(huán)錘式碎煤機(jī)使用說明書(參考)
評(píng)論
0/150
提交評(píng)論