數(shù)據(jù)邏輯結(jié)構(gòu)淺析

葉軍偉

（麗江師范高等專(zhuān)科學(xué)校，云南麗江 674100）

數(shù)據(jù)邏輯結(jié)構(gòu)淺析

葉軍偉

（麗江師范高等專(zhuān)科學(xué)校，云南麗江 674100）

在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的邏輯結(jié)構(gòu)通常是指程序設(shè)計(jì)問(wèn)題中（可以是數(shù)值計(jì)算，也可以是非數(shù)值計(jì)算）計(jì)算機(jī)的操作對(duì)象（又叫數(shù)據(jù)元素）之間的抽象的邏輯上的關(guān)系和基于這種邏輯關(guān)系的運(yùn)算。本文介紹了幾類(lèi)常用的邏輯結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)；邏輯結(jié)構(gòu)；程序設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何一個(gè)問(wèn)題中，我們要處理的數(shù)據(jù)都不會(huì)孤立存在，它們之間總會(huì)存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱(chēng)為結(jié)構(gòu)。抽象的邏輯上的關(guān)系稱(chēng)為邏輯結(jié)構(gòu)，物理的在計(jì)算機(jī)中的存儲(chǔ)關(guān)系稱(chēng)為存儲(chǔ)結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間的關(guān)系，有四種常用的數(shù)據(jù)結(jié)構(gòu)：集合結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)。本文中的數(shù)據(jù)結(jié)構(gòu)是從操作對(duì)象抽象出來(lái)的數(shù)學(xué)模型，結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱(chēng)為邏輯結(jié)構(gòu)。

1 集合結(jié)構(gòu)

集合結(jié)構(gòu)是由具有相同屬性的數(shù)據(jù)元素按任意次序排列而成。若集合為空，則表示為{}，若非空則表示為：

其中n＞0，每個(gè)元素的下標(biāo)為對(duì)該元素的編號(hào)，它是為了區(qū)別而任意標(biāo)注的，不代表任何次序。

2 線(xiàn)性結(jié)構(gòu)

線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)元素是一對(duì)一的關(guān)系，是有序的集合。其特點(diǎn)是：可以用元素的下標(biāo)確定該元素的位置；存在唯一的一個(gè)“第一個(gè)”數(shù)據(jù)元素和唯一的一個(gè)“最后一個(gè)”數(shù)據(jù)元素；除第一個(gè)元素外，集合中的每個(gè)數(shù)據(jù)元素有且只有一個(gè)前驅(qū)；除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)后繼。

2.1 線(xiàn)性表。線(xiàn)性表是具有相同屬性的數(shù)據(jù)元素的一個(gè)有限序列。該序列中元素的個(gè)數(shù)稱(chēng)為線(xiàn)性表長(zhǎng)度。線(xiàn)性表長(zhǎng)度可以為0，表明它是一個(gè)空表，即不含有任何元素。若線(xiàn)性表為一個(gè)非空表，則一般表示為：

線(xiàn)性表中的第一個(gè)元素a1稱(chēng)為表頭元素，an稱(chēng)為表尾元素。線(xiàn)性表的元素是按照前后位置線(xiàn)性有序的。

2.2 棧。棧是一種特殊的線(xiàn)性表，其限定僅在表尾進(jìn)行插入或刪除操作。棧的表頭端稱(chēng)為棧底，表尾端叫做棧頂。由于棧的插入和刪除僅在棧頂一端進(jìn)行，后進(jìn)棧的元素必定先出棧，所以棧又稱(chēng)為后進(jìn)先出的線(xiàn)性表。

2.3 隊(duì)列。和棧相反，它只允許在表的一端（隊(duì)尾）進(jìn)行插入操作，而在表的另一端（隊(duì)頭）進(jìn)行刪除操作。隊(duì)列是一種先進(jìn)先出的線(xiàn)性表。

除了以上三種線(xiàn)性結(jié)構(gòu)外，還有串、數(shù)組和廣義表等線(xiàn)性結(jié)構(gòu)。

3 樹(shù)型結(jié)構(gòu)

樹(shù)型結(jié)構(gòu)是一種重要的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。常見(jiàn)的有樹(shù)和二叉樹(shù)，而多顆樹(shù)或者二叉樹(shù)則稱(chēng)為森林，直觀(guān)看來(lái)，樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。

