數據結構線性表

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

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

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

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

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

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

線性表的順序存儲——順序表第5頁，共19頁。邏輯功能設計顯示所有學生的信息獲取當前學生數量對單個學生進行增、刪、查找、顯示使用前面設計的線性表的基本操作來實現上述功能第6頁，共19頁。交互頁面的設計第7頁，共19頁。Main函數的設計Switch（）{ case: case: case: ……}第8頁，共19頁。2.3線性表的鏈式存儲——單鏈表由于順序表中的每個元素至多只有一個前驅元素和一個后繼元素,即數據元素之間是一對一的邏輯關系,所以當進行鏈式存儲時,一種最簡單也最常用的方法是:在每個結點中除包含有數據域外,只設置一個指針域,用以指向其后繼結點,這樣構成的鏈接表稱為線性單向鏈接表,簡稱單鏈表；

2.3.1

線性表的鏈式存儲一——鏈表第9頁，共19頁。在單鏈表中,假定每個結點類型用LinkList表示,它應包括存儲元素的數據域,這里用data表示,其類型用通用類型標識符ElemType表示,還包括存儲后繼元素位置的指針域,這里用next表示。

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

單鏈表的定義2.3線性表的鏈式存儲——單鏈表第10頁，共19頁。2.3.3

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

ElemType*pElem);第11頁，共19頁。2.3線性表的鏈式存儲——單鏈表2.3.3

單鏈表基本運算及其實現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線性表的鏈式存儲二——雙鏈表

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

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

第14頁，共19頁。2.4線性表的鏈式存儲二——雙鏈表

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

循環(huán)鏈表是另一種形式的鏈式存儲結構。它的特點是表中最后一個結點的指針域不再是空,而是指向表頭結點,整個鏈表形成一個環(huán)。由此,從表中任一結點出發(fā)均可找到鏈表中其他結點。帶頭結點的單向循環(huán)鏈表和