数据结构的基本概念.doc

《数据结构的基本概念.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构的基本概念大纲对本节的要求就是：本节的标题——数据结构的基本概念。说到概念，绝对不是死记硬背的方式解决，而应该注意理解！（因为没有填空题或者是论述题，不需要记住。）本节所涉及到所需要掌握的概念有：1．数据结构的概念数据结构：是讨论计算机系统中数据的组织形式及其相互关系。数据的基本单位：数据元素。数据的逻辑结构：分为线性结构和非线性结构。存储结构：数据在计算机中的存储方法。（在理解存储方法的时候要注意：不是把数据放在存储器里就完了，重要的是在以后怎样找到他们）数据的存储结构分为：顺序存储、链接存储

2、、索引存储和散列存储。顺序存储方法：逻辑上相邻的数据元素存储在实际相邻的存储单元中。链接存储方法：元素间的逻辑关系由指针字段确定，元素间的关系只是逻辑上的相邻，并不一定要求在物理上也相邻，数据元素的存储单元＝数据项＋指针项。索引存储方法：在存储元素信息时，建立一张附加索引表与之对应的方法。稠密索引：索引项对应元素稀疏索引：索引项对应一组元素散列存储方法：根据关键字直接算出元素的地址数据的处理：常用数据处理与运算的几种基本操作：遍历、插入、更新、删除、查找、排序。遍历和排序操作后，没有改变或增减数据元素；

3、排序将改变其位置2．举例例1.1.1在已知的一个线性结构中有20个元素，将第8个元素的数据进行一次替代，则该操作属于算法中的（）。A）遍历B）插入C）排序D）更新【解析】所谓遍历是指在数据结构的各个元素中移动或查看所有数据元素，而插入是指往数据结构中添加新的元素；更新则指个性或替代数据结构中指定元素的一个或多个数据项，显然，本题中，没有涉及到增加新的元素，而仅仅是对原已有的元素进行了数据项的替换。故答案应选D。例1.1.2（判断）采用“索引存储方法”的数据可以进行随机读写（）【解析】所谓“随机读写”，是

4、相对于“顺序读写”而言，就是可以读写任意指定位置的数据，可以根据索引表找到元素的地址，而不需要从头开始。所以应该是正确的。线性结构考生在本节复习时，要着重从以下几个方向进行：1．概念：线性结构的逻辑特征：有且仅有一个开始数据元素和个终点数据元素，并且所有数据元素都最多只有一个直接前趋和一个直接后继。线性表、数组、字符串、队列等都有属于线性结构。如人们排队，一个人前后最多只一个人，不能有两个。有且只有一个无直接前继的开始元素和一个无直接后继的终点元素。线性结构的类型主要有：线性表（又包括顺序表，线性链表）

5、、堆栈、队列、数组、串等。1、线性表的两种存储方式：顺序存储方式（由此形成顺序表）链式存储方式（由此形成链表）顺序表：数据元素按其逻辑次序依次存放在一组地址连续的存储单元里。缺点：插入、删除等操作比较麻烦，长度动态的变化不方便。线性链表：采用链式存储方式进行存储的线性表，即用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，从而可以大提高存储器的使用效率。链：在存储一个数据元素中，除了存储的数据本身外，还包含数据的直接后继（或直接前趋）的位置，或指针，这一部分称为链

6、。线性链表主要有：单链表，双链表，循环链表。单向链表：。在单链表中，数据元素由数值域和数据元素的指针域两部分组成，即：每一个数据元素=数据域＋直接后继元素的地址。其中终点结点无直接后继，终结点的指针域值为空NIL。双向链表：每一元素的指针域既包含直接后继，也包含直接前趋。即：每一个数据元素=直接前驱元素的地址＋数据域＋直接后继元素的地址。循环链表：是一种首尾连接的链表。注意理解：计算机是根据“地址”来读写数据的：对于顺序表是不是不需要地址？当然不是。对于顺序表我们只关心第一个地址，因为后面一个一个的都挨

7、着——连续存放。在此应理解顺序表，链表的插入、删除算法。栈：只能在表的一端进行插入和删除运算的线性表。插入和删除的一端称为栈顶；另一端称为栈底。栈中没有元素为空栈。栈的指针始终指向栈顶。栈的基本操作原则：后进先出LastInFirstOut（LIFO）。栈的主要应用：子程序的嵌套调用，递归调用，中断系统的断点保护，编译系统的后缀表达式计算等。队列：只能在表的一端进行删除（队头）另一端进行插入（队尾）的线性表。操作原则：先进先出FirstInFirstOut（FIFO）队列有两个指针,队头指针：总是指队头

8、元素前一位置；队尾指针：总是指向队尾元素所在的存储位置。二维数组行优先的某一元素地址：Loc(aij)=Loc(a11)+((i-1)*n+(j-1))*S二维数组列优先的某一元素地址：Loc(aij)=Loc(a11)+((j-1)*m+(i-1))*S其中M，N为二维数组最大行号和列号，i,j为某一元素的行、列下标，S为数组中每一元素所占字节数。串由若干字符组成。串的基本单位：为一个字节。2．举例：例：1.2.1判断题和选择题（1）顺序