数据结构课程设计

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

2、all ，实现其主要操作(如计算体积和表面积，输出空间坐标 等)。【主要代码】 #include using namespace std;double const PI=3.14; template class TPoint protected:T x,y,z;public:TPoint()x=0;y=0;z=0;TPoint(T a,T b,T c)x=a;y=b;z=c; ;templateclass TBall: public TPoint private:T r;public:TBall()r=0;TBall(T a,T b,T c,T d) x=a;y=b;z=c;r=d;void

3、output_S();void output_V();void output_P(); template void TBall:output_P()coutvv球心的坐标vvxvv vvyvv zendl; templatevoid TBall:output_S() coutvv球的表面积void TBallvT:output_V ()coutvv球的体积为vvPl*r*r*r*4/3vvendl;void main() int a,b,c,d;coutvv请输入球心坐标vvx=;cina;coutvvy=;cinb;coutvvz=;cinc;coutvv请输入半径vvr=;cind;TBa

4、llvint ball(a,b,c,d);ball.output_S();ball.output_V();ball.output_P();【实验过程】首先定义一个点的类作为一个基类，在定义个球的类，并且公共继承点类 将球的类的公共函数作为一个调用类的私有成员的接口 具体公共函数的实现在类的外面。使用公共模版类请输人球心坐标1g请魏入半径尸2琲的表面积50.24球的休积为33.4933抹心S坐标1 1 1Press any key to continue【实验体会】通过这次实验我掌握了点的类定义、 空间中一个球体的定义和从点到球体公有继 承的方法以及输入输出的方法！实验里首先定义一个PI，接着在

5、实验中就能很好 的简化实验操作步骤和代码量！2链表的建立、合并与拆分【实验简介】 链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系， 链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操 作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。1. 设线性链表A=(a1,a2,am), B=(b1,b2,bm)按下列规则合并 A, B为线性表C 的算法，即使得C = (a1,b1,am,bm, b (m +1),bn)当 mnC

6、表利用A表和B表中的结点空间构成。2. 将C表原地逆置。D和E。3. 将C表的中偶数和奇数分别链接为两个循环链表 说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】#i nclude/定义在LinkedList.h/链表结点类的定义/数据域链指针域T data;Lin kNodevT *li nk;Lin kNode(Li nkNodevT *ptr = NULL ) link = p tr; / 构造函数Lin kNode(co nst T& item, Li nkNodevT *ptr = NULL) data = item; link = p tr; 构造函数tempi at

7、e struct Lin kNode ；23template class List protected: LinkNode *first;public:List() first = new LinkNode; /单链表类定义/表头指针/构造函数List(const T& X) first = new LinkNode(X); List( List& L);/复制构造函数List() makeEmpty();/析构函数void makeEmpty();/将链表置为空表int Length() const;/计算链表的长度/搜索含X元素定位第i个元素取出第i元素值更新第i元素值在第i元素后插入X/

8、删除第i个元素，X返回该元素值合并A，B为线性LinkNode *getHead() const return first; LinkNode *Search(T X); LinkNode *Locate(int i); bool getData(int i, T &X); void setData(int i, T &X); bool Insert (int i, T &X); bool Remove(int i, T &X); bool uniom(List &A,List &B,List &C);表C,C利用A和B的存储空间void chan geover();将L链表原地逆转void

9、classify(List &C,List &D,List &E);/将 C表的中偶数和奇数分别链接为两个循环链表D和E。bool IsEmpty() const/判表空否 return first-link = NULL ? true : false; void Sort();/排序void input();void output();List& operator=(List& L);void main() List A,B; void List:classify(List &C,List &D,List &E) 置空D、E链表D.makeEmpty(); E.makeEmpty(); Li

10、nkNode *current = C.first;LinkNode *p = current-link ；LinkNode *pd = D.first;/循环地分别连接C中的结点到LinkNode *pe = E.first; while(p!=null)循环链表D和 E中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链

11、表存放偶数结点/E链表存放奇数结点/p结点后移一个template bool List:changeover() LinkNode *aq,*pr; aq = first-link; first-link = null; while(aq != null) pr = aq-link; aq-link = first; first = aq;/把C转置aq = pr;template bool List:uniom(List &A,List &B);List C=A; int m,n,min,i=1, min=(m=n?m:n) m=A.length();n=B.length(); LinkNo

