2022年数据结构课程设计实验报告 .pdf

《2022年数据结构课程设计实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计实验报告 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、int 2.描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输出空间坐标等）。【主要代码】头文件：TPoint.h:#ifndef TPOINT_H#define TPOINT_H#include using namespace std;class TPoint public: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

3、 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;/点的三坐标;#endif TBall.h#ifndef TBALL_H#define TBALL_H#include TPoint.h const double PI=3.14159;class TBall 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 17 页 -p

4、ublic:TBall(TPoint SC,double R):sphCtr(SC),r(R)/构造函数TBall(TBall&TB):sphCtr(TB.sphCtr),r(TB.r)double getSurfArea()const;/计算球的表面积double getV olume()const;/计算球的体积TPoint getSphctr()return sphCtr;double getRadius()constreturn r;/取球的半径void Move(double Mx,double My,double Mz)sphCtr.Move(Mx,My,Mz);/在空间坐标系内移

5、动球void ChangR(double newR)r=newR;void DisBallInfo()const;/显示球体的基本信息private:TPoint sphCtr;/球心坐标double r;/球的半径;#endif 源文件：Define.cpp:#include#include TBall.h using namespace std;/TPoint/void TPoint:Move(double Mx,double My,double Mz)/移动点的坐标 x+=Mx;y+=My;z+=Mz;/TBall/double TBall:getSurfArea()const/计算球的

6、表面积 return 4*PI*r*r;double TBall:getVolume()const/计算球的体积 return(4.0/3)*PI*r*r*r;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 17 页 -void TBall:DisBallInfo()const/显示球体的基本信息 coutINFORMATION OF THIS BALL:endl;couttSPHERICAL CENTRE:;sphCtr.DisplayTP();couttRADIUS:rendl;couttSURFACE AREA:getSurfArea()endl;couttVOLUME:g

7、etV olume()endl;Main.cpp:#include#include TBall.h#includeTPoint.h using 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、后新建主文件，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。【实验体会】初步了解了面向对象的编程方式，体会到了函数声明与实现分离的安全性。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 17 页 -2 链表的建立、合并与拆分【实验简介】链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。1

9、.设线性链表A=(a1,a2,am),，B=(b1,b2,bm)，按下列规则合并A，B 为线性表C的算法，即使得C=(a1,b1,am,bm,b(m+1),bn)当 mn C 表利用 A 表和 B 表中的结点空间构成。2.将 C 表原地逆置。3.将 C 表的中偶数和奇数分别链接为两个循环链表D 和 E。说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】单链表头文件：LinkedList.h#ifndef LINKEDLIST_H#define LINKEDLIST_H#include#include LinkNode.h template class LinkedList publ

10、ic: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)c

11、onst;/取i号表项的地址bool getData(int i,T&x)const;/取i号表项的数据名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 17 页 -void setData(int i,T&x);/用x修改第 i个元素的值bool Insert(int i,T&x);/在第i个元素后插入 x bool Remove(int i,T&x);/删除第 i个元素，x返回该元素的值bool IsEmpty()const/判断表空否，空则返回 true return first-link=NULL?true:false;void Output();/输出void Turn(

12、);/将单链表的指向倒转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;dest

