Tasks.Data_Structure

数据结构第一次实验课作业

题目

第二章实验题6

目的

掌握单链表的应用和算法设计。

内容

编写一个程序 exp2-6.cpp ，以给定值 x 为基准将单链表分割为两部分，所有小于 x 的节点排在大于或等于 x 的节点之前。

第三章实验题7

目的

掌握栈应用的算法设计。

内容

编写一个程序 exp3-7.cpp ，按升序对一个字符栈进行排序，即最小元素位于栈顶，最多只能使用一个额外的栈存放临时数据，并输出排序过程。

第四章实验题3

目的

掌握串的模式匹配算法（即 BF 和 KMP 算法）设计。

内容

编写一个程序 exp4-3.cpp ，实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：

建立目标串 s="abcabcdabcdeabcdefabcdefg" 和模式串 t="abcdeabcdefab" 。
采用简单匹配算法求 t 在 s 中的位置。
由模式串 t 求出 next 数组值和 nextval 数组值。
采用 KMP 算法求 t 在 s 中的位置。
采用改进的 KMP 算法求 t 在 s 中的位置。

第五章实验题2

目的

领会基本递归算法设计和递归执行过程。

内容

编写程序 exp5-2.cpp 求路径和路径条数的问题。有一个 m*n 的网格，如图所示是一个 2*5 的网格。现在一个机器人位于左上角 (m,n) ，该机器人在任何位置上时，只能向下 (-1,0) 或者向右 (0,-1) 移动一格，问机器人到达网格右下角 (1,1) 位置的所有可能的路径条数，并输出所有的路径。

     5   4   3   2   1
   +---+---+---+---+---+
 2 | S |   |   |   |   |
   +---+---+---+---+---+
 1 |   |   |   |   | T |
   +---+---+---+---+---+

 S : 机器人初始位置
 T : 终点位置

以 m=2, n=2 为例说明输出所有路径的过程。

提交

将作业打包为压缩文件，如 zip 格式。
压缩文件命名为你的学号，如 2018302114514.zip 。
将压缩文件以附件形式发送到邮箱 DS_Exp1 # superexercisebook.com
如果一切顺利，你将会收到一个投递成功回执。