数据结构与算法:Python语言描述 1~5章课后习题
发布时间：-07-19 20:42,
浏览次数：1885
, 标签：
Python
MarkDown语法写的，不知道为啥上传到CSDN不生效，算了就这样将就着看吧......还有，转载请注明出处，谢谢！
1）这本书为什么值得看：
* Python语言描述，如果学的Python用这本书学数据结构更合适
* 出版，内容较新
* 作者裘宗燕，北大教授，质量有保证
2）这本书为什么不值得看：
*
这本书从第七章开始分别是‘图’,‘字典与集合’,‘排序’，这三章在数据结构中属于较难部分，但到这里却能明显感受到作者已经开始着急完本了，明显的越写越不走心，出现了好多错误，讲解的也不像前几章详细了。
## 第三章、线性表
***
### 1.复习下面概念
* 线性表：某类元素的集合，元素之间可能存在某种关系。
* 基本元素集合：
* 元素集合和序列：序列就是元素排列有顺序。
* 下标：序列中的元素在表中有一个确定的位置，称为这个元素的下标。
* 空表：没有元素的表。
* 表的长度：表中元素的个数。
* 顺序关系（线性关系）：表元素之间有一个基本关系，叫做下一个关系，下一个关系就是顺序关系（线性关系）。
* 首元素：表的第一个元素。
* 前驱和后继：表中每个元素（除首元素）都有一个前驱元素；表中每个元素（除尾元素）都有一个后驱元素。
* 数据抽象的实现者和使用者：实现；使用。
* 顺序表和链接表：表元素顺序的放在一块连续的存储区里；表元素存放在通过链接构造起来的一系列存储块里。
*
顺序表的元素布局：一种是元素大小相同，在表里等距安排同样大小的存储位置；一种是元素大小不同，实际数据元素另行存储，在顺序表里各单位位置保存对应元素的引用信息（链接）。
* 索引和索引结构：不存放实际数据元素，只存放找到实际数据的线索的顺序表叫做索引。这也是最简单的索引结构。
* 容量：表的存储量大小。
* 元素遍历：完全的访问（可能有操作）一遍表中元素。
* 查找（检索）： 查找给定元素（第一次出现）的位置。
* 定位：表的元素的编号。
* 加入和删除元素：加入删除。
* 尾部加入和删除：在表的已有元素之后插入元素；删除表的已有元素的最后一个。
* 保存插入和删除：在位置i处插入元素；删除位置i的元素。
* 表的一体式实现和分离式实现：存储表信息的单元和元素存储区已连续的方式安排在一块存储区里；表对象只存放表信息，实际数据元素独立存储，通过链接关联。
* 动态顺序表：表的容量在使用中能扩充。方式是：申请一块更大的存储区，把实际数据元素复制到这块存储区，修改表对象和元素存储区的链接。
*
元素存储区的增长策略（线性增长，加倍增长）：当表容量填满时，要更换一块更大的存储区，存储容量的增大量每次都为一个常量n，就叫做线性增长（其实就是加法）；存储量的增加每次都是原容量的某倍，叫做加倍增长（乘法）。
* 元素反转和排序：元素排列顺序进行反转；元素按照某种顺序进行排列。
* 链接结构：链接表中元素存放在一批小块存储区中，用显式的链接将它们连成一串，形成链接结构。
* 单链表（单向链接表）：每个表结点记录着下一个表元素的结点的标识（引用/链接）。
* 链接：引用，指向。
* 表头变量（表头指针）：保存着一个表的首结点的引用（标识/链接）的变量。
* 空链接：结点不存放下一个表元素的引用，在Python中就是系统常量None。
*
链表处理的扫描模式：由于单链表只有一个方向的链接，开始情况下只有表头变量在掌控中，所以对表内容的一切检查都只能从表头变量开始，沿着表中链接逐步进行。这种操作过程称为链表的扫描。
* 汇集对象：把线性表一类的对象称为汇集对象，他们本身是对象，又包含着一组元素对象。
* 尾结点引用：为提高表的后端插入操作的效率，给表对象增加一个表尾结点的引用域，这样，在表尾插入新结点只需O(1)时间。
* 循环单链表：表的尾结点的next域不用None，而是记录着首结点的引用，单链表就形成了一个圈。
* 双向链接表（双链表）：表的每个结点不仅记录着下一个结点的引用，还记录着上一个结点的引用，这样两段插入和删除操作都能高效进行。
* 循环双链表：表尾结点的next域记录着首结点的引用，首结点的prey域记录着尾结点的引用。
* 链表反转：结点顺序反转，可以不断从表的首端取下结点，将其放到另一个空表的首端，就形成了一个反转过程。
* Josephus问题:n个人坐成一圈，从第k个人开始报数，报到第m个数的人退出。然后从下一个人开始继续报数并按相同规则退出，知道所有人退出。
* 随机存取：顺序表中元素顺序存放在一大块存储区中，要存取下表为i的元素，可以用简单的公式计算出元素位置，在O(1)时间直接存取。
* 顺序存取：链接表中元素存放在一批小块存储区中，用显式的链接将它们连成一串，形成链接结构。
*
访问的局部性：顺序表的表元素顺序映射到内存中连续的单元里，下一个元素的实际存储位置与当前元素很近，由于当前计算机体系结构的特点，顺序访问内存中相近位置的效率较高，而真正的随机访问（比如链接表访问下一个结点）效率较低。
* 类定义的内在一致性：再设计一个类时，需要考虑一套统一的规则。类初始化方法建立起的对象应满足这套规则，操作也不能破坏规则，这样定义的类才是有效的。
***
### 2.那些事物适合用线性表存储和管理?并说明原因。
顺序表优点：随机存取，在O(1)时间进行；缺点：插入和删除都可能需要移动很多元素，操作代价很高（尾端插入、删除除外）。
* 书架上的一排书。
* 计算机桌面上的图标以及相关信息。
* 计算机的文件、文件夹（目录）。
### 3.
* 尾端，尾端插入和删除不需要移动其他元素，时间复杂度为O(1)。
* 哪端都可以，时间复杂度都是O(1)。
### 4.
* 顺序表，条件中的几种操作在顺序表中时间复杂度都是O(1)。
### 5.
* 表对象记录着表首结点引用、尾结点引用。要在尾端插入删除，为提高效率，应增加一个尾结点指针。
### 6.
* 插入和删除都可能需要移动很多元素，操作代价很高（尾端插入、删除除外）；能避免。
* 存取元素是顺序存取，效率很低。能避免。
### 7.
淘宝的购物车，用户需要首端加入和随机删除，用链接表合适。
### 8.
* 选择使用顺序表的情况：频繁随机存取元素、尾端插入和删除新元素，不常用插入和删除元素。
* 选择使用链接表的情况：相反情况。
### 9.
设计一个程序，对两个排序序列L1和L2进行归并，要求时间复杂度为O(max(m,n)),m和n是两个排序序列的元素个数。
def guibing(L1,L2):
for x in L1:
for y in L2:
while x
### 10.比较带尾结点指针的单链表和循环单链表。
* 带尾结点指针的单链表：支持高效的后端操作，包括表元素访问和新元素插入，但不包括删除。在需要频繁两端插入的情况下适用。
* 循环单链表：表的每一个结点都可以作为首结点，也是支持高效的后端操作，包括表元素访问和新元素插入，但不包括删除。
### 11.比较循环单链表和双链表的特点。
* 循环单链表：表的每一个结点都可以作为首结点，也是支持高效的后端操作，包括表元素访问和新元素插入，但不包括删除。
* 双链表：可以向前访问，也可以向后访问。增加一种数据访问顺序，使表中间结点的操作更加方便。实现两端的高效插入和删除。
***
***
## 第四章、字符串
### 1.复习下面概念
* 字符：基本文字符号。
* 字符集：有穷的一组字符构成的集合。
* 字符串（串）：字符的序列。
* ASCII：由127个字符组成的、基于拉丁字母的一套电脑编码系统。
* Unicode：国际通用编码。
* 字符序：字符集里的字符定义的一种顺序。
* 字符串长度：串中字符的个数。
* 空串：串中字符个数为零。
* 下标（字符位置）：串中字符顺序排列，每个字符都有确定的位置，本书中用从零开始的自然数表示下标。
* 字符串相等：两个串的长度相等，对应下标的字符也一一对应相同。
* 字典序：字符串上的一种序关系，基于字符串定义。
* 拼接：两个字符串通过拼接得到一个字符串，在Python中用+表示字符串拼接。
* 子串：一个串和另一个串的一个连续片段相同，就说是它的子串。
* 子串的出现位置：在母串(?)中跟子串相同的字符段的首字符的下标。
* 前缀、后缀：一个串的前缀就是该串开头的任意一段字符构成的子串。后缀同理。
* 串的幂：一个串的n次幂就是n个这个串的拼接。
* 串替换：把一个串里的一些串替换为另一些串得到的结果。
* 子串检索（子串匹配）：同字符串匹配。
*
Python的str类型：可以看作抽象的字符串概念的一个实现。str是不变类型。str对象采用第三章线性表里提到过的，一体式顺序表形式实现。（元素有数字有子母，大小不同，表元素外置）
* 字符串匹配：
* 模式匹配：
* 模式串：
* 目标串：
* 朴素匹配算法：
* KMP算法（无回溯串匹配）：
* 模式：
* 模式语言：
* 描述能力和匹配算法的复杂性：
* 通配符：
* 正则表达式：
* 正则表达式匹配：
* Python标准库re包：
* Python原始字符串：
* 元字符：
* 常规字符：
* 顺序组合（拼接）：
* 字符组：
* 重复模式:
* 选择模式：
* 组概念：
***
### 2.
### 3.
### 4.
***
***
## 第五章、栈和队列
***
### 1.复习下面概念
* 容器：一个容器结构里总包含一组其他类型的数据对象，称其为元素，支持对这些元素的存储、管理、使用。
* 元素：容器中包含的数据对象。
* 容器数据结构：能保证存入的元素被保存在容器中，尚未明确删除的元素总可以访问，而取出并删除的元素就不能存在于容器中了。
* 栈（堆栈）：保存数据的容器，主要用于在计算过程中保存临时数据，栈是保证元素后进先出关系的结构，简称为LIFO结构。
* 队列（队）：队列是保证元素先进先出关系的结构，简称为FIFO结构。
*
缓冲存储（缓存）：工作中产生的中间数据暂时不用或者用不完，就有必要把当时不能立即用掉的数据存起来，如果需要存储的数据项数不能事先确定，就不能用设置变量的方法来存储了，就需要采用更复杂的机制存储和管理。这样的存储机制叫做缓冲机制或者缓存。
* 后进先出（LIFO，后进先出表）：按照数据生成的顺序，较后生成并保存的数据需要先行使用和处理。（支持这种顺序使用元素的缓存数据结构就叫做栈）
* 先进先出（FIFO）：按照先后顺序处理，先生成的数据先处理。
* 实现结构：实现其功能所用的结构。
* 入栈：把元素压入栈中。
* 出栈：从栈中弹出元素并返回。
* 栈顶：执行插入和删除元素操作的一端。
* 栈底：栈的另一端。
* 括号匹配问题：在许多正文中都有括号，特别是程序、数学表达式的正文片段中，括号应该正确的嵌套并分别配对。
*
表达式的中缀表示、前缀表示、后缀表示：二元运算符写在两个运算对象中间，这种写法叫做中缀表示；函数符号写在运算对象前面的写法叫做前缀表示；运算符写在运算对象之后的写法叫做后缀表示。
* 波兰表达式：前缀表达式的另一种叫法。
* 逆波兰表达式：后缀表达式的另一种叫法。
* 表达式求值：表达式的运算求得结果过程。
* 表达式形式转换：中缀表达式在计算机中情况很复杂，求值不好处理，所以可以把它转换为后缀表达式来处理。
* 运算符栈：表达式型式转换中，存放运算符的栈。
* 数据栈：表达式型式转换中，存放数据对象的栈。
* 函数的递归定义：在一个定义中引用了被定义的函数本身，这种定义就叫递归定义。
* 递归结构：在一种数据结构里的某个或某几个部分具有与整体同样的结构，就叫做递归结构。
* 递归调用：在Python中定义一个函数时，允许在函数的定义体中出现对这个函数自身的调用。
* 运行栈：要支持递归函数的实现，需要一个栈保存递归函数执行时每层调用的局部信息，留待函数调用返回后继续使用，这个栈叫做运行栈。
*
函数帧（帧）：递归函数执行中的局部信息包括函数的形参、局部变量以及保存的数据，这些信息用一个运行栈保存。运行栈对递归函数的每个调用都在这个栈上给它开辟一块区域，叫做一个函数帧（帧）。
* 入队：把一个元素放入队列。
* 出队：从队列中删除一个元素并返回它。
* 循环顺序表：顺序表的变形。其最后存储位置之后是最前的位置，形成一个环形结构。
* 数据不变式：实现一种数据结构里的操作时，最基本的问题就是这些操作需要维护对象属性间的正确关系。这样一套关系被称为数据结构的数据不变式。
* 消息：windows系统里，各种活动（窗口界面操作、各种输入输出、程序活动）都可能产生各种消息，要求某些系统程序或者用户程序对他们做出响应。
* 消息驱动的系统：消息要求某些系统程序或者用户程序对他们做出响应。
* 消息队列：保存系统从各种活动中接收到各种消息。系统消息分发机制检查消息队列中的消息，根据情况把它们分发给相应程序。
*
离散时间系统和模拟：离散时间系统是真实世界中许多实际系统的抽象。模拟是人们通过计算机程序的运行，来模拟真实系统的活动情况。帮助理解真实世界实际运行中的行为，或者是为计划中的实际系统的设计和实现方式做一些准备。
* 迷宫问题：给一个迷宫图，图上有一个入点，一个出点，要求找到一条可以通过的从入点到出点的路径。
* 当前位置：。
* 探查：检查当前位置是否能通行。
* 回溯法：后退并考虑其他可能性的动作叫做回溯。回溯法通常总是用一个栈作为辅助结构，保存工作中发现的回溯点，以便后续考虑其他可能性时使用。
* 搜索：
*
状态空间搜索（路径搜索）：以迷宫问题为代表的一类问题叫做状态空间搜索。这类问题的基本特征是存在位置、情况等状态；有一个初始状态，一个或者几个结束状态（或者是有判断结束的方法）；每个状态都有neighbor(x)表示跟这个状态x相邻的一组状态；有一个判断函数来判断一个状态是否可行；问题：从x出发，设法找到一个或者全部的解。
* 通用问题求解方法：
* 深度优先搜索：基于栈的搜索称为~，进入一个局部区域，只有穷尽了哪里的状态并发现无法到达目标后才退出来。
* 宽度优先搜索：基于队列的搜索称为~，从入点开始，只有检查完所有与入口同样距离的位置之后，才往前进一步。
* 最优解：在迷宫问题中，就是长度最短的那个路径。
* 双端队列（deque）：允许两段插入、删除元素的缓存结构。
***
### 2.
* 栈只能栈顶插入、删除元素。
d,c,b,a ？？？
### 3.
* a,b,c,d ？？？
### 4.
* a2=k-1;a(i+1)=k-1 ？？？
### 5.
* ai>aj>ak
### 6.中缀形式-->前缀形式
* + a b * - c d
* * 2 + / / a b c d
### 7.后缀形式-->中缀形式
* a-[b/c-f*d/(3+r)]
* (2+a)/b/[(c-d)-e*f]
### 8.中缀形式-->前缀形式、后缀形式
* 前缀形式： / + 1 - * 2 3 5 4 ; 后缀形式： 1 2 3 5 - * 4 + /
* 前缀形式： + * + 7 4 - / 6 3 4 ；后缀形式： 7 4 + 2 6 3 - / 4 * /
### 9.
~~~
while 支线上还有车厢：
for 车厢=硬座：
连接到车头上
else：
进入另一条支线
把另一条支线上的车厢连接到硬座车厢后面
~~~
### 10.
* 24
* 120
