数据结构中经典算法分析

【前言】数据结构中经典算法分析由文秘帮小编整理而成，但愿对你的学习工作带来帮助。数据结构是一门研究数据的逻辑结构和存储结构（物理结构）以及它们之间的关系的学科，且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中，数据的逻辑结构是指数据之间逻辑关系的描述，逻辑结构的分类有线性结构、...

摘要：计算机数据结构是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具，数据结构与算法分析是两门紧密联系的学科，算法要靠好的数据结构来实现，二者的关系是密不可分的。本文主要对数据结构算法进行了研究，就经典算法展开了讨论，期望能对读者有所帮助。

关键词：数据结构；算法；软件设计

【中图分类号】TP311.12-4；G642

一、数据结构与算法概述

1.1数据结构

数据结构是一门研究数据的逻辑结构和存储结构（物理结构）以及它们之间的关系的学科，且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中，数据的逻辑结构是指数据之间逻辑关系的描述，逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构，也称为物理结构，在程序设计语言中，数据结构直接反映在数据类型上，比如一个整型变量就是一个节点，根据类型给他分配内存单元。

1.2算法

1.2.1算法是由基本运算及规定的运算顺序所构成的完整的解题步骤。计算机算法与数据结构之间的关系，算法最终依附于数据结构，数据结构直接影响算法的选择和运行效率。运算是计算机完成的，这就要设计计算机在操作时对相的一些操作模式，如插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。

1.2.2算法与数据结构研究的目的简单地说就是优化代码，提高程序执行效率。比如，把一堆无顺的数据通过一个算法实现顺序排列实现方法太多太多，但是也许运行速率最快的占用的存储空间很大也许运行速率不是很快的占用的存储空间却很小，所以要通过算法与数据结构分析。

二、数据机构经典算法的选择

选择经典算法的重要性，PASCAL语言的创始人、著名的计算机科学家N.沃思说得好“程序=数据结构+算法”，足以见得算法在程序设计中的重要地位。在合理的数据结构基础上，算法是对数据结构的操作（运算），是数据处理的核心。数据结构中所讲的基本数据结构有线性表、堆栈、队列、数组、树、二叉树、图以及相应的算法。一个算法是建立在某种数据结构的基础上，一个算法不可能脱离数据结构而孤立存在。只有通过分析算法，才能真正掌握某种数据结构。一个经典算法往往能起到以一当十、以点带面的关键作用。选择好经典算法后下一步就是要对其展开综合分析，下面以具体的算法为例进行讨论。

三、利用经典算法说明基本原理

3.1经典算法应能体现某个数据结构的基本特征

我们知道线性表顺序存储时其优点是能够对每个数据元素随机访问，存储密度高，其缺点是插入、删除操作时需要移动大量的数据元素，操作效率低。“向有序（由小到大或由大到小）的线性表（顺序存储）插入一个新的数据元素”，这一经典算法集中反映了线性表顺序存储的这些特点。

分析：将一个值为X的数据元素插入到有序（由小到大或由大到小）的线性表（顺序存储）中，可以分两步进行，首先查找到值为X的数据元素在线性表中应有的位置，采用从头到尾循环比较的方法确定其位置I，然后，将第I个以后的全部数据元素向后移动一个存储单元，最后将值为X的数据元素存放到第I个位置上，线性表元素个数增1。

【算法1】

PROCEDUREINSERT（V，m，n，X）

//将值为X的数据元素插入到V数组中，（线性表顺序存贮在V中）m为最多元素个数，n为当前实际元素个数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】的优点是简单，便于理解，缺点是：①循环体内有提前退出语句，不利于结构化程序设计；②确定新数据元素位置和移动数据元素分两步进行，有重复操作，可以改进之，将两步合并一步完成，即将循环比较与移动数据元素同时进行。从线性表的尾部开始向前循环比较，比新数据元素大者后移，直到小于等于时停止。

【算法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】中循环条件，当循环结束后I=0或V（I）〈=X，新数据元素的位置为I+1，【算法1】的时间复杂度为0（2n），而【算法2】的时间复杂度为0（n），效率提高一倍。循环结构是结构化程序设计中最基本最核心的部分，归纳循环条件是关键。【算法2】能进一步推广。

3.2利用经典算法学习算法设计

经典算法能给学习者以启示、示范作用。分析：可以将【算法2】用于对线性表（顺序存储）排序算法中。在直接插入排序算法中，其算法思想是从第2个数据元素开始直到第n个数据元素，逐一插入到已有序的子线性表中。【算法3】

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】其结构分为双重循环，外循环完成逐一取数据元素，即取第I个数据元素，内循环完成将第I个数据元素插入到前I-1个已有序的子线性表中。内循环完成的功能可以独立成为一个子函数（子过程），可以借用【算法2】。这正是结构化程序设计思想的体现，即主程序完成任务的划分，说明“做什么”，子函数（子过程）完成任务的具体实现，说明“如何做”。结构化程序设计方法采取“分解”的手段来控制系统的复杂性，将大系统划分为若干个相对独立的、功能单一的子模块。一方面子函数（子过程）可以实现软件的重用性，在不同的程序段有相同的处理过程时调用子函数（子过程），减少软件开发的工作量；另一方面子函数（子过程）对具体的实现技术细节进行隐藏，便于开发人员集中精力把握软件开发的核心和主要问题，降低了软件开发难度，从而保证软件质量。

四、结束语

对于计算机科学来说，算法的概念至关重要。通俗的讲，算法是指解决问题的一种方法或一个过程，在众多的算法中选择好少量的经典算法对于研究数据结构以及解决实际问题至关重要。掌握好经典算法的原理和规律，将对计算机程序设计开发起到事半功倍的作用。

参考文献：

[1]邓建龙.计算机软件基础数据结构之算法[J].信息与电脑：理论版，2012，（6）.

作者简介：赵梦龙（1981年12月21日），男，河南驻马店市，硕士研究生，讲师，信息安全与密码学