數(shù)據(jù)結(jié)構(gòu)中經(jīng)典算法分析

摘要：計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)從業(yè)和研究人員了解、開發(fā)及最大程度的利用計(jì)算機(jī)硬件的一種工具，數(shù)據(jù)結(jié)構(gòu)與算法分析是兩門緊密聯(lián)系的學(xué)科，算法要靠好的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，二者的關(guān)系是密不可分的。本文主要對數(shù)據(jù)結(jié)構(gòu)算法進(jìn)行了研究，就經(jīng)典算法展開了討論，期望能對讀者有所幫助。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法；軟件設(shè)計(jì)

【中圖分類號】TP311.12-4；G642

一、數(shù)據(jù)結(jié)構(gòu)與算法概述

1.1數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)（物理結(jié)構(gòu)）以及它們之間的關(guān)系的學(xué)科，且為該結(jié)構(gòu)定義相應(yīng)的運(yùn)算設(shè)計(jì)相應(yīng)的算法。這里的數(shù)據(jù)是指可輸入到計(jì)算機(jī)能被程序處理的符號的集合。其中，數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間邏輯關(guān)系的描述，邏輯結(jié)構(gòu)的分類有線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)，在程序設(shè)計(jì)語言中，數(shù)據(jù)結(jié)構(gòu)直接反映在數(shù)據(jù)類型上，比如一個整型變量就是一個節(jié)點(diǎn)，根據(jù)類型給他分配內(nèi)存單元。

1.2算法

1.2.1算法是由基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。計(jì)算機(jī)算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系，算法最終依附于數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接影響算法的選擇和運(yùn)行效率。運(yùn)算是計(jì)算機(jī)完成的，這就要設(shè)計(jì)計(jì)算機(jī)在操作時對相的一些操作模式，如插入、刪除和修改的算法。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。

1.2.2算法與數(shù)據(jù)結(jié)構(gòu)研究的目的簡單地說就是優(yōu)化代碼，提高程序執(zhí)行效率。比如，把一堆無順的數(shù)據(jù)通過一個算法實(shí)現(xiàn)順序排列實(shí)現(xiàn)方法太多太多，但是也許運(yùn)行速率最快的占用的存儲空間很大也許運(yùn)行速率不是很快的占用的存儲空間卻很小，所以要通過算法與數(shù)據(jù)結(jié)構(gòu)分析。

二、數(shù)據(jù)機(jī)構(gòu)經(jīng)典算法的選擇

選擇經(jīng)典算法的重要性，PASCAL語言的創(chuàng)始人、著名的計(jì)算機(jī)科學(xué)家N.沃思說得好“程序=數(shù)據(jù)結(jié)構(gòu)+算法”，足以見得算法在程序設(shè)計(jì)中的重要地位。在合理的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上，算法是對數(shù)據(jù)結(jié)構(gòu)的操作（運(yùn)算），是數(shù)據(jù)處理的核心。數(shù)據(jù)結(jié)構(gòu)中所講的基本數(shù)據(jù)結(jié)構(gòu)有線性表、堆棧、隊(duì)列、數(shù)組、樹、二叉樹、圖以及相應(yīng)的算法。一個算法是建立在某種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，一個算法不可能脫離數(shù)據(jù)結(jié)構(gòu)而孤立存在。只有通過分析算法，才能真正掌握某種數(shù)據(jù)結(jié)構(gòu)。一個經(jīng)典算法往往能起到以一當(dāng)十、以點(diǎn)帶面的關(guān)鍵作用。選擇好經(jīng)典算法后下一步就是要對其展開綜合分析，下面以具體的算法為例進(jìn)行討論。

三、利用經(jīng)典算法說明基本原理

3.1經(jīng)典算法應(yīng)能體現(xiàn)某個數(shù)據(jù)結(jié)構(gòu)的基本特征

我們知道線性表順序存儲時其優(yōu)點(diǎn)是能夠?qū)γ總€數(shù)據(jù)元素隨機(jī)訪問，存儲密度高，其缺點(diǎn)是插入、刪除操作時需要移動大量的數(shù)據(jù)元素，操作效率低?！跋蛴行颍ㄓ尚〉酱蠡蛴纱蟮叫。┑木€性表（順序存儲）插入一個新的數(shù)據(jù)元素”，這一經(jīng)典算法集中反映了線性表順序存儲的這些特點(diǎn)。

分析：將一個值為X的數(shù)據(jù)元素插入到有序（由小到大或由大到小）的線性表（順序存儲）中，可以分兩步進(jìn)行，首先查找到值為X的數(shù)據(jù)元素在線性表中應(yīng)有的位置，采用從頭到尾循環(huán)比較的方法確定其位置I，然后，將第I個以后的全部數(shù)據(jù)元素向后移動一個存儲單元，最后將值為X的數(shù)據(jù)元素存放到第I個位置上，線性表元素個數(shù)增1。

【算法1】

PROCEDUREINSERT（V，m，n，X）

