文档介绍：数据结构
—— C语言描述
王国钧主编
唐国民、苏晓萍、马瑜副主编
科学出版社
2005年8月
第 1 章概论
什么是数据结构
     为什么要学习数据结构
     算法和算法分析
什么是数据结构
数据和数据元素
数据(data)是信息的载体,是对客观事物的符号表示,它能够被计算机识别、存储和加工处理。可以说,数据是计算机程序加工的“原料”。目前,象图像、声音、视频等都可以通过编码而由计算机处理,因此它们也属于数据的范畴。
数据元素(data element)是数据的基本单位,通常在计算机程序中作为一个整体进行考虑和处理。数据元素也称为元素、结点或记录。有时,一个数据元素可以由若干个数据项(也称字段、域),数据项是数据不可分割的最小单位。
数据对象和数据类型
数据对象(data object)是性质相同的数据元素的集合,它是数据的一个子集。例如,整数数据对象是集合N={0,±1,±2,±3,…};大写字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’}。要注意的是,计算机中的整数数据对象集合N1应该是上述集合N的一个子集,N1={0,±1,±2,…,±maxint},其中maxint是依赖于所使用的计算机和语言的最大整数。
数据类型(data type)是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。例如,C语言中的整数类型是区间[-maxint,maxint]上的整数,在这个集合上可以进行加、减、乘、整除、求余等操作。
数据结构
数据结构(data structure)是指数据对象以及该数据对象集合中的数据元素之间的相互关系(即数据元素的组织形式)。
数据元素的组织形式一般包含下列内容:
⑴数据元素之间的逻辑关系,也称为数据的逻辑结构。数据的逻辑结构通常有下列4类():
①集合:其中的数据元素之间除了“属于同一个集合”的关系以外,别无其他关系。
②线性结构:其中的数据元素之间存在一对一的关系。
③树型结构:其中的数据元素之间存在一对多的关系。
④图状结构(或称网状结构):其中的数据元素之间存在多对多的关系。
⑵数据元素以及它们之间的相互关系在计算机存储器内的表示(又称映象),称为数据的存储结构,也称数据的物理结构。
⑶数据元素之间的运算,亦即对数据元素施加的操作,有时也直接称为数据的运算或操作。
学生成绩表()是一个数据结构。
学生成绩表
学号
姓名
计算机导论
高等数学
普通物理
平均成绩
04081101
陈小洁
80
90
85
85
04081102
马丽丽
75
68
78
74
04081103
林春英
82
78
66
75
04081104
王澄娟
90
85
93
89
┆
┆
┆
┆
┆
┆
04081150
张吉祥
70
88
75
78
数据结构可以理解为:按某种逻辑关系组织起来的一批数据,应用计算机语言,按一定的存储表示方式把它们存储在计算机的存储器中,并在这些数据上定义了一个运算的集合。
数据结构的内容可归纳为三个部分:逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据,按一定的映象方式把它存放在计算机的存储器中,并在这些数据上定义了一个运算的集合, 就叫做数据结构。
数据的存储结构可采用以下4种基本的存储方法得到:
⑴顺序存储方法
⑵链接存储方法
⑶索引存储方法
⑷散列存储方法
上述4种基本的存储方法,既可以单独使用,也可以组合起来对数据结构进行存储映象。同一种逻辑结构,若采用不同的存储方法,则可以得到不同的存储结构。