数据结构--复习资料

《数据结构--复习资料》由会员分享，可在线阅读，更多相关《数据结构--复习资料（83页珍藏版）》请在金锄头文库上搜索。

1、 第0章 C+极速入门1. 文件后缀名C+文件的后缀名有许多种，较为常见的是.cpp；头文件的后缀名也有很多种，较为常见的是.h。2. #include对于#include,这相当于Java中的Import，作用是引入需要的库文件。中包含了标准输入输出流，我们常用的cin和cout函数以及和运算符都在其中。是一个迭代器库，使用istream_iterator或者ostream_iterator都要把他包含进来。提供了一些函数和符号常量，如NULL。3. #include 后面接还是 ?对于标准库，其后应该接,如;对于自定义的头文件，则应该用 ，这时候使用的是相对路径。4. 什么是声明？什么是定

2、义？简单的来讲：声明就是说明这个类中有什么类型，什么名字的变量和什么样的成员函数（当然必须指明函数的返回值，函数名和形参列表），却不用对变量初始化或者具体写出成员函数的实现代码；而变量的初始化或者函数的具体代码实现的过程叫做定义。5. C+中声明和定义类通常的做法C+是一种面向对象的编程语言，因此不可避免的要声明和定义类，我们在java中总是在把声明和定义放在一起做，比如刚声明了一个变量就给它初始化，或者刚声明了一个方法紧接着就在后面跟上 ，并在其中给出代码实现来定义。虽然C+中也可以这样做，但通常的做法是把类的声明放入头文件中，而把类的定义放入相对应的.cpp中。6. ： 作用域运算符：表示

3、：右边的操作数可以在：左边的作用域上找到。例如：A：function（）表示这个function（）是类A的。7. 命名空间编码中，我们总是使用如std：cout 这样的形式会使代码冗余，如果一个函数中总是调用一个命名空间中的其他函数，我们可以使用using声明来简化代码，语法：using namespace std；这样我们之后就可以直接调用cout而省去std：了。8. Const关键字Const关键字用来使一个变量不可被更改，常用于常量的定义。9. 引用引用是一个对象的别名，是一种复合类型，通过在变量名前添加“&”符号来定义，操作引用就是操作对象本身，如int a = 10; int &

4、b = a; b+;此时a的值已经变为了11。与指针不同，指针定义后可以变换所指的对象，但引用一经定义，则不能改变与之相关联的对象。10. C+中的函数传参方式C+中的函数，有三种参数传递方式，传值，传引用，传指针。传值时，会在函数执行时为形参分配内存，等待函数执行完毕后，把形参的值return出去赋给指定的变量，再将形参销毁，而传引用时，函数会直接操作引用，也就是直接操作引用所绑定的对象，不会为形参实际分配空间，函数执行完以后也不用再把值赋回去，因为操作的就是变量本身，效率很高。而传指针，类似于传值，会在函数内部产生一个形参作为实参的副本。操作指针形参时，真正的那个指针的值并没有发生变化，你

5、要是不把形参指针的值再赋回去，相当于没有操作。11. 操作符的重载比之于Java只能重载函数，C+中可以重载操作符显得更为灵活，重载操作符的语法为：返回值类型 operator关键字 要重载的运算符（形参列表），对于现在的我们，认识即可。抱佛脚不要求我们会使用。12. 析构函数与Java不同，C+采用手动内存管理，因此我们需要手动回收动态分配出去的内存，因此对于C+类来说，它们还有一类特殊的函数，叫做析构函数，在我们使用delete关键字删除一个对象（确切的说，是删除指向这个对象的指针时）时，析构函数会自动被调用，但并不是所有时候都需要显式的编写析构函数，只有当对象在其生命周期内或构造函数中获

6、取资源时，我们才需编写以释放。13. 模板类我敢保证，你总是在PPT或者其他地方看见这么一行代码：template 这叫啥，这叫模板。模板有两种，一个叫模板函数，一个叫模板类，先说模板函数，如果有时候你需要定义一大堆的重载函数，而这些函数仅仅只有形参列表中的参数类型不一样（就是除过类型，形参个数一样，甚至连变量名都一样。），那此时就有一个简单的办法：只写一个函数，而使用一个暂不指出的类型把这些类型都替换掉，等需要用的时候再确定，给啥类型，函数中用Type标记的类型就是啥，非常灵活。这样的想法，用于实现函数，就叫函数模板，用于实现类，就叫类模板。那咋在需要的时候指定类型呢？在函数模板中，编译器会

7、推断出到底是在是用什么类型，我们直接给出实参就可以。而使用类模板时，必须为模板形参显式的指定实参。语法：类名 对象名。接下来，我将告诉你C+极速入门的至关重要的一句话！你若遵循，技术必定突飞猛进！请注意，这个真谛是：你看了上面的解说，最好动手写上一两个C+程序，哪怕不比helloworld复杂多少都行，否则的话，你看了上面，基本等于白看！第1章 概论1. 、数据结构要想方便的使用数据，你就需要把他们组织起来，特别是有大量的数据的时候要用的时候，你不得不组织。所以，抛开那些严谨的定义，通俗的来讲：组织数据的方法或者数据被组织起来的形式就是数据结构。2. 分类数据结构可以分为线性结构和非线性结构。

