《計算機科學導論》之數(shù)據(jù)結(jié)構(gòu)基礎知識

《計算機科學導論（第二版）》  11章   數(shù)據(jù)結(jié)構(gòu)

11.1  引言 

1、為什么要使用數(shù)據(jù)結(jié)構(gòu)？

    盡管單變量在程序設計語言中被大量使用，但是它們不能有效地解決復雜問題。此時考慮使用數(shù)據(jù)結(jié)構(gòu)。

2、數(shù)據(jù)結(jié)構(gòu)是什么？

    數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

3、三種數(shù)據(jù)結(jié)構(gòu)

    數(shù)組；

    記錄;

    鏈表；

大多的編程語言都隱式實現(xiàn)了前兩種，而第三種則通過指針和記錄來模擬。

11.2  數(shù)組

1、為什么使用數(shù)組？

    為了處理大量的數(shù)據(jù)，需要一個數(shù)據(jù)結(jié)構(gòu)，如數(shù)組。當然還有其他的數(shù)據(jù)結(jié)構(gòu)。

2、數(shù)組的定義

    數(shù)組是元素的順序集合，通常這些元素具有相同的數(shù)據(jù)類型。

3、數(shù)組的基礎知識

    1索引

    表示元素在數(shù)組中的順序號，順序號從數(shù)組開始計數(shù)。

    數(shù)組元素通過索引被獨立給出了地址，使用索引可以訪問數(shù)組中的元素。

    有些現(xiàn)代語言（如C、C++和Java）是從0開始數(shù)組索引的。

    2數(shù)組名與元素名

    在一個數(shù)組中，有兩種標識符：數(shù)組的名字（scores）和各個元素的名字（scores[1]、scores[2]）。

    3多維數(shù)組

    許多應用需要數(shù)據(jù)以多于一維的形式存儲。一個常見的例子是表，其是由行和列組成的二維數(shù)組。

    多維數(shù)組（多于二維的數(shù)組）也是可以的。

    二維數(shù)組在內(nèi)存中可以使用行主序存儲或列主序存儲，第一種更常見。

4、數(shù)組操作

    數(shù)組操作是值得一些把數(shù)組作為數(shù)據(jù)結(jié)構(gòu)的操作。

    常見的數(shù)組操作有：查找、插入、刪除、檢索和遍歷

    1查找

    未排序的數(shù)組使用順序查找。對排序的數(shù)組使用折半查找；

    2插入（操作冗長和棘手）

    語言允許可變長數(shù)組的前提（例如，C語言的最新版本）

    ①尾部的插入

    ②開始或中間的插入

    首先查找數(shù)組。找到插入的位置后，插入新的元素。

    注意移位需要在數(shù)組的尾部進行，以防止元素值的丟失。

    3刪除（操作冗長和棘手）

    需要把需要移動的元素向數(shù)組的開始位置移動一個位置。

    4檢索

    檢索操作就是隨機（注意對隨機地理解）地存取一個元素，達到檢查或拷貝元素中的數(shù)據(jù)的目的。

5、數(shù)組的應用

    當需要進行的插入和刪除操作數(shù)目較少，而需要大量的查找和檢索操作時，數(shù)組是合適的數(shù)據(jù)結(jié)構(gòu)。

11.3  記錄

1、為什么要用記錄？

    記錄也是為了處理大量的數(shù)據(jù)而被需要的一個數(shù)據(jù)結(jié)構(gòu)。

2、什么是記錄？

    記錄是一組相關(guān)元素的集合，它們可能是不同的類型，但整個記錄有一個名稱。

    記錄中的數(shù)據(jù)必須都與一個對象關(guān)聯(lián)。

3、記錄的基礎知識

    1域

    記錄中的每個元素稱為域。域是具有含義的最小命名數(shù)據(jù)。域不同于變量主要在于它是記錄的一部分。

    2記錄名與域名

    就像數(shù)組一樣，在記錄中也有兩種標識符：記錄的名字student和記錄中各個域的名字。

    域名（student.id student.name）

