数据结构课程设计实验报告.doc

空间数据结构基础课程实习报告（测绘10级）姓名 班级 学号 环境与测绘学院1 C+面向对象程序设计基础【实验简介】学会用算法语言C+描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C+描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。【实验内容】1. 定义三维空间的坐标点TPoint2. 描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输出空间坐标等）。【主要代码】头文件：TPoint.h:#ifndef TPOINT_H#define TPOINT_H#includeusing namespace std;class TPointpublic:TPoint(double xx,double yy,double zz):x(xx),y(yy),z(zz)TPoint(TPoint &TP):x(TP.x),y(TP.y),z(TP.z)double getX()constreturn x;/取x坐标值double getY()constreturn y;/取y坐标值double getZ()constreturn z;/取z坐标值void DisplayTP() const cout(x,y,z)endl;/显示点的三坐标void Move(double Mx,double My,double Mz);/移动点的坐标private:double x,y,z;/点的三坐标;#endifTBall.h#ifndef TBALL_H#define TBALL_H#include TPoint.hconst double PI = 3.14159;class TBallpublic:TBall(TPoint SC,double R):sphCtr(SC),r(R)/构造函数TBall(TBall &TB):sphCtr(TB.sphCtr),r(TB.r)double getSurfArea()const;/计算球的表面积double getVolume()const;/计算球的体积TPoint getSphctr()return sphCtr;double getRadius()constreturn r;/取球的半径void Move(double Mx,double My,double Mz)sphCtr.Move(Mx,My,Mz);/在空间坐标系内移动球void ChangR(double newR)r = newR;void DisBallInfo()const;/显示球体的基本信息private:TPoint sphCtr;/球心坐标double r;/球的半径;#endif源文件：Define.cpp:#include #include TBall.husing namespace std;/TPoint/void TPoint:Move(double Mx,double My,double Mz)/移动点的坐标x += Mx;y += My;z += Mz;/TBall/double TBall:getSurfArea()const/计算球的表面积return 4*PI*r*r;double TBall:getVolume()const/计算球的体积return (4.0/3)*PI*r*r*r;void TBall:DisBallInfo()const/显示球体的基本信息coutINFORMATION OF THIS BALL: endl;couttSPHERICAL CENTRE: ;sphCtr.DisplayTP();couttRADIUS: rendl;couttSURFACE AREA: getSurfArea()endl;couttVOLUME: getVolume()endl;Main.cpp:#include#include TBall.h#includeTPoint.husing namespace std;void main()TPoint TP1(1,3,2);TBall TB1(TP1,7);TP1.DisplayTP();TB1.DisBallInfo();TB1.Move(3,2,5);TB1.ChangR(22);TB1.DisBallInfo();【实验过程】设计好点类和球类的相关属性和操作后，打开C+编译环境，建立两个空的头文件，分别输入点类和球类的声明代码。然后新建一个源文件，输入点类和球类的函数体实现代码。最后新建主文件，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。【实验体会】初步了解了面向对象的编程方式，体会到了函数声明与实现分离的安全性。2 链表的建立、合并与拆分【实验简介】链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。1. 设线性链表A=(a1,a2,am),，B=(b1,b2,bm)，按下列规则合并A，B为线性表C的算法，即使得 C = (a1,b1,am,bm, b (m+1),bn) 当mnC表利用A表和B表中的结点空间构成。2. 将C表原地逆置。3. 将C表的中偶数和奇数分别链接为两个循环链表D和E。说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】单链表头文件：LinkedList.h#ifndef LINKEDLIST_H#define LINKEDLIST_H#include #include LinkNode.htemplateclass LinkedListpublic:LinkedList()first = new LinkNode;/默认构造函数LinkedList(const T &x)first = new LinkNode(x);/带形参的构造函数LinkedList(LinkedList &L);/复制构造函数LinkedList()makeEmpty();/析构函数void makeEmpty();/将表置空int Length()const;/求表长度LinkNode *getHead()const return first;/取表头结点指针LinkNode *Search(T x);/搜索数据域为x的结点LinkNode *Locate(int i)const;/取i号表项的地址bool getData(int i,T &x)const;/取i号表项的数据void setData(int i,T &x);/用x修改第i个元素的值bool Insert(int i,T &x);/在第i个元素后插入xbool Remove(int i,T &x);/删除第i个元素，x返回该元素的值bool IsEmpty()const/判断表空否，空则返回truereturn first-link=NULL?true:false;void Output();/输出void Turn();/将单链表的指向倒转void Combine(LinkedList &A,LinkedList &B);/将两个单链表合并void Divide(LinkedList &D,LinkedList &E);protected:LinkNode *first;template/复制构造函数实现LinkedList:LinkedList(LinkedList &L)T value;LinkNode *srcptr = L.getHead();LinkNode *destptr = first = new LinkNode;while (srcptr-link!=NULL)value = srcptr-link-data;destptr-link = new LinkNode(value);srcptr = srcptr-link;destptr = destptr-link;destptr-link = NULL;template/置空函数实现void LinkedList:makeEmpty()LinkNode *p;while (first-link!=NULL)p = first-link;first-link = p-link;delete p;template/求长函数实现int LinkedList:Length()constLinkNode *p = first-link;int count = 0;while (p!=NULL)p = p-link;count+;return count;template/搜索函数实现LinkNode *LinkedList:Search(T x)LinkNode *current = first-link;while (current!=NULL)if (current-data=x)break;elsecurrent = current-link;return current;template/定位函数实现LinkNode *LinkedList:Locate(int i)constif (i0)return NULL;LinkNode *current = first;int k = 0;while (current!=NULL&klink;k+;return current;template/取值函数实现bool LinkedList:getData(int i,T &x)constif (i=0)return NULL;LinkNode *current = Locate(i);if (current=NULL)return false;elsex = current-data;return true;template/修改函数实现void LinkedList:setData(int i,T &x)if (i=0)return;LinkNode *current = Locate(i);if (current=NULL)return;elsecurrent-data = x;template/插入函数实现bool LinkedList:Insert(int i,T &x)LinkNode *current = Locate(i);if (current=NULL)return false;LinkNode *newNode = new LinkNode(x);newNode-link = current-link;current-link = newNode;return true;template/删除函数实现bool LinkedList:Remove(int i,T &x)LinkNode *current = Locate(i-1);if (current=NULL|current-link=NULL)return false;LinkNode *del = current-link;x = del-data;delete del;return true;template/输出函数实现void LinkedList:Output()LinkNode *current = first-link;while (current!=NULL)coutdatalink;coutendl;template/倒置函数实现void LinkedList:Turn()if (first-link=NULL)return;LinkNode *current1 = first-link,*current2 = first-link-link;LinkNode *p;while(p!=NULL)p = current2-link;current2-link = current1;current1 = current2;current2 = p;first-link-link = NULL;/让倒置后的最后一个结点的指针域为空first-link = current1;/让附加的表头结点的指针域指向第一个结点templatevoid LinkedList:Combine(LinkedList &A,LinkedList &B)/合并函数T value1,value2;LinkNode *srcptr1 = A.getHead();LinkNode *srcptr2 = B.getHead();LinkNode *destptr = first = new LinkNode;if (A.Length()link!=NULL)value1 = srcptr1-link-data;value2 = srcptr2-link-data;destptr-link = new LinkNode(value1);srcptr1 = srcptr1-link;destptr = destptr-link;destptr-link = new LinkNode(value2);srcptr2 = srcptr2-link;destptr = destptr-link;while (srcptr2-link!=NULL)value2 = srcptr2-link-data;destptr-link = new LinkNode(value2);srcptr2 = srcptr2-link;destptr = destptr-link;destptr-link = NULL;if (A.Length()=B.Length()while (srcptr2-link!=NULL)value1 = srcptr1-link-data;value2 = srcptr2-link-data;destptr-link = new LinkNode(value1);srcptr1 = srcptr1-link;destptr = destptr-link;destptr-link = new LinkNode(value2);srcptr2 = srcptr2-link;destptr = destptr-link;destptr-link = NULL;if (A.Length()B.Length()while (srcptr2-link!=NULL)value1 = srcptr1-link-data;value2 = srcptr2-link-data;destptr-link = new LinkNode(value1);srcptr1 = srcptr1-link;destptr = destptr-link;destptr-link = new LinkNode(value2);srcptr2 = srcptr2-link;destptr = destptr-link;while (srcptr1-link!=NULL)value1 = srcptr1-link-data;destptr-link = new LinkNode(value1);srcptr2 = srcptr2-link;destptr = destptr-link;destptr-link = NULL;templatevoid LinkedList:Divide(LinkedList &D,LinkedList &E)T value;LinkNode *srcptr = this-getHead();LinkNode *destptr1 = D.first = new LinkNode;LinkNode *destptr2 = E.first = new LinkNode;while (srcptr-link!=NULL&srcptr-link-link!=NULL)value = srcptr-link-data;destptr1-link = new LinkNode(value);srcptr = srcptr-link-link;destptr1 = destptr1-link;destptr1-link = NULL;srcptr = this-getHead();srcptr = srcptr-link;while (srcptr-link!=NULL&srcptr-link-link!=NULL)value = srcptr-link-data;destptr2-link = new LinkNode(value);srcptr = srcptr-link-link;destptr2 = destptr2-link;destptr1-link = NULL;#endif节点头文件：LinkNode.h：#ifndef LINKNODE_H#define LINKNODE_H#include templatestruct LinkNodeT data;/数据域LinkNode *link;/指针域LinkNode(LinkNode *ptr = NULL)link = ptr;/仅有指针域形参的构造函数LinkNode(const T &item,LinkNode *ptr = NULL)/构造函数data = item;link = ptr;#endif主函数源文件：Main.cpp:#include #include LinkedList.h#include LinkNode.hvoid main()LinkedList List1,List2,List3,List4,List5;int a = 1,2,3,4,5,6,7,8,9,10;int b = 1,2,3,4,5,6,7,8,9,10,11,12;for (int i = 0;i10;i+)List1.Insert(i,bi);for (int j = 0;j12;j+)List2.Insert(j,bj);cout逆转前：endl;coutList1: ;List1.Output();coutList2: ;List2.Output();coutList3为List1与List2的合并链表。endl;List3.Combine(List1,List2);coutList3: ; List3.Output();cout将List3逆转后：endl;List3.Turn();coutList3: ;List3.Output();cout将List3拆分后：endl;List3.Divide(List4,List5);coutList4: ;List4.Output();coutList5: ;List5.Output();【实验过程】设计好单链表的建立、拆分、合并、转置代码后，打开C+编译环境，建立两个空的头文件，分别输入节点类和链表类的声明代码及实现代码。然后新建主文件，对两个类的构造函数、复制构造函数以及合并，转置函数等进行调试，最后进行评估。【实验体会】转置算法为利用3个指针的经典算法，需要记牢。合并与拆分算法总体都是建立在复制函数算法的基础上。经过这次实验，对单链表的性质有了更深刻的体会。5 将中缀表达式转换为后缀表达式【问题描述】表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。例如： a*(x+y)/(b-x) 转换后得： a x y + * b x - /【数据结构】l 定义一个暂时存放运算符的转换工作栈opst。l 中缀表达式字符串char *infix;l 后缀表达式字符串char *postfix;【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：l 数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；l 左括号，进栈，直到遇见相配的右括号，才出栈；l 右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；l 对于运算符，分两种情况处理：u 该运算符的优先级大于栈顶符号的优先级，则入栈；u 若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。说明：自行设计运算符优先级的表示。【主要代码】链式栈头文件：LinkedStack.h:#ifndef LINKEDSTACK_H#define LINKEDSTACK_H#include#includeLinkNode.h#includeusing namespace std;templateclass LinkedStackpublic:LinkedStack():top(NULL)LinkedStack()if (IsEmpty()=false)makeEmpty();void Push(const T &x);bool Pop(T &x);bool getTop(T &x)const;bool IsEmpty()const return (top=NULL)?true:false;void makeEmpty();private:LinkNode *top;templatevoid LinkedStack:makeEmpty()LinkNode *p;p = top;top = top-link;delete p;templatevoid LinkedStack:Push(const T &x)top = new LinkNode(x,top);assert(top !=NULL);templatebool LinkedStack:Pop(T &x)if(IsEmpty()=true)return false;LinkNode *p = top;top = top-link;x = p-data;delete p;return true;templatebool LinkedStack:getTop(T &x)constif(IsEmpty()=true)return false;x = top-data;return true;#end