12、de *p=A.first; while(i=min) LinkNode *current = B.first; LinkNode *aiq = current-link;curre nt-li nk = aiq-li nk;/ 拿出 aiq 结点/把aiq结点插入到A的第i个结点后LinkNode *pt=A.locate(i); aiq-link=pt-link; pt-link=aiq;i+； 调整if(mlink=B.first-link； if(C.length()=m+n)return true；elsereturn false；/A链表比B链表长的情况不用再/B链表比A链表长的情

13、况；template void List:makeEmpty() LinkNode *q；while (first-link != NULL) q = first-link； first-link = q-link； delete q； ；/保存被删结点 /从链上摘下该结点/删除template int List : Length ( ) const ListNode *p = first-link; int count = 0;while ( p != NULL )/逐个结点检测 p = p-link; count+; return count;template LinkNode *List

14、:Search(T x) 在表中搜索含数据X的结点,搜索成功时函数返该结点地址；否则返回NULL。LinkNode *current = first-link; while ( current != NULL & current-data != X )current = current-link;return current；template LinkNode *List:Locate ( int i )/函数返回表中第 i 个元素的地址。若 i 0或 i 超出表中结点个数，则返回NULL 。if (i 0) return NULL;/i 不合理LinkNode *current = firs

15、t； int k = 0；while ( current != NULL & k link; k+;return current; /返回第 i 号结点地址或 NULL ;template bool List vT:getData(int i, T& x)取出链表中第i个元素的值 if ( i = 0 ) return false;LinkNode *current = Locate(i);if ( cunent = NULL ) return false;else x = current-data; return true; template void List :setData(int i

16、, T& x)给链表中第i个元素的赋值x if ( i = 0 ) return;LinkNode *current = Locate(i);if ( cunent = NULL ) return;else current-data = x; template bool List:Insert (int i, T& x)/将新元素 x 插入在链表中第 i 个结点之后。LinkNode *current = Locate(i);if (current = NULL) return false;/无插入位置exit(1);/链入/插入成功LinkNode *newNode = new LinkNo

17、de(x); if ( newNode = NULL ) cerrvv内存分配错误！ link = current-link; current-link = newNode; return true;template bool List:Remove (int i, T& x )删除链表第i个元素,通过引用参数x返回元素值 LinkNode *current = Locate(i-1);if ( current = NULL | current-link = NULL) return false; /删除不成功 LinkNode *del = current-link; current-lin

18、k = del-link;x = del-data; delete del;return true;template void List:output() LinkNode *current = first-link; while ( current !=NULL ) coutdatalink;template void List :inputFront (T endTag) LinkNode *newNode; T val; makeEmpty();cinval;while (val != endTag) newNode = new LinkNode(val);if ( newNode =

19、NULL )cerr内存分配错误！ link = first-link;/插在表前端first-link = newNode;cin val;【实验过程】对实验内容进行分析，由1)设线性链表A=(a1,a2,am), B=(b1,b2,bm),按下 列规则合并 A，B 为线性表 C 的算法，即使得C = (a1,b1,am,bm, b(m+1),bn)当 mn 设计出函数 uniom;由 2) 将 C 表原地逆置 ,设计出了函数 changeove；r 由 3) 将 C 表的中偶数和奇数分别链接为两 个循环链表D和E设计出了函数classify。然后再设计主函数，逐步进行调试。【实验体会】通过

20、该实验, 我能了解链表的概念、 功能及应用。 链表是用链接存储的方式来表达线性 表,它用指针表示结点间的逻辑关系, 链表适用于插入或删除频繁, 存储空间需求不定的情 形。6 图元识别和替换（用队列实现）【问题描述】 对于点阵式的图， 在程序中可以用二维数组来表示。 图中一片连续 的具有相同颜色的点称为 “图元 ”。现给出的问题是， 对图中指定的图元用另一种 颜色来替换。用队列实现。输入输出界面与实验指导书中算法实现 _程序 3.1 相 同。【主要代码】#include #include #define QMAX 30 /设栈空间最大为 30 单元#define M 8/ 设方阵大小为 8 行