11.4 記錄與數(shù)組

1、記錄與數(shù)組的比較

    數(shù)組定義了元素的集合，而記錄定義了元素可以確認的部分。

2、記錄數(shù)組

    1什么時候使用記錄數(shù)組？

    如果我們需要定義元素的集合，且同時還需要定義元素的屬性，那么可以使用記錄數(shù)組。

    2規(guī)則

    1、數(shù)組的名字定義了整個結(jié)構(gòu)，作為一個整體的學生組。

    2、首先定義元素，然后在定義元素的部分（屬性），如（student[2]）.id，括號告訴我們索引運算符要先于點運算符。

    3、通常使用循環(huán)來讀記錄數(shù)組中的數(shù)據(jù)。

    3數(shù)組與記錄數(shù)組

    數(shù)組可以看成是記錄數(shù)組的一種特例，其中每個元素是只帶一個域的記錄。

11.3  鏈表

1、為什么要用到鏈表？

      記錄也是為了處理大量的數(shù)據(jù)而被需要的一個數(shù)據(jù)結(jié)構(gòu)。

2、什么是鏈表？

    鏈表是一個有序數(shù)據(jù)的集合，其中每個元素（節(jié)點）包含下一個元素的地址。鏈表中的節(jié)點是至少包含兩個域的記錄。

3、鏈表的基本知識

    1元素

    習慣上稱節(jié)點，包含兩個部分：數(shù)據(jù)和鏈。鏈包含指明列表中下一個元素的指針（地址）；

    2空指針和空鏈表

    3節(jié)點間的連線：實心圓和箭頭；

    4鏈表名和節(jié)點名

    ①鏈表名是頭指針的名字，該頭指針指向表中的第一個節(jié)點。

    ②節(jié)點的名字與指向節(jié)點的指針有關(guān)。不同語言不同。C語言的約定是指向節(jié)點的指針稱為p，則稱節(jié)點為*p。這種命名約定隱含一個節(jié)點可以有多于一個名字。

4、數(shù)組與鏈表區(qū)別

    1連接工具：數(shù)組是索引，鏈表是指向下一元素的鏈（指針或地址）

    2在內(nèi)存中的存儲方式：數(shù)組是無間隔存儲；鏈表是有間隔存儲。

5、鏈表操作

    1搜索鏈表

    鏈表的搜索算法只能是順序的。由于鏈表中的節(jié)點沒有特定的名字，我們使用兩個指針來進行搜索：

pre（先前的）和cur（當前的）。

    搜索算法使用一個標記（一個只能取真值或假值的變量），目標找到為真，未找到為假。

    2插入節(jié)點

    在插入鏈表之前，我們首先要使用搜索算法。如果搜索算法的返回值為假，將允許插入，否則終止算法。因為我們不允許重復值的數(shù)據(jù)。

    ①在空表中插入

    ②在表的開始插入

    ③在表的末尾插入

    ④在表中間插入

    對list<--new的理解

    3刪除節(jié)點

    在插入鏈表之前，我們首先要使用搜索算法。如果搜索算法的返回值為真（節(jié)點找到），我們可以在鏈表中刪除該節(jié)點。

    ①刪除首節(jié)點

    ②刪除中間或末尾節(jié)點

    4檢索節(jié)點

    檢索就是為了檢索或復制節(jié)點中的所含數(shù)據(jù)的目的而隨機訪問節(jié)點。在檢索之前也是需要檢索的。

檢索只使用cur指針。

    遍歷鏈表

    為了遍歷鏈表我們需要一個步行指針，當指針被處理時，他從一個節(jié)點移到另一個節(jié)點。

    使用循環(huán)，步行指針為空的時候，循環(huán)終止。

6、鏈表的應用（與數(shù)組應用比較）

如果需要大量的插入和刪除，那么鏈表是合適的數(shù)據(jù)結(jié)構(gòu)。但是搜索一個鏈表比搜索一個數(shù)組要慢。

    11.4 疑問：

為什么沒有記錄操作？鏈表為什么是有序的？