《王道》数据结构笔记整理2022.pdfVIP

《王道》数据结构笔记整理2022 数据结构 第⼀章 ：绪论 1.1数据结构的基本概念 1.数据 ：数据是信息的载体，是 述客观事物属性的数、字符以及所有能输⼊到计算机中并被程序识别和处理的符号的集合。 2.数据元素 ：数据元素是数据的基本单位，通常作为⼀个整体进⾏考虑和处理。⼀个数据元素可由若⼲数据项组成，数据项是构成数据元素 的不可分割的最⼩单位。例如，学⽣记录就是⼀个数据元素，它由学号、姓名、性别等数据项组成。 3.数据对象:数据对象是具有相同性值的数据元素的集合，是数据的⼀个⼦集。 4.数据类型:数据类型是⼀个值的集合和定义再此集合上的⼀组操作的总称。 1）原⼦类型。其值不可再分的数据类型。如bool 和int 类型。 2）结构类型。其值可以再分解为若⼲成分 （分量）的数据类型。 3）抽象数据类型。抽象数据组织及与之相关的操作。 5.数据结构:数据结构是相互之间存在⼀种或多种特定关系的数据元素的集合。 1.2数据结构的三要素 1.数据的逻辑结构 ： 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上 述数据。 逻辑结构包括 ： 1. 集合结构 ：结构中的数据元素之间除 “同属⼀个集合”外，别⽆其它关系。 2. 线性结构 ：结构中的数据元素之间只存在⼀对⼀的关系，除了第⼀个元素，所有元素都有唯⼀前驱 ；除了最后⼀个元素，所有元素都 有唯⼀后继。 3. 树形结构 ：结构中数据元素之间存在⼀对多的关系。 4. 图状结构 ：数据元素之间是多对多的关系。 2.数据的存储结构 （物理结构） ： 存储结构是指数据结构在计算机中的表⽰ （⼜称映像），也称物理结构。 存储结构包括 ： 1. 顺序存储 ：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。 2. 链式存储 ：逻辑上相邻的元素在物理位置上可以不相邻，借助指⽰元素存储地址的指针来表⽰元素之间的逻辑关系。 3. 索引存储 ：在存储元素信息的同时，还建⽴附加的索引表，索引表中的每项称为索引项，索引项的⼀般形式是 （关键字，地址） 4. 散列存储 ：根据元素的关键字直接计算出该元素的存储地址，⼜称哈希 （Hash）存储。 3.数据的运算 ：施加在数据上的运算包括运算的定义何实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构 的，指出运算的具体操作步骤。 1.3算法的基本概念 程序=数据结构+算法 算法 （algorithm)是对特定问题求解步骤的⼀种 述，它是指令的有限序列，其中的每条指令表⽰⼀个或多个操作。 算法的特性 ： 1.有穷性 ：⼀个算法必须总在执⾏有穷步之后结束，且每⼀步都可在有穷时间内完成。 2.确定性 ：算法中每条指令必须有确定的含义，对于相同的输⼊只能得到相同的输出。 3.可⾏性 ：算法中 述的操作都可以通过已经实现的基本运算执⾏有限次来实现。 4.输⼊ ：⼀个算法有零个或多个输⼊，这些输⼊取 ⾃于某个特定的对象的集合。 5.输出：⼀个算法有⼀个多个输出，这些输出是与输⼊有着某种特定关系的量。 好的算法达到的⽬标 ： 1. 正确性 ：算法应能够正确的求接问题。 2. 可读性 ：算法应具有 良好的可读性，以帮助⼈们理解。 3. 健壮性 ：输⼊⾮法数据时，算法能适当地做出反应或进⾏处理，⽽不会产⽣莫名奇妙地输出结果。 4. 效率与低存储量需求：效率是指算法执⾏的时间，存储量需求是指算法执⾏过程中所需要的最⼤存储空间，这两者都与问题的规模有 关。 1.4算法的时间复杂度 ⼀般情况下，算法中基本操作重复执⾏的次数是问题规模n的某个函数f (n)，算法的时间量度记作T （n)=O(n)，它表⽰随问题规模n的增⼤ ⽽增⼤，算法执⾏时间的增长率和f (n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 1.5算法的空间复杂度 算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为S(n)=O(g(n))。 第⼆章 ：线性表 2.1线性表的定义 线性表是具有相同数据类型的n(n0)个数据元素的有限序列，其中n为表长，当n=0时线性表是⼀个空表。 2.2顺序表的定义 2.2.1静态分配: //顺序表的实现--静态分配 #includestdio.h #define MaxSize 10 //定义表的最⼤长度 typedef struct{ int data[MaxSize] ;//⽤静态的数组存放数据元素 in