13、ptr-link=new LinkNode(value);srcptr=srcptr-link;destptr=destptr-link;destptr-link=NULL;template/置空函数实现void LinkedList:makeEmpty()LinkNode*p;while(first-link!=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -p=first-link;first-link=p-link;delete p;template/求长函数实现int LinkedList:Length()const LinkNode*p=first

14、-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;else current=current-link;return current;template/定位函数实现LinkNode*LinkedList:Locate(int i)const if(i0)return NULL;LinkNode

15、*current=first;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 17 页 -int k=0;while(current!=NULL&klink;k+;return current;template/取值函数实现bool LinkedList:getData(int i,T&x)const if(i=0)return NULL;LinkNode*current=Locate(i);if(current=NULL)return false;else x=current-data;return true;template/修改函数实现void LinkedList:set

16、Data(int i,T&x)if(i=0)return;LinkNode*current=Locate(i);if(current=NULL)return;else current-data=x;template/插入函数实现bool LinkedList:Insert(int i,T&x)LinkNode*current=Locate(i);if(current=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 17 页 -return false;LinkNode*newNode=new LinkNode(x);newNode-link=current-link;c

17、urrent-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!=NU

18、LL)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;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 17 页 -current2-link=current1;current1=current2;current2=p;first-link-link=NULL;/让倒置后的

19、最后一个结点的指针域为空first-link=current1;/让附加的表头结点的指针域指向第一个结点 template void 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-dat

20、a;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

21、(A.Length()=B.Length()while(srcptr2-link!=NULL)value1=srcptr1-link-data;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 17 页 -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=

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

23、data;destptr-link=new LinkNode(value1);srcptr2=srcptr2-link;destptr=destptr-link;destptr-link=NULL;template void 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&sr

24、cptr-link-link!=NULL)value=srcptr-link-data;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 17 页 -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;destptr

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

26、NULL)/构造函数 data=item;link=ptr;#endif 主函数源文件：Main.cpp:#include#include LinkedList.h#include LinkNode.h void main()名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 17 页 -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=

27、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.Ou

28、tput();coutList5:;List5.Output();【实验过程】设计好单链表的建立、拆分、合并、转置代码后，打开C+编译环境，建立两个空的头文件，分别输入节点类和链表类的声明代码及实现代码。然后新建主文件，对两个类的构造函数、复制构造函数以及合并，转置函数等进行调试，最后进行评估。【实验体会】转置算法为利用3个指针的经典算法，需要记牢。合并与拆分算法总体都是建立在复制函数算法的基础上。经过这次实验，对单链表的性质有了更深刻的体会。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -5 将中缀表达式转换为后缀表达式【问题描述】表达式转换。输入的中缀表达式为字

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

30、于运算符，分两种情况处理：该运算符的优先级大于栈顶符号的优先级，则入栈；若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。说明：自行设计运算符优先级的表示。【主要代码】链式栈头文件：LinkedStack.h:#ifndef LINKEDSTACK_H#define LINKEDSTACK_H#include#includeLinkNode.h#include using namespace std;template class LinkedStack public:LinkedStac

31、k():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;template void LinkedStack:makeEmpty()名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 17 页 -LinkNode*p;p=top;top=top-

32、link;delete p;template void LinkedStack:Push(const T&x)top=new LinkNode(x,top);assert(top!=NULL);template bool LinkedStack:Pop(T&x)if(IsEmpty()=true)return false;LinkNode*p=top;top=top-link;x=p-data;delete p;return true;template bool LinkedStack:getTop(T&x)const if(IsEmpty()=true)return false;x=top-

33、data;return true;#endif 节点头文件：LinkNode.h:#ifndef LINKNODE_H#define LINKNODE_H template struct LinkNode T data;LinkNode*link;LinkNode(LinkNode*ptr=NULL)link=ptr;LinkNode(const T&item,LinkNode*ptr=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 17 页 -data=item;link=ptr;#endif 主函数源文件:Postfix.cpp:#includeLinkedSta

34、ck.h#include#include using namespace std;int isp(char a)int tag;if(a=#)tag=0;if(a=()tag=1;if(a=*|a=/|a=%)tag=5;if(a=+|a=-)tag=3;if(a=)tag=6;return tag;int icp(char a)int tag;if(a=#)tag=0;if(a=()tag=6;if(a=*|a=/|a=%)tag=4;if(a=+|a=-)tag=2;if(a=)tag=1;return tag;void postfix(char*infix)LinkedStack s;c

35、har ch=#,ch1,op;s.Push(ch);名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -ch=*infix;while(s.IsEmpty()=false)if(isdigit(ch)coutch;ch=*(+infix);else s.getTop(ch1);if(isp(ch1)icp(ch)s.Pop(op);coutop;else s.Pop(op);if(op=()ch=*(+infix);void main()char str100;cout请输入一个中缀表达式，运算符号仅限“+，-，*，/,%,(,)”。输入完后请在最后追加一个#符号：str;postfix(str);【实验过程】设计好点相关符号的优先级和中缀转后缀的算法，打开C+编译环境，建立两个空的头文件，分别输入链式栈和节点类的声明代码和实现代码。然后新建一个源文件，输入优先级定义函数的代码和中缀转后缀函数的代码。最后写一个主函数，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。【实验体会】了解了关于运算符优先级的相关制定方法，更加透彻的理解了栈的后进先出的性质。名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 17 页 -