数据结构基本概念讲义

《数据结构基本概念讲义》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章数据结构1.1数据结构的基本概念与算法1.2线性表1.3栈和队列1.4树和二义树1.5查找1.6内部排序1.1数据结构的基本概念与算法1.1.1数据结构的基本概念计算机是一门研究用计算机进行信息表示和处理的科学。这里血涉及到两个M题：>信总的表示>信息的处理而信息的表示和存储乂直接关系到处理信息的程序的效率。随着计算机的普及，信息S的增加，信息范I利的拓宽，使许多系统程序和应用程序的规模很人，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所耍研究的问题。什么是数裾结构就象谈一场恋爱，先研究一下你的“进攻”对象

2、，再研究她身边的朋友，然后，确定方案:直接开始主攻，还是使用迂回战术<分析>下而文字的含义：漆黑的头发没脊麻子脚不人周正演绎1漆黑的失发，没有麻了，脚不大，周正。结论：描述-个古代美人！演绎2漆黑的头发没有，麻子，脚不大周正。结论：描述了一个古代丑女人，还是个瘸子。结论：两个不同的演绎表现为不同的结果，一个是古代美人，一个确实古代丑女人，原因只是文字的不同组合造成！也就是说：相同的文字（数据）经过不同的组合（结构）会得到不同的结果，这就是我们要介绍的数据结构：数据及其之间的关系（结构）。1.数据结构的定义1）.数据：信息载体，能够被计算机识別、存储和加工处理。可以是数值数据（整数、实数）

3、，也可以是非数值数据（声音、图像等）。2）.数据项：是数据的具冇独立含义的不可分割的敁小标识单位，如成绩表中学号，姓名等.3）.数据元素:一个数据元素由若干数据项组成,是数据的基本单位，通常作为一个整体进行考虑和处理（又称结点、记录＞。学号姓名系别住址电话981111李洪机械六舍5371111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎53722214个数据元素5个数据项4）.数椐对象：具冇相同性质的数据元素的巢合。是数裾的一个了•集。例：成绩表整体由4个记录组成，表中每行是一个记录，每个记录由5个数据项组成.关键码：值唯一能区别

4、不同的数据元素的数据项5）.数裾结构：相互之叫存在着一种成多种关系的数据元素的集合。研究内容①数据的逻辑结构：各数据元素之W的逻辑关系②数据的存储结构：各数裾元素在汁算机屮的存储关系③对各种数据结构进行的运算：添加，删除，排序等。这三个方囬的关系为：（考点）数据的逻辑结构独立于计算机，是数据本身所固奋的存储结构是逻辑结构在计算机存贮器屮的映像，必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。研究R的一是提高数裾处理的速度.二是尽S节省在数裾处理过程中所占用的计兑机存储空间.1.数据的逻辑结构r集合——元素间为松散的关系（属于关系

5、）I线性结构——元素间为一对一关系I树形结构——元素间为一对多关系I图状结构——元素间为多对多关系集合、树型、图形结构属于非线性结构同属色彩集合蓝色黄色学号姓名语文数学C语言1001张三8554921002李四9284641003干石877473♦•參多对多北京i合肥、一连云港4梅南‘’公路交通网通迅录、成绩单、花名册■•〉线性结构电子字典、家谱、目录I卜树型结构（结点间具有分层次的连接关系）交通线路、通信网络1＞图状结构1.数据结构的存储结构数据的存储结构是指数据元素及M:关系在计算机存储器内的表示（又称映象）。存储结构研究的是逻辑结构用计兑机语言实现，依赖于计算机语言。一种数据

6、结构可以根据需耍采用多种不M的存储结构，常用的存储结构奋顺序、链接与索引等存储方式。数据的存储结构不同，解决问题的方法就奋所不同，数据处理的效率也是不同的。（1）顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组來实现。线性表(aO,a1,a2,a3)100101102顺序存储结构的线性表（2）链式存储方式：对逻辑上相邻的元素不要求K物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。100102104106108110a0108a2104a3Aal102链式存储结构的线性表链式存储方式特点：1、每个结点由两部分组成：

7、一部分存放数据，另一部分存储指叫前件或后件结点的指针域。2、逻辑上相邻的结点物理上不必相连。3、数据运算（插入和删除等）灵活。4、数裾类型及其分类数据类型（DataType）是程序设计语言中所允许使用的变量类型。一个数裾类型不仅定义了相应变M可以设定的值的的集合，还规定了对变M允许进行的一组运算及其规则。例：C语言中的整型变景，K值为[-32768，32767]区叫上整数，定义在K上的操作为：力口，减、乘、除和求余数等算术运算。高级