資源描述：
《數(shù)據(jù)結(jié)構(gòu) C語言版 教學(xué)課件 作者 嚴(yán)蔚敏 李冬梅 吳偉民 第2章 線性表.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、*李冬梅數(shù)據(jù)結(jié)構(gòu)*北京林業(yè)大學(xué)信息學(xué)院近3周 上課 內(nèi)容第2章線性表第3章棧和隊(duì)列第4章串、數(shù)組和廣義表線性結(jié)構(gòu)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼?？杀硎緸椋海╝1,a2,……,an）線性結(jié)構(gòu)的定義：（邏輯、存儲(chǔ)和運(yùn)算）*北京林業(yè)大學(xué)信息學(xué)院線性結(jié)構(gòu)的特點(diǎn)：①只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；②除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性結(jié)構(gòu)表達(dá)式：（a1,a2,……,an）線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是線性表簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)
2、間的邏輯關(guān)系是一對(duì)一的*北京林業(yè)大學(xué)信息學(xué)院第2章線性表1.了解線性結(jié)構(gòu)的特點(diǎn)2.掌握順序表的定義、查找、插入和刪除3.掌握鏈表的定義、查找、插入和刪除4.能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合教學(xué)目標(biāo)*北京林業(yè)大學(xué)信息學(xué)院2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4線性表的應(yīng)用教學(xué)內(nèi)容*北京林業(yè)大學(xué)信息學(xué)院（a1,a2,…ai-1，ai,ai＋1，…,an）線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中
3、的位置n為元素總個(gè)數(shù)，即表長空表線性終點(diǎn)2.1線性表的類型定義*北京林業(yè)大學(xué)信息學(xué)院例1分析26個(gè)英文字母組成的英文表（A,B,C,D,……,Z）學(xué)號(hào)姓名性別年齡班級(jí)041810205于春梅女1804級(jí)計(jì)算機(jī)1班041810260何仕鵬男2004級(jí)計(jì)算機(jī)2班041810284王爽女1904級(jí)計(jì)算機(jī)3班041810360王亞武男1804級(jí)計(jì)算機(jī)4班：：：：：例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性*北京林業(yè)大學(xué)信息學(xué)院線性表的基本操作1.初始化線性表LInitList(L
4、)2.銷毀線性表LDestoryList(L)3.清空線性表LClearList(L)4.求線性表L的長度ListLength(L)5.判斷線性表L是否為空IsEmpty(L)6.獲取線性表L中的某個(gè)數(shù)據(jù)元素內(nèi)容GetElem(L,i,e)7.檢索值為e的數(shù)據(jù)元素LocateELem(L,e)8.在線性表L中插入一個(gè)數(shù)據(jù)元素ListInsert(L,i,e)9.刪除線性表L中第i個(gè)數(shù)據(jù)元素ListDelete(L,i,e)抽象數(shù)據(jù)類型的定義為*北京林業(yè)大學(xué)信息學(xué)院2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。簡言之，邏輯上相
5、鄰，物理上也相鄰順序存儲(chǔ)方法：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組V[n]來實(shí)現(xiàn)。順序存儲(chǔ)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。*北京林業(yè)大學(xué)信息學(xué)院元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)*北京林業(yè)大學(xué)信息學(xué)院#defineMAXSIZE100//最大長度typedefstruct{ElemType*elem;//指向數(shù)據(jù)元素的基地址intlength;//線性表的當(dāng)前長度}SqList；
6、順序表的類型定義數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：查找、插入、刪除*北京林業(yè)大學(xué)信息學(xué)院malloc(m)：開辟m字節(jié)長度的地址空間，并返回這段空間的首地址sizeof(x)：計(jì)算變量x的長度free(p)：釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量補(bǔ)充：C語言的動(dòng)態(tài)分配函數(shù)（）*北京林業(yè)大學(xué)信息學(xué)院new類型名T（初值列表）功能：申請(qǐng)用于存放T類型對(duì)象的內(nèi)存空間，并依初值列表賦以初值結(jié)果值：成功：T類型的指針，指向新分配的內(nèi)存失?。?（NULL）int*p1=newint;或int*p1=newint(10);delete指針P功能：
7、釋放指針P所指向的內(nèi)存。P必須是new操作的返回值deletep1;補(bǔ)充：C++的動(dòng)態(tài)存儲(chǔ)分配*北京林業(yè)大學(xué)信息學(xué)院函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保持一致參數(shù)傳遞有兩種方式傳值方式（參數(shù)為整型、實(shí)型、字符型等）傳地址參數(shù)為指針變量參數(shù)為引用類型參數(shù)為數(shù)組名補(bǔ)充：C++中的參數(shù)傳遞*北京林業(yè)大學(xué)信息學(xué)院voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<voidswap(floatm,floatn){floatt
8、emp;temp=m;m=n;n=temp;}傳值方式把實(shí)參的值傳送給函數(shù)局部工作區(qū)相應(yīng)的副本