3.1 樹(shù)。樹(shù)是n（n大于等于0）個(gè)結(jié)點(diǎn)的有限集。在任意一顆非空樹(shù)中：①有唯一的一個(gè)根結(jié)點(diǎn)；②當(dāng)n＞1時(shí)，其余結(jié)點(diǎn)可分為m（m＞0）個(gè)交集為空的有限集合K1,K2,…,Km,其中每一個(gè)集合本身又是一顆樹(shù)，并且稱(chēng)其為根的子樹(shù)。

3.2 二叉樹(shù)。二叉樹(shù)是一種特殊的樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)，并且子樹(shù)有左右之分。二叉樹(shù)的遞歸定義為：二叉樹(shù)或者是一棵空樹(shù)，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的子樹(shù)所組成的非空樹(shù)，這兩棵子樹(shù)又同樣都是一棵二叉樹(shù)，分別稱(chēng)作根的左子樹(shù)和右子樹(shù)。

4 圖狀結(jié)構(gòu)

圖狀結(jié)構(gòu)是由頂點(diǎn)集合和邊集合組成的。其中，頂點(diǎn)集合是頂點(diǎn)的非空有限集，邊集合是邊的有限集合，邊集合可以為空，邊是頂點(diǎn)的無(wú)序?qū)蛐蚺肌?duì)于頂點(diǎn)集合上的每個(gè)頂點(diǎn)，在邊集合中都允許有任意多個(gè)前驅(qū)和任意多個(gè)后繼，即對(duì)每個(gè)頂點(diǎn)的前驅(qū)和后繼個(gè)數(shù)均不加限制。

對(duì)于一個(gè)圖G，若邊集E(G)中的邊是頂點(diǎn)的無(wú)序?qū)Γ瑒t稱(chēng)此圖為無(wú)向圖；若若邊集E(G)中的邊是頂點(diǎn)的序偶，則稱(chēng)此圖為有向圖。

圖狀結(jié)構(gòu)是一種較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，在線(xiàn)性結(jié)構(gòu)中，數(shù)據(jù)元素之間為線(xiàn)性關(guān)系，在樹(shù)型結(jié)構(gòu)中，數(shù)據(jù)元素之間為層次關(guān)系，有明顯的前驅(qū)和后繼，而在圖狀結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系可以是任意的。

5 結(jié)束語(yǔ)

計(jì)算機(jī)應(yīng)用范圍的普及，需要處理的信息量也變得十分巨大，信息的類(lèi)型也多種多樣，而相應(yīng)的需要開(kāi)發(fā)的系統(tǒng)程序和應(yīng)用程序也規(guī)模很大，結(jié)構(gòu)復(fù)雜。因此，要開(kāi)發(fā)設(shè)計(jì)出一個(gè)“好”的程序，必須分析待處理對(duì)象信息的特征及各對(duì)象信息之間存在的關(guān)系，抽象設(shè)計(jì)出適當(dāng)?shù)臄?shù)學(xué)模型，并根據(jù)需要對(duì)信息做出的操作和處理選取適當(dāng)?shù)臄?shù)學(xué)模型，這就是數(shù)據(jù)結(jié)構(gòu)所要研究的問(wèn)題。不管在何種類(lèi)型的程序設(shè)計(jì)中，數(shù)據(jù)的邏輯結(jié)構(gòu)的選擇都是最重要的設(shè)計(jì)考慮因素和前提。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)都表明，系統(tǒng)構(gòu)造的質(zhì)量和系統(tǒng)實(shí)現(xiàn)的困難程度都嚴(yán)重依賴(lài)于是否選擇了適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。很多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過(guò)來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。

要處理數(shù)據(jù)首先要把數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)內(nèi)，數(shù)據(jù)的存儲(chǔ)方法是數(shù)據(jù)邏輯結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示，所以討論一個(gè)數(shù)據(jù)邏輯結(jié)構(gòu)必須同時(shí)討論其可能的存儲(chǔ)結(jié)構(gòu)及其之上能夠執(zhí)行的算法才有意義。

[1]徐孝凱,王鳳祿.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程[M].北京:清華大學(xué)出版社,2005.

[2]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社,2007.

TP391

A

1003-5168(2014)04-0025-01