8、线性结构也称为线性表，这种结构中的所有数据都按某种顺序排列在一个序列中。而线性表又分为顺序表和链表。非线性结构中各个元素不再保持在一个线性序列中，每个数据元素可能与零或多个其他数据元素发生关系，根据关系不同又分为层次结构和群结构，层次结构如树，群结构如图。3. ADTAbstract data type 即抽象数据类型，我们要使用一个非内置的数据类型时，就需要先对它进行设计，进行设计的时候应该关心这个数据类型应该包含那些信息，或者支持那些操作，而不是一开始就关注这个数据类型该如何实现，所以，好的做法是把数据类型抽象一下，把声明和实现分开，设计的时候考虑声明，用的时候在去实现。4. 算法性能分析

9、和度量算法的复杂性度量属于事前估计，它可以分为时间复杂度和空间复杂度， 常采用大O表示法来描述。第2章 数组1. 简介数组是具有相同类型的若干变量的有序组织形式。通常使用一块连续的内存。数组是线性结构，每个元素都有唯一的前驱和后继（第一个和最后一个元素除外），元素的个数和数组的起始地址必须在分配内存的时候就指定。数组中的元素可以被任意的直接访问，这个随机访问是通过数组的下标来实现的。2. 一维数组元素地址推算公式设为该数组的起始地址，数组中每个元素要用l的存储空间，则：Addri = +3. 顺序表定义：把线性表中所有的表项按照逻辑顺序依次存储到一块指定地址的连续的存储空间。显然数组是顺序表。

10、顺序表类至少应该支持一下操作：（）插入元素（）移除元素（）查找某元素的先驱（）查找某元素的后继（）判断是否为空（）判断是否为满（）按索引得到某一元素。4. 顺序表的性能分析主要是分析搜索，插入和删除运算的实现代码的时间复杂度。搜索算法中，设各个表项的搜索概率为，找到该表项时数据比较次数为搜索的平均比较次数为ACN（average comparing number） = ,若搜索表项的各项可能性相同，则ACN = = ( 1+2+n)= 分析顺序表的插入和删除的时间代价主要看循环内的数据移动次数AMN（average moving number）插入：AMN = 若个表项插入概率相等，AMN =

11、 删除：AMN = 若个表项删除概率相等，AMN = 5. 三角矩阵的存储对于一个n*n对称方阵来说，可以只存储它的上三角或者下三角部分来节省空间，而其上（下）三角矩阵的元素个数为可以用一个一维数组来存放这些元素：a00a10a11a20a21a22a30a31a32a33Loc(i,j) = k;i(i+1)/2 +j i jk =j(j+1)/2 +i i j6. 对角矩阵的存储a00 a11 a 02 0 0 0 a10 a11 a12 a13 0 0 a20 a21 a22 a23 a24 0 0 a31 a32 a33 a34 a35 0 0 a42 a43 a43 a45 0 0

12、0 a53 a54 a55 a11a12a21a22a23a32a33a34an(n-1)ann设第i（i1,n）行非零元素的个数为m,则d = 则带状矩阵中，非零元素的个数为：（2d+1）n - (1+d)d7. 稀疏矩阵使用一个三元组只存储矩阵中的非零元素，可以实现对稀疏矩阵的压缩，三元组：对于一个稀疏矩阵，如果要对其进行转置，应当考虑在其压缩状态下直接对其进行转置，最简单的方法是把三元表内的row与col呼唤后，再对新的三元表进行row主序排序。这里讲一种方法：假设稀疏矩阵A有Cols列，则对这个三元组进行Cols次扫描，第k次扫描是在三元组表中寻找列号为k的所有三元组，意味着此三元组应

13、该放在新表中的第k行，此时交换该三元组的row和col，再连同value一同存入新的三元表中。为了提高效率，还有一种快速转置的方法，通过一如两个辅助数组来提高效率rowSize 来记录每一列有多少个非零元素，rowStart 来记录每行第一个三元组应该存放在新表中的什么位置8. String类的抽象数据结构由零个或多个字符的顺序排列所组成的数据结构，基本组成元素是单个字符，S0S1S2S3S4.Sn-1一个字符串的连续字符子集叫做子字符串，空字符串不包含任何字符。实现可增长字符串有三种方法：（1）创建一个字符缓冲区并且只初始化这个区域的一部分，剩下的缓冲区以后使用。（2）创建一个新的第三字符串

14、，其容量是另两个字符串的容量之和，并把这两个字符串的内容拷贝进来。（3）创建一个字符串链表，而不是数组，这种方法是真正地无限制方法，但是需要维持链表9. 字符串模式匹配老师PPT中提到的有两种模式，一种是朴素匹配，另外一种是KMP匹配。KMP匹配算法因为无回溯，效率较高。（PPT 86页）10. STL中的stringSTL中已经给我们提供了string类供我们使用，只要#include 就可以使用了，此类包含了初始化，串接，获取长度，输入输出等基本操作的支持。string类提供了字符串高级处理函数的集合。11. STL中的vector同样。只要#include 就可以使用STL中的vector了，vector提供了一个安全的对数组的替代，因为它提供成员函数来实现那些更高级的操作。实际上，可以简单的理解vector为一个大小可变的数组。vector引用的声明语法：vector v;其中type叫做泛型，它制定了vector中存储的数据类型。我们可以用vector声明一个整形矩阵：vector vector matrix;