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

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

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

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

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

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

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

2.3.1

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

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

單鏈表的定義2.3線性表的鏈?zhǔn)酱鎯Α獑捂湵淼?0頁，共19頁。2.3.3

單鏈表基本運(yùn)算及其實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Α獑捂湵?、創(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頁，共19頁。2.3線性表的鏈?zhǔn)酱鎯Α獑捂湵?.3.3

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

intloc,

ElemTypemyElem);11、刪除指定位置的元素intDelElem(LinkList*list,intloc,ElemType*pElem);第12頁，共19頁。第13頁，共19頁。2.4線性表的鏈?zhǔn)酱鎯Χp鏈表

對于雙鏈表,采用類似于單鏈表的類型定義,其DLinkList類型的定義如下:

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

第14頁，共19頁。2.4線性表的鏈?zhǔn)酱鎯Χp鏈表

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

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