數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述

第三章線性表2016Fall《數(shù)據(jù)結(jié)構(gòu)》數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第1頁。內(nèi)容提要線性結(jié)構(gòu)線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第2頁。

線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第3頁。學(xué)生信息表通訊錄短信、聊天記錄郵件列表購物清單賬單何處用到線性結(jié)構(gòu)？？？數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第4頁。

首元素相鄰的元素組成前驅(qū)與后繼關(guān)系線性表線性表的邏輯結(jié)構(gòu)尾元素數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第5頁。線性表線性表是n個數(shù)據(jù)元素的有限序列。一般形式：(a1,…,ai-1,ai,ai+1,…,an)直接前驅(qū)、直接后繼長度：表中元素的個數(shù)n(n=0時稱為空表)非空表中，每個元素都有一個確定的位置數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第6頁。

結(jié)構(gòu)+操作結(jié)構(gòu)的創(chuàng)建、結(jié)構(gòu)的銷毀：構(gòu)造與析構(gòu)引用型（訪問型）：get加工型（改變型）：set線性表抽象數(shù)據(jù)類型？數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第7頁。ADTList{數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：

InitList(&L)

//初始化

操作結(jié)果：構(gòu)造一個空的線性表L。

CreatList(&L,n)//創(chuàng)建

操作結(jié)果：構(gòu)造一個含n個元素的線性表L。

DestroyList(&L)

//結(jié)構(gòu)銷毀

初始條件：線性表L已存在。

操作結(jié)果：銷毀線性表L。線性表類型數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第8頁。//引用型操作

ListLength(L)//求線性表的長度

初始條件：線性表L已存在。

操作結(jié)果：返回L中元素個數(shù)。

ListEmpty(L)//判斷線性表是否為空

初始條件：線性表L已存在。

操作結(jié)果：若L不空，返回true，否則為false。

PriorElem(L,cur_e,&pre_e)

//求數(shù)據(jù)元素的前驅(qū)

初始條件：線性表L已存在。

操作結(jié)果：若cur_e是L的元素，但不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。

NextElem(L,cur_e,&next_e)

//求數(shù)據(jù)元素的后繼

初始條件：線性表L已存在。

操作結(jié)果：若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第9頁。GetElem(L,i,&e)//取線性表中第i個數(shù)據(jù)元素初始條件：線性表L已存在，且1≤i≤LengthList(L)。操作結(jié)果：用e返回L中第i個元素的值。LocateElem(L,e,compare())//定位函數(shù)初始條件：線性表L已存在，e為給定值， compare()是元素判定函數(shù)。操作結(jié)果：返回第1個與e滿足compare關(guān)系的元素的位序。

若這樣的元素不存在，則返回值為0。ListTraverse(L,visit())//遍歷線性表初始條件：線性表L已存在，visit()為某個訪問函數(shù)。操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit()。

一旦visit()失敗，則操作失敗。數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第10頁。//加工型操作：&L!!!

ClearList(&L)//線性表置空

初始條件：線性表L已存在。

操作結(jié)果：將L重置為空表

ListInsert(&L,i,e)//插入數(shù)據(jù)元素

初始條件：線性表L已存在，且1≤i≤LengthList(L)+1。

操作結(jié)果：在L的第i個元素之前插入新的元素e，L的長度增1。

ListDelete(&L,i,&e)//刪除數(shù)據(jù)元素

初始條件：線性表L已存在且非空，1≤i≤LengthList(L)。

操作結(jié)果：刪除L的第i個元素，并用e返回其值，L的長度減1。}ADTList數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第11頁。題目：假設(shè)利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=A∪B。方法：只要從LB中依次取出每個數(shù)據(jù)元素，并依值在LA中進行查訪，若不存在，則插入。線性表類型的應(yīng)用——求集合的并集數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第12頁。voidunionSet(List&La,ListLb){ La_len=ListLength(La); Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,e); if(!LocateElem(La,e,EQUAL)) InsertList(La,++La_len,e);

}}線性表類型的應(yīng)用——求集合的并集數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第13頁。題目：已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的數(shù)據(jù)元素仍按值非遞減有序排列。方法：設(shè)置兩個指針分別指向LA和LB的當(dāng)前元素，將數(shù)值較小的元素插入LC中。線性表類型的應(yīng)用——歸并操作數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第14頁。voidMergeList(ListLa,ListLb,List&Lc){ClearList(Lc);//這里假定Lc已經(jīng)做過InitList操作， //ClearList之后表的空間還在！i=j=1;k=0; La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}} while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第15頁。線性表的順序表示和實現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的表示和實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第16頁。是指用一組地址連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素以元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯相鄰線性表的順序表示數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第17頁。是指用一組地址連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素設(shè)每個數(shù)據(jù)元素需占用C個存儲單元LOC(ai)=LOC(ai-1)+CLOC(ai)=LOC(a1)+(i-1)×C線性表的順序表示和實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第18頁。是指用一組地址連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素線性表的順序存儲結(jié)構(gòu)是一種能夠隨機存取的存儲結(jié)構(gòu)，通常用動態(tài)數(shù)組來實現(xiàn)。線性表的順序表示和實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第19頁。#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量#defineLISTINCREMENT10//線性表存儲空間的分配增量typedefstruct{ ElemType*elem;//存儲空間基址

intlength;//當(dāng)前長度

intlistsize;//當(dāng)前分配的存儲容量}List;順序存儲結(jié)構(gòu)的表示a1a2a3a6a7a4a5listsizeelemlength數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第20頁。2023/6/15數(shù)學(xué)科學(xué)學(xué)院21279103listsizelengthelem動態(tài)內(nèi)存空間List類型的對象L數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第21頁。StatusInitList(List&L){//分配空間 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);//空間總長賦初值

L.listsize=LIST_INIT_SIZE;

//表長賦初值0

L.length=0;

returnOK;}順序存儲時基本操作的實現(xiàn)listsizeelemlength=0數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第22頁?！窘Y(jié)構(gòu)的銷毀——沒有空間了！】voidDestroyList(List&L){//空間釋放

free(L.elem);

L.elem=NULL;

L.length=0; L.listsize=0;}【清空——表空間還在，只是“沒有”元素了！】voidClearList(List&L){

L.length=0; }數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第23頁。//引用型voidTraverseList(ListL,void(*visit)(ElemType)){ for(i=0;i<L.length;i++)

