汇编网首页登录博客注册
masmaster的学习博客
博客首页博客互动【做检测题】论坛求助

我的博客

个人首页 |  我的文章 |  我的相册 |  我的好友 |  最新访客 |  文章收藏 |  论坛提问 |  友情链接 |  给我留言  
图片载入中
文章收藏

[2010-08-03 10:13] 数据结构基本概念

1,数据结构
是用来描述现实世界的数字、字符、图像、声音以及能够输入到计算机中并能被计算机处理的符号集合。比如表述数值的整数、实数,描述图书馆里数目的字符串等等。

2,数据元素
是数据的基本单位。是数据集合中的个体,也称为元素、节点、顶点、记录。例如图书馆数目数据里,有“数据结构”、“C语言”、“数据库”等元素,整数数据中的“1,2,。。。”等元素。
一个数据元素可以由若干数据项组成。数据项是数据不可分割的最小标识单位,也称为字段、域、属性。例如员工信息可以由“员工号”、“姓名”、“性别”、“年龄”、“住址”、“电话”、“所属部门”等数据项组成。

3,数据对象
是具有相同性质的数据元素的集合。是数据的一个子集,例如:数目数据对象是集合{“数据结构”、“C语言”、“数据库”},桥牌数据对象是集合{2,3,...,J,Q,K,A},英文字符数据对象是集合{a,b,...,z,A,B,....,Z}

4,数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括:

(1)数据的逻辑结构
数据的逻辑结构是指数据元素之间存在的固有的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据,于数据的存储无关,是独立于计算机的。数据的逻辑结构可以看做是具体问题抽象出来的数学模型。
依据数据元素之间的关系,可以把数据的逻辑结构分为:

①集合:结构中的数据元素之间除了“同属于一个集合”的关系外,没有其他关系。如图所示:

集合:
|------------------|
|A            B    |
|     C  D         |
--------------------
②线性结构:结构中的数据元素之间存在“一对一”的关系。如果结构为非空集,则除了第一个数据元素和最后一个数据元素以外, 其他数据元素都有一个直接前驱和一个直接后继,如图所示:

线性:第一元素为A,最后元素为D

A--B--C--D

③树形结构:结构中的元素存在“一对多”的关系, 若结构非空,则除了第一数据元素之外, 其他每个数据元素都只有一个直接前驱,以及零个或多个直接后继。如图所示:

树形:

     A
   / | \
  B  C  D
       /|\
      E F G
图中A为第一数据元素,他的直接后继元素为B,C,D,而B,C没有直接后继,D有E,F,G三个直接后继。

④图状结构:结构中的数据元素之间存在“多对多”的关系, 若结构非空,则每个数据结构可能有零个或多个直接前驱和直接后继。 如图所示:

图状:

    A------B-----C
          / \   /
         /   \ /
        D-----E  
图中数据元素A没有直接前驱,只有一个直接后继,B有一个直接前驱A,有三个直接后继D,E,C。

注:直接前驱是指与该数据元素相邻的前一个数据元素;直接后继是指与该数据元素响铃的后一个数据元素。

数据结构可以用一个二元组来表示,即:
data_struc=(D,E)
其中,D是某个数据对象,E为该对象中所有数据元素之间的关系的集合。

(2)数据的存储结构
数据元素及其关系在计算机内部的表示称为数据的存储结构。
要想用计算机处理数据,就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为下面4种存储结构:

①顺序存储结构:把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中。借助元素在存贮器中的相对位置来表示数据元素之间的逻辑关系。有此得到的存储结构称为顺序存储结构。

②链式存储结构:借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素在物理位置上也相邻。由此得到的存储结构称为链式存储结构。

③索引存储结构:在存储数据元素的同时,建立附加的索引表。通过索引表,可以找到存储数据元素的节点。

④散列存储结构:根据散列函数和处理冲突的方法确定数据元素的存储位置。

(3)数据的操作
数据的操作是在数据的逻辑结构上定义的操作算法,比如插入、删除、检索等。

需要注意的是,数据的逻辑结构和数据的存储结构是指同一事物的两个方面。 二者相辅相成不可分割。同时,一种数据的逻辑结构可以映射为多种数据存储结构。
评论次数(0)  |  浏览次数(273)  |  类型(数据结构笔记) |  收藏此文  | 
 
 请输入验证码  (提示:点击验证码输入框,以获取验证码