1.2 基本概念和術語

1.2.1 基本概念和術語

本節將對一些常用的概念和術語進行介紹，這些概念和術語在以后的章節中會多次出現。

1. 數據

數據即信息的載體，是對客觀事物的符號表示，凡能輸入到計算機中并被計算機程序處理的符號都可稱之為數據，如整數、實數、字符、文字、聲音、圖像等都是數據，如圖1.3所示。

2. 數據元素

數據元素是數據的基本單位，它在計算機處理和程序設計中通常作為獨立個體。數據元素一般由一個或多個數據項組成，一個數據元素包含多個數據項時，常稱為記錄、結點等。數據項也稱為域、字段、屬性、表目、頂點。

如表1-3所示，每個同學的信息即表中的一行，是一個數據元素。每個數據元素又包含若干個數據項，如專業、學號等。

3. 數據對象

數據對象是具有相同特征的數據元素的集合，是數據的一個子集，如一個整型數組、一個字符串數組都是一個數組對象。

例如要將表1-3中的學生信息按照學號大小進行排序，排序時比較的是各個數據元素中學號這一數據項的大小。此時整個表中的數據元素就是待處理的數據對象。

4. 數據結構

數據結構簡稱DS（Data Structure），是數據及數據元素的組織形式。任何數據都不是彼此孤立的，通常把相關聯的數據按照一定的邏輯關系組織起來，這樣就形成了一個數據結構。

數據結構包含兩個方面的內容，一是數據對象，二是數據對象中數據元素之間內在的關系。數據結構通常有四類基本形式：集合結構，線性結構，樹型結構，圖形結構或網狀結構。

（1）集合結構：集合結構中的數據元素除了同屬于一個集合外，它們之間沒有其他關系。各個數據元素是“平等”的，它們的共同屬性是“同屬于一個集合”。數據結構中的集合關系就類似于數學中的集合。

【例1-4】電視機、冰箱等家用電器構成的就是一個集合結構，如圖1.4所示。

（2）線性結構：線性結構中的數據元素之間是一對一的關系。

【例1-5】節氣是中國古代訂立的一種用來指導農事的補充歷法，是漢族勞動人民長期經驗的積累和智慧的結晶。春季的節氣有立春、雨水、驚蟄、春分、清明、谷雨，這些節氣一個接一個就是一種線性關系，如圖1.5所示。

（3）樹型結構：樹形結構中的數據元素之間存在一種一對多的層次關系。

【例1-6】院系機構的組織就是一種樹型結構，如圖1.6所示。計科系和電子系的地位是“平等”的，電子系開設有信息工程、通信、微電子等專業，它們受電子系的“領導”。反過來看，無論是通信工程，還是微電子，都屬于電子系，無論是計科系，還是電子系，都屬于某學院，即樹型結構中正關系是一對多，逆關系是一對一。

（4）圖狀結構：圖狀結構中的數據元素是多對多的關系。

【例1-7】在一個學生選課系統中，數據庫的設計采用的就是網狀結構，如圖1.7所示。把S1學生和他的選課記錄（選修的C1、C2兩門課程的選課記錄）鏈接起來，同樣把S2、S3、S4學生和他們的選課記錄鏈接起來，把C1課程和選修了C1課程的選課記錄（有S1、S2、S3、S4學生選修了C1）鏈接起來，同樣把C2、C3課程和選修了這些課程的選課記錄鏈接起來，通過分析可以發現一個學生可以選修若干門課程，某一課程可以被若干同學選修，學生與課程之間是多對多的關系。

5. 數據類型

數據類型是一組具有相同性質的操作對象以及該組操作對象上的運算方法的集合，如整數類型、字符類型等。每一種數據類型都有自身特點的一組操作方法，即運算規則。JAVA中提供的基本的數據類型有int，double，long，float，short，byte，character，boolean。

由于集合中的元素的關系極為松散，可用其他數據結構來表示，所以本書不做專門介紹。

從數據類型和數據結構的概念可知，二者的關系非常密切。數據類型可以看作是簡單的數據結構。數據的取值范圍可以看作是數據元素的有限集合，而對數據進行操作的集合可以看作是數據元素之間關系的集合。

1.2.2 數據的邏輯結構

數據的邏輯結構（Logic Structure）是從具體問題抽象出來的數學模型，與數據在計算機中的具體存儲沒有關系。數據的邏輯結構獨立于計算機，是數據本身所固有的特性。從邏輯上可以把數據結構分為線性結構和非線性結構，上述數據結構的定義就是數據的邏輯結構（Logic Structure），主要包括：集合、線性、樹和圖形結構，其中集合、樹和圖形結構都屬于非線性結構。

數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D上的關系集，它反映了D中各數據元素之間的前驅后繼關系，通常記為R，即一個數據結構可以表示成二元組B=(D,R)。

【例1-8】一年四季可表示成B1=(D1,R1)，其中