21、8 列/ 像素的行下标/ 像素的列下标/ 像素类型名/ 矩阵中四个方向的移动修正表typedef struct / 像素结构 int row; int col;Pixel;Pixel offset4;class Stackprivate:Pixel stQMAX; / 像素类型的栈空间 int top;/ 栈顶public:Stack()top=0; void push(Pixel &e); / 像素 e 进栈 Pixel pop();/ 出栈一个像素int IsEmpty();/ 判断栈是否为空，若空则返回 1，否则返回 0;void Stack:push(Pixel &e) / 像素 e

22、进栈 if(top=QMAX) exit(0); sttop.row=e.row; sttop.col=e.col; top+;/ 出栈一个像素，由 e 返回Pixel Stack:pop()Pixel e; if(top=0) exit(0); top-; e.row=sttop.row; e.col=sttop.col; return e;int Stack:IsEmpty() / 判断栈是否为空 if(top=0) return 1;else return 0;/right/down/left/upvoid In it (P ixel pos)/ 初始化移动修正表数组，pos即 offs

23、et4pos0.row=0; pos0.col=1; pos1.row=1; pos1.col=0;pos2.row=0; pos2.col=-1; pos3.row=-1; pos3.col=0;int seekp(int arra8, int ai, int aj, int x, int y)/ 使用栈的图元替换算法 Pixel nbr,here; /进栈变量和出栈变量Stack ms;/ 栈int i, ni, nj;/工作变量，下一个工作点的行下标和列下标cout搜索到的图元像素：e ndl;/ 替换 /替换coutai,aj,arraaiajendl; arraaiaj=x;arra

24、aiaj+1=x;return 1;void main() int arra88= / 存储图的数组初始化 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/ 四周设一圈围墙（值为 0）以保证数据处理的可靠性; int i, j, x, y;/ 初始化移动修正表数组 endl;/ 输出图矩阵Init(offset); cout像素矩阵： for(i=0;iM;i+)for(j=

25、0;jM;j+) coutarraij ;coutijx; /输入数据用空格分隔 y=arraij; /取指定像素的值 if(y!=x)seekp(arra, i, j, x, y); / 进行图元替换 coutvv替换后的像素矩阵：e ndl; for(i=0;ivM;i+)/ 输出图矩阵for(j=0;jvM;j+)coutvvarraijvv; coutvve ndl;coutvv图元替换完毕！ *ess any key to continue.【实验体会】在二叉树中正确地理解和应用递归思想是很重要。由于二叉树的结构的特殊性， 所以能充分发挥递归函数的强大功能。9 字符串【实验简介】 字

26、符串是由零个或多个字符的顺序排列所组成的数据结构， 字符串在计算机 处理中使用非常广泛。通过本次实验理解字符串运算的原理，掌握主要算法的实现。 【实验内容】建立字符串类， 并实现求子串、 字符串赋值、 字符串连接等运算符重载函数， 实现字符 串的模式匹配功能。编写一个能够统计字符串中各个字符出现频度的函数。【主要代码】 #include using namespace std; #include in t co nst defaultSize=128;/常量 class AString public:AStri ng();/构造函数AString(const char* i n it) ;/构

27、造函数AStri ng(co nst AStri ng& ob);/ 复制构造函数AString()delete ch;/ 析构函数int Len gth()c on stretu rn curLe ngth;/ 取长度AStri ng op erator () (int p os, in t le n);/取子串函数AStri ng& op erator=(co nst AStri ng& ob);/ 赋值函数AStri ng& op erator+=(co nst AStri ng& ob);/ 连接函数char& op erator(i nt i);/取特定位子的函数void out p

28、ut();/输出字符串函数void input(char *init);/ 输入字符串函数int Find(AString &pat,int k);/ 匹配函数void char_co un t();/统计各个字符函数 private:char* ch;/字符串指针in t curLe ngth;/ 当前长度int maxSize;/可 用长度;AString:AString()/ 没有参数的构造函数maxSize=defaultSize;ch=new charmaxSize+1;if(ch=NULL)cerrAllocation ErrordefaultSize) ? len:default