//將值為X的數(shù)據(jù)元素插入到V數(shù)組中，（線性表順序存貯在V中）m為最多元素個數(shù)，n為當(dāng)前實(shí)際元素個數(shù)IF（m=n）THEN{“OVERFLOW”；RETURN}FORI=1TOnDO

IF（X〈V（I））THENBREAK

FORJ=nTOIBY-1DOV（J+1）=V（J）V（I）=X

n=n+1

RETURN

分析：【算法1】的優(yōu)點(diǎn)是簡單，便于理解，缺點(diǎn)是：①循環(huán)體內(nèi)有提前退出語句，不利于結(jié)構(gòu)化程序設(shè)計(jì)；②確定新數(shù)據(jù)元素位置和移動數(shù)據(jù)元素分兩步進(jìn)行，有重復(fù)操作，可以改進(jìn)之，將兩步合并一步完成，即將循環(huán)比較與移動數(shù)據(jù)元素同時進(jìn)行。從線性表的尾部開始向前循環(huán)比較，比新數(shù)據(jù)元素大者后移，直到小于等于時停止。

【算法2】

PROCEDUREINSERT（V，m，n，X）

IF（m=n）THEN{“OVERFLOW”；RETURN}

I=n

WHILE（I〉=1）AND（V（I）〉X）DO{V（I+1）=V（I）；I=I-1}V（I+1）=X

n=n+1

RETURN

分析：注意【算法2】中循環(huán)條件，當(dāng)循環(huán)結(jié)束后I=0或V（I）〈=X，新數(shù)據(jù)元素的位置為I+1，【算法1】的時間復(fù)雜度為0（2n），而【算法2】的時間復(fù)雜度為0（n），效率提高一倍。循環(huán)結(jié)構(gòu)是結(jié)構(gòu)化程序設(shè)計(jì)中最基本最核心的部分，歸納循環(huán)條件是關(guān)鍵?！舅惴?】能進(jìn)一步推廣。

3.2利用經(jīng)典算法學(xué)習(xí)算法設(shè)計(jì)

經(jīng)典算法能給學(xué)習(xí)者以啟示、示范作用。分析：可以將【算法2】用于對線性表（順序存儲）排序算法中。在直接插入排序算法中，其算法思想是從第2個數(shù)據(jù)元素開始直到第n個數(shù)據(jù)元素，逐一插入到已有序的子線性表中?！舅惴?】

PROCEDURESORT（V，n）

FORI=2TOnDO

{Y=V（I）

J=I-1

WHILE（J〉=1）AND（V（J）〉Y）DO{V（J+1）=V（J）；J=J-1}V（J+1）=Y}

RETURN

分析：【算示3】其結(jié)構(gòu)分為雙重循環(huán)，外循環(huán)完成逐一取數(shù)據(jù)元素，即取第I個數(shù)據(jù)元素，內(nèi)循環(huán)完成將第I個數(shù)據(jù)元素插入到前I-1個已有序的子線性表中。內(nèi)循環(huán)完成的功能可以獨(dú)立成為一個子函數(shù)（子過程），可以借用【算法2】。這正是結(jié)構(gòu)化程序設(shè)計(jì)思想的體現(xiàn)，即主程序完成任務(wù)的劃分，說明“做什么”，子函數(shù)（子過程）完成任務(wù)的具體實(shí)現(xiàn)，說明“如何做”。結(jié)構(gòu)化程序設(shè)計(jì)方法采取“分解”的手段來控制系統(tǒng)的復(fù)雜性，將大系統(tǒng)劃分為若干個相對獨(dú)立的、功能單一的子模塊。一方面子函數(shù)（子過程）可以實(shí)現(xiàn)軟件的重用性，在不同的程序段有相同的處理過程時調(diào)用子函數(shù)（子過程），減少軟件開發(fā)的工作量；另一方面子函數(shù)（子過程）對具體的實(shí)現(xiàn)技術(shù)細(xì)節(jié)進(jìn)行隱藏，便于開發(fā)人員集中精力把握軟件開發(fā)的核心和主要問題，降低了軟件開發(fā)難度，從而保證軟件質(zhì)量。

四、結(jié)束語

對于計(jì)算機(jī)科學(xué)來說，算法的概念至關(guān)重要。通俗的講，算法是指解決問題的一種方法或一個過程，在眾多的算法中選擇好少量的經(jīng)典算法對于研究數(shù)據(jù)結(jié)構(gòu)以及解決實(shí)際問題至關(guān)重要。掌握好經(jīng)典算法的原理和規(guī)律，將對計(jì)算機(jī)程序設(shè)計(jì)開發(fā)起到事半功倍的作用。

參考文獻(xiàn)：

[1]鄧建龍.計(jì)算機(jī)軟件基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)之算法[J].信息與電腦：理論版，2012，（6）.

作者簡介：趙夢龍（1981年12月21日），男，河南駐馬店市，碩士研究生，講師，信息安全與密碼學(xué)