数据结构课程设计

《空间数据结构基础》课程实习报告（测绘10级）姓名班级学号环境与测绘学院1C++面向对象程序设计基础【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。【实验内容】定义三维空间的坐标点TPoint描述三维空间的球TBall，实现其主要操作(如计算体积和表面积，输出空间坐标等)。【主要代码】#include<iostream>usingnamespacestd;doubleconstPI=3.14;template<classT>classTPoint{protected:Tx,y,z;public:TPoint(){x=0;y=0;z=0;}TPoint(Ta,Tb,Tc){x=a;y=b;z=c;}};template<classT>classTBall:publicTPoint<T>{private:Tr;public:TBall(){r=0;}TBall(Ta,Tb,Tc,Td){x=a;y=b;z=c;r=d;}voidoutput_S();voidoutput_V();voidoutput_P();};template<classT>voidTBall<T>::output_P(){coutvv"球心的坐标〃vvxvv""vvyvv""<<z<<endl;}template<classT>voidTBall<T>::output_S(){coutvv"球的表面积"<<4*Pl*r*rvvendl;}templatevclassT>voidTBallvT>::output_V(){coutvv〃球的体积为"vvPl*r*r*r*4/3vvendl;}voidmain(){inta,b,c,d;coutvv"请输入球心坐标"vv"x=";cin>>a;」〃〃coutvvy-;cin>>b;」〃〃coutvvz-;cin>>c;coutvv〃请输入半径〃vv〃r-〃；cin>>d;TBallvint>ball(a,b,c,d);ball.output_S();ball.output_V();ball.output_P();}【实验过程】⑴首先定义一个点的类作为一个基类，在定义个球的类，并且公共继承点类⑵将球的类的公共函数作为一个调用类的私有成员的接口⑶具体公共函数的实现在类的外面。⑷使用公共模版类请输人球心坐标〃1g请魏入半径尸2琲的表面积50.24球的休积为33.4933抹心’坐标］11Pressanykeytocontinue【实验体会】通过这次实验我掌握了点的类定义、空间中一个球体的定义和从点到球体公有继承的方法以及输入输出的方法！实验里首先定义一个PI，接着在实验中就能很好的简化实验操作步骤和代码量！2链表的建立、合并与拆分【实验简介】链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象 A和B，应用线性表的基本操作对表的实例对象进行操作测试。设线性链表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>nC表利用A表和B表中的结点空间构成。将C表原地逆置。将C表的中偶数和奇数分别链接为两个循环链表说 D和E。明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】#include<iostream.h>tempiate<classT>structLinkNode{ //定义在"LinkedList.h"Tdata; 〃链表结点类的定义LinkNodevT>*link; //数据域LinkNode(LinkNodevT>*ptr=NULL){link=ptr;} //构造函}；数LinkNode(constT&item,LinkNodevT>*ptr=NULL)

template<classT>classList{protected:LinkNode<//单链i表类定template<classT>classList{protected:LinkNode<//单链i表类定public: 义List(){first二newLinkNode<T>;}List(constT&X){first=List(List<T>&L);~List(){makeEmpty();}voidmakeEmpty();intLength()const;LinkNode<T>*getHead()constLinkNode<T>LinkNode<T>getData(intsetData(int*Search(TX);*Locate(inti);booli,T&X);voidi,T&X);boolInsert针//构造函数newLinkNode<T>(X);}//复制构造函数〃析构函数〃将链表置为空表〃计算链表的长度{returnfirst;}//搜索含X元素〃定位第i个元素〃取出第i元素值〃更新第i元素值〃在第i元素后插入X//删除第1个元素，X返回该元素值(inti,T&X);boolRemove(inti,T&X);booluniom(List<T>&A,List<T>&B,List<T>&C);表C,C利用A和B的存储空间voidchangeover();〃将(inti,T&X);boolRemove(inti,T&X);booluniom(List<T>&A,List<T>&B,List<T>&C);表C,C利用A和B的存储空间voidchangeover();〃将L链表原地逆转boolIsEmpty()const 〃判表空否{returnfirst->link=二NULL?true:false;}voidSort(); 〃排序voidinput();voidoutput();List<T>&operator=(List<T>&L););voidmain(){List<int>A,B;}voidList<T>::classify(List<T>&C,List<T>&D,List<T>&E){D.makeEmpty();E.makeEmpty();LinkNode<T>〃置空D、E链表*current二C.first;LinkNode<T>*p=current->link；LinkNode<T>*pd=D.first;LinkNode<T>*pe=E.first;while(p!=null)循环链表D和E中 〃循环地分别连接C中的结点到

｝；current->link=p->link;if((p->data)%2==0){pd->link=p;pd=｝；current->link=p->link;if((p->data)%2==0){pd->link=p;pd=pd->link;

pd->link=D.first;}

else{pe->link=p;pe=pe->link;

pe->link=E.first;}

p=current->link;〃拿出p结点八、、//D链表存放偶数结点八、、//E链表存放奇数结点八、、//p结点后移一个template<classT>boolList<T>::changeover(){LinkNode<T>*aq,*pr;aq=first->link;first->link=null;while(aq!=null){aq=pr;pr=aq->link;aq->link=first;first=aq;aq=pr;//把C转置);template<classT>boolList<T>::uniom(List<T>&A,List<T>&B);List<T>C=A;intm,n,min,i=1,min=(m<=n?m:n)m=A.length();n=B.length();LinkNode<T>*p=A.first;while(i<=min){LinkNode<T>*current=B.first;LinkNode<T>*aiq=current->link;current->link=aiq->link;//拿出aiq结点LinkNode<T>*pt=A.locate(i);aiq->link=pt->link;pt->link=aiq;〃把aiq结点插入到A的第i个结点后

i++；}i++；}调整if(m<=n){aiq->link=B.first->link；}if(C.length()=m+n)returntrue；elsereturnfalse；//A链表比B链表长的情况不用再//B链表比A链表长的情况；template<classT>voidList<T>::makeEmpty()whileNULL){q=whileNULL){q=first->link//保存被删结点//保存被删结点//从链上摘下该结点//删除first->link；=q->link；deleteq；}}；template<classT>intList<T>::Length()const{ListNode<T>*p=first->link;intcount=0;while(p!=NULL) 〃逐个结点检测{p=p->link;count++;}returncount;}template<classT>LinkNode<T>*List<T>::Search(Tx){〃在表中搜索含数据X的结点，搜索成功时函数返该结点地址；否则返回NULL。LinkNode<T>*current=first->link;while(current!=NULL&¤t->data!=X) current=current->link;returncurrent；}；template<classT>LinkNode<T>*List<T>::Locate(inti)(//函数返回表中第i个元素的地址。若i<0或i超出表中结点个数，则返回NULL。if(i<0)returnNULL;//i不合理LinkNode<T>*current=first；intk=0；while(current!=NULL&&k<i){current=current->link;k++; }returncurrent;//返回第i号结点地址或NULL};template<classT>boolListvT>::getData(inti,T&x) 〃取出链表中第i个兀素的值{if(i<=0)returnfalse;LinkNode<T>*current=Locate(i);if(cunent==NULL)returnfalse;else{x=current->data;returntrue;}template<classT>voidList<T>::setData(inti,T&x)〃给链表中第i个兀素的赋值x{if(i<=0)return;LinkNode<T>*current=Locate(i);if(cunent==NULL)return;elsecurrent->data=x;}template<classT>boolList<T>::Insert(inti,T&x)//将新元素x插入在链表中第i个结点之后。LinkNode<T>*current=Locate(i);if(current==NULL)returnfalse;//无插入位置LinkNode<T>*newNode=newLinkNode<T>(x);if(newNode==NULL){cerrvv"内存分配错误！"<<endl;newNode->link=current->link;current->link=newNode;returntrue;exit(1);}; }//链入template<classT> 〃插入成功boolList<T>::Remove(inti,T&x)〃删除链表第i个元素,通过引用参数x返回元素值{LinkNode<T>*current=Locate(i-1);if(current==NULL||current->link==NULL)returnfalse;〃删除不成功LinkNode<T>*del=current->link;current->link=del->link;x=del->data;deletedel;returntrue;);template<classT>voidList<T>::output(){LinkNode<T>*current二first->link;while(current!=NULL){cout<<current->data<<endl;current二current->link;}template<classT>voidList<T>::inputFront(TendTag){LinkNode<T>*newNode;Tval;makeEmpty();cin>>val;while(val!=endTag){newNode=newLinkNode<T>(val);if(newNode==NULL){ cerr<<"内存分配错误！"<<endl;exit(1);}newNode->link=first->link;〃插在表前端first->link=newNode;cin>>val;});【实验过程】对实验内容进仃分析，由】)设线性链表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,bna(n+1),…,am)当m>n设计出函数uniom;由2)将C表原地逆置，设计出了函数changeove;r由3)将c表的中偶数和奇数分别链接为两个循环链表D和E设计出了函数classify。然后再设计主函数，逐步进行调试。【实验体会】通过该实验，我能了解链表的概念、功能及应用。链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。6图元识别和替换(用队列实现)【问题描述】对于点阵式的图，在程序中可以用二维数组来表示。图中一片连续的具有相同颜色的点称为“图元”。现给出的问题是，对图中指定的图元用另一种颜色来替换。用队列实现。输入输出界面与实验指导书中算法实现—程序3.1相同。【主要代码】#include<iostream.h>#include<stdlib.h>#defineQMAX30//设栈空间最大为30单元#defineM8 //设方阵大小为8行8列typedefstruct{//像素结构introw;intcol;}Pixel; //像素的行下标Pixel //像素的列下标offset[4]; //像素类型名//矩阵中四个方向的移动修正classStack{ 表private:Pixelst[QMAX];//像素类型的栈空间inttop;//栈顶public:Stack(){top=0;}voidpush(Pixel&e);//像素e进栈Pixelpop();//出栈一个像素intIsEmpty();//判断栈是否为空，若空则返回1，否则返回0);voidStack::push(Pixel&e){//像素e进栈if(top==QMAX)exit(0);st[top].row=e.row;st[top].col=e.col;top++;}PixelStack::pop(){//出栈一个像素，由e返回Pixele;if(top==0)exit(0);top--;e.row=st[top].row;e.col=st[top].col;returne;}intStack::IsEmpty(){//判断栈是否为空if(top<=0)return1;elsereturn0;}voidInit(Pixelpos[]){// 初始化移动修正表数组，pos[]即offset[4]pos[0].row=0;pos[0].col=1;//right pos[1].row=1;pos[1].col=0;pos[2].row=0;pos[2].col=-1;//down pos[3].row=-1;pos[3].col=0;//left} //upintseekp(intarra[][8],int ai,intaj,intx,inty){//使用栈的图元替换算法Pixelnbr,here;//进栈变量和出栈变量Stackms;//栈inti,ni,nj;〃工作变量，下一个工作点的行下标和列下标cout<<"搜索到的图元像素："<<endl;cout<<ai<<','<<aj<<','<<arra[ai][aj]<<endl;arra[ai][aj]=x;arra[ai][aj+1]=x; //替return1; 换//} 替换voidmain(){intarra[8][8]={//存储图的数组初始化0,0,0,0,0,0,0,0,0,0,3,3,0,5,2,0,0,0,3,3,0,0,2,0,0,6,2,3,8,8,8,0,0,0,2,3,8,0,0,0,0,2,2,8,8,7,3,0,0,0,2,5,8,3,3,0,0,0,0,0,0,0,0,0};inti,j,x,//四周设一圈围墙(值为0)以保证数据处理的可靠性y;Init(offset);//初始化移动修正表数cout<<"像素矩 组"<<endl;阵： //输出图矩阵for(i=0;i<M;i++){for(j=0;j<M;j++)cout<<arra[i][j]<<'';cout<<endl;}coutvv"请输入指定图元的坐标和新像素值(ijx用空格分隔)："；cin>>i>>j>>x;//输入数据用空格分隔y=arra[i][j];〃取指定像素的值if(y!=x){seekp(arra,i,j,x,y);//进行图兀替换coutvv"替换后的像素矩阵:"<<endl;for(i=0;ivM;i++){//输出图矩阵for(j=0;jvM;j++)coutvvarra[i][j]vv'';coutvvendl;}coutvv'图兀替换完毕！"<<endl;}elsecoutvv味做替换!〃vvendl;//未进行替换操作}ooe00000000eooe00000000e050S073O00a989oa93a0e・B・嘛舍甫i夏魏坐标和新橡素值Gj〃用空格分隔）：24e2?4.e八鹭"换后的燔素矩阵］0099PressonykeykeytocontLnucPressonykeykeytocontLnuc1aa1aaaaaa&&02・022e浊a|2|Eeae7e3B^乎图吒的坐标和新像素值（iJK屈空格分隔）沦40P>*essanykeytocontinue.【实验体会】在二叉树中正确地理解和应用递归思想是很重要。由于二叉树的结构的特殊性，所以能充分发挥递归函数的强大功能。9字符串【实验简介】字符串是由零个或多个字符的顺序排列所组成的数据结构，字符串在计算机处理中使用非常广泛。通过本次实验理解字符串运算的原理，掌握主要算法的实现。【实验内容】建立字符串类，并实现求子串、字符串赋值、字符串连接等运算符重载函数，实现字符串的模式匹配功能。编写一个能够统计字符串中各个字符出现频度的函数。【主要代码】#include<iostream>usingnamespacestd;#include<string.h>intconstdefaultSize=128;//常量classAString{public:AString();//构造函数AString(constchar*init);//构造函数AString(constAString&ob);//复制构造函数~AString(){delete[]ch;}//析构函数intLength()const{returncurLength;}//取长度AStringoperator()(intpos,intlen);//取子串函数AString&operator=(constAString&ob);//赋值函数AString&operator+=(constAString&ob);//连接函数char&operator[](inti);//取特定位子的函数voidoutput();//输出字符串函数voidinput(char*init);//输入字符串函数intFind(AString&pat,intk);//匹配函数voidchar_count();//统计各个字符函数private:char*ch;//字符串指针intcurLength;//当前长度intmaxSize;//可用长度);AString::AString(){//没有参数的构造函数maxSize=defaultSize;ch=newchar[maxSize+1];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=0;ch[0]='\0';);AString::AString(constchar*init){//有参数的构造函数intlen;len=strlen(init);maxSize=(len>defaultSize)?len:defaultSize;ch=newchar[maxSize+1];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=len;strcpy(ch,init);}AString::AString(constAString&ob){//赋值构造函数maxSize=ob.maxSize;ch=newchar[maxSize+1];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=ob.curLength;strcpy(ch,ob.ch);}AStringAString::operator()(intpos,intlen){//取子串函数的实现AStringtemp;if(pos<0||pos+len-1>=maxSize||len<0){temp.curLength=0;temp.ch[0]='\0';}else{if(pos+len-1>=curLength)len=curLength-pos;temp.curLength=len;for(inti=0,j=pos;i<len;i++,j++)temp.ch[i]=ch[j];temp.ch[len]='\0';}returntemp;}AString&AString::operator=(constAString&ob){//赋值函数的实现if(&ob!=this){delete[]ch;ch=newchar[ob.maxSize];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}curLength=ob.curLength;strcpy(ch,ob.ch);}elsecout<<"ERROR"<<endl;return*this;}AString&AString::operator+=(constAString&ob){//连接函数的实现char*temp=ch;intn=curLength+ob.curLength;intm=(maxSize>=n)?maxSize:n;ch=newchar[m];if(ch==NULL){cerr<<"AllocationError"<<endl;exit(1);}maxSize=m,curLength=n;strcpy(ch,temp);strcat(ch,ob.ch);delete[]temp;return*this;}char&AString::operator[](inti){//取特定位置字符函数的实现if(i<0||i>=curLength){cout<<"overrange"<<endl;exit(1);}returnch[i];}intAString::Find(AString&pat,intk){//inti,j;for(i=k;i<=curLength-pat,curLength;i++){for(j=0;j<pat.curLength;j++)if(ch[i+j]!=pat.ch[j])break;if(j==pat.curLength)returni;}return-1;}voidAString::output(){//输出字符串函数的实现inti;for(i=0;i<curLength;i++){cout<<ch[i]<<"";}cout<<endl;}voidAString::input(char*init){//输入字符串的函数实现intlen=strlen(init);curLength=len;strcpy(ch,init);}voidAString::char_count(){//统计各个字符的函数的实现intchar_let,char_num,char_other;char_let=char_num=char_other=0;for(inti=0;i<curLength;i++){if(ch[i]<='Z'&&ch[i]>='A'||ch[i]<'z'&&ch[i]>='a'){char_let++;}elseif(ch[i]<='9'&&ch[i]>=T'){char_num++;}elsechar_other++;}coutvv"字母有"vvchar_letvvendl;coutvv"数字有"vvchar_numvvendl;coutvv"其他有"vvchar_othervvendl;}voidmain(){//charstr[100];coutvv"请输入一串字符串"vvendl;cin.getline(str,100);AStringmainStr;mainStr.input(str);mainStr.output();intpos,len;coutvv"请输入要取出的子串的位置"vvendl;cin>>pos>>len;AStringsub_mainStr;sub_mainStr=mainStr(pos,len);sub_mainStr.output();mainStr+=sub_mainStr;coutvv"将取出的子串连接到主串后面为"<<endl;mainStr.output();intlocation;location=mainStr.Find(sub_mainStr,0);coutvv"子串的位置为"vvlocationwendl;mainStr.char_count();【实验过程】⑴重新定义一个字符串类⑵在类中构造函数和各个功能函数的声明⑶在类的私有成员中为字符串和字符串的长度和空间的大小⑷各个成员函数的实现⑸主函数的实现请输入一串字符串!Laf125s上F诳盘safArefsfl25请输入要取出的子串的位置t4勺将取出的子串连接到主串后面为魏字<3safarefsfl25s子串的勺将取出的子串连接到主串后面为魏字<3safarefsfl25s子串的位置为1苴他有空Ppessanykeytocontinue【实验体会】在这一个实验中，以字符串味载体，再一次巩固了类的学习。同时也掌握了字符串的特性，通过封装成类和运算符的重载，使字符串的函数更加好用，这也是C++语言的强大之处。7二叉树的操作【实验简介】二叉树是树形结构的一种重要类型。通过本次实验，熟悉二叉树结点的结构，掌握二叉树的基本操作以及具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。【实验内容】编写程序，实现对二叉树的以下操作：建立二叉树。按任一种遍历次序输出二叉树中的所有结点。求二叉树的深度。求二叉树中的所有节点数。求二叉树中的所有叶子节点数。6. 清除二叉树，使之编程一只空树。【主要代码】#includeviostream>Usingnamespacetemplate<classT>structBinTreeNode //二叉树结点类定义(Tdata; ii数据域BinTreeNode<T>*leftChild,*rightChild;II左子女、右子女链域{leftChild={leftChild=NULL;rightChild=NULL;}〃构造函数BinTreeNode()〃构造函数BinTreeNode(Tx,BinTreeNode<T>*left=NULL,BinTreeNode<T>*right=NULL)rightChild=right;} };{data=x; leftChild=left;template<classT>classBinaryTree{public:BinaryTree(){root=NULL; //二叉树类定义BinaryTree(Tvalue){RefValue=value;root=NULL; //构造函数BinaryTree(){destroy(root);}bool //构造函数IsEmpty(){returnroot==NULL;}//int}Height(){returnHeight(root);}int //析构函数判二Size()(returnSize(root);} 叉树空否〃求树BinTreeNode<T>*getRoot()const 高度{returnroot;}BinTreeNode<T>札eftChild //求结点数(BinTreeNode<T>*cur)//返回左子女{return(cur!=NULL)？cur->leftChild:NULL;}BinTreeNode<T>*RightChild(BinTreeNode<T>*cur)//返回右子女{return(cur!=NULL)？cur->rightChild:NULL;}protected:BinTreeNode<T>*root; //二叉树的根指针TRefValue; //数据输入停止标志voidCreateBinTree(istream&in,BnTreeNode<T>*&subTree);//从文件读入建树voiddestroy(BinTreeNode<T>*&subTree); //删除intHeight(BinTreeNode<T>*subTree);//返回树高度intSize(BinTreeNode<T>*subTree); //返回结点数BinTreeNode<T>*Parent(BinTreeNode<T>*subTree,BinTreeNode<T>*cur);返回父结点//template<classT>voidBinaryTree<T>::destroy(BinTreeNode<T>*subTree)//私有函数：删除根为subTree的子树{if(subTree!=NUL