信息检索上机报告

1、信息储存与检索上机报告姓名：马云学号：06121001日期：2015.5.15（一）逆波兰变换一、上机题目： 编写算法和程序，实现布尔检索式的逆波兰变换。二、试验编程语言：C 语言三、程序设计总体思路：1、建立两个栈：算项指针栈和算符栈。2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：如果是算项，将指向该算项的指针放到算项栈中。如果是“（” ，则“（”无条件进算符栈，如果是“） ” ，则将算符栈中“（”以及“（”以上的算符出栈。如果是运算符+ - *,将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符

2、作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈,作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“” 。一棵表达式二叉树建立完成。3、后序遍历此二叉树，显示逆波兰表达式。四、程序源代码#include stdafx.h#include stdafx.h#include#includetypedef structchar s2020;int top;SQ;void copystr(char *a,char *b) int i=0; do bi=ai; i+; while

3、(ai!=0); bi=0;void voidSQ(SQ *s) s-top=-1;int ifempty(SQ *s) return(s-top=-1);void push(SQ *S,char *c) if(S-top=19) printf(over flown); else S-top+; copystr(c,S-sS-top); char *pop(SQ *S) if(ifempty(S) printf(over flow!n); return(NULL); else return(S-sS-top-);int judge(char *c) if(c1=0) switch(c0) ca

4、se +:return(3); case -:return(3); case *:return(2); case /:return(2); default:return(1); else return(1);void write(char *a,char *b,char *c) strcat(a,c); strcat(a,b);int seek(char *c,int start) int signal=1; for(start=start+;cstart!=0&signal!=0;start+) if(cstart=) signal-; else if(cstart=() signal+;

5、if(signal=0) return(start-1); else printf(输入无效式子n); return(-1); void FB(SQ *A,SQ *B) for(;!ifempty(A);) push(B,A-sA-top); pop(A); char *rewrite(char *A) SQ front; SQ back; int i,j,k,flag=0; char *result; char mid20; voidSQ(&front); voidSQ(&back); for(i=0;Ai!=0;) if(Ai=() j=seek(A,i); for(k=i+1;k=2;)

6、 flag=0; for(i=0;i=2;) if(judge(front.sfront.top)=1&judge(front.sfront.top-1)=2&judge(front.sfront.top-2)=1) write(front.sfront.top,front.sfront.top-1,front.sfront.top-2); push(&back,front.sfront.top); pop(&front); pop(&front); pop(&front); else push(&back,front.sfront.top); pop(&front); FB(&front,&

7、back); FB(&back,&front); else for(;front.top=2;) if(judge(front.sfront.top)=1&judge(front.sfront.top-1)=3&judge(front.sfront.top-2)=1) write(front.sfront.top,front.sfront.top-1,front.sfront.top-2); push(&back,front.sfront.top); pop(&front); pop(&front); pop(&front); else push(&back,front.sfront.top)

8、; pop(&front); FB(&front,&back); FB(&back,&front); result=front.sfront.top; return(result);void main() char re20; char a20; printf(请输入算式：n); scanf(%s,a); copystr(rewrite(a),re); printf(逆波兰式：n%sn,re);五、程序运行结果将中缀表达式：a*(b+(c-d)转换为逆波兰形式六、上机结果分析与总结（1）能够实现检索提问表达式的逆波兰形式输出，结果正确。（2）检索指令必须是精确匹配，友好性不是很好。（3）程序调

9、试环境为 Win-Tc,不能在中文 DOS 环境下运行，直观性差。（二）准波兰一、上机题目：编写算法和程序，实现布尔检索式的准波兰变换。二、试验编程语言：C 语言三、程序设计总体思路：在逆波兰变换的基础上，进一步实现准波兰变换：（1） 如上题程序中，建立前缀表达式的二叉树。（2） 利用递归调用的思想，将每个节点左右子树的深度进行比较，如果右子树的深度大于左子树，将它们调换；如果小于或相等，则不动。（3） 后序遍历打印二叉树，输出的即为准波兰表达式。如下图，即为二叉树变换为可以后序遍历生成准波兰表达式的树的过程：四、程序源代码/ xinguan.cpp : Defines the entry p

10、oint for the console application./#include stdafx.h#include#include #include #include typedef struct node /* 结构体 */ char chValue; struct node *pLeftChild, *pRightChild; /* 指向左右节点的指针 */ BiNode; BiNode *GenerateTree(char *pFormula); /* 由一般表达式生成树 */ int DepthTree(BiNode *pRoot); void ChangeTree(BiNode

11、*pRoot); void PostOrderPrintTree(BiNode *pRoot); /* 后续打印 */void PostOrderFreeTree(BiNode *pRoot); /* 释放节点 */ void main() char Formula100,*a; BiNode *pRoot; printf(请输入算式:n); a=Formula; scanf(%s,a); pRoot = GenerateTree(Formula);/* 返回根节点的指针 */ printf(n); printf(准波兰式是:n); ChangeTree(pRoot); PostOrderPr

12、intTree(pRoot); PostOrderFreeTree(pRoot); printf(n); getch(); unsigned char IsOper(char op) /* 判断是否为运算符 */ int i; char oper = (, ), +, -, *, ; for(i=0; ichValue = ch; pNode-pLeftChild = NULL; pNode-pRightChild = NULL; PushNode(pNode); ch = pFormulaidx+; else switch(ch) case (:/* 进栈 */ PushOper(); ch

13、 = pFormulaidx+; break; case ):/* 脱括号 */ while(1) c = PopOper(); if(=c) break; pNode = (BiNode *)malloc(sizeof(BiNode); pNode-chValue = c; pNode-pLeftChild = NULL; pNode-pRightChild = NULL; if(0!=SizeNode() pNode-pRightChild = PopNode();if(0!=SizeNode() pNode-pLeftChild = PopNode(); PushNode(pNode);

14、 ch = pFormulaidx+; break; default: if(0=SizeOper() | 0!=ch & GetOperPri(TopOper() chValue = PopOper(); pNode-pLeftChild = NULL; pNode-pRightChild = NULL; if(SizeNode() pNode-pRightChild = PopNode(); if(SizeNode() pNode-pLeftChild = PopNode(); PushNode(pNode); /* PopOper(); */ break; pNode = PopNode

15、(); /* 根节点 */ return pNode; int DepthTree(BiNode *pRoot) /* 树深度 */ int l,r; if(pRoot=NULL)return 0; l=DepthTree(pRoot-pLeftChild); r=DepthTree(pRoot-pRightChild); return(l=r? l+1:r+1); void ChangeTree(BiNode *pRoot) /* 如果右子树大于左子树，交换 */ BiNode *pTree=NULL; if(NULL != pRoot) if(DepthTree(pRoot-pLeftCh

16、ild)pRightChild) pTree=pRoot-pRightChild; pRoot-pRightChild=pRoot-pLeftChild; pRoot-pLeftChild=pTree; ChangeTree(pRoot-pLeftChild); ChangeTree(pRoot-pRightChild); void PostOrderPrintTree(BiNode *pRoot) if(NULL != pRoot) PostOrderPrintTree(pRoot-pLeftChild); PostOrderPrintTree(pRoot-pRightChild); pri

17、ntf(%c, pRoot-chValue); void PostOrderFreeTree(BiNode *pRoot) if(NULL != pRoot) PostOrderFreeTree(pRoot-pLeftChild); PostOrderFreeTree(pRoot-pRightChild); free(pRoot); 五、程序运行结果六、上机结果分析与总结（1）能够实现检索提问表达式的准波兰形式输出，结果正确。（2）准波兰是对逆波兰变换的改进，在子树根不对称时，先处理较大分支，这样占用工作区较少。（3）该方法算法稍微复杂，不过只在已有逆波兰检索系统上增加一个重组模块，可以将内存工作区从 7 个降低至 5 个。（4）另外，在编程过程中，暴露出自己编程的知识还不够扎实。以后需加强。（三）检索指令表将表达式 a+b*c-d 变为检索指令的过程：地址检索词01a02b03c04d检索词表特征内容0010020031*1+00410。逆波兰输出区生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022输入1033与4234或3142输入11非5123存储237终止0将表达式 a-(b+c)*d 变为