資料結構與算法問題解析 緒論

本章的目的是闡述算法分析的重要性、它們的表示法和關系，并盡可能求解多個問

題。首先，讓我們重點關注算法的基本要素、分析的重要性，然後再逐漸讨論上述提及

的其他主題。在完成本章的學習後，能夠分析任意給定算法的複雜度（特别是遞歸函數）。

1.1 變量

在開始讨論變量的定義之前，先來看看以前學習過的數學方程式，它與變量是有關

聯的。許多人從國中階段就學會了求解許多數學方程式。例如，考慮如下方程式：

x2+2y-2=1

我們不必關心這個方程式用在什麼地方。需要了解的重點是，這個方程式包含一些

名稱(x和y),它們能儲存值（資料）。即名稱(x和y)是用來表示資料的占位符。類似地，

在計算機科學中，也需要一些東西來儲存資料，變量就是實作這一功能的方式。

1.2資料類型

在上述方程式中，變量x和y能表示任意值，例如整數(10、20)、實數(0.23、5.5)》或僅僅是0和1。為了求解該方程式，需要将它們與其所能表示的資料值的類型關聯起來。在計算機科學中，資料類型就用于這一目的。程式設計語言中的資料類型是指具有預定義值的一個資料集合。典型的資料類型有：整數、浮點數、字元、字元串等。計算機記憶體中全由0和1填充。如果直接用0和1來編碼求解問題是非常困難的。為了幫助程式員，程式設計語言和編譯器提供了資料類型。例如，整數(integer)資料類型占2位元組（具體的位元組數與編譯器有關），浮點(float)資料類型占4位元組等。這就是說，在記憶體中将2個位元組組合起來(16位)可稱為整數。類似

地，将4個位元組組合起來(32位)可稱為浮點數。資料類型可以減少編碼的工作量。在頂層，有兩種資料類型：系統定義的資料類型（也稱為基本資料類型）。使用者定義的資料類型。

1.系統定義的資料類型（基本資料類型）》

系統定義的資料類型叫作基本資料類型。許多程式設計語言提供的基本資料類型有：it、float、char、double、bool等。每一個基本資料類型配置設定的位數與程式設計語言、編譯器和作業系統有關。對于相同的基本資料類型，不同的程式設計語言可能使用不同的大小。根據資料類型的大小變化，總的有效資料值（值域）也是變化的。例如，it可能占2位元組或4位元組。如果占2位元組(16位)，則總的取值範圍為一32768~32767(-215~215-1);如果占4位元組(32位)，那麼總的取值範圍為-2147483648~2147483648(一231~231一1)。其他資料類型也是這樣。

2.使用者定義的資料類型

如果系統定義的資料類型不夠，那麼大多數程式設計語言允許使用者定義自己的資料類型，稱為使用者定義的資料類型。使用者定義的資料類型的經典執行個體是：C/C++中的結構體和Java中的類。

例如，下面的代碼片段把許多系統定義的資料類型組合在一起，然後用新的名字“new Type'”将其表示為使用者定義的資料類型。這樣可以更加靈活和友善地處理計算機記憶體。

public int datal;

public int data 2;

private float data3;

private char data;

/1操作

1.3 資料結構

基于上述讨論，一旦變量中有資料，就需要一種操縱這些資料的機制來求解問題。

資料結構(data structure)就是計算機中存儲群組織資料的一種特定方式，它将使得資料

處理更加有效。一個資料結構就是一種組織和存儲資料的特定形式。常用的資料結構包

括數組、檔案、連結清單、棧、隊列、樹和圖等。

根據元素的組織方式，資料結構可以分為兩種類型：

1)線性資料結構：可以按線性次序通路元素，但它并不強制将所有元素連續地存儲

在一起（例如，連結清單）。例如，連結清單、棧和隊列。

2)非線性資料結構：這種資料結構的元素是以非線性次序來存儲和通路的。例如，

樹和圖。

1.4抽象資料類型

在定義抽象資料類型前，先從不同的視角分析系統定義的資料類型。我們都知道，在預設情況下，所有基本資料類型(int、float等)都支援基本運算，如加法和減法。系統實作了這些基本資料類型的基本運算。對于使用者自定義的資料類型，也需要定義相應的運算。在實際使用這些運算時需要實作這些運算。即，通常使用者定義的資料類型需要與它們的運算一起定義。為簡化求解問題的過程，将資料結構和相關的運算組合起來，将其稱為抽象資料類

型(ADT)。一個ADT包含兩個部分：

1)資料的聲明。

2)運算的聲明。

常用ADT包括：連結清單、棧、隊列、優先隊列、二叉樹、字典、并查集（并和查找）、

散清單、圖和許多其他類型。例如，棧使用後進先出(LIFO)機制将資料存儲到資料結構

中，最後插入棧的元素第一個被删除。它的常用操作有：建立棧、入棧、出棧、查找棧

頂元素、在棧中查找某一個元素等。

當定義ADT時，不需要考慮其實作細節。僅當需要使用它們時才考慮具體的實作。

不同的ADT類型适合不同的應用。有些是用于高度專業化的特定任務。到本書結束時，

我們将探讨許多ADT。讀者也能夠學會将相關資料結構與需要解決的問題進行關聯。