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

《数据结构课程设计实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告.docx（13页珍藏版）》请在三一办公上搜索。

1、数据结构课程设计实验报告空间数据结构基础 课程实习报告10 1 C+面向对象程序设计基础 学会用算法语言C+描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集，第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C+描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。 1. 定义三维空间的坐标点TPoint 2. 描述三维空间的球TBall，实现其主要操作。 头文件： TPoint.h: #ifndef TPOINT_H

2、#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 getXconstreturn x;/取x坐标值 double getYconstreturn y;/取y坐标值 double getZconstreturn z;/取z坐标值 void DisplayTP const cout(x,y,z)endl;

3、/显示点的三坐标 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 public: TBall(TPoint SC,double R):sphCtr(SC),r(R)/构造函数 TBall(TBall &TB):sphCtr(TB.sphCtr),r(TB.r) double ge

4、tSurfAreaconst;/计算球的表面积 double getVolumeconst;/计算球的体积 TPoint getSphctrreturn sphCtr; double getRadiusconstreturn r;/取球的半径 void Move(double Mx,double My,double Mz)sphCtr.Move(Mx,My,Mz);/在空间坐标系内移动球 void ChangR(double newR)r = newR; void DisBallInfoconst;/显示球体的基本信息 private: TPoint sphCtr;/球心坐标 double r

5、;/球的半径 ; #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:getSurfAreaconst/计算球的表面积 return 4*PI*r*r; double TBall:getVolumeconst/计算球的体积 return (4.0/3)*PI*r*r*r; void T

6、Ball:DisBallInfoconst/显示球体的基本信息 coutINFORMATION OF THIS BALL: endl; couttSPHERICAL CENTRE: ; sphCtr.DisplayTP; couttRADIUS: rendl; couttSURFACE AREA: getSurfAreaendl; couttVOLUME: getVolumeendl; Main.cpp: #include #include TBall.h #includeTPoint.h using namespace std; void main TPoint TP1(1,3,2); TB

7、all TB1(TP1,7); TP1.DisplayTP; TB1.DisBallInfo; TB1.Move(3,2,5); TB1.ChangR(22); TB1.DisBallInfo; 设计好点类和球类的相关属性和操作后，打开C+编译环境，建立两个空的头文件，分别输入点类和球类的声明代码。然后新建一个源文件，输入点类和球类的函数体实现代码。最后新建主文件，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。 初步了解了面向对象的编程方式，体会到了函数声明与实现分离的安全性。 2 链表的建立、合并与拆分 链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，

8、链表适用于插入或删除频繁，存储空间需求不定的情形。 定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。 1. 设线性链表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。 说明：每一次合并、拆分和逆置等操作的结果均要

9、输出。 单链表头文件：LinkedList.h #ifndef LINKEDLIST_H #define LINKEDLIST_H #include #include LinkNode.h template class LinkedList public: LinkedListfirst = new LinkNode; /默认构造函数 LinkedList(const T &x)first = new LinkNode(x); /带形参的构造函数 LinkedList(LinkedList &L); /复制构造函数 LinkedListmakeEmpty; /析构函数 void makeEmp

10、ty; /将表置空 int Lengthconst; /求表长度 LinkNode *getHeadconst 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个元素后插入x bool Remove(int i,T &x); /删除第

11、i个元素，x返回该元素的值 bool IsEmptyconst /判断表空否，空则返回true return 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 &

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

13、 (first-link!=NULL) p = first-link; first-link = p-link; delete p; template /求长函数实现 int LinkedList:Lengthconst LinkNode *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!=

14、NULL) if (current-data=x) break; else current = current-link; return current; template /定位函数实现 LinkNode *LinkedList:Locate(int i)const if (i0) return NULL; LinkNode *current = first; int k = 0; while (current!=NULL&klink; k+; return current; template /取值函数实现 bool LinkedList:getData(int i,T &x)const

15、if (i=0) return NULL; LinkNode *current = Locate(i); if (current=NULL) return false; else x = current-data; return true; template /修改函数实现 void LinkedList:setData(int i,T &x) if (i=0) return; LinkNode *current = Locate(i); if (current=NULL) return; else current-data = x; template /插入函数实现 bool LinkedL

16、ist: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-l

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

18、irst-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;/让附加的表头结点的指针域指向第一个结点 template void LinkedList:Combine(LinkedList &A,LinkedList &B) 合并函数 T

19、 value1,value2; LinkNode *srcptr1 = A.getHead; LinkNode *srcptr2 = B.getHead; LinkNode *destptr = first = new LinkNode; if (A.Lengthlink!=NULL) value1 = srcptr1-link-data; value2 = srcptr2-link-data; destptr-link = new LinkNode(value1); srcptr1 = srcptr1-link; destptr = destptr-link; destptr-link =

20、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-li

21、nk-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.LengthB.Length) while (srcptr2-link!=NULL) value1 = srcptr1-link

22、-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); src

23、ptr2 = 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&srcptr-link-link

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

25、); 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 *pt

26、r = NULL) /构造函数 data = item; link = ptr; ; #endif 主函数源文件：Main.cpp: #include #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+

27、) 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: ; Lis

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

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

30、大于栈顶符号的优先级，则入栈； 若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止。 说明：自行设计运算符优先级的表示。 链式栈头文件：LinkedStack.h: #ifndef LINKEDSTACK_H #define LINKEDSTACK_H #include #includeLinkNode.h #include using namespace std; template class LinkedStack public: LinkedStack:top(NULL) LinkedStackif (IsE

31、mpty=false)makeEmpty; void Push(const T &x); bool Pop(T &x); bool getTop(T &x)const; bool IsEmptyconst return (top=NULL)?true:false; void makeEmpty; private: LinkNode *top; ; template void LinkedStack:makeEmpty LinkNode *p; p = top;top = top-link;delete p; template void LinkedStack:Push(const T &x)

32、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-data; return true; #endif 节点头文件：L

33、inkNode.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) data = item;link = ptr; ; #endif 主函数源文件:Postfix.cpp: #includeLinkedStack.h #include #include using namespace std; i

34、nt 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) LinkedSta

35、ck s; char ch = #,ch1,op; s.Push(ch); 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+编译环境，建立两个空的头文件，分别输入链式栈和节点类的声明代码和实现代码。然后新建一个源文件，输入优先级定义函数的代码和中缀转后缀函数的代码。最后写一个主函数，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。 了解了关于运算符优先级的相关制定方法，更加透彻的理解了栈的后进先出的性质。