空间数据结构基础设计报告.doc

1、空间数据结构设计空间数据结构基础课程实习报告（地信12级）姓名 朱红鑫 班级 地信12-2 学号 07122960 环境与测绘学院目 录实验一：C+面向对象程序设计基础.2实验三：通讯簿管理（顺序表的应用）.6实验五：将中缀表达式转换为后缀表达式.13实验七：二叉树的操作.18实验九：字符串.241 C+面向对象程序设计基础【实验简介】学会用算法语言C+描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C+描述数据结构的基本方法，即通过建立类来描述抽象数据类

2、型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。【实验内容】1. 定义三维空间的坐标点TPoint2. 描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输出空间坐标等）。【主要代码】#include#includeclass TPoint protected:double x; /虚拟类型的水平坐标值double y; /虚拟类型的垂直坐标值double z; /z坐标public: TPoint()x = 0; y = 0; z = 0; /缺省构造函数TPoint(double px, double py,double

3、pz)x = px;y = py;z=pz; /带参数的构造函数void move(double mx,double my,double mz)x = mx;y = my;z=mz; /移动位置(修改坐标值)void show()coutx=x y=y z=zendl;/输出坐标值double getx()return x; /取xdouble gety()return y;/取ydouble getz()return z;/取z;#define PI 3.141592653class TBall:public TPointdouble r; /定义球半径public:TBall()x=0;y

4、=0;z=0;r=0; /缺省的构造函数TBall(double mx,double my,double mz,double mr)x=mx;y=my;z=mz;r=mr;/有参数的构造函数TBall(TPoint &p):TPoint(p)r=1;/用点来决定球心位置，半径默认为1double set(double sx,double sy,double sz)x=sx;y=sy;z=sz;/重置球心的坐标double area()return 4*PI*r*r; /计算球体表面积double volume()return 4/3*PI*r*r*r;/计算球体体积void show(); /

5、输出球心坐标double distance(TPoint &a,TPoint &b);/计算两点的距离或者球心与点、球心与球心之间的距离void judge(TBall &ma,TPoint &pb);/判断一点与一球的位置关系;void TBall:show()coutx=xty=ytz=zendl;/输出球心的坐标coutr=rendl;/输出半径coutarea=area()endl;/输出表面积coutvolume=volume()ma.r)cout该点在球外面endl;else if(distance(ma,pb)=ma.r)cout该点在球面上endl;elsecout该点在球内e

6、ndl;void main()TBall a;/调用缺省的函数couta球的基本参数为：endl;a.show();/调用show函数TBall b(15,25,36,2);coutb球的基本参数为：endl;b.show();TPoint c(15,25,37.5); /创建点c coutc点的基本参数为：endl;c.show();TBall d(c);/调用TBall(TPoint &p)函数coutd球的基本参数为：endl;d.show();TBall e;coutbd两球心的距离：e.distance(b,d)endl;/b、d两球心的距离coutc点与b球的位置关系为：;TBal

7、l f;f.judge(b,c);【实验过程】1、 首先对三维点的定义，包括缺省和有参数的构造函数；2、 之后对球的定义，因为是继承的所以只把半径作为数据成员，包括对球缺省和有参数的构造函数，另一个为点创建的球定义（半径默认为r=1）；3、 对两点的距离求解的实现，也是球心与球心或者点的距离的求解4、 对点与球的位置判断，利用点与球心的距离与半径的比较来得到，编制实现函数,之后就是main函数的实现。【实验结果】【实验体会】通过本次实验，我了解到类的基本概念。类中分公有成员和私有成员。私有成员需在公有成员中对其操作。掌握了模板类的基本用法。对点的定义是重要的，对点的取值操作在后面的使用很重要，