D1={春,夏,秋,冬}，R1={<春,夏>,<夏,秋>,<秋,冬>}；

序偶關系<春,夏>表示：春季之后的下一個季節是夏季，反過來夏季的前一個季節是春季，其他依此類推，通過關系集R1就可以描述出一年四季的更替順序春、夏、秋、冬，同時我們可以發現在關系集R1中，夏季和秋季都有一個直接前驅和一個直接后繼，春季作為一年之首是沒有前驅的，但是有一個直接后繼夏，冬季作為一年之尾沒有后繼，但是有一個前驅，所以二元組B1描述的是一個一對一關系的線性結構。

注意，<x,y>意為x和y之間存在"x領先于y"的次序關系。而(x,y)表示x和y之間沒有次序上的關系。

【例1-9】某單位的管理關系可表示成B2=(D2,R2)，其中

D2={總經理，部門經理A，部門經理B，組長A，組長B，組長C，組長D，職工A，職工B，職工C，職工D，職工E，職工F，職工G，}

R2={<總經理, 部門經理A>,<總經理, 部門經理B>,<部門經理A, 組長A>，<部門經理A, 組長B>，<部門經理B, 組長C>，<部門經理B, 組長D>，<組長A，職工A>，<組長A，職工B>，<組長A，職工C>， <組長D，職工D>，<組長D，職工E>，<組長D，職工F>，<組長D，職工G>}；

通過分析關系集R2可知該單位人員的關系為：一個總經理管理若干部門經理，每個部門經理管理若干小組長，每個小組長管理若干職工。但是每個職工的直接領導，即組長，只有一個，每個組長的直接領導，即部門經理，只有一個，每個部分經理的直接領導總經理只有一個，即二元組描述的是一個一對多關系的樹型結構，如圖1.8所示。

【例1-10】A某的人際關系可以表示成B3=(D3,R3)，其中

D3={A某，B某，C某，D某，E某，F某，G某，H某}，

R3={<A某,B某>,<A某,C某>,<B某，D某>，<B某,，E某>,<B某，F某>,<C某，F某>，<C某，G某>,<E某，H某>，<F某，H某>}；

通過分析關系集R3可知A某的人際關系為：每個人可以有多個朋友，同一個人也可以是多個人共同的朋友。例如，F某既是B某的朋友，也是C某的朋友，即二元組描述的是一個多對多關系的圖形結構，如圖1.9所示。

上述數據結構的定義僅是對操作對象的一種數學描述，是從操作對象抽象出來的數學模型，結構定義的“關系”抽述的是數據元素之間的邏輯關系，所以稱為邏輯結構。

1.2.3 數據的物理結構

我們討論數據結構的目的是為了在計算機中實現對它的操作，因此還需要研究在計算機中如何表示和存儲數據結構，即數據的物理結構（Physical Structure）。數據的物理結構又稱存儲結構，它的實現依賴于具體的計算機語言。數據存儲結構有順序和鏈式兩種不同的方式，順序存儲的特點是數據元素在存儲器的相對位置來體現數據元素相互間的邏輯關系，順序存儲結構通常用高級編程語言中的一維數組來描述或實現。

例如：一個有序的數字序列（25，34，48，57，63），25有一個直接后繼34，如果該有序表用數組存儲，通過圖1.10可以發現相鄰的25和34在存儲器中的地址也是相鄰的，即數據元素在存儲器中的相對位置可以體現數據元素在有序表中的前驅和后繼關系，整個數組在存儲器中占用的是一片連續的存儲空間。

鏈式存儲結構是通過一組任意的存儲單元來存儲數據元素的，而這些存儲單元可以是連續的，也可以是不連續的。為建立起數據元素之間的邏輯關系，對任一數據元素a，除了存放元素自身信息a之外，還需要存放與a有關系的其他元素的地址150，通過這個地址就可以找到下一個數據元素b，依此類推，可以發現字符序列（‘a’，‘b’，‘c’，‘d’，‘e’，‘f’）在存儲器中的地址是不連續的。

在順序存儲結構的基礎上，又可延伸出另外兩種存儲結構，即索引存儲和散列存儲。

索引存儲就是在數據文件的基礎上增加了一個索引表文件。通過索引表建立索引，可以把一個順序表分成幾個順序子表，其目的是在查詢時提高查找效率，避免盲目查找。

散列存儲就是通過數據元素與存儲地址之間建立起某種映射關系，使每個數據元素與每一個存儲地址之間盡量達到一一對應的目的。這樣，查找時同樣可以大大提高效率。

數據的邏輯結構和物理結構是密切相關的兩個方面，任何一個算法的設計取決于選定的邏輯結構，而算法的實現依賴于采用的存儲結構。綜上所述，數據結構主要描述的是數據元素之間的邏輯關系、數據在計算機系統中的存儲方式和數據的運算三個方面的內容，即數據的邏輯結構、存儲結構和數據的操作集合。