29、Size;ch=new charmaxSize+1;if(ch=NULL)cerrAllocation Errorendl;exit(1); curLength=len;strcpy(ch,init);AString:AString(const AString& ob)/ 赋值构造函数 maxSize=ob.maxSize;ch=new charmaxSize+1;if(ch=NULL)cerrAllocation Errorendl;exit(1); curLength=ob.curLength;strcpy(ch,ob.ch);AString AString:operator()(int

30、pos,int len)/ 取子串函数的实现AString temp;if(pos=maxSize|len=curLength)len=curLength-pos; temp.curLength=len;for(int i=0,j=pos;ilen;i+,j+)temp.chi=chj; temp.chlen=0;return temp;AString& AString:operator=(const AString& ob)/ 赋值函数的实现 if(&ob!=this)delete ch;ch=new charob.maxSize;if(ch=NULL)cerrAllocation Erro

31、rendl;exit(1); curLength=ob.curLength;strcpy(ch,ob.ch);else coutERROR=n)?maxSize:n;ch=new charm;if(ch=NULL)cerrAllocation Errorendl;exit(1); maxSize=m,curLength=n;strcpy(ch,temp);strcat(ch,ob.ch);delete temp;return *this;char& AString:operator(int i)/ 取特定位置字符函数的实现if(i=curLength)coutover rangeendl;ex

32、it(1);return chi;int AString:Find(AString& pat,int k)/int i,j;for(i=k;i=curLength-pat.curLength;i+)for(j=0;jpat.curLength;j+) if(chi+j!=pat.chj)break; if(j=pat.curLength)return i;return -1;void AString:output()/ 输出字符串函数的实现int i;for(i=0;icurLength;i+) coutchi ; coutendl;void AString:input(char *init)

33、/ 输入字符串的函数实现int len=strlen(init);curLength=len;strcpy(ch,init);void AString:char_count()/ 统计各个字符的函数的实现int char_let,char_num,char_other; char_let=char_num=char_other=0; for(int i=0;icurLength;i+) if(chi=A|chi=a)char_let+;elseif(chi=1) char_num+; else char_other+;coutvv字母有vvchar_letvvendl;coutvv数字有vvc

34、har_numvvendl;coutvv其他有vvchar_othervvendl;void main()/char str100;coutvv请输入一串字符串vvendl; cin.getline(str,100);AString mainStr;mainStr.input (str);mainStr.output ();int pos,len;coutvv请输入要取出的子串的位置vvendl; cinposlen;AString sub_mainStr; sub_mainStr=mainStr(pos,len);sub_mainStr.output ();mainStr+=sub_main

35、Str;coutvv将取出的子串连接到主串后面为Using n ames pace std;清除二叉树，使之编程一只空树。temp late struct Bin TreeNode/二叉树结点类定义 T data;II数据域Bi nTreeNode *leftChild, *rightChild;II 左子女、右子女链域BinTreeNode ()/构造函数 leftChild = NULL;rightChild = NULL; BinTreeNode (T x, BinTreeNode *left = NULL, data = x;leftChild = left;BinTreeNode *

36、right = NULL) rightChild = right; ;/二叉树类定义/构造函数/构造函数/析构函数 判二叉树空否 /求树高度/求结点数template class BinaryTree public:BinaryTree () root=NULL;BinaryTree (T value) RefValue = value; root = NULL;Bi naryTree () destroy(root); bool IsEmpty() return root = NULL; / int Height() return Height(root); int Size() retur

37、n Size(root); BinTreeNode *getRoot () const return root; BinTreeNode *LeftChild (BinTreeNode *cur) / 返回左子女 return (cur!= NULL) ？cur-leftChild:NULL;BinTreeNode *RightChild (BinTreeNode *cur) / 返回右子女 return (cur!= NULL) ？ cur-rightChild:NULL; protected:BinTreeNode *root;/二叉树的根指针T RefValue;/ 数据输入停止标志vo

38、id CreateBinTree (istream& in, BnTreeNode *& subTree); / 从文件读入建树 void destroy (BinTreeNode *& subTree);/ 删除int Height (BinTreeNode *subTree); / 返回树高度 int Size (BinTreeNode *subTree);/ 返回结点数/BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *cur); 返回父结点templatevoid BinaryTree:destroy (BinTreeNode * subTree) /私有函数 : 删除根为 subTree 的子树/删除左子树 /删除右子树 if (subTree != NULL) destroy (subTree-leftChild);/删除根结点destroy (subTree-rightChild);delete subTree;templa