前言

　　由于自己已經(jīng)大四，開始決定寫這個博客，記錄下自己每一天一點(diǎn)一滴的進(jìn)步，希望自己的收獲能與大家一同分享。數(shù)據(jù)結(jié)構(gòu)這門課是我在大二上學(xué)期所學(xué)的，由于之前學(xué)習(xí)C語言的時候已經(jīng)接觸了常用的一些數(shù)據(jù)結(jié)構(gòu)，加之自己以前也看過不少數(shù)據(jù)結(jié)構(gòu)方面的書，因此學(xué)習(xí)起來比較輕松。馬上要參加2012年的研究生入學(xué)考試，數(shù)據(jù)結(jié)構(gòu)作為專業(yè)課的一門，就要重新開始復(fù)習(xí)了。因此通過記錄這個博客，來每天更新自己的復(fù)習(xí)成果。這是一個系列，希望自己能夠堅持下去。所用的教材是清華大學(xué)出版的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》。

?

基本概念

　　數(shù)據(jù)（data）：客觀事物的符號表示。【CS】指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。【注】一般來說，現(xiàn)實(shí)中的數(shù)據(jù)輸入到計算機(jī)后，都會被轉(zhuǎn)化為計算機(jī)的數(shù)據(jù)表示。

　　數(shù)據(jù)元素（data element）：數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。【注】比如C語言中的結(jié)構(gòu)體，C++中的類等等。

　　數(shù)據(jù)項（data item）：數(shù)據(jù)元素的組成單位。【注】比如結(jié)構(gòu)體中的成員等等。

　　數(shù)據(jù)對象（data object）：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。【注】比如，在C語言中，一個數(shù)組的元素的全體就是一個數(shù)據(jù)對象。按照概念來講，這個數(shù)組并不屬于數(shù)據(jù)對象，因?yàn)樗皇谴鎯?shù)據(jù)對象一種數(shù)據(jù)結(jié)構(gòu)的組織形式（下面會講到數(shù)據(jù)結(jié)構(gòu)的概念）。

　　數(shù)據(jù)結(jié)構(gòu)（data structure）：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存在以下四種基本結(jié)構(gòu)（structure）：（1）集合；（2）線性結(jié)構(gòu)；（3）樹形結(jié)構(gòu)；（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。結(jié)構(gòu)有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之分。邏輯結(jié)構(gòu)是抽象角度來講數(shù)據(jù)之間的關(guān)系，而物理結(jié)構(gòu)又稱為存儲結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的實(shí)際表示。存在邏輯相關(guān)的數(shù)據(jù)不一定存在物理相關(guān)，十分明顯的一個例子是鏈表。

　　數(shù)據(jù)類型（data type）：一個值的集合和定義在這個值即上的一組操作的總稱。【注】看到它是不是很容易想起來類（class）的定義？

算法和算法分析

　　算法（algorithm）：對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它具有以下5個重要特性：

　　　　（1）有窮性。【注】必須能夠結(jié)束。

　　　　（2）確定性。【注】相同輸入必須得到相同輸出。

　　　　（3）可行性。【注】算法操作必須通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。

　　　　（4）輸入。【注】可以沒有輸入。

　　　　（5）輸出。【注】必須有輸出。

　　算法設(shè)計應(yīng)該考慮的目標(biāo)有：

　　　　（1）正確性。

　　　　（2）可讀性。

　　　　（3）健壯性。

　　　　（4）效率與低存儲量需求。【注】也許大家現(xiàn)在不注意存儲量，對內(nèi)存隨意分配，有時候甚至對內(nèi)存只申請而沒有釋放，這都是一種不好的習(xí)慣。

　　在此小節(jié)中，比較重要的一個概念就是時間復(fù)雜度與空間復(fù)雜度，他們是衡量算法效率高低的重要指標(biāo)。具體的不再介紹，如果對它們不了解，可以再次閱讀課本上相關(guān)內(nèi)容。需要提一點(diǎn)的是，在通常的計算機(jī)科學(xué)中，時間資源與空間資源往往“魚與熊掌不可得兼”，所以當(dāng)追求時間效率時，往往會犧牲大量的空間資源，但對于當(dāng)前情況來說是可取的，因?yàn)橛布蟠筘S富的今天，人們不必為沒有空間而感到捉襟見肘。當(dāng)然，也可以通過犧牲時間來降低空間復(fù)雜度，但大多數(shù)情況下，這樣的事情不會發(fā)生。畢竟時間的重要性要大于空間的重要性。

轉(zhuǎn)載于:https://www.cnblogs.com/XjChenny/archive/2011/09/06/2169105.html

總結(jié)

以上是生活随笔為你收集整理的【数据结构复习】（1）绪论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。