数据结构课设报告

《数据结构课设报告》由会员分享，可在线阅读，更多相关《数据结构课设报告（32页珍藏版）》请在金锄头文库上搜索。

1、1二、计算命题公式的真值 1问题描述 所谓命题演算公式是指由逻辑变量（其值为 TRUE 或 FALSE）和逻辑运算符（AND） 、 （OR）和（NOT）按一定规则所组成的公式（蕴含之类的运算可以用、和来表示） 。公式运算的先后顺序为、，而括号（）可以改变优先次序。已知一个命题演算 公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： 1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然 后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值， 即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真 值。 2）逻辑变

2、元的标识符不限于单字母，而可以是任意长的字母数字串。 3）根据用户的要求显示表达式的真值表。2需求分析 2.1、命题演算公式的定义 命题演算公式是指由逻辑变量（其值为 TRUE 或 FALSE）和逻辑运算符（AND） 、 （OR）和（NOT）按一定规则所组成的公式（蕴含之类的运算可以用、和来表示） 。2.2、运算规则 公式运算的先后顺序为、，而括号（）可以改变优先次序。2.3、输入输出 输入一个中缀表达式，将此表达式转换为后缀表达式，并以此给变量赋值，求出该逻 辑表达式的真值。3概要设计 3.1、存储数据所用数据结构 3.1.1、用字符数组 ab100存放用户输入的中缀表达式并将其转换为用 D

3、ata 结构体数 组 a100存放的中缀表达式； 抽象数据类型定义如下： typedef struct char biao100; int num; Data;typedef struct/栈 char stackMaxSize; int top; SeqStack;23.1.2、用 Data 结构体数组 b100存放转换后的后缀表达式；3.1.3、用 BiTreeNode 结构体存放二叉树的结点； 抽象数据类型定义如下： typedef struct Node DataType data100; struct Node *leftChild; struct Node *rightChild;

4、 struct Node *parent; BiTreeNode;3.1.4、用 Stack 结构体存放二叉树结点的栈类型。 抽象数据类型定义如下： typedef struct BiTreeNode *address1000; int top; Stack;3.2、基本计算步骤 3.2.1、利用堆栈将中缀形式的公式变为后缀形式； 3.2.2、根据后缀形式，从叶结点开始构造相应的二叉树； 3.2.3、按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出 来，当到达根结点时，求得的值就是公式之真值。3.3、基本要求 3.3.1、逻辑变元的标识符不限于单字母，而可以是任意长的字母数

