数据结构-c语言描述(本科)第1章

《数据结构-c语言描述(本科)第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、面向21世纪高等学校计算机类专业系列教材数据结构——C语言描述DataStructuresinC陈慧南编著西安电子科技大学出版社目录第1章概论第2章两种基本数据结构第3章堆栈和队列第4章线性表和数组第5章字符串和广义表第6章树第7章集合和搜索第8章搜索树第9章跳表和散列表第10章图第11章内排序第12章文件和外排序第1章概论1.1什么是数据结构1.2数据抽象和抽象数据类型1.3数据结构的描述1.4算法和算法分析习题11.1什么是数据结构数据结构是计算机科学与技术领域广泛使用的术语，然而，究竟什么是数据结构，在计算机科学界至今没有标准的定义。随着计算机科学与技术的发展，计算机

2、的应用已远远超出了单纯进行科学计算的范围。今天，信息技术作为现代技术的标志已成为世界各国经济增长的主要动力。计算机技术已渗透到国民经济的各行各业和人们日常生活的方方面面。计算机已经从传统的应用领域，如工业控制、情报检索、企业管理、商务处理、图形图像、人工智能等数据处理领域，发展到了电子政务、电子商务、办公自动化、企业资源管理系统、电子图书馆、远程教育、远程医疗等诸多领域。现实世界各领域中的大量信息都必须转换成数据才能在计算机中存储、处理。数据是信息的载体。应用程序处理各种各样的数据。笼统地说，所谓数据(data)，就是计算机加工处理的对象。数据一般分两类：数值数据(nume

3、ricaldata)和非数值数据(non-numericaldata)。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等。非数值数据包括字符、文字、图形、图像、语音、表格等。数据结构主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法。它表达数据的构造形式，即一个数据由哪些成分数据构成，以什么方式构成，具有什么结构。在这里，我们称组成数据的成分数据为数据元素(dataelement)。一般地，数据元素可以是简单类型的，如整数、实数、字符等，也可以是结构类型，如记录。若把每个学生的记录看成一个数据元素，它包括学号、姓名、性别等数据项(d

4、ataitem)，一个班的学生记录组成了图1－1所示的学生情况表。表是一个数据结构。从数学概念上讲，一个数据结构(datastructure)是由数据元素依据某种逻辑联系组织起来的。对数据元素间的逻辑关系的描述被称为数据的逻辑结构(logicalstructure)。根据数据结构中数据元素之间的结构关系的不同特征，通常将数据结构分为如下四种基本结构：学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁菁女…B02040104张可可男………………………图1－1学生情况表(1)集合结构(set)：数据元素的有限集合。数据元素之间除了“

5、属于同一个集合”的关系之外没有其他关系。元素顺序是随意的。(2)线性结构(linear)或称序列(sequence)结构：数据元素的有序集合。数据元素之间形成一对一的关系。(3)树形结构(tree)：树是层次数据结构，树中数据元素之间存在一对多的关系。(4)图结构(graph)：图中数据元素之间的关系是多对多的。(a)(b)(c)(d)图1－2四种基本结构示意图(a)集合结构；(b)线性结构；(c)树形结构；(d)图结构由于集合结构的元素间没有固有的关系，因此往往需要借助其他结构才能在计算机中实际表示该结构。上述四种基本的结构关系可分为两类：线性结构(linearstruc

6、ture)和非线性结构(non-linearstructure)。我们把除了线性结构以外的几种结构关系——树、图和集合归入非线性结构一类。数据的逻辑结构是面向应用问题的，是从用户角度看到的数据的结构。数据必须在计算机内存储，数据的存储结构(storagestructure)是数据在计算机内的组织方式，是逻辑数据的存储映像，它是面向计算机的。我们知道，计算机存储器(主存)是由有限个存储单元组成的一个连续的存储空间，这些存储单元或者是字节编址，或者是字编址的。从存储器角度看，存储器中是一堆二进制数据，它们可以被机器指令解释成为指令、整数、字符、布尔数等等，也可以被数据结构的算法

7、解释成为具有某种结构的数据。顺序(sequential)存储结构和链接(linked)存储结构是两种最基本的存储表示方法。所谓顺序或连续(contiguous)的表示方法，也称计算的方法，需要一块连续的存储空间，并把逻辑上相邻的数据元素依次存储在连续的存储单元中。例如有四个数据元素组成的线性数据结构(a0,a1,a2,a3)，存储在某个连续的存储区内，设存储区的起始地址是100，假定每个元素占2个存储单元，则其顺序存储表示如图1－3(a)所示。在顺序存储结构表示时，可以容易地用一个数学公式来确定每个元素的位置。对于