《信息检索上机报告.doc》由会员分享，可在线阅读，更多相关《信息检索上机报告.doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、书山有路勤为径，学海无涯苦作舟。信息检索上机报告 信息储存与检索上机报告 姓名：马云学号：06121001日期：2021.5.15 （一）逆波兰变换 一、上机题目： 编写算法和程序，实现布尔检索式的逆波兰变换。 二、试验编程语言：c语言三、程序设计总体思路： 1、建立两个栈。算项指针栈和算符栈。 2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理： 如果是算项，将指向该算项的指针放到算项栈中。如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。 如果是运算符+-*，将他们与算符栈栈顶算符进行比较，如果优先级高于那个算
2、符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈，作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“”。一棵表达式二叉树建立完成。 3、后序遍历此二叉树，显示逆波兰表达式。 四、程序源代码 #include#include#include#include typedefstructchars2020;inttop;sq;voidcopystr（char*a，char*b） inti=0;do bi=ai;i+; wh
3、ile（ai。=0）;bi=0; voidvoidsq（sq*s） s-top=-1; intifempty（sq*s） return（s-top=-1）; voidpush（sq*s，char*c） if（s-top=19） printf（else s-top+; copystr（c，s-ss-top）; char*pop（sq*s） if（ifempty（s） printf（return（null）;else return（s-ss-top-）; intjudge（char*c） if（c1=0）switch（c0） case+：return（3）;case-：return（3）;case
4、*：return（2）;case/：return（2）;default：return（1）;else return（1）; voidwrite（char*a，char*b，char*c） strcat（a，c）;strcat（a，b）; intseek（char*c，intstart） intsignal=1; for（start=start+;cstart。=0&signal。=0;start+） if（cstart=）signal-; elseif（cstart=（）signal+; if（signal=0） return（start-1）;else printf（输入无效式子nretur
5、n（-1）; voidfb（sq*a，sq*b） for（;。ifempty（a）;） push（b，a-sa-top）;pop（a）; char*rewrite（char*a） sqfront;sqback; inti，j，k，flag=0;char*result;charmid20;voidsq（&front）;voidsq（&back）;for（i=0;ai。=0;） if（ai=（） j=seek（a，i）; for（k=i+1;k=2;） flag=0; for（i=0;i=2;） if（judge（front.sfront.top）=1&judge（front.sfront.top
6、-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，&back）;fb（&back，&front）;else for（;front.top=2;） if（judge（front.sfront.top）=1&judg
7、e（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）;pop（&front）; fb（&front，&back）;fb（&back，&front）; result=front.sfront.top;return（result
8、）; voidmain charre20;chara20; printf（请输入算式：n scanf（ copystr（rewrite（a），re）; printf（逆波兰式：n%sn 五、程序运行结果 将中缀表达式：a*（b+（c-d）转换为逆波兰形式 六、上机结果分析与总结 （1）能够实现检索提问表达式的逆波兰形式输出，结果正确。（2）检索指令必须是精确匹配，友好性不是很好。 （3）程序调试环境为win-tc，不能在中文dos环境下运行，直观性差。 （二）准波兰 一、上机题目： 编写算法和程序，实现布尔检索式的准波兰变换。 二、试验编程语言：c语言三、程序设计总体思路： 在逆波兰变换的基础
9、上，进一步实现准波兰变换。（1）如上题程序中，建立前缀表达式的二叉树。（2）利用递归调用的思想，将每个节点左右子树的深度进行比较，如果右子树 的深度大于左子树，将它们调换；如果小于或相等，则不动。（3）后序遍历打印二叉树，输出的即为准波兰表达式。 如下图，即为二叉树变换为可以后序遍历生成准波兰表达式的树的过程： 四、程序源代码 /xinguan.cpp：definestheentrypointfortheconsoleapplication./ #include#include#include#include#include typedefstructnode/*结构体*/ charchval
10、ue; structnode*pleftchild，*prightchild;/*指向左右节点的指针*/binode; binode*generatetree（char*pformula）;/*由一般表达式生成树*/intdepthtree（binode*proot）;voidchangetree（binode*proot）; voidpostorderprinttree（binode*proot）;/*后续打印*/ voidpostorderfreetree（binode*proot）;/*释放节点*/voidmain charformula100，*a;binode*proot; prin
11、tf（请输入算式：na=formula;scanf（ proot=generatetree（formula）;/*返回根节点的指针*/printf（printf（准波兰式是：nchangetree（proot）; postorderprinttree（proot）;postorderfreetree else switch（ch） case（：/*进栈*/pushoper（）; ch=pformulaidx+;break; case）：/*脱括号*/while（1） c=popoper;if（=c）break; pnode=（binode*）malloc（sizeof（binode）;pnod
12、e-chvalue=c; pnode-pleftchild=null;pnode-prightchild=null; if（0。=sizenode） pnode-prightchild=popnode;if（0。=sizenode） pnode-pleftchild=popnode;pushnode（pnode）; ch=pformulaidx+;break;default： if（0=sizeoper|0。=ch&getoperpri（topoper）chvalue=popoper;pnode-pleftchild=null;pnode-prightchild=null; if（sizeno
13、de） pnode-prightchild=popnode;if（sizenode） pnode-pleftchild=popnode;pushnode（pnode）;/*popoper;*/ break;pnode=popnode;/*根节点*/returnpnode; intdepthtree（binode*proot）/*树深度*/intl，r; if（proot=null）return0; l=depthtree（proot-pleftchild）;r=depthtree（proot-prightchild）;return（l=r。l+1：r+1）; voidchangetree（bi
14、node*proot）/*如果右子树大于左子树，交换*/ binode*ptree=null;if（null。=proot） if（depthtree（proot-pleftchild）prightchild）ptree=proot-prightchild; proot-prightchild=proot-pleftchild;proot-pleftchild=ptree; changetree（proot-pleftchild）;changetree（proot-prightchild）; voidpostorderprinttree（binode*proot）if（null。=proot）
15、 postorderprinttree（proot-pleftchild）;postorderprinttree（proot-prightchild）;printf（voidpostorderfreetree（binode*proot） if（null。=proot） postorderfreetree（proot-pleftchild）;postorderfreetree（proot-prightchild）;free（proot）; 五、程序运行结果 六、上机结果分析与总结 （1）能够实现检索提问表达式的准波兰形式输出，结果正确。 （2）准波兰是对逆波兰变换的改进，在子树根不对称时，先处理
16、较大分支，这样占用工作区较少。（3）该方法算法稍微复杂，不过只在已有逆波兰检索系统上增加一个重组模块，可以将内存工作区从7个降低至5个。 （4）另外，在编程过程中，暴露出自己编程的知识还不够扎实。以后需加强。 （三）检索指令表 将表达式a+b*c-d变为检索指令的过程。地址检索词特征内容01a00102b00203c00304d1*检索词表1+00410。逆波兰输出区 生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022输入1033与4234或3142输入11非5123存储237终止0将表达式a-（b+c）*d变为检索指令的过程：特征内容地址检索词00101a002
17、02b00303c1+04d004检索词表1* 1 0。 逆波兰输出区 生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022输入1033或3234输入12与4243非5132存储227终止0 将表达式（a-b）*c+d变为检索指令的过程：地址检索词特征内容01a00102b00203c104d003检索词表1*0041+0。逆波兰输出区生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022非5123输入1031与4132输入1041或3123存储237终止0 将表达式（a-b）*c+d变为检索指令的过程：地址检索词特征内容01a00102b00203c104d003检索词表1*0041+0。逆波兰输出区生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022非5123输入1031与4132输入1041或3123存储237终止0 第 10 页 共 10 页