5、字串。 3.3.2、根据用户的要求显示表达式的真值表。3.4、简要流程图3首先调用其次调用最后调用3.5、算法设计 本设计从总体上划分为以下四个模块： 3.5.1、主函数 main()模块 本模块的功能是实现逻辑表达式的输入以及各函数的调用和逻辑表达式计算结果的输 出，并控制程序的开始与结束。通过调用 houzhui(a,b,s)来实现中缀转变为后缀；通过调用 CreatTree(b,n)来实现从叶子结点开始构造一棵二叉树；通过调用 PostOrder(t,b,n)来实现对 二叉树的后续遍历并计算出逻辑表达式的真值。3.5.2、中缀表达式转为后缀表达式 int houzhui(Data zho

6、ngzhui,Data *b,SeqStack s)模块 本模块的功能是利用堆栈来实现把中缀逻辑表达式转换为后缀逻辑表达式，本模块所 用函数及抽象数据类型均在 houzhui.h 这个头文件中，此模块将转换之后的后缀表达式数组 的个数返回给主函数。3.5.3、构造二叉树 BiTreeNode *CreatTree(Data *b,int n)模块 此模块利用堆栈来实现从叶子结点构造二叉树。通过调用 SInitiate(/定义后缀数组 int count=0,j=0,i=0; while(zhongzhuij.biao0!=0)/取中缀字符 current=zhongzhuij.biao0;/取

7、当前为中缀字符 if(!if_operator(current)/判断字符是运算变量 for(i=0;zhongzhuij.biaoi!=0;i+) bcount.biaoi=zhongzhuij.biaoi; bcount.num=count; count+; j+; if(if_operator(current) while(priority(d)priority(current)/当前字符的优先级小于栈顶元素的优 先级 StackPop( bcount.biao0=d1; bcount.num=count; count+; StackTop(s, if(priority(d)data,0

8、,sizeof(p-data);/清零申请结点的 data 域 for(j=0;bi.biaoj!=0;j+) p-dataj=bi.biaoj; /将变量赋给结点 P 的 data 域 p-rightChild=NULL;/初始化左右子树以及双亲指针 p-leftChild=NULL; p-parent=NULL; if(bi.biao0=!)/变量为!时，栈顶元素为该结点的右孩子 q=Pop( p-rightChild=q; /将弹出后的结点作为右孩子6q-parent=p; Push(/将该结点入栈 else if(bi.biao0=|bi.biao0= /弹出 q 作为右孩子o=Pop

9、( /弹出 0 作为左孩子q-parent=p; o-parent=p; p-leftChild=o; p-rightChild=q; Push( /将该结点入栈 else Push(/如果变量为运算变量，则将该结点入栈 p=Pop( /弹出构造好的二叉数的根结点指针，并返回 return p; 4.3、后续遍历二叉树并计算真值 int PostOrder(BiTreeNode *t,Data b,int n) 本模块主要思想如下：（1）后续遍历所创建的二叉树，读出对应的 data 域对应的真 值；（2）若结点的 data 域为运算变量，则直接返回该变量所对应的真值；（3）若结点的 data

10、域为!，则对该结点的右孩子结点对应真值 a1 求反，并返回计算结果；（4）若结点 的 data 域为if(t!=NULL) a=PostOrder(t-leftChild,b,n);/遍历左子树并返回对应的真值 a1=PostOrder(t-rightChild,b,n);/遍历右子树并返回对应的真值 for(i=0;idataj) k=bi.num; else break; p=ck;/找到真值7if(t-data0=!)/变量为!时对右子树真值取反 if(a1=0) return 1;if(a1=1) return 0; else if(t-data0= else return 0; el

11、se if(t-data0=|)/变量为|时对左子树真值与右子树真值进行或运算，只有 真值均为 0 时返回 0 if(a=0 else return 1; else return p; /如果该变量为运算变量则直接返回该变量对应的真值 return -1; 5测试结果 组数测试输入测试目的正确输出实际输出错误原因当前状态1A时间复杂度 O(n) 空间复杂度 O(n) BiTreeNode * CreatTree();时间复杂度 O(2n) 空间复杂度 O(n) PostOrder();时间复杂度 O(2n) 空间复杂度 O(n)6.3、其他算法及意见 本程序中还可以用二维数组来存放中缀表达式及

12、后缀表达式，并且可以以动态申请的 方式，这样可以节省内存空间，同样也可以利用链式堆栈来替代顺序堆栈。7、附录 程序文件名清单： 逻辑表达式真值.c /计算逻辑表达式程序的 c 语言文件 houzhui.h /将中缀表达式转换为后缀表达式函数所在头文件 参考文献： 1 朱战立，数据结构使用 C 语言，西安交通大学出版社，2004 年五、迷宫问题1问题描述 以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 基本要求： （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归

13、程序。 求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d 表示走到下一坐 标的方向。 （2）测试几组数据，数据的规模由小变大，即网格越来越小，障碍越来越复杂。 拓展要求：实现该问题的可视化界面，用鼠标点击即可一步步走出迷宫。 提示：10计算机解迷宫问题通常采用“穷举求解”方法2需求分析 2.1、迷宫的表示方法 以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。 2.2、实现方法 计算机解迷宫问题通常采用“穷举求解”方法。 2.3、输入输出 以一个二维数组的形式输入迷宫，求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指 示迷宫

14、中的一个坐标，d 表示走到下一坐标的方向。3概要设计 3.1、数据结构的设计 3.1.1、用链式堆栈来存储在迷宫中寻找路径所走过的结点，方便在找不到前进路径的 时候进行出栈回溯； 3.1.2、用一个 Data 结构体来存放堆栈中对应数据域元素的属性，方便对对应的元素 进行操作； 3.1.3、用一个二维数组来存放以矩阵形式表示的迷宫，方便对迷宫路径的寻找及方向 的标记与表示。3.2、算法的设计 本程序主要分为以下三个部分： 3.2.1、主函数 main()模块 本模块主要是实现用户可视界面及迷宫的输入，利用二维数组来存放用户输入的迷宫 的内容，通过调用函数 search 和 printpath

15、来实现路径的寻找与输出。 3.2.2、寻找路径 search()模块 本模块主要是实现找到从迷宫入口到迷宫出口的路径，并记录下在每个结点进行寻找 时到下一个结点的方向，返回查找是否成功。函数接口为：search(a,p,q,r,S)。 3.2.3、输出路径 printpath()模块 本模块主要是实现对找到的路径进行输出，以三元组(i,j,d)的形式输出，其中(i,j)指示迷 宫中的一个坐标，d 表示走到下一坐标的方向。函数接口为：printpath(s)。 调用关系图如下：3.3、抽象数据类型的设计 3.3.1、链式堆栈结点typedef struct snode主 函 数SearchPrintpathStackInitiate、StackPush 、 StackNotEmpty、StackTopStackNotEmpty、StackPop11 Data data; struct snode *next; LSNode;3.3.2、Data 结构体typedef struct int row;/行坐标 int col;/列坐标 int di