数据结构课程设计

环境与测绘学院1C++面向对象程序设计基础【实验简介】学会用算法语言C++描述抽象数据类型。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。【实验内容】1.定义三维空间的坐标点TPoint2.描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输出空间坐标等）。3.实现功能：输入一点，判断它与球的位置关系。【主要代码】#includeiostream.h#definePI3.141592653classTPoint{//空间坐标点类protected:doublex,y,z;public://TPoint(){x=0;y=0;z=0;}//构造函数TPoint(doublepx,doublepy,doublepz){x=px;y=py;z=pz;}//带参数的构造函数doubleGetx(){returnx;}//返回坐标点的x值doubleGety(){returny;}//返回坐标点的y值doubleGetz(){returnz;}//返回坐标点的z值voidMove(doublemx,doublemy,doublemz){x=mx;y=my;z=mz;};};//移动坐标点的位置classTball:publicTPoint{doubler;public://Tball(){r=0;x=0;y=0;z=0;}//构造函数Tball(doublea,doubleb,doublec,doubled):TPoint(a,b,c){r=d;}//带参数的构造函数Tball(TPoint&pn):TPoint(pn){r=1;}doubleA(){return4*PI*r*r;}//计算球的面积doubleV(){return4.0/3.0*PI*r*r*r;}//计算球的体积intPosition(TPoint&pt);//判断点pt相对于球的位置voidJudge(TPoint&pt);//判断点pt相对于球的位置voidShow();//输出球的各属性值};intTball::Position(TPoint&pt)//求点pt相对于球的位置{doublet,s;t=(pt.Getx()-x)*(pt.Getx()-x)+(pt.Gety()-y)*(pt.Gety()-y)+(pt.Getz()-z)*(pt.Getz()-z);s=r*r;if(ts)return1;//点在球外elseif(ts)return-1;//点在球内elsereturn0;//点在球上}voidTball::Judge(TPoint&pt){switch(Position(pt)){case-1:cout此点在球内endl;break;case0:cout此点在球面上endl;break;case1:cout点此在球外endl;break;}}voidTball::Show()//输出球的各属性值{coutx=x'\t'y=y'\t'z=z'\t';cout球的半径=r'\t';cout球的表面积=A()'\t';cout球的体积=V()endl;}voidmain(){intx,y,z,R,x0,y0,z0;cout输入球心坐标(x,y,z)，以及球的半径Rendl;cinxyz;cout输入半径R：;cinR;TballA(x,y,z,R);//定义一个球类对象A.Show();//输出球的属性值cout输入空间一点的坐标(x0,y0,z0)endl;cinx0y0z0;TPointp(x0,y0,z0);//定义一个Point类对象cout点和球的位置关系为:;A.Judge(p);}【实验过程】【实验体会】本题要求学会用算法语言C++描述抽象数据类型，属于一道比较简单的题目，对继承又有了进一步的了解。通过本题的训练，使C++面向对象的编程的基础知识得到了巩固和复习，对面向对象编程的思想有了更加深刻的认识，为以后更复杂的问题的解决奠定了必要的基础。上机练习4将中缀表达式转换为后缀表达式【问题描述】表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。例如：a*(x+y)/(b-x)转换后得：axy+*bx-/【数据结构】定义一个暂时存放运算符的转换工作栈opst。中缀表达式字符串char*infix;后缀表达式字符串char*postfix;【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；左括号，进栈，直到遇见相配的右括号，才出栈；右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；对于运算符，分两种情况处理：该运算符的优先级大于栈顶符号的优先级，则入栈；若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。说明：自行设计运算符优先级的表示。【主要代码】#includeassert.h#includeiostreamusingnamespacestd;constintstackIncreament=20;//栈溢出时扩展空间的增量templateclassTclassSeqStack//顺序栈的类定义{public:SeqStack(intsz=50);//构造函数，建立一个空栈~SeqStack(){delete[]elements;}//析构函数voidPush(constT&x);//如果IsFull(),则溢出处理；否则把x插入到栈顶boolPop(T&x);//如果IsEmpty(),则不执行退栈，返回false;否则退掉位于栈顶的元素，返回trueboolgetTop(T&x);boolIsEmpty()const{return(top==-1)?true:false;}boolIsFull()const{return(top==maxSize-1)?true:false;}intgetSize()const{returntop+1;}//函数返回栈中元素个数voidMakeEmpty(){top=-1;}//清空栈中的内容friendostream&operator(ostream&os,SeqStackT&s);//输出栈中元素的重载操作private:T*elements;inttop;intmaxSize;voidoverflowProcess();//栈的溢出处理};templateclassTSeqStackT::SeqStack(intsz):top(-1),maxSize(sz)//建立一个最大尺寸为sz的空栈，若分配不成功则错误处理{elements=newT[maxSize];//创建栈的数组空间assert(elements!=NULL);//断言：动态存储分配是否成功};templateclassTvoidSeqStackT::overflowProcess(){T*newArray=newT[maxSize+stackIncreament];if(newArray=NULL){cerr储存分配失败endl;exit(1);}for(inti=0;i=top;i++)newArray[i]=elements[i];maxSize=maxSize+stackIncreament;delete[]elements;elements=newArray;};templateclassTvoidSeqStackT::Push(constT&x)//公共函数：若栈不满，则将元素x插入到该栈的栈顶，否则溢出处理{if(top==maxSize-1)overflowProcess();//栈满则溢出处理elements[++top]=x;//栈顶指针先加1再进栈};templateclassTboolSeqStackT::Pop(T&x){if(top==-1)returnfalse;x=elements[top--];returntrue;};templateclassTboolSeqStackT::getTop(T&x){if(top==-1)returnfalse;x=elements[top];returntrue;};templateclassTostream&operator(ostream&os,SeqStackT&s){ostop=s.topendl;//输出栈顶位置for(inti=0;i=s.top;i++)//逐个输出栈中元素的值osi:s.elements[i]endl;returnos;};intisdigit(charch){switch(ch){case'+':case'-':case'*':case'/':case'(':case')':return0;break;default:return1;break;}}intisp(charch)//栈中优先数{switch(ch){case'#':return0;break;case'(':return1;break;case'*':return5;break;case'/':return5;break;case'%':return5;break;case'+':return3;break;case'-':return3;break;case')':return6;break;default:break;}}inticp(charch)//栈外优先数{switch(ch){case'#':return0;break;case'(':return6;break;case'*':return4;break;case'/':return6;break;case'%':return4;break;case'+':return2;break;case'-':return2;break;case')':return1;break;default:break;}}voidpostfix(SeqStackchar&s){//定义栈的对象为s，其元素为字符charch='#',ch1,op;s.Push(ch);cin.get(ch);//栈底放入一个#，读入一个字符cout后缀表达式为:endl;while(s.IsEmpty()==false&&ch!='#')//连续处理if(isdigit(ch)){coutch;cin.get(ch);}//是操作数，输出之else{s.getTop(ch1);//取栈顶操作符ch1if(isp(ch1)icp(ch))//新输入操作符优先级高{s.Push(ch);cin.get(ch);}//进栈读入下一字符elseif(isp(ch1)icp(ch))//新输入操作符优先级低{s.Pop(op);coutop;}//退栈并输出else{s.Pop(op);//输入操作符优先级等于栈顶优先级if(op=='(')cin.get(ch);}}s.Pop(op);coutop;};voidmain(){SeqStackcharinfix;//定义顺序栈的对象中缀表达式cout输入中缀表