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

数据结构课程设计实验报告空间数据结构基础 课程实习报告10 1 C+面向对象程序设计基础 学会用算法语言C+描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集，第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C+描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。 1. 定义三维空间的坐标点TPoint 2. 描述三维空间的球TBall，实现其主要操作。 头文件： TPoint.h: #ifndef TPOINT_H #define TPOINT_H #include<iostream> 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;/显示点的三坐标 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 getSurfAreaconst;/计算球的表面积 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;/球的半径 ; #endif 源文件： Define.cpp: #include <iostream> #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 TBall:DisBallInfoconst/显示球体的基本信息 cout<<"INFORMATION OF THIS BALL: "<<endl; cout<<'t'<<"SPHERICAL CENTRE: " sphCtr.DisplayTP; cout<<'t'<<"RADIUS: "<<r<<endl; cout<<'t'<<"SURFACE AREA: "<<getSurfArea<<endl; cout<<'t'<<"VOLUME: "<<getVolume<<endl; Main.cpp: #include<iostream> #include "TBall.h" #include"TPoint.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+编译环境，建立两个空的头文件，分别输入点类和球类的声明代码。然后新建一个源文件，输入点类和球类的函数体实现代码。最后新建主文件，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。 初步了解了面向对象的编程方式，体会到了函数声明与实现分离的安全性。 2 链表的建立、合并与拆分 链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。 定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。 1. 设线性链表A=(a1,a2,am),，B=(b1,b2,bm)，按下列规则合并A，B为线性表C的算法，即使得 C = (a1,b1,am,bm, b (m+1),bn) 当m<=n 或 C = (a1,b1,an,bn, a(n+1),am) 当m>n C表利用A表和B表中的结点空间构成。 2. 将C表原地逆置。 3. 将C表的中偶数和奇数分别链接为两个循环链表D和E。 说明：每一次合并、拆分和逆置等操作的结果均要输出。 单链表头文件：LinkedList.h #ifndef LINKEDLIST_H #define LINKEDLIST_H #include <iostream.h> #include "LinkNode.h" template<class T> class LinkedList public: LinkedListfirst = new LinkNode<T> /默认构造函数 LinkedList(const T &x)first = new LinkNode<T>(x); /带形参的构造函数 LinkedList(LinkedList<T> &L); /复制构造函数 LinkedListmakeEmpty; /析构函数 void makeEmpty; /将表置空 int Lengthconst; /求表长度 LinkNode<T> *getHeadconst return first; /取表头结点指针 LinkNode<T> *Search(T x); /搜索数据域为x的结点 LinkNode<T> *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); /删除第i个元素，x返回该元素的值 bool IsEmptyconst /判断表空否，空则返回true return first->link=NULL?true:false; void Output; /输出 void Turn; /将单链表的指向倒转 void Combine(LinkedList<T> &A,LinkedList<T> &B); /将两个单链表合并 void Divide(LinkedList<T> &D,LinkedList<T> &E); protected: LinkNode<T> *first; ; template<class T> /复制构造函数实现 LinkedList<T>:LinkedList(LinkedList<T> &L) T value; LinkNode<T> *srcptr = L.getHead; LinkNode<T> *destptr = first = new LinkNode<T> while (srcptr->link!=NULL) value = srcptr->link->data; destptr->link = new LinkNode<T>(value); srcptr = srcptr->link; destptr = destptr->link; destptr->link = NULL; template<class T> /置空函数实现 void LinkedList<T>:makeEmpty LinkNode<T> *p; while (first->link!=NULL) p = first->link; first->link = p->link; delete p; template<class T> /求长函数实现 int LinkedList<T>:Lengthconst LinkNode<T> *p = first->link; int count = 0; while (p!=NULL) p = p->link; count+; return count; template<class T> /搜索函数实现 LinkNode<T> *LinkedList<T>:Search(T x) LinkNode<T> *current = first->link; while (current!=NULL) if (current->data=x) break; else current = current->link; return current; template<class T> /定位函数实现 LinkNode<T> *LinkedList<T>:Locate(int i)const if (i<0) return NULL; LinkNode<T> *current = first; int k = 0; while (current!=NULL&&k<i) current = current->link; k+; return current; template<class T> /取值函数实现 bool LinkedList<T>:getData(int i,T &x)const if (i<=0) return NULL; LinkNode<T> *current = Locate(i); if (current=NULL) return false; else x = current->data; return true; template<class T> /修改函数实现 void LinkedList<T>:setData(int i,T &x) if (i<=0) return; LinkNode<T> *current = Locate(i); if (current=NULL) return; else current->data = x; template<class T> /插入函数实现 bool LinkedList<T>:Insert(int i,T &x) LinkNode<T> *current = Locate(i); if (current=NULL) return false; LinkNode<T> *newNode = new LinkNode<T>(x); newNode->link = current->link; current->link = newNode; return true; template<class T> /删除函数实现 bool LinkedList<T>:Remove(int i,T &x) LinkNode<T> *current = Locate(i-1); if (current=NULL|current->link=NULL) return false; LinkNode<T> *del = current->link; x = del->data; delete del; return true; template<class T> /输出函数实现 void LinkedList<T>:Output LinkNode<T> *current = first->link; while (current!=NULL) cout<<current->data<<'t' current = current->link; cout<<endl; template<class T> /倒置函数实现 void LinkedList<T>:Turn if (first->link=NULL) return; LinkNode<T> *current1 = first->link,*current2 = first->link->link; LinkNode<T> *p; while(p!=NULL) p = current2->link; current2->link = current1; current1 = current2; current2 = p; first->link->link = NULL;/让倒置后的最后一个结点的指针域为空 first->link = current1;/让附加的表头结点的指针域指向第一个结点 template<class T> void LinkedList<T>:Combine(LinkedList<T> &A,LinkedList<T> &B) 合并函数 T value1,value2; LinkNode<T> *srcptr1 = A.getHead; LinkNode<T> *srcptr2 = B.getHead; LinkNode<T> *destptr = first = new LinkNode<T> if (A.Length<B.Length) while (srcptr1->link!=NULL) value1 = srcptr1->link->data; value2 = srcptr2->link->data; destptr->link = new LinkNode<T>(value1); srcptr1 = srcptr1->link; destptr = destptr->link; destptr->link = new LinkNode<T>(value2); srcptr2 = srcptr2->link; destptr = destptr->link; while (srcptr2->link!=NULL) value2 = srcptr2->link->data; destptr->link = new LinkNode<T>(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<T>(value1); srcptr1 = srcptr1->link; destptr = destptr->link; destptr->link = new LinkNode<T>(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<T>(value1); srcptr1 = srcptr1->link; destptr = destptr->link; destptr->link = new LinkNode<T>(value2); srcptr2 = srcptr2->link; destptr = destptr->link; while (srcptr1->link!=NULL) value1 = srcptr1->link->data; destptr->link = new LinkNode<T>(value1); srcptr2 = srcptr2->link; destptr = destptr->link; destptr->link = NULL; template<class T> void LinkedList<T>:Divide(LinkedList<T> &D,LinkedList<T> &E) T value; LinkNode<T> *srcptr = this->getHead; LinkNode<T> *destptr1 = D.first = new LinkNode<T> LinkNode<T> *destptr2 = E.first = new LinkNode<T> while (srcptr->link!=NULL&&srcptr->link->link!=NULL) value = srcptr->link->data; destptr1->link = new LinkNode<T>(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<T>(value); srcptr = srcptr->link->link; destptr2 = destptr2->link; destptr1->link = NULL; #endif 节点头文件：LinkNode.h： #ifndef LINKNODE_H #define LINKNODE_H #include <iostream.h> template<class T> struct LinkNode T data; /数据域 LinkNode<T> *link; /指针域 LinkNode<T>(LinkNode<T> *ptr = NULL)link = ptr; /仅有指针域形参的构造函数 LinkNode<T>(const T &item,LinkNode<T> *ptr = NULL) /构造函数 data = item; link = ptr; ; #endif 主函数源文件：Main.cpp: #include <iostream.h> #include "LinkedList.h" #include "LinkNode.h" void main LinkedList<int> 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;i<10;i+) List1.Insert(i,bi); for (int j = 0;j<12;j+) List2.Insert(j,bj); cout<<"逆转前："<<endl; cout<<"List1: " List1.Output; cout<<"List2: " List2.Output; cout<<"List3为List1与List2的合并链表。"<<endl; List3.Combine(List1,List2); cout<<"List3: " List3.Output; cout<<"将List3逆转后："<<endl; List3.Turn; cout<<"List3: " List3.Output; cout<<"将List3拆分后："<<endl; List3.Divide(List4,List5); cout<<"List4: " List4.Output; cout<<"List5: " 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<assert.h> #include"LinkNode.h" #include<iostream> using namespace std; template<class T> class LinkedStack public: LinkedStack:top(NULL) LinkedStackif (IsEmpty=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<T> *top; ; template<class T> void LinkedStack<T>:makeEmpty LinkNode<T> *p; p = top;top = top->link;delete p; template<class T> void LinkedStack<T>:Push(const T &x) top = new LinkNode<T>(x,top); assert(top !=NULL); template<class T> bool LinkedStack<T>:Pop(T &x) if(IsEmpty=true) return false; LinkNode<T> *p = top; top = top->link; x = p->data; delete p; return true; template<class T> bool LinkedStack<T>:getTop(T &x)const if(IsEmpty=true) return false; x = top->data; return true; #endif 节点头文件：LinkNode.h: #ifndef LINKNODE_H #define LINKNODE_H template<class T> struct LinkNode T data; LinkNode<T> *link; LinkNode(LinkNode *ptr = NULL)link = ptr; LinkNode(const T &item,LinkNode<T> *ptr = NULL) data = item;link = ptr; ; #endif 主函数源文件:Postfix.cpp: #include"LinkedStack.h" #include<iostream> #include<string> 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<char> s; char ch = '#',ch1,op; s.Push(ch); ch = *infix; while(s.IsEmpty=false) if(isdigit(ch) cout<<ch<<' ' ch = *(+infix); else s.getTop(ch1); if(isp(ch1)<icp(ch) s.Push(ch);ch = *(+infix); else if(isp(ch1)>icp(ch) s.Pop(op);cout<<op; else s.Pop(op); if(op='(') ch = *(+infix); void main char str100; cout<<"请输入一个中缀表达式，运算符号仅限“+，-，*，/,%,(,)”。输入完后请在最后追加一个#符号： "<<endl; cin>>str; postfix(str); 设计好点相关符号的优先级和中缀转后缀的算法，打开C+编译环境，建立两个空的头文件，分别输入链式栈和节点类的声明代码和实现代码。然后新建一个源文件，输入优先级定义函数的代码和中缀转后缀函数的代码。最后写一个主函数，对两个类的构造函数、复制构造函数、操作函数等进行调试，最后进行评估。 了解了关于运算符优先级的相关制定方法，更加透彻的理解了栈的后进先出的性质。