《計算機科學導論》之數據結構基礎知識

《計算機科學導論（第二版）》  11章   數據結構

11.1  引言 

1、為什么要使用數據結構？

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

2、數據結構是什么？

    數據結構是相互之間存在一種或多種特定關系的數據元素的集合。

3、三種數據結構

    數組；

    記錄;

    鏈表；

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

11.2  數組

1、為什么使用數組？

    為了處理大量的數據，需要一個數據結構，如數組。當然還有其他的數據結構。

2、數組的定義

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

3、數組的基礎知識

    1索引

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

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

    有些現代語言（如C、C++和Java）是從0開始數組索引的。

    2數組名與元素名

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

    3多維數組

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

    多維數組（多于二維的數組）也是可以的。

    二維數組在內存中可以使用行主序存儲或列主序存儲，第一種更常見。

4、數組操作

    數組操作是值得一些把數組作為數據結構的操作。

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

    1查找

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

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

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

    ①尾部的插入

    ②開始或中間的插入

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

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

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

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

    4檢索

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

5、數組的應用

    當需要進行的插入和刪除操作數目較少，而需要大量的查找和檢索操作時，數組是合適的數據結構。

11.3  記錄

1、為什么要用記錄？

    記錄也是為了處理大量的數據而被需要的一個數據結構。

2、什么是記錄？

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

    記錄中的數據必須都與一個對象關聯。

3、記錄的基礎知識

    1域

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

    2記錄名與域名

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

    域名（student.id student.name）

11.4 記錄與數組

1、記錄與數組的比較

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

2、記錄數組

    1什么時候使用記錄數組？

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

    2規則

    1、數組的名字定義了整個結構，作為一個整體的學生組。

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

    3、通常使用循環來讀記錄數組中的數據。

    3數組與記錄數組

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

11.3  鏈表

1、為什么要用到鏈表？

      記錄也是為了處理大量的數據而被需要的一個數據結構。

2、什么是鏈表？

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

3、鏈表的基本知識

    1元素

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

    2空指針和空鏈表

    3節點間的連線：實心圓和箭頭；

    4鏈表名和節點名

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

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

4、數組與鏈表區別

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

    2在內存中的存儲方式：數組是無間隔存儲；鏈表是有間隔存儲。

5、鏈表操作

    1搜索鏈表

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

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

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

    2插入節點

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

    ①在空表中插入

    ②在表的開始插入

    ③在表的末尾插入

    ④在表中間插入

    對list<--new的理解

    3刪除節點

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

    ①刪除首節點

    ②刪除中間或末尾節點

    4檢索節點

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

檢索只使用cur指針。

    遍歷鏈表

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

    使用循環，步行指針為空的時候，循環終止。

6、鏈表的應用（與數組應用比較）

如果需要大量的插入和刪除，那么鏈表是合適的數據結構。但是搜索一個鏈表比搜索一個數組要慢。

    11.4 疑問：

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