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

1、空间数据结构基础课程实习报告（测绘10级）姓名班级 学号环境与测绘学院1 C+ 面向对象程序设计基础【实验简介】 学会用算法语言 C+ 描述抽象数据类型，使用模板建立数据结构。理解数据 结构的组成分为两部分， 第一部分是数据集 （数据元素） ，第二部分是在此数据集上的操作。 从面向对象的观点看， 这两部分代表了对象的属性和方法。 掌握用 C+ 描述数据结构的基本 方法，即通过建立类来描述抽象数据类型。 类的数据成员提供对象属性， 成员函数 提供操作 方法，方法是公共接口，用 户通过调用方法实现对 属性的访问。【实验内容】1. 定义三维空间的坐标点 TPoint2. 描述三维空间的球 TBall

2、 ，实现其主要操作（如计算体积和表面积，输出空间坐标 等）。【主要代码】 头文件：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()co nstretum x;/ 取 x 坐标值double getY()co nstretum y;/ 取 y 坐标值d

3、ouble getZ()co nstretum 乙取 z 坐标值void DisplayTP() const cout(x,y,z)endl;/ 显示点 的三坐标void Move(double Mx,double My,double Mz);/ 移动点的坐标private:double x,yz;/点的三坐标;#endifTBall.h #ifndef TBALL_H#define TBALL_H#include TPoint.h const double PI = 3.14159;class TBallpublic:TBall(TPoint SC,double R):sphCtr(SC),

4、r(R)/ 构造函数TBall(TBall &TB):sphCtr(TB.sphCtr),r(TB.r)double getSurfAreaOco nst;/计算球的表面积double getV)lume()co nst;/计算球的体积TPoint getSphctr()return sphCtr;double getRadius()co nstretum r;/取 球的半径void Move(double Mx,double My,double Mz)sphCtr.Move(Mx,My ,Mz);/ 在空 间坐标系内移动球void ChangR(double newR)r = newR;vo

5、id DisBallI nfo()co nst;/显示球体的基本信息 private:TP oi nt sp hCtr;球心坐标double r;/球的半径;#endif源文件：Define.cpp: #include #include TBall.h using namespace std;/TPoint/void TP oi nt:Move(double Mx,double My ,double Mz)/ 移动点的坐标x += Mx;y += My;z += Mz;/TBall/double TBall:getSurfArea()co nst/计算球的表面积return 4*PI*r*r;

6、double TBall:getVolume()co nst/计算球的体积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: getV olume()endl;Main.cpp: #include#include TBa

7、ll.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+ 编译环境，建立两个 空的头文件， 分别输入点类和球类的声明代码。 然后新建一个源文件， 输入点类 和球类的函数体实现代码。 最后新建主文件， 对两个类的构造函数、 复制构造函 数、操作函数等进行调试，最

8、后进行评估。【实验体会】初步了解了面向对象的编程方式，体会到了函数声明与实现分离的安全性。2 链表的建立、合并与拆分【实验简介】 链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系， 链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】 定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。1. 设线性链表A=(a1,a2,am), B=(b1,b2,bm)按下列规则合并 A, B为线性表C 的算法，即使得C = (a1,b1,

9、 ,am,bm, b(m+1),bn)当 mnC 表利用 A 表和 B 表中的结点空间构成。2. 将 C 表原地逆置。3. 将 C 表的中偶数和奇数分别链接为两个循环链表 说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】 单链表头文件： LinkedList.h #ifndef LINKEDLIST_H #define LINKEDLIST_H#include #include LinkNode.h template class LinkedList public:LinkedList()first = new LinkNode; /默认构造函数LinkedList(const

10、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;/取

11、 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(LinkedLis

12、t &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 = des

13、tptr-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()const LinkNode *p = first-link; int count = 0;while (p!=NULL)p = p-link; count+;return count;template/搜索函数

14、实现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+;retu

15、rn 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;e

16、lse current-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

17、= 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

18、) return;LinkNode *current1 = first-link,*current2 = first-link-link;LinkNode *p;while(p!=NULL)current2-link = current1;current1 = current2; current2 = p;first-link-link = NULL;/ 让倒置后的最后一个结点的指针域为空 first-link = current1;/ 让附加的表头结点的指针域指向第一个结点 template/void LinkedList:Combine(LinkedList &A,LinkedList &

19、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-l

20、ink = 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-lin

21、k-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;value

22、2 = 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;

23、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)destptr1-link = new

24、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

25、;destptr1-link = NULL;#endif 节点头文件： LinkNode.h：#ifndef LINKNODE_H#define LINKNODE_H#include template struct LinkNodeT data;/数据域LinkNode *link;/指针域LinkNode(LinkNode *ptr = NULL)link = ptr; /仅有指针域形参的构造函数LinkNode(const T &item,LinkNode *ptr = NULL) /构造函数data = item; link = ptr;#endif主函数源文件： Main.cpp:#i

26、nclude #include LinkedList.h#include LinkNode.h void 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);coutvv逆转前：e ndl;coutList1: ;List1.Output();coutList2:

27、;List2.Output(); coutvvList3 为 Listi 与 List2 的合并链表。e ndl;List3.Combine(List1,List2);coutList3: ;List3.Output();coutvv将 List3 逆转后：e ndl;List3.Turn();coutvvList3: ;List3.Output();coutvv将 List3 拆分后：vve ndl;List3.Divide(List4,List5);coutvvList4: ;List4.Output();coutvvList5: ;List5.Output();【实验过程】设计好单链表的

28、建立、拆分、合并、转置代码后，打开C+编译环境，建立两个空的头文件， 分别输入节点类和链表类的声明代码及实现代码。 然后新 建主文件，对两个类的构造函数、 复制构造函数以及合并， 转置函数等进行调试， 最后进行评估。【实验体会】转置算法为利用 3个指针的经典算法，需要记牢。合并与拆分算法总体都是建立在复制 函数算法的基础上。经过这次实验，对单链表的性质有了更深刻的体会。5 将中缀表达式转换为后缀表达式【问题描述】 表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符 数组中并输出。例如： a*(x+y)/(b-x) 转换后得： a x y + * b x - / 【数据结构】op

29、st。定义一个暂时存放运算符的转换工作栈 中缀表达式字符串 char *infix; 后缀表达式字符串 char *postfix;【算法提示】 转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。 从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：数字或小数点，直接写入字符串 postfix ，并在每个数值后面写入一个空格； 左括号，进栈，直到遇见相配的右括号，才出栈； 右括号， 表明已扫描过括号内的中缀表达式， 把从栈顶直到对应左括号之间的运算 符依次退栈，并把结果推入栈内；对于运算符，分两种情况处理： 该运算符的优先级大于栈顶符号的优先级，则入栈； 若该运算符的优先级小于栈

30、顶优先级，则先弹出栈顶运算符、写入 postfix 串；继续将该 运算符与栈顶运算符比较，直到能把它推入栈内为止(即优先级大于栈顶运算符) 。说明：自行设计运算符优先级的表示。【主要代码】链式栈头文件： LinkedStack.h:#ifndef LINKEDSTACK_H#define LINKEDSTACK_H#include#includeLinkNode.h#includeusing namespace std;templateclass LinkedStackpublic:LinkedStack():top(NULL)LinkedStack()if (IsEmpty()=false)

31、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;#endif节点头文件： LinkNode.h:#ifn