数据结构述

摘 要:数据结构是计算机及相关专业的基础课程,是提高计算机程序设计能力的必要条件.数据结构是介于数学、计算机软件和计算机硬件之间的一门课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等重要基础,广泛的应用于信息学、系统工程学等各种领域.本文简述了数据结构的基本概念,基本原理,运算方法.

关 键 词:数据结构;逻辑结构;物理结构;算法

中图分类号:TP3-0文献标识码:A文章编号:1006-4311(2014)07-0188-02

0引言

数据结构等于数据+结构,既有数据又有结构,结构就是关系,根据关系确定结构,结构又体现关系.本门课程所要研究的主要问题,第一,根据数据之间的逻辑关系如何组织这批数据?第二,如何将这批数据存储在计算机的存储器中?第三,对于存储在计算机中的这批数据可以进行那些操作?这些操作如何实现?同一问题的不同解决方法好坏如何进行评价?

1基本概念和术语

1.1数据数据就是计算机化的信息.

1.2数据结构的概念如果从数据元素之间的组织形式来看,可以认为数据结构指的是计算机所处理的数据元素之间的组织形式和相互关系.自然界中,数据元素都不是孤立存在的,它们之间必定存在着某种固有的必然的内在的关系或者是根据需要人为定义的关系,这种关系就是这些数据元素的数据结构.

数据结构一般包括以下三个方面的内容:

1.2.1数据元素之间的逻辑关系,即数据的逻辑结构,是用户根据需要而建立起来的.是用户看到的感觉到的表面的就是逻辑的.例如逻辑上计算机认识十进制物理上计算机只认识二进制.逻辑上感觉计算机有四个硬盘C、D、E、F,物理上计算机只有一个硬盘,C、D、E、F称为四个分区.不穿高跟鞋,物理高度1.7米,穿上高跟鞋逻辑高度1.75米.

1.2.2数据元素及其关系在计算机存储器内的表示、存贮,即数据的存储结构,又称数据的物理结构.

1.2.3数据的运算,即对数据元素所进行的操作.

可以把数据结构定义为:对计算机处理的一批数据,首先按某种逻辑关系把它们组织起来,再按一定的存储表示方式把它们存储在计算机的存储器中,然后给这批数据规定一组操作.如对学生的管理,有成千上万个学生,先按一个接一个的顺序组织所有学生,再按顺序结构或链式(非顺序)结构存于内存,尔后对学生定义操作,增加、删除、修改、查询、统计、排序、打印等.

2逻辑结构

根据数据元素之间的不同特性,可以把数据的逻辑结构分为四种基本类型:集合、线性结构、树形结构和图形结构.

2.1集合集合中的数据元素之间除了“同属于一个集合”的关系外,没有其它任何关系.大街上人来人往的人群可以看成是一个集合.集合是数据结构的一种特例.大街上人来人往的人群除了其共性属于人类以外,人与人之间没有任何关系.

2.2线性结构数据元素之间存在一个对一个的前驱后继关系.火车站熙熙攘攘的人群,是集合关系,人与人之间无任何关系,但一旦排成长长的购票队列,人与人之间就有关系,我在你前,你在我后,我的前边有且仅有一个人,我的后边有且仅有一个人,人与人之间就有前后关系,就是线性结构.

2.3树形结构自然生活中,家谱、行政组织机构、语法结构树.即每个结点最多只有一个直接前驱,每个结点可以有多个直接后继,只有一个结点没有前驱,称为根结点,叶子结点没有后继结点,它是一种层次结构.中国是由省、市、区县、镇、乡村,户,个人的层次结构就是一种典型的树形结构,中国是根,而个人就是叶子,windows的文件夹就是一个倒立的树.一个父亲几个儿子,一个儿子有且仅有一个父亲就是树形结构.

2.4图形结构数据元素之间是任意关系,一对一、一对多、多对多均可.树形、线形均可看作是图形的特例.即每个结点可以有多个直接前驱,也可以有多个直接后继而形成的网状结构.四通八达的公路网就是图形结构.计算机网、电网、通信网、销售网等都是图形结构.树形结构和图形结构统称非线性结构.

3存储结构