8、公有继承等操作不能取父类的私有成员。对球的操作也应该包括以点创建球心赋初值，这对构造球有更加方便的作用，对程序的调试更加方便。程序的实现对返回的类型也有很大的影响，所以要正确的选用返回类型。3通讯簿管理（顺序表的应用）【问题描述】通讯簿是一个线性表，可以存储一定数量的联系人记录，提供查找、插入、删除和修改等操作。通讯簿的特点是以查找为主要操作，要求快速查找到指定对象的位置，故宜采用具有随机访问功能的顺序表。【数据结构】使用顺序表SeqList建立通讯簿。作为表项的联系人记录，至少应包括以下属性： 序号，姓名，与本人关系，电话号码其中序号具有唯一性。序号和姓名可作为查找的主要关键字。与本人关系可

9、枚举为“亲人”、“朋友”和“同事”，主要作用是为联系人分组，并作为次要关键字。将上述联系人记录定义为一个结构（struct），在主程序中建立模板类顺序表SeqList的对象时用该结构实例化表结点的类型。【主要功能】程序应为用户提供操作选择界面，必要的操作包括：查找某人电话号码，添加新记录，修改记录，删除记录，打印亲人清单、朋友清单或同事清单以及退出等。另外，为初始化方便，原始数据可存储在磁盘文件中。【主要代码】#include#include#includestatic n=1;enum RelationFriends,Familiers,Colleague;templatestruct Pe

10、rson char Num10;/编号 char PhoNum12;/电话号码 char Name20;/姓名 int m;/关系 Person( int &ite) m=ite;Person(int &p1,char Name,char P, char item) for(int i=0;i20;i+) Namei=Namei; for(int j=0;j11;j+)PhoNumj=Pj; for(int k=0;k10;k+) Numk=itemk; m=p1; ;templateclass SeqListprotected: Person *data;public: SeqList(T&

11、 x)data=new Person(x); bool Input(); void Output(); void Insert(); void Search(); void Show_All(); void Delete(); void Correct(); void Show_Select(); void Show_Friends(); void Show_Familiers(); void Show_Colleague();template bool SeqList:Input() static l;coutdatal.Num;coutdatal.Name;coutdatal.PhoNum