(*visit)(L.elem[i]);}//加工型——map操作！voidTraverseList(List&L, void(*visit)(&ElemType)){ for(i=0;i<L.length;i++) (*visit)(L.elem[i]);}//注意引用參數(shù)的使用！??！數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第24頁。StatusGetElem(ListL,inti,ElemType&e){//i的合法性檢測

if(i<1||i>L.length)returnERROR;//取元素

e=L.elem[i-1]; returnOK;}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第25頁。intLocateElem(ListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){//起步 i=1;p=L.elem;//在有效范圍內(nèi)查詢 while(i<=L.length&&!(*compare)(*p++,

e)) ++i;//返回元素的真實位置 if(i<=L.length)returni; elsereturn0;}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第26頁。intLocateElem(ListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){//起步 i=1; //在有效范圍內(nèi)查詢 while(i<=L.length&&!(*compare)(L.elem[i-1],e)) ++i;//返回元素的真實位置 if(i<=L.length)returni; elsereturn0;}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第27頁。插入操作：StatusInsertList()插入前的線性表：(a1,…,ai-1,ai,ai+1,…,an)插入后的線性表：(a1,…,ai-1,b,ai,ai+1,…,an)時間復(fù)雜度：最壞和平均的情況O(n)邏輯關(guān)系發(fā)生了變化數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第28頁。數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第29頁。StatusInsertList(List&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; }【實驗時可先假定空間總是夠用，先不考慮空間追加，先做好基本的元素移動、和插入，回頭再考慮空間的追加與元素的拷貝！】【問題：實驗一下realloc也做了元素的拷貝工作么？】數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第30頁?！緮?shù)組方式的元素移動、插入】//從插入位置開始向后的元素，自后向前依次后移 for(j=L.length;j>=i;j--){ L.elem[j]=L.elem[j-1]; }

//插入e，修改表長 L.elem[i-1]=e;

++L.length; returnOK;}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第31頁?！局羔樂绞降脑匾苿?、插入，有些難以閱讀。。。?！?/從插入位置開始向后的元素，自后向前依次后移 q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;//插入e，修改表長 *q=e;

++L.length; returnOK;}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第32頁。刪除操作：StatusDeleteList()刪除前的線性表：(a1,…,ai-1,ai,ai+1,…,an)刪除后的線性表：(a1,…,ai-1,ai+1,…,an)時間復(fù)雜度：最壞和平均的情況O(n)邏輯關(guān)系發(fā)生了變化數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第33頁。數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第34頁。StatusDeleteList(List&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;}數(shù)據(jù)結(jié)構(gòu)與算法Python語言描述全文共37頁，當(dāng)前為第35頁。//