數(shù)據(jù)結(jié)構(gòu)線性表

第2章線性表第1頁(yè)，共19頁(yè)。2.1線性表的基本概念線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。該序列中所含元素的個(gè)數(shù)叫做線性表的長(zhǎng)度,用n表示,n≥0。當(dāng)n=0時(shí),表示線性表是一個(gè)空表,即表中不包含任何元素。設(shè)序列中第i(i表示位序)個(gè)元素為ai(1≤i≤n)。線性表的一般表示為:(a1,a2,…ai,ai+1,…,an)線性結(jié)構(gòu)的基本特征為:

1．集合中必存在唯一的一個(gè)“第一元素”；

2．集合中必存在唯一的一個(gè)“最后元素”；

3．除最后一個(gè)元素之外，均有唯一的后繼(后件)；4．除第一個(gè)元素之外，均有唯一的前驅(qū)(前件)。

第2頁(yè)，共19頁(yè)。線性表的應(yīng)用實(shí)例問(wèn)題：使用線性表來(lái)存儲(chǔ)一組學(xué)生信息，并支持常規(guī)的增刪查找等操作。分析：針對(duì)此問(wèn)題，線性表中的元素應(yīng)該是單個(gè)學(xué)生的基本信息，如（學(xué)號(hào)，姓名，年齡，專(zhuān)業(yè)，入學(xué)年份）。需要編寫(xiě)線性表的基本操作（創(chuàng)建線性表、插入一個(gè)元素、刪除一個(gè)元素、顯示線性表中數(shù)據(jù)、在線性表中查找指定元素等），然后再利用這些基本操作來(lái)構(gòu)造解決問(wèn)題所需的邏輯功能模塊，如（插入一個(gè)學(xué)生信息，刪除某個(gè)學(xué)生，查找某個(gè)學(xué)生等）解決方案給出線性表的定義和存儲(chǔ)方案編寫(xiě)線性表的基本操作編寫(xiě)問(wèn)題描述中所需的邏輯功能模塊編寫(xiě)主函數(shù)，通過(guò)與終端的交互，實(shí)現(xiàn)上述問(wèn)題描述第3頁(yè)，共19頁(yè)。2.2

線性表的順序存儲(chǔ)——順序表2.2.1定義順序表線性表的順序存儲(chǔ)結(jié)構(gòu)就是:把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)器中指定存儲(chǔ)位置開(kāi)始的一塊連續(xù)的存儲(chǔ)空間中?？山柚鷶?shù)組實(shí)現(xiàn)。分析得知，構(gòu)成線性表的元素及線性表自身可定義如下：typedefstruct{ ElemTypedata[MAXCOUNT]; intlength;}SqList;typedefstruct{ charnum[20]; charname[20]; intage; charmajor[20]; intregisterYear;}ElemType;第4頁(yè)，共19頁(yè)。2.2.2順序表上的運(yùn)算及其實(shí)現(xiàn)(1).建立順序表CreateList創(chuàng)建一個(gè)空的順序表，要完成線性表所需空間的分配和其他初始化設(shè)置。(2)求線性表的長(zhǎng)度ListLength(3)輸出線性表DispList(4)在線性表中的指定位置插入一個(gè)元素InsertElem(5)根據(jù)鍵值查找指定元素FindElemByNum(6)獲取指定位置的元素信息GetElem(7)刪除指定位置的元素DelElem(8)釋放線性表DestroyList2.2

線性表的順序存儲(chǔ)——順序表第5頁(yè)，共19頁(yè)。邏輯功能設(shè)計(jì)顯示所有學(xué)生的信息獲取當(dāng)前學(xué)生數(shù)量對(duì)單個(gè)學(xué)生進(jìn)行增、刪、查找、顯示使用前面設(shè)計(jì)的線性表的基本操作來(lái)實(shí)現(xiàn)上述功能第6頁(yè)，共19頁(yè)。交互頁(yè)面的設(shè)計(jì)第7頁(yè)，共19頁(yè)。Main函數(shù)的設(shè)計(jì)Switch（）{ case: case: case: ……}第8頁(yè)，共19頁(yè)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表由于順序表中的每個(gè)元素至多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素,即數(shù)據(jù)元素之間是一對(duì)一的邏輯關(guān)系,所以當(dāng)進(jìn)行鏈?zhǔn)酱鎯?chǔ)時(shí),一種最簡(jiǎn)單也最常用的方法是:在每個(gè)結(jié)點(diǎn)中除包含有數(shù)據(jù)域外,只設(shè)置一個(gè)指針域,用以指向其后繼結(jié)點(diǎn),這樣構(gòu)成的鏈接表稱(chēng)為線性單向鏈接表,簡(jiǎn)稱(chēng)單鏈表；

2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)一——鏈表第9頁(yè)，共19頁(yè)。在單鏈表中,假定每個(gè)結(jié)點(diǎn)類(lèi)型用LinkList表示,它應(yīng)包括存儲(chǔ)元素的數(shù)據(jù)域,這里用data表示,其類(lèi)型用通用類(lèi)型標(biāo)識(shí)符ElemType表示,還包括存儲(chǔ)后繼元素位置的指針域,這里用next表示。

LinkList類(lèi)型的定義如下:typedefstructLNode/*定義單鏈表結(jié)點(diǎn)類(lèi)型*/{ElemTypedata;structLNode*next;/*指向后繼結(jié)點(diǎn)*/}LinkList;2.3.2

單鏈表的定義2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表第10頁(yè)，共19頁(yè)。2.3.3

單鏈表基本運(yùn)算及其實(shí)現(xiàn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表1、創(chuàng)建單鏈表LinkList*CreateList();2、初始化單鏈表voidInitList(LinkList*list);3、釋放單鏈表voidDestroyList(LinkList*list);4、獲取單鏈表中元素的數(shù)量intListLength(LinkList*list);5、輸出單鏈表中的所有數(shù)據(jù)voidDispList(LinkList*list);6、獲取單鏈表中指定位置的元素intGetElem(LinkList*list,intloc,ElemType*pElem);7、根據(jù)鍵值查找指定元素intFindElemByNum(LinkList*list,char*keyCh,

ElemType*pElem);第11頁(yè)，共19頁(yè)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表2.3.3

單鏈表基本運(yùn)算及其實(shí)現(xiàn)8、采用頭插法向單鏈表中插入一個(gè)元素intInsertElem_Head(LinkList*list,ElemTypemyElem);9、采用尾插法向單鏈表中插入一個(gè)元素intInsertElem_Foot(LinkList*list,ElemTypemyElem);10、向單鏈表中的指定位置插入一個(gè)元素intInsertElem_Loc(LinkList*list,

intloc,

ElemTypemyElem);11、刪除指定位置的元素intDelElem(LinkList*list,intloc,ElemType*pElem);第12頁(yè)，共19頁(yè)。第13頁(yè)，共19頁(yè)。2.4線性表的鏈?zhǔn)酱鎯?chǔ)二——雙鏈表

對(duì)于雙鏈表,采用類(lèi)似于單鏈表的類(lèi)型定義,其DLinkList類(lèi)型的定義如下:

typedefstructDNode/*定義雙鏈表結(jié)點(diǎn)類(lèi)型*/{ ElemTypedata; structDNode*prior;/*指向前驅(qū)結(jié)點(diǎn)*/ structDNode*next;/*指向后繼結(jié)點(diǎn)*/}DLinkList;在雙鏈表中,有些操作如求長(zhǎng)度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)涉及到前后結(jié)點(diǎn)的一個(gè)指針域的變化。而在雙鏈表中,結(jié)點(diǎn)的插入和刪除操作涉及到前后結(jié)點(diǎn)的兩個(gè)指針域的變化。

第14頁(yè)，共19頁(yè)。2.4線性表的鏈?zhǔn)酱鎯?chǔ)二——雙鏈表

歸納起來(lái),在雙鏈表中p所指的結(jié)點(diǎn)之后插入一個(gè)*s結(jié)點(diǎn)。其操作語(yǔ)句描述為: s->next=p->next;/*將s插入到p之后*/ p->next->prior=s; s->prior=p; p->next=s;歸納起來(lái),刪除雙鏈表L中*p結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。其操作語(yǔ)句描述為: p->next=q->next; q->next->prior=p;第15頁(yè)，共19頁(yè)。2.5循環(huán)鏈表

循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域不再是空,而是指向表頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)。由此,從表中任一結(jié)點(diǎn)出發(fā)均可找到鏈表中其他結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單向循環(huán)鏈表和