工程软件作业题目.doc

一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在20之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表的第i个位置插入新元素，并打印线性表。4）找到线性表中数值值最小的结点，输出该值；5） 将第4）步中找到的结点删除，并输出打印剩下的线性表。二/三、单链表（带头结点/不带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单链表结构实现如下算法（各算法边界条件适当给出）：1）按照后插法（带头结点）、前插法 （不带头结点）、创建任意有序单循环链表（即链表的元素随机在键盘上输入），长度限定在15之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）找到链表节点中数值最小的结点，并输出该结点。4） 将第3）步中找到的结点删除，并输出打印剩下的链表。四、双向循环链表的基本操作实验要求：数据元素类型ElemType取float。按照动态双向循环链表结构实现如下算法（各算法边界条件适当给出）：1）按照前插法创建任意双向循环链表（即链表的元素随机在键盘上输入），长度限定在15之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表的第i个位置插入新元素，并打印新链表。4） 删除链表第i个位置的元素，并打印新链表。五、栈/链栈基本操作实验要求：数据元素类型ElemType取字符型char。从键盘随机输入字符元素，长度限制在10个字符之内。完成栈/链栈的入栈和退栈运算，直到退为空栈，分别打印出每入栈和退栈一个元素后栈内的元素。六、队列/链队列基本操作实验要求：数据元素类型ElemType取字符型char。从键盘随机输入字符元素，长度限制在10个字符之内。完成队列/链队列的入队和退队运算，直到退为空队列，分别打印出每入队和退队一个元素后队列内的元素。七、栈的应用：要求：从键盘输入一个10进制整型变量，利用链栈将其转化为2进制数数，并打印。(负整数采取补码的形式输出。)八、链表的应用：要求：从键盘随机输入整型元素，长度限制在10个字符之内，按照键盘输入的顺序创建有序单循环链表。并将此链表分解为两个单循环链表，其中一个链表只有偶数，一个链表只有奇数。九、链表的应用：要求：设多项式利用单循环链表输出上述两个多项式，并完成多项式的加法。十、稀疏矩阵压缩存储的基本操作实现实验要求：数据元素类型ElemType取float。1）从键盘输入稀疏矩阵的各元素。（行=5,列=5）2）建立稀疏矩阵的三元组表和POS、NUM向量，并输出。3）完成矩阵的转置和快速转置运算，并输出。十一、稀疏矩阵压缩存储的基本操作实现实验要求：数据元素类型ElemType取float。1）从键盘输入两个稀疏矩阵A、B的各元素。（行=5,列=5）2）完成矩阵的加法运算，并输出。十二、稀疏矩阵压缩存储的基本操作实现实验要求：数据元素类型ElemType取float。1）从键盘输入两个稀疏矩阵A、B的各元素。（行=5,列=5）2）完成矩阵的乘法运算，并输出。十三、稀疏矩阵压缩存储的基本操作实现实验要求：数据元素类型ElemType取float。1）从键盘输入稀疏矩阵的各元素。（行=5,列=5）2）建立稀疏矩阵的三元组链表，并依次输出链表中各元素的数据域。3）利用三元组链表，完成矩阵的转置和快速转置运算，并输出。十四、稀疏矩阵压缩存储的基本操作实现实验要求：数据元素类型ElemType取float。1）从键盘输入两个稀疏矩阵A、B的各元素。（行=5,列=5）2）建立稀疏矩阵A、B的三元组链表，并依次输出链表中各元素的数据域。3）利用三元组链表，完成矩阵的加法运算，并输出。十五、稀疏矩阵压缩存储的基本操作实现实验要求：数据元素类型ElemType取float。1）从键盘输入稀疏矩阵的各元素。（行=5,列=5）2）建立稀疏矩阵的十字链表。3）分别按行、列输出链表中各元素的数据域。 十六、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘输入某二叉树的前序序列和中序序列(中间无标识空结点的标识符)，创建此二叉树。(提示：前序序列的第一个元素是根结点，在中序序列中，以此元素为界，前后分别为左右子树，然后对左右子树进行递归。)2）对该二叉树进行前序、中序、后序遍历，并输出遍历后的序列。十七、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘按照前序遍历的顺序依次输入二叉树的各元素，创建此二叉树。2）对该二叉树进行层次遍历，并输出遍历后的序列。(参照图的广度优先搜索)十八、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘输入某二叉树的中序序列和后序序列(中间无标识空结点的标识符)，创建此二叉树。(提示：后序序列的最后一个元素是根结点元素，中序序列中以此元素为界，前后分别为左、右子树。然后对左、右子树分别进行递归。)2）依次输出该二叉树中的所有叶子结点。十九、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘按照前序遍历的顺序依次输入二叉树的各元素，创建此二叉树。2）按照某种遍历方法对二叉树进行遍历的同时，将二叉树的各结点的左右子树对调，并对调后和对调前的遍历序列。二十、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘按照前序遍历的顺序依次输入二叉树的各元素，创建此二叉树。2）对二叉树进行中序遍历，输出该二叉树的中序遍历序列。3）求该二叉树中叶子结点的数目。4）求该二叉树中大于x的结点个数。二十一、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘按照前序遍历的顺序依次输入二叉树的各元素，创建此二叉树。2）利用非递归算法对二叉树进行前序遍历，输出该二叉树的前序遍历序列，（其中，栈采取顺序存储结构）。3）求该二叉树中叶子结点的数目。二十二、二叉树的创建及遍历实验要求：数据元素类型ElemType取float。1）从键盘按照前序遍历的顺序依次输入二叉树的各元素，创建此二叉树。2）利用非递归算法对二叉树进行中序遍历，输出该二叉树的中序遍历序列，（其中，栈采取链式存储结构）。3）求该二叉树中大于x的结点个数。二十三、二叉树的穿线实验要求：数据元素类型ElemType取float。1）从键盘按照前序遍历的顺序依次输入二叉树的各元素，创建此二叉树。2）对输入的二叉树进行中序穿线，得到中序穿线二叉树。3）对中序穿线二叉树从根节点开始，按照寻找后件的方法进行遍历，并输出遍历后的序列。4）对中序穿线二叉树从根节点开始，按照寻找前件的方法进行遍历，并输出遍历后的序列。二十四、无向图的存储实验1）将右图按照邻接表进行存储2）依次输出顶点表中，各顶点的数据值3）根据邻接表判定各顶点之间是否存在边，若存在，则输出该边，如(A,B)。二十五、有向图的存储实验1）将右图按照邻接表进行存储2）依次输出顶点表中，各顶点的数据值3）根据邻接表判定各顶点之间是否存在边，若存在，则输出该边，如。二十六、无向图的存储实验1）将右图按照邻接多重表进行存储2）依次输出顶点表中，各顶点的数据值3）根据邻接多重表，依次输出依附于各顶点的边，如：A: (A,B), (A,E),(A,D)。二十七、有向图的存储实验1）将右图按照关联矩阵进行存储2）从关联矩阵出发，求某个节点的出度和入度。3）从关联矩阵出发，将此关联矩阵，转换为邻接表进行存储，并输出每个顶点的所有后件。二十八、无向图的存储实验要求：数据元素类型ElemType取char。1）将右图按照关联矩阵进行存储2）从关联矩阵出发，判定各顶点之间是否存在边，如果存在，输出该边，如(A,B)3）从关联矩阵出发，将此关联矩阵转换为邻接表进行存储，并输出每个顶点的所有后件。二十九、图的遍历实验要求：数据元素类型ElemType取char。1）将右图按照邻接表进行存储2）对该图进行DFS