存储结构也就是物理结构,数据在计算机中如何存放、安排、组织、表示.既有数据元素的表示又有关系的表示.按照关系确定表示,表示又反映出关系.如5在计算机中如何表示,-5在计算机中如何表示,小数在计算机中如何表示等.数据在内存不能乱堆乱放,为了节省空间、提高查找速度必须对大量数据在内存进行有效组织.


存储结构可以分为顺序存储结构和非顺序存储结构两大类.顺序存储的特点是数据在内存中存放时每个单元彼此相邻,即逻辑上相邻的结点物理上也必须相邻.非顺序存储则比较灵活,可以将数据分散存储在内存中,即逻辑上相邻的结点物理上不一定相邻.常用的非顺序存储有链式存储、Hash存储和索引存储.

3.1顺序存储结构优缺点优点:随机存取,省时间.存贮效率高,省空间,无额外附加的链接信息.缺点:插入删除要移动大量数据.

3.2链式存储结构优缺点优点:插入删除无需移动数据.缺点:顺序存取,费时间.存贮效率低,费空间,有额外附加的链接信.

4算法(Algorithm)

简单地说,算法就是计算的方法、解决特定问题的方法.严格地说,算法就是操作的集合.例如:将一组给定的数据由小到大进行排序,解决的方法有若干种,而每一种排序方法就是一种算法.

4.1算法的特性①有穷性.一个算法在执行有限条指令后必须要完成,不能无限次进行,永远没有结束.②确定性.每条语句必须含义清楚,不能有二义性.③可行性.所有操作均可实现.④输入.算法用于数据加工,必须有待加工的数据.⑤输出.算法用于数据加工,必须有对数据加工的结果.算法程序有所不同,程序可以不满足上述的有穷性.例如,Windows操作系统在用户未操作之前一直处于“等待”的循环中,直到出现新的用户操作为止.

4.2算法的评价标准对于一个特定的问题,采用不同的存储结构,其算法描述一般是不相同的,对于解决同一问题的不同算法,如何评价哪一种算法较好,这就是算法评价.

算法优劣标准:正确性.一个算法能否正确地执行预先的功能,这是评价一个算法的最重要也是最基本的标准.其要求是:①可读性:可读性好能帮助人们更好的理解算法、更方便的排除算法中潜在的错误、更重要的是便于算法的交流、改进和移植.②健壮性:算法应具有很强的容错能力,即算法能对非法数据的输入进行检查和处理,不会因非法数据的输入而导致异常中断或死机等现象.③运行时间:算法中每条语句执行时间的总和.执行时间越短则算法的效率越高、性能越好.④占用空间:占用空间是指算法在计算机存储器上所占用的存储空间.越节省存储空间,算法越好.

实际上,算法的时间效率和空间效率经常是一对矛盾体,二者很难求全,有时增加辅助的存储空间可以加快算法的运行速度,即用空间换取时间;有时因为内存空间不够,必须压缩辅助的存储空间,从而降低了算法的运行速度,即用时间换取空间.其中运行时间,占用空间是衡量一个算法好坏的两个主要标准.

5结语

编程就要涉及大量数据的处理,为了提高程序运行效率,必须对数据进行有效组织,本文简述了数据的逻辑结构,存储结构以及算法.

类似论文

《数据结构》课

【摘 要】本文阐述了《数据结构》课程的地位和作用,详细论述了《数据结构》课程的教学过程设计,提出。
更新日期:2024-1-17 浏览量:17848 点赞量:4564

应用型本科院校数据结构课程教学改革

摘 要: 数据结构课程的教学在应用型本科院校存在着较大难度 为此,分析了该课程的教学现状,并以软件学院Ja数据结构课程改革作为参。
更新日期:2024-1-23 浏览量:22297 点赞量:6571

《数据结构》的学习方法

摘 要:“数据结构”在计算机科学中是一门非常重要的综合性的专业基础课,其内容丰富,涉及面广泛,但却存。
更新日期:2024-10-3 浏览量:17592 点赞量:4948

计算机软件基础数据结构之算法

摘 要:计算机软件的基础数据结构,主要负责讲解计算机内信息的寄存方式、集合和整理,通常是与算法密不可分的 算。
更新日期:2024-9-23 浏览量:119586 点赞量:26015

探究计算机软件基础数据结构之算法

摘 要:近年来计算机在我国各行各业扮演的越来越重要的角色,加强对计算机的有效性探讨是实现。
更新日期:2024-10-22 浏览量:132634 点赞量:28923