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

实验四：基于二叉排序树的商品信息查询算法的设计与实现

一、试验内容

查找是数据处理的重要操作。请设计并实现基于二叉排序树的商品信息查询算法。完成信息的查询、插入、删除、查询频度的统计等功能。

二、试验目的

熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法。

三、流程图

开始输入a a==’A’Y建立头结点平衡化C==’Y’YNN调用插入函数，插入一个节点 a==’B’NY插入函数输入名称找到位置，插入平衡化 a==’C’Y进入查询函数输入名称查找商品查到输出信息没查到N储存相关信息到数组c查到查找商品删除节点没查到N删除失败 a==’D’Y进入删除函数输入名称平衡化 a==’E’NY输出数组c a==’F’Y结束N

四、源程序代码

#include #include #include #include using namespace std; struct shangpin {

int cishu,pingheng,jiage; char mingcheng[40]; shangpin *l,*r,*p; int shendu,quan; };

int max(int a,int b) {

if(a>b)return(a); else return(b); };

shangpin *charu(shangpin *p) {

shangpin *p1,*l,*r; char a[40]; int b=0;

cout<<\请输入商品名称：\ cin>>a;

err:b=strcmp(a,p->mingcheng); if(b==0){

cout<<\此商品已有。\ return(NULL); }

else if(b==-1){

if(p->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<<\请输入此商品的价格：\ cin>>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<<\请输入此商品的价格：\ cin>>p1->jiage; return(p->r); }

else {r=p->r;p=r;goto err;}; }; };

void chushi(shangpin *p) {

cout<<\建立初始节点：\请输入商品名称：\ cin>>p->mingcheng;

cout<<\请输入此商品价格：\ cin>>p->jiage;

cout<<\请输入访问次数：\ cin>>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<<\查找成功，输出有关信息：\ p->cishu=p->cishu+1;

cout<<\此商品价格为：\ return(1); }

else if(b==-1){ p=p->l;

if(p==NULL){

cout<<\没有此商品，查找失败！！\ return(0); }

else goto err3; }

else {

p=p->r;

if(p==NULL){

cout<<\没有此商品，查找失败！！\ return(0); }

else goto err3; } };

int shanchu(shangpin *p) {

shangpin *p1; char a[40]; int b;

cout<<\请输入要删除的商品的名称：\ cin>>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<<\删除成功。\ return(1); }

else if(b==-1){ p=p->l;

if(p==NULL){

cout<<\没有此商品，删除失败！！\ return(0); }

else goto err2; }

else {

p=p->r;

if(p==NULL){

cout<<\没有此商品，删除失败！！\ return(0); }

else goto err2; }; };

int bianlishendu(shangpin *p3) {

int a=0;

shangpin *p1,*l,*r,*p;p=p3; if(p->l==NULL&&p->r==NULL){ cout<<\只有一头节点！！！\ return(0); };

本文来源：https://www.bwwdw.com/article/tvnv.html