12、;coutdatal.m; l+; n+; return true;template void SeqList:Insert() this-Input(); cout信息已保存好！endl; template void SeqList:Search() char pr20; coutpr; bool flag=1; for(int li=0;lin-1;li+) if(IfEqual(pr,datali.Name)|IfEqual(pr,datali.Num) cout序号：datali.Numtt姓名：datali.Namet电话：; for(int k=0;datali.PhoNumk!=

13、0;k+) coutdatali.PhoNumk; coutt;Switch(datali.m);flag=0; if(flag) cout查找失败!请查证后再试!endl;template void SeqList:Show_All() cout所有人的信息如下：endl; for(int lm=0;lmn-1;lm+) cout序号：datalm.Numtt姓名：datalm.Namet电话：; for(int k=0;datalm.PhoNumk!=0;k+) coutdatalm.PhoNumk; coutt; Switch(datalm.m); template void SeqLi

14、st:Show_Select()coutm;switch(m)case 1:Show_Familiers();break; case 2:Show_Friends();break; case 3:Show_Colleague();break;case 4:Search();break; default: cout关系设置错误！;break;template void SeqList:Show_Friends() cout所有朋友的信息如下：endl; for(int lm=0;lmn-1;lm+) if(datalm.m=0) cout序号：datalm.Numtt姓名：datalm.Name

15、t电话：; for(int k=0;datalm.PhoNumk!=0;k+) coutdatalm.PhoNumk; coutt;Switch(datalm.m); template void SeqList:Show_Familiers() cout所有亲人的信息如下：endl; for(int lmm=0;lmmn-1;lmm+) if(datalmm.m=1) cout序号：datalmm.Numtt姓名：datalmm.Namet电话：; for(int k=0;datalmm.PhoNumk!=0;k+) coutdatalmm.PhoNumk; coutt; Switch(dat

16、almm.m); template void SeqList:Show_Colleague() cout所有同事的信息如下：endl;for(int lmp=0;lmpn-1;lmp+) if(datalmp.m=2) cout序号：datalmp.Numtt姓名：datalmp.Namet电话：; for(int k=0;datalmp.PhoNumk!=0;k+) coutdatalmp.PhoNumk; coutt; Switch(datalmp.m); template void SeqList:Correct() char ptk20; coutptk; bool flag=1; f

17、or(int lp=0;lpn-1;lp+)if(IfEqual(ptk,datalp.Name)|IfEqual(ptk,datalp.Num) coutdatalp.Num; coutdatalp.Name; coutdatalp.PhoNum; coutdatalp.m; flag=0; if(flag) cout您要修改的联系人不存在！endl;template void SeqList:Delete() char ptr20; coutptr;bool flag=1; for(int lr=0;lrn-1;lr+)if(IfEqual(ptr,datalr.Name)|IfEqual

18、(ptr,datalr.Num) strcpy(datalr.Num,datan-2.Num);strcpy(datalr.Name,datan-2.Name); strcpy(datalr.PhoNum,datan-2.PhoNum); datalr.m=datan-2.m; n-; cout信息已删除！endl; flag=0; if(flag) cout删除失败！endl; void Switch(int i)switch(i)case 1: cout亲人tendl;break;case 2: cout朋友tendl;break; case 3: cout同事tendl;break;de

19、fault: cout关系设置错误！;break;int IfEqual(char p1,char p2)int flag=strcmp(p1,p2);return flag; void Menu() couttt endltt endltt 我的通迅录 endl tt endltt 1. 添加新联系人. 4. 修改信息. endl tt endltt 2. 删除联系人. 5. 查询联系人. endltt endltt 3. 显示所有联系人. 6. 关闭通讯簿. endl tt endltt endl;void main()cout_ 欢迎使用通讯簿!endl; char ptr20;cout

20、ptr; int flag=strcmp(ptr,朱红鑫); if(flag=0)cout通过验证!endl; else cout#_# 对不起，您无访问权限! endl; exit(1); bool flag1=0; Menu(); int x=0; SeqList hyb(x); while (1) coutn; switch (n) case 1: hyb.Insert();break;/添加联系人 case 2: hyb.Delete();break;/删除联系人 case 3: hyb.Show_All();break;/显示所有联系人 case 4: hyb.Correct();b

21、reak;/修改联系人信息 case 5: hyb.Show_Select();break;/选择查询联系人 case 6: cout tt安全退出 endl; flag1=1; break; default: break; if(flag1) break; 【实验过程】【实验体会】Switch开关语句用得比较多，写完后想想应该给通讯簿加把锁，查资料才搞清楚包含在stdlib.h中的exit(1)可以判断后直接退出程序。以前一直以为exit(1)可有可无，现在在实际应用中才理解了它的意思。看来课本上的内容还是蛮有用的。程序还存在一些缺陷。5将中缀表达式转换为后缀表达式【问题描述】表达式转换。输

22、入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。例如： a*(x+y)/(b-x) 转换后得： a x y + * b x - /【数据结构】l 定义一个暂时存放运算符的转换工作栈opst。l 中缀表达式字符串char *infix;l 后缀表达式字符串char *postfix;【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：l 数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；l 左括号，进栈，直到遇见相配的右括号，才出栈；l 右括号，表明已扫描过括号内的中缀表达式，把

23、从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；l 对于运算符，分两种情况处理：u 该运算符的优先级大于栈顶符号的优先级，则入栈；u 若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。说明：自行设计运算符优先级的表示。【主要代码】#include #include const int stackIncreament=20; class SeqStack private: char *elements; int top; int maxSize; void overflowPr

24、ocess();public: SeqStack(int sz=50); SeqStack() delete elements; void Push(const char &x); /入栈 bool Pop(char &x); /出栈 bool getTop(char &x); /取头 int isdigit(char ch); int isp(char ch1); int icp(char ch2); bool IsEmpty() const /判断是否为空 return (top = -1)? true:false; bool IsFull() const /判断是否已经满 return

25、(top = maxSize-1)? true:false; int getSize() const return top+1; /长度 void MakeEmpty() top= -1; ;SeqStack:SeqStack(int sz) top = -1; maxSize = sz; elements = new charmaxSize; assert(elements!=NULL); void SeqStack:overflowProcess() char*newArray=new charmaxSize+stackIncreament; for (int i = 0; i =0&ch

26、=a&ch=A&ch=Z)return 1;elsereturn 0;int SeqStack:isp(char ch1) int val;switch(ch1)case #: val=0; break; case (:val=1;break;case *:case /:case %:val=5;break;case +: case -: val=3; break;case ): val=6; break;return val;int SeqStack:icp(char ch2) int val;switch(ch2)case #: val=0; break;case (: val=6; br

27、eak;case *: case /: case %: val=4; break;case +: case -: val=2; break;case ): val=1; break;return val;class Show:public SeqStack public: Show(int sz):opst(sz) void Clear();void Postfix();void Input();void Output(); private: SeqStack opst; char *infix; char *postfix;void Show:Clear()opst.MakeEmpty();

28、void Show:Input() infix=new char20;cout请输入中缀表达式:infix;void Show:Postfix() postfix=new char20;cout输出的后缀表达式为:endl;SeqStack opst;char ch=#,ch1,op;opst.Push(ch);int i=0;ch=infixi;while(opst.IsEmpty()=false&ch!=#)if(opst.isdigit(ch)=1) coutch; i+;ch=infixi;else cout ;opst.getTop(ch1);if(opst.isp(ch1)opst

29、.icp(ch)opst.Pop(op); if(op!=#)coutop; elseopst.Pop(op);i+;ch=infixi; coutendl;void main() Show a(100); a.Input();a.Postfix();【实验过程】1.首先将一个左括号（进栈，作为栈底元素；2.接着从左到右对算数表达式进行扫描，每次读一个字符，若遇到左括号（，则进栈；若遇到的是操作数，则立即输出； 3.若又遇到运算符，如果他的优先级比栈顶元素的优先级高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级比他低的时候，将他压栈； 4.若遇到的是右括号），则将栈顶的运算符输出

30、，知道栈顶的元素为（，谈后，左右括号互相抵消； 5.如果最终，我们要扫描的表达式结束，就将栈中的运算符全部输出，消除栈底的左括号（【实验结果】【实验体会】中缀转后缀的实验，让我深入了解栈的创建并且掌握了关于运算符优先级的相关制定方法，熟悉栈的后进先出的性质。在实验的过程中，虽然有很多自己尚未理解的补分，但通过查询交流我很快就找到了解决的办法，所以编程贵在坚持！7二叉树的操作【实验简介】二叉树是树形结构的一种重要类型。通过本次实验，熟悉二叉树结点的结构，掌握二叉树的基本操作以及具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。【实验内容】 编写程序，实现对二叉树的以下操作：1

31、 建立二叉树。2 按任一种遍历次序输出二叉树中的所有结点。3 求二叉树的深度。4 求二叉树中的所有节点数。5 求二叉树中的所有叶子节点数。6 清除二叉树，使之编程一只空树。【主要代码】#include#includetemplate struct bintreenode/二叉树结点类定义 T data; /数据域 bintreenode *leftchild, *rightchild; /左子女、右子女链域 bintreenode () /构造函数 leftchild = NULL; rightchild = NULL; bintreenode (T x, bintreenode *left = NULL, bintreenode *right = NULL) data = x; leftchild = left; rightchild = right; ;template class binarytree /二叉树类定义 public: binarytree () root=NULL; /构造函数 binarytree (T value)