河北工业大学-数据结构实验报告-基于二叉排序树的商品信息查询算法的设计与实现.doc

实验四：基于二叉排序树的商品信息查询算法的设计与实现 一、试验内容查找是数据处理的重要操作。请设计并实现基于二叉排序树的商品信息查询算法。完成信息的查询、插入、删除、查询频度的统计等功能。二、试验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法。三、流程图四、源程序代码#include#include#include#include using namespace std;struct shangpinint cishu,pingheng,jiage;char mingcheng40; shangpin *l,*r,*p;int shendu,quan;int max(int a,int b)if(ab)return(a);else return(b);shangpin *charu(shangpin *p)shangpin *p1,*l,*r;char a40;int b=0;cout请输入商品名称：a;err:b=strcmp(a,p-mingcheng);if(b=0)cout此商品已有。l=NULL)p-l=new shangpin;p1=p-l;strcpy(p1-mingcheng,a);p1-cishu=0;p1-l=NULL;p1-r=NULL;p1-p=p;p1-pingheng=0;cout请输入此商品的价格：p1-jiage;return(p-l);else l=p-l;p=l;goto err;else if(p-r=NULL)p-r=new shangpin;p1=p-r;strcpy(p1-mingcheng,a);p1-cishu=0;p1-r=NULL;p1-l=NULL;p1-p=p;p1-pingheng=0;cout请输入此商品的价格：p1-jiage;return(p-r);else r=p-r;p=r;goto err;void chushi(shangpin *p)cout建立初始节点：endl请输入商品名称：p-mingcheng;cout请输入此商品价格：p-jiage;cout请输入访问次数：p-cishu; p-l=NULL;p-r=NULL;p-p=NULL;p-pingheng=0;int chaxun(shangpin *p,char a)int b;err3:b=strcmp(a,p-mingcheng);if(b=0)cout查找成功，输出有关信息：cishu=p-cishu+1;cout此商品价格为：jiagel;if(p=NULL)cout没有此商品，查找失败！r;if(p=NULL)cout没有此商品，查找失败！endl;return(0);else goto err3;int shanchu(shangpin *p)shangpin *p1;char a40;int b;cout请输入要删除的商品的名称：a;err2:b=strcmp(a,p-mingcheng);if(b=0)p1=p-p;if(p1-l=p)if(p-l=NULL&p-r=NULL)p1-l=NULL;else if(p-l=NULL)p1-l=p-r;else if(p-r=NULL)p1-l=p-l;else p1-l=p-l;p1=p-r;while(p1-r!=NULL)p1=p1-r;p1-r=p-r;else if(p-l=NULL&p-r=NULL)p1-r=NULL;else if(p-l=NULL)p1-r=p-r;else p1-r=p-l;p1=p-r;while(p1-r!=NULL)p1=p1-r;p1-r=p-r;cout删除成功。l;if(p=NULL)cout没有此商品，删除失败！r;if(p=NULL)cout没有此商品，删除失败！l=NULL&p-r=NULL)cout只有一头节点！l=NULL)a=1;else p1=p;p=p-l;a=0;goto err7;if(a=1)if(p-r=NULL)a=2;else p1=p;p=p-r;a=0;goto err7;if(a=2)p1=p;p=p-p;if(p-l=p1)a=1;if(p-r=p1)a=2;if(p1-l=NULL&p1-r=NULL)p1-shendu=0;else if(p1-l=NULL)r=p1-r;p1-shendu=r-shendu+1;else if(p1-r=NULL)l=p1-l;p1-shendu=l-shendu+1;else r=p1-r;l=p1-l;p1-shendu=max(l-shendu,r-shendu)+1;if(p3-r=p1&a=2)l=p3-l;r=p3-r;if(l!=NULL)p3-shendu=max(l-shendu,r-shendu)+1;else p3-shendu=r-shendu+1;else if(p3-r=NULL&p3-l=p1)if(p3=p)p3-shendu=p1-shendu+1;else goto err7;else goto err7;return(0);shangpin *pinghenghua(shangpin *p0) shangpin *p2,*p3,*p4,*p5,*p6,*p7,*p8;int i,j,a,yong;a=0;shangpin *pq40,*p1,*l,*r,*p;err10:p=p0;if(p-l=NULL&p-r=NULL)cout这里只有一个节点！endl;return(p0);for(i=0;i40;i+)pqi=NULL;a=0;yong=bianlishendu(p0);for(i=0;i40;i+)for(j=0;jl=NULL)a=1;else p1=p;p=p-l;a=0;continue;if(a=1)if(p-r=NULL)a=2;else p1=p;p=p-r;a=0;continue;if(a=2)p1=p;p=p1-p;if(p-l=p1)a=1;if(p-r=p1)a=2;if(p1-l=NULL&p1-r=NULL)p1-quan=0;else if(p1-l=NULL)r=p1-r;p1-quan=-r-shendu-1;else if(p1-r=NULL)l=p1-l;p1-quan=l-shendu+1;else r=p1-r;l=p1-l;p1-quan=l-shendu-r-shendu;if(p0-r=p1&a=2)l=p0-l;r=p0-r;if(l!=NULL)p0-quan=l-shendu-r-shendu;else p0-quan=-r-shendu;goto err8;else if(p0-l=p1&p0-r=NULL)if(p0=p)p0-quan=p1-shendu+1;goto err8;else ;else ;err8:a=i; for(i=0;iquan=2)p2=pqi-l;if(p2-quan=1)if(p2!=NULL)p3=p2-l;p4=p2-r;p5=pqi-r;p6=pqi-p;if(p6=NULL)p2-p=NULL;else if(p6-l=pqi)p6-l=p2;p2-p=p6;else p6-r=p2;p2-p=p6;pqi-l=p4;if(p4!=NULL)p4-p=pqi;pqi-r=p5;if(p5!=NULL)p5-p=pqi;pqi-p=p2;if(p2!=NULL)p2-r=pqi;if(p2!=NULL)p2-l=p3;if(p3!=NULL)p3-p=p2;pqi-quan=0;pqi-shendu=pqi-shendu-2;if(p2!=NULL)p2-quan=0;p=p0;while(p-p!=NULL)p=p-p;yong=bianlishendu(p);break;if(p2-quan=-1)if(p2!=NULL)p3=p2-r;p4=pqi-p;if(p2!=NULL)p5=p2-l;if(p3!=NULL)p6=p3-l;if(p3!=NULL)p7=p3-r;p8=pqi-r;if(p4=NULL)p3-p=NULL;else if(p4-l=pqi)p4-l=p3;p3-p=p4;else p4-r=p3;p3-p=p4;if(p3!=NULL)p3-l=p2;if(p2!=NULL)p2-p=p3;if(p3!=NULL)p3-r=pqi;pqi-p=p3;if(p2!=NULL)p2-r=p6;if(p6!=NULL)p6-p=p2;pqi-l=p7;if(p7!=NULL)p7-p=pqi;pqi-r=p8;if(p8!=NULL)p8-p=pqi;pqi-quan=-1;if(p2!=NULL)p2-quan=0;if(p3!=NULL)p3-quan=0;if(p8!=NULL)pqi-shendu=p8-shendu+1;if(p2!=NULL)p2-shendu=p2-shendu-1;if(p2!=NULL&p3!=NULL)p3-shendu=p2-shendu+1;while(p-p!=NULL)p=p-p;yong=bianlishendu(p);break;if(pqi-quan=-2)p2=pqi-r;if(p2-quan=-1)if(p4!=NULL)p3=p2-l;p4=p2-r;p5=pqi-l;p6=pqi-p;if(p6=NULL)p2-p=NULL;else if(p6-l=pqi)p6-l=p2;p2-p=p6;else p6-r=p2;p2-p=p6;pqi-l=p5;if(p5!=NULL)p5-p=pqi;pqi-r=p3;if(p3!=NULL)p3-p=pqi;pqi-p=p2;if(p2!=NULL)p2-l=pqi;pqi-quan=0;pqi-shendu=pqi-shendu-2;if(p2!=NULL)p2-quan=0;while(p-p!=NULL)p=p-p;yong=bianlishendu(p);break;if(p2-quan=1)if(p2!=NULL)p3=p2-l;p5=p2-r;p4=pqi-p;if(p4!=NULL)p6=p3-r;p7=p3-l;p8=pqi-r;if(p4=NULL)p3-p=NULL;else if(p4-l=pqi)p4-l=p3;p3-p=p4;else p4-r=p3;p3-p=p4;if(p3!=NULL)p3-r=p2;if(p2!=NULL)p2-p=p3;if(p3!=NULL)p3-l=pqi;pqi-p=p3;if(p2!=NULL)p2-l=p6;if(p6!=NULL)p6-p=p2;pqi-l=p8;if(p8!=NULL)p8-p=pqi;pqi-r=p7;if(p7!=NULL)p7-p=pqi;pqi-quan=0;if(p2!=NULL)p2-quan=-1;if(p3!=NULL)p3-quan=0;if(p8!=NULL)pqi-shendu=p8-shendu+1;if(p2!=NULL)p2-shendu=p2-shendu-1;if(p3!=NULL&p2!=NULL)p3-shendu=p2-shendu+1;while(p-p!=NULL)p=p-p;yong=bianlishendu(p);break;for(i=0;iquan=-1&pqi-quanp=NULL;p-l=NULL;p-r=NULL;void main()char a,b,mingcheng40,*p1;int c,d=0,i,yong;shangpin head,meiyou40;shangpin *p,*t;p=&head;err7:p1=&mingcheng0;cout初始化输入A，插入输入B，查询输入C，删除输入D，了解客户需要的新商品输入E，结束输入F.endl#a;if(a=A)cout进入初始化程序：endl*endl;chushi(p);cout已生成一个头节点，是否继续插入节点Y/Nb;if(b=Y)err6:t=charu(p);cout请输入访问次数：t-cishu;p=pinghenghua(p);cout是否继续Y/Nb;if(b=Y)goto err6;else cout初始化结束。endl*endl;if(a=C)cout进入查询程序：endl请输入要查询的商品的名称：a;c=chaxun(p,a);if(c=0)for(i=0;id;i+)yong=strcmp(meiyoui.mingcheng,a);if(yong=0)meiyoui.cishu=meiyoui.cishu+1;break;if(i=d)strcpy(meiyoui.mingcheng,a);meiyoui.cishu=1;d=d+1;cout*endl;if(a=D)cout进入删除程序：endl;c=shanchu(p);cout*endl;p=pinghenghua(p);if(a=E)for(i=0;id;i+)cout商品名称为：meiyoui.mingcheng的商品，被查找过meiyoui.cishu次endl;cout*endl;if(a=B)cout进入插入程序：endl;t=charu(p);cout*endl;p=pinghenghua(p);if(a=F);else goto err7; 参考自百度文库五、实验结果：初始化输入A，插入输入B，查询输入C，删除输入D，了解客户需要的新商品输入E，结束输入F.#A进入初始化程序：*建立初始节点：请输入要查询的商品的名称：A请输入此商品价格：1请输入访问次数：1已生成一个头节点，是否继续插入节点Y/NY请输入要查询的商品的名称：B输入此商品的价格：2请输入访问次数：2是否继续Y/NY请输入要查询的商品的名称：C请输入此商品的价格：3请输入访问次数：3是否继续Y/NY请输入要查询的商品的名称：D请输入此商品的价格：4请输入访问次数：4是否继续Y/NY请输入要查询的商品的名称：E请输入此商品的价格：5请输入访问次数：5是否继续Y/NN初始化结束。初始化输入A，插入输入B，查询输入C，删除输入D，了解客户需要的新商品输入E，结束输入F.#C进入查询程序：请输入要查询的商品的名称：A查找成功，输出有关信息：此商品价格为：1*初始化输入A，插入输入B，查询输入C，删除输入D，了解客户需要的新商品输入E，结束输入F.#C进入查询程序：请输入要查询的商品的名称：B查找成功，输出有关信息：此商品价格为：2*初始化输入A，插入输入B，查询输入C，删除输入D，了解客户需要的新商品输入E，结束输入F.#C进入查询程序：请输入要查询的商品的名称：C查找成功，输出有关信息：此商品价格为：3*初始化输入A，插入输入B，查询输入C，删除输入D，了解客户需要的新商品输入E，结束输入F.#C进入查询程序：请输入要查询的商品的名称：D查找成功，输出有关信息：此商品价格为：4*初始化输入A，插入输入B，查询输入