數(shù)據(jù)結(jié)構(gòu)（C#語(yǔ)言描述）第二章.ppt

1、數(shù)據(jù)結(jié)構(gòu)與算法,第二章,預(yù)習(xí)檢查,預(yù)習(xí)內(nèi)容 線性表,本章任務(wù),線性表的基本概念 順序表 鏈表,線性表是n個(gè)數(shù)據(jù)元素的有限序列。其一般描述為： A=（a1，a2，an） 其中A稱為線性表的名稱， 每個(gè)ai（ni1）稱為線性表的數(shù)據(jù)元素，具體n的值含義則稱為線性表中包含有數(shù)據(jù)元素的個(gè)數(shù)，也稱為線性表的長(zhǎng)度；當(dāng)n的值等于0時(shí)，表示該線性表是空表。每個(gè)數(shù)據(jù)元素的含義在不同情況下各不相同，它們可能是一個(gè)字母、一個(gè)數(shù)字、也可以是一條記錄等。一般情況下，在線性表中每個(gè)ai的描述的是一組相同屬性的數(shù)據(jù)。,線性表,線性表的特點(diǎn)： （1）除第一個(gè)位置的數(shù)據(jù)元素外，其它數(shù)據(jù)元素位置的前面都只有一個(gè)數(shù)據(jù)元素； （2）

2、除最后一個(gè)位置的數(shù)據(jù)元素外，其它數(shù)據(jù)元素位置的后面都只有一個(gè)元素。 也就是說(shuō)，數(shù)據(jù)元素是一個(gè)接一個(gè)的排列。因此，可以把線性表想象為一種數(shù)據(jù)元素序列的數(shù)據(jù)結(jié)構(gòu)。,線性表,線性表的常用操作： 1、求長(zhǎng)度：GetLength() 操作結(jié)果：返回線性表中所有數(shù)據(jù)元素的個(gè)數(shù)。 、判斷線性表是否為空：IsEmpty() 操作結(jié)果：如果線性表為空返回true，否則返回false。 、附加操作：Append(T item) 操作結(jié)果：將值為item的新元素添加到表的末尾。 、插入操作：Insert(T item, int i) 操作結(jié)果：在線性表的第i個(gè)位置上插入一個(gè)值為item的新元素。 、刪除操作：Del

3、ete(int i) 操作結(jié)果：在線性表中刪除序號(hào)為i的數(shù)據(jù)元素。 、取表元：GetElem(int i) 操作結(jié)果：返回線性表中第i個(gè)數(shù)據(jù)元素。 、按值查找：Locate(T value) 操作結(jié)果：在線性表中查找值為value的數(shù)據(jù)元素。,線性表,順序表 用址連續(xù)的存儲(chǔ)單元存儲(chǔ)線性表中的元素 如：數(shù)組 順序表查找 順序表插入 順序表刪除,線性表,/在順序表的末尾追加數(shù)據(jù)元素 public void Append(T a) if (IsFull() Console.WriteLine(插入錯(cuò)誤!); return; datalength = a; length+; 代碼演示,順序表的常用操作

4、,/在順序表的第i個(gè)數(shù)據(jù)元素的位置插入一個(gè)數(shù)據(jù)元素 public void Insert(T a, int i) if (IsFull() Console.WriteLine(表已滿!); return; if (i length + 1) Console.WriteLine(位置錯(cuò)誤!); return; else for (int j = length-1; j = i - 1; j-) dataj + 1 = dataj; datai - 1 = a; length+; 代碼演示,順序表的常用操作,/刪除順序表的第i個(gè)數(shù)據(jù)元素 public void Delete(int i) if (

5、IsEmpty() Console.WriteLine(表空！); return; if (i length) Console.WriteLine(位置錯(cuò)誤!); return; for (int j = i; j length; j+) dataj-1 = dataj; length -; 代碼演示,順序表的常用操作,/獲得順序表的第i個(gè)數(shù)據(jù)元素 public T GetElem(int i) if (IsEmpty() | (i length) Console.WriteLine(表為空或位置錯(cuò)誤!); return default(T); return datai - 1; 代碼演示,順

6、序表的常用操作,順序表總結(jié)： 特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰； 優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素；存儲(chǔ)空間使用緊湊 缺點(diǎn)：1.在插入、刪除某一元素時(shí)，需要移動(dòng)大量元素; 2.預(yù)先分配空間需按最大空間分配，利用不充分; 3.插入數(shù)據(jù)元素需要考慮溢出情況,討論： 在線性表中插入和刪除數(shù)據(jù)元素時(shí)可不可以不移動(dòng)元素？,答：可以！引入線性表的另一種物理映象鏈表,線性表,什么是鏈表？,鏈表 鏈?zhǔn)酱鎯?chǔ)的線性表 用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素（這組存儲(chǔ)地址可以連續(xù)或者非連續(xù)） 以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址作為線性表的地址，為線性表的頭指針,鏈表,【例】設(shè)有一組線性

7、排列的數(shù)據(jù)元素（zhao, qian, sun, li, zhou, wu, zheng, wang），其鏈接存儲(chǔ)形式下頁(yè)圖所示：,討論：在該存儲(chǔ)方式下，如何找到表中任一元素？,答：在鏈接存儲(chǔ)方式下（鏈表中），每一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是存放在其直接前驅(qū)結(jié)點(diǎn)的next域中，只要知道第一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）zhao的存儲(chǔ)地址，就可以“順藤摸瓜”找到其后續(xù)的所有結(jié)點(diǎn)。,線性表,頭指針H,170,通常情況下，我們用箭頭來(lái)表示指針域中的指針，忽略每一個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置，而重點(diǎn)突出鏈表中結(jié)點(diǎn)間的邏輯順序，將鏈表直觀地畫(huà)成用箭頭鏈接起來(lái)的結(jié)點(diǎn)序列。,線性表,常用鏈表結(jié)構(gòu)： 單鏈表 雙鏈表 循環(huán)鏈表,鏈表,單

8、鏈表,單鏈表: 結(jié)點(diǎn)結(jié)構(gòu): public class SLinkListNode private T data; /數(shù)據(jù)域 private SLinkListNode next; /引用域 ,單鏈表查找,單鏈表插入,單鏈表刪除,/在單鏈表的末尾追加數(shù)據(jù)元素 public void Append(T a) if (start = null) start = new SLinkListNode(a); return; SLinkListNode current = start; while (current.Next != null) current = current.Next; current

9、.Next = new SLinkListNode(a); length+; 代碼演示,單鏈表的常用操作,/在單鏈表的第i個(gè)數(shù)據(jù)元素的位置前插入一個(gè)數(shù)據(jù)元素 public void InsertNode(T a, int i) SLinkListNode current; SLinkListNode previous; if (i newnode = new SLinkListNode(a); /在空鏈表或第一個(gè)元素前插入第一個(gè)元素 if (i = 1) newnode.Next = start; start = newnode; length+; return; /單鏈表的兩個(gè)元素間插入一個(gè)

10、元素 current = start; previous = null; int j = 1; while (current!= null 代碼演示,單鏈表的常用操作,/刪除單鏈表的第i個(gè)數(shù)據(jù)元素 public void DeleteNode(int i) if (IsEmpty() | i current = start; if (i = 1) start = current.Next; length-; return; SLinkListNode previous=null; int j = 1; while (current.Next != null 代碼演示,單鏈表的常用操作,帶頭結(jié)點(diǎn)

11、單鏈表 在單鏈表的第一個(gè)結(jié)點(diǎn)之前設(shè)一個(gè)頭結(jié)點(diǎn) 頭結(jié)點(diǎn)的數(shù)據(jù)域不存儲(chǔ)數(shù)據(jù) 頭結(jié)點(diǎn)的指針域存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址 空鏈表 L.next= NULL,為什么要設(shè)頭結(jié)點(diǎn)？,答：頭結(jié)點(diǎn)即在鏈表的首元素結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元素結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。,討論. 在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？,單鏈表,問(wèn)：鏈表只能查找結(jié)點(diǎn)的直接后繼，能不能找到直接前驅(qū)？,答：能，只要給每個(gè)結(jié)點(diǎn)多開(kāi)一個(gè)指針域,prior data next,雙鏈表,雙鏈表： 雙鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接前趨的地址。 結(jié)點(diǎn)

12、圖 class DLinkListNode private T data; /數(shù)據(jù)域 private DLinkListNode prior; /前驅(qū)引用域 private DLinkListNode next; /后繼引用域 雙鏈表的查找 雙鏈表的插入 雙鏈表的刪除 參考代碼,雙鏈表,循環(huán)鏈表: 循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),循環(huán)鏈表,循環(huán)鏈表插入,循環(huán)鏈表刪除,循環(huán)鏈表查找,總結(jié)(1),線性表是最簡(jiǎn)單、最基本、最常用的數(shù)據(jù)結(jié)構(gòu)，線性表的特點(diǎn)是數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系，也就是說(shuō)，除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，其余數(shù)據(jù)元素都有且只有一

13、個(gè)直接前驅(qū)和直接后繼。 線性表有兩種不同的存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)的線性表稱為順序表，順序表中的存儲(chǔ)單元是連續(xù)的，在C#語(yǔ)言中用數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)。鏈?zhǔn)酱鎯?chǔ)的線性表稱為鏈表，鏈表中的存儲(chǔ)單元不一定是連續(xù)的，所以在一個(gè)結(jié)點(diǎn)有數(shù)據(jù)域存放數(shù)據(jù)元素本身的信息，還有引用域存放其相鄰的數(shù)據(jù)元素的地址信息。,總結(jié)（）,單鏈表的結(jié)點(diǎn)只有一個(gè)引用域，存放其直接后繼結(jié)點(diǎn)的地址信息，雙向鏈表的結(jié)點(diǎn)有兩個(gè)引用域，存放其直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的地址信息。循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的引用域存放頭引用的值。,總結(jié)（）,對(duì)線性表的基本操作有查找、插入、刪除等操作。順序表由于具有隨機(jī)存儲(chǔ)的特點(diǎn)，所以查找比較方便，效率很高，但插入和刪除數(shù)據(jù)元素都需要移動(dòng)大量的數(shù)據(jù)元素，所以效率很低。而鏈表由于其存儲(chǔ)空間不要求是連續(xù)的，所以插入和刪除數(shù)據(jù)元素的效率很高