数据结构C章节总结.docVIP

绪论 数据结构：数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。数据结构被形式地定义为(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合. 数据类型：一个值的集合和定义在这个值集上的一组操作的总称；数据运算：对数据施加的一种操作；数据结构和数据类型两个概念之间区别：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。 逻辑结构：我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。 物理结构：抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称；数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据的最小单位。 数据对象：性质相同的数据元素的集合，是数据的一个子集。 数据结构：是相互之间一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性。数据结构包括逻辑结构（线性结构，如线性表，栈，队，串，数组 和非线性结构如 树结构、图结构）、物理（存储）结构（集合、线性结构、树形结构和图状结构或网状结构）和数据运算如插入、删除、修改、排序、查找。数据结构中，与所使用的计算机无关的数据叫逻辑结构，数据结构在计算机内存中的表示是指数据的存储结构 四大类存储结构：顺序存储、链式存储、索引存储和散列存储。顺序存储包括数据存储（把逻辑上相邻的元素存储在地址连续的存储单位）和数据关系存储（通过连续的物理地址体现关系）；链式存储包括数据存储（把逻辑上相邻的元素存放在物理地址随意的存储单元）和数据关系存储（不仅存放数据本身还存放数据元素的物理地址） 抽象数据类型ADT：一个数学模型以及定义在该模型上的一组操作，包括_数据和操作_两个部分 算法的特性：有穷性（执行有穷步结束）、确定性（确切含义，不会产生二义性）、可行性、输入（零个或多个输入）和输出（一个或多个输出） 算法设计的要求：正确性、可读写、健壮性、效率与低存储量需求。 2、数据的逻辑结构是指 数据元素之间的逻辑关系；数据逻辑结构包括 线性结构、树形结构和图形结构_三种类型，树形结构和图形结构合称为非线性结构_。数据的逻辑结构被分为 集合结构、线性结构、树形结构、图形结构４种。 17、一个数据结构在计算机中的表示（或映射）_称为存储结构. 18、链式存储方法中结点间的逻辑关系是由附加的指针字段表示的. 21、算法的执行时间是 问题规模 的函数。一个算法的效率可分为时间效率和空间效率。 37、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫值域_，另一个叫指针域。 1、某算法的时间复杂度为O(n2),表明该算法的_执行时间与n2成正比____. 2. 算法分析的目的是_分析算法的效率以求改进，算法分析的主要任务是分析算法的执行时间和问题规模之间的关系;算法分析的两个主要方面是空间复杂度和时间复杂度 5．在决定选取何种存储结构时，一般不考虑 A 。 A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.编程语言实现这种结构是否方便。 10．程序段i ＝ 0；while（i=n）｛i = i * 3｝的时间复杂度是 O(log3n) 。 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 1.数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象以及它们之间的关系和运算等的学科。数据结构式相互之间存在一种或多种特定关系的数据元素的集合。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、 查找 、排序。 线性表 1.线性表:一个线性表是n个类型相同的数据元素的有限序列。线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。顺序存储结构的特点：优，可随机存取表中任一元素，方便快捷；缺，再插入或删除时，需移动大量元素，数组的静态空间分配。 2.线性结构与非线性结构的不同点：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。 3.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较(n-1）/2个结点, 链表适用于顺序查找. 4. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 p-next=s;s-n