《空间数据结构基础》 上机实验报告（2012

姓名班级 地信12-1 学号 07122857

环境与测绘学院 级）

实验报告1

C++面向对象程序设计范例

1. 二维坐标点point的C++描述

【实验目的】用面向对象的方法定义一个简单的抽象数据结构，本例实验内容为坐标点的数据结构。学会如何用C++语言描述数据结构和算法，理解将数据集和在此数据集上的操作分开描述的方法。

调试程序及分布编程的方法

以下是平面直角坐标系中的点的类定义，main()函数对类Point的属性和操作进行测试。

#include <iostream.h>

class Point{ //平面直角坐标系中的点

private:

double x; //水平坐标值 double y; //垂直坐标值

public:

Point(){x = 0; y = 0; }//缺省构造函数 Point(double px,double py){x = px;y = py;}//带参数的构造函数 void move(double mx,double my){x = mx;y = my;}//移动位置(修改坐标值)

};

void main(){

Point a,b(12.5,34.8); //建立两个Point对象 cout<<"点a的位置："; void Show(){cout<<"x="<<x<<' '<<"y="<<y<<endl;}//输出坐标值

} a.Show(); //输出点a的坐标值 cout<<"点b的位置："; b.Show(); //输出点b的坐标值 a.move(45.6,57.8); cout<<"点a移动后的位置："; a.Show(); //输出点a的坐标值

2. 使用模板建立坐标点point的数据结构，直接表示抽象数据类型

【实验目的】将程序1.1数据结构的类型参数化（模板），实现更高层次的数据抽象。

#include <iostream.h>

template <class ptType> class Point{ //平面直角坐标系中的点 private:

ptType x; //虚拟类型的水平坐标值 ptType y; //虚拟类型的垂直坐标值

public:

Point(){x = 0; y = 0; }//缺省构造函数 Point(ptType px, ptType py){x = px;y = py;}//带参数的构造函数 void move(ptType mx,ptType my){x = mx;y = my;} //移动位置(修改坐标

值)

};

void main(){

} Point <int> a(24,36); //建立整型的Point对象 Point <double> b(12.5,34.8); //建立浮点型的Point对象 cout<<"点a的位置："; a.Show(); //输出点a的坐标值 cout<<"点b的位置："; b.Show(); //输出点b的坐标值 a.move(25,18); cout<<"点a移动后的位置："; a.Show(); //输出点a的坐标值 b.move(45.6,57.8); cout<<"点b移动后的位置："; b.Show(); //输出点b的坐标值

void Show(){cout<<"x="<<x<<' '<<"y="<<y<<endl;}//输出坐标值

顺序表的模板类

【实验目的】本例给出了较完整的顺序表的抽象数据类型定义，通过C++模板的应用体现了数据抽象原理。

【问题描述】定义一个顺序存储的线性表数据结构，在应用程序（main函数）

中建立一个整型的线性表对象，在该表中进行插入、删除、查找和输出等操作。

#include <iostream.h>

#include <stdlib.h>

//#include "linearList.h"

#define DefaultSize 20

template <class Type> class SeqList {

Type *element; //顺序表的存储数组 int MaxSize; //表的最大允许长度 int last; //表中最后元素下标

int current; //游标(迭代子)，指示表中当前元素(最近处理的元素)的位置，初始化为-1

public:

SeqList ( int MaxSize = DefaultSize ); //构造函数 ~SeqList ( ) { delete [ ] element; } //析构函数

int Length ( ) const { return last+1; } //计算顺序表的长度（元素个数）

int Find ( Type & x ); //查找，返回表中第一个与x相等的元素的位置

int IsIn ( Type & x ); //判断x是否在表中

Type GetElem ( int i ) {current=i;return i < 0 || i > last ? NULL:element[i];}

//取第i个元素的值 Type LocaElem() {return current==-1? NULL: element[current];} //取当前元素的值

int Insert ( Type & x, int i ); //插入x在表的第i个位置处，并置为当前位置

int Append(Type &x); //在表尾添加元素x，并置为当前位置

//删除表中第一个值为x的元素， int Delete ( Type & x );

返回该元素的位置

Type First(); //如果表不空返回表的第一个元素值 Type Next ( ) {return current<last ? element[++current]:NULL;} //得到当前元素的后继

Type Prior ( ) {return current>=0 ? element[--current]:NULL;} //得到当前元素的前趋

int IsEmpty ( ) { return last ==-1; } //判断顺序表是否为空，空则返回1，否则返回0

int IsFull ( ) { return last == MaxSize-1; } //判断顺序表是否满，满则返回1，否则返回0

friend ostream &operator << (ostream &out,SeqList<Type> &sl);//输出顺序表中的全部元素

};

template <class Type>

SeqList<Type> :: SeqList ( int sz ) { //构造函数 if ( sz > 0 ) {

MaxSize = sz; last = -1; element = new Type[MaxSize];

if ( element == NULL ) {

MaxSize = 0; last = -1;

current=-1;return;

}

}

template <class Type> }

int SeqList<Type>::Find ( Type & x ) {

//查找函数：在表中从前向后顺序查找 x，若查找成功，

//返回x在表中的位置，否则返回-1，当前指针置于表尾之后 current=0;//int i = 0;

while ( current <= last && element[current] != x ) current++;

if ( current > last ) return -1;

else return current;

}

template <class Type>

int SeqList<Type>::Insert ( Type & x, int i ){

//插入x在表的第i个位置处，并置为当前位置。函数返回否成功信息，成功为1，否则为0。

}

template <class Type>

int SeqList<Type>::Append(Type &x){

if(last==MaxSize-1)return 0; if(i<0||i>last+1||last==MaxSize-1)return 0; else{ } last++; for(current=last;current>i;current--) element[current]=element[current-1]; element[i]=x; return 1;

} current=++last; element[current]=x; return 1;

template <class Type>

int SeqList<Type>::Delete ( Type & x ){

//删除表中第一个值为x的元素，返回该元素的位置，未找到x时，返回-1。

}

template <class Type>

Type SeqList<Type>::First(){ //返回表的第一个元素值

if(last==-1) return NULL; //如果表空返回NULL int i=Find(x); if(i>=0){ } return -1; last--; for(int j=i;j<=last;j++)element[j]=element[j+1]; return i;

} current=0; return element[0];

template <class Type> //输出顺序表中的全部元素 ostream &operator << (ostream &out,SeqList<Type> &sl){

}

//#include "seqlist.h"

#define NUM 8

main(){

SeqList <int> a; //声明一个顺序表对象 int s,t; //工作变量 cout<<"连续插入8个数并输出:"<<endl; for(int i=0;i<NUM;i++) { s=2*i; //生成表元素数据，将2*i存入s out<<"表中现有元素: "; for(int i=0;i<=sl.last;i++) cout<<sl.element[i]<<' '; cout<<endl; return out;

} s=a.Insert ( s, i ); //在表中第i个位置插入元素s cout<<a.GetElem ( i )<<','; //输出表中刚插入的新元素 cout<<endl; s=a.Length(); //计算表的实际长度 cout<<"顺序表长度:"<<s<<endl; cout<<a; //用重载的输出运算符输出表中所有元素 t=a.Find(s); //在表中查找值与s相等的元素 cout<<"s在表中的位置:"<<t<<endl;//输出查找结果 cout<<"在表中删除一个元素"<<endl; t=a.Delete(s); //在表中删除值与s相等的元素 cout<<"删除的位置:"<<t<<','<<a<<"长度:"<<a.Length()<<endl; s=a.LocaElem(); //取当前元素的值 cout<<"当前元素 s="<<s<<",下一个:"<<a.Next()<<endl; s=s*8; cout<<"在表尾插入一个元素"<<endl; t=a.Append(s); //在表的末尾插入元素s cout<<a;

}

cout<<"顺序表长度:"<<a.Length()<<endl; s=a.GetElem(7); //取第7个元素的值 cout<<"第8个元素:"<<s; cout<<",前一个:"<<a.Prior()<<endl; //输出当前元素的前趋 return 0;

Ppt中的

#include<iostream.h> template < class T > T max ( T x, T y ) { return x > y ? x:y;} void main()

{

int i1='n', i2=56;

float f1=12.5, f2=24.5; char c1='k', c2='n';

cout<<"The max of i1,i2 is:"<< max(i1,i2) <<endl;

cout<<"The max of f1,f2 is:"<< max(f1,f2) <<endl;

cout<<"The max of c1,c2 is:"<< max(c1,c2) <<endl;

}

课后习题12题

设有两个整数类型的顺序表A（m个元素）和B（n个元素）其元素军从大到小排列，将这两个函数合并成一个顺序表C，也冲大到小排列

#include<iostream.h>

#include<stdlib.h>

const int defaultSize=100;

template<class T>

class SeqList{

protected:

T *data;

int maxSize;

int Last;

void reSize(int newSize);

public:

SeqList(int sz=defaultSize);

SeqList(SeqList<T>& L);

~SeqList(){delete[]data;}

int Size() const{return maxSize;}

int Length()const{return Last+1;}

int Search(T& x)const;

int Locate(int i) const;

T getData(int i) const;

bool setData(int i,T& x)

{if(i>0&&i<=Last+1) data[i-1]=x;}

bool Insert(int i,T& x);

bool Remove(int i,T& x);

bool IsEmpty()

{return (Last==-1)?true:false;}

bool IsFull()

{return(Last==maxSize-1)?true:false;}

void input();

void output();

SeqList<T> operator=(SeqList<T>& L);

friend void bubble(SeqList<int>& L);

friend void hebing(SeqList<int>& LA,SeqList<int>& LB); };

template<class T>

SeqList<T>::SeqList(int sz){

if(sz>0){

maxSize=sz;

Last=-1;

data=new T[maxSize];

if(data==NULL)

{cerr<<"存储分配错误"<<endl;exit(1);}

}

}

template<class T>

SeqList<T>::SeqList(SeqList<T>& L){

maxSize=L.Size();

Last=L.Length()-1;

data=new T[maxSize];

if(data==NULL)

{cerr<<"存储分配错误"<<endl;exit(1);}

for(int i=1;i<=Last+1;i++)

data[i-1]=L.getData(i);

}

template <class T>

T SeqList<T>::getData(int i) const{

if (i<1 || i>Last+1){cerr<<"存储分配错误"<<endl;exit(1);} else return data[i-1];

}

template<class T>

void SeqList<T>::reSize (int newSize)

{

if (newSize<=0)

{cerr<<"无效的数组大小"<<endl;return;} if(newSize!=maxSize)

{T*newarray=new T[newarray]; if(newarray=NULL)

{cerr<<"存储分配错误"<<endl;exit(1);} int n=Last+1;

T*srcptr=data;

T*destptr=newarray;

while(n--)*destptr++=*srcptr++; delete []data;

data=newarray;maxSize=newSize; }

}

template<class T>

int SeqList<T>::Search(T& x)const {

for(int i=0;i<=Last;i++)

if(data[i]==x)return i+1;

return 0;

}

template<class T>

int SeqList<T>::Locate(int i)const{

if(i>=1&&i<=Last+1)return i;

else return 0;

}

template<class T>

bool SeqList<T>::Insert(int i,T& x){ if(Last==maxSize-1) return false; if(i<0||i>Last+1) return false;

for(int j=Last;j>=i;j--)

data[j]=data[j-1];

data[i]=x;

Last++;

return true;

}

template<class T>

bool SeqList<T>::Remove(int i,T&x){ if(Last==-1)return false;

if(i<1||i>Last+1)return false;

x=data[i-1];

for(int j=i;j<=Last;j++)

data[j-1]=data[j];

Last--;

return true;

}

template<class T>

void SeqList<T>::input(){

cout<<"开始建立顺序表，请输入表中元素的最后位置：";

while(1){

cin>>Last;Last--;

if(Last<=maxSize-1) break;

cout<<"表元素个数有误，个数不能超过"<<maxSize-1<<":"; }

for(int i=0;i<=Last;i++)

{cin>>data[i];}

}

template<class T>

void SeqList<T>::output(){

cout<<"顺序表中当前元素的最后位置为："<<Last<<endl; for(int i=0;i<=Last;i++)

cout<<"#"<<i+1<<":"<<data[i]<<endl;

}

template<class T>

SeqList<T> SeqList<T>::operator=(SeqList<T>& L){

maxSize=L.Size();

Last=L.Length()-1;

data=new T[maxSize];

if(data==NULL)

{cerr<<"存储分配错误"<<endl;exit(1);}

for(int i=1;i<=Last+1;i++)

data[i-1]=L.getData(i);

}

void hebing(SeqList<int>& LA,SeqList<int>& LB){

int n=LA.Length(),m=LB.Length(),k,x;

for(int i=1;i<=m;i++)

{

x=LB.getData(i);

k=LA.Search(x);

if(k==0)

{LA.Insert(n,x);n++;}

}

}

void bubble(SeqList<int>& L)

{

int i,j,temp;

for(i=1;i<L.Length();i++)

for(j=0;j<L.Length()-i;j++)

{

if(L.data[j]>L.data[j+1]) {

temp=L.data[j];

L.data[j]=L.data[j+1]; L.data[j+1]=temp; }

}

}

void main()

{ SeqList<int>LA;

SeqList<int>LB;

LA.input();

LB.input();

hebing(LA,LB);

SeqList<int>LC(LA);

bubble(LC);

LC.output();

}

实验报告2 单链表及其基本操作

【数据结构】定义一个链表存储的线性表，提供表元素的插入、删除、查找和输出等操作。

#include <iostream.h>

template <class T>

struct LinkNode

{ T data; //数据域

LinkNode<T> *link; //链指针域

LinkNode(LinkNode<T> *ptr = NULL )

{ link = ptr; } //构造函数

LinkNode(const T& item, LinkNode<T> *ptr = NULL)

{ data = item; link = ptr; } //构造函数

};

template <class T>

class List : public LinearList<T> //单链表类定义

{ protected:

LinkNode<T> *first; //表头指针

public:

List() { first = new LinkNode<T>; } //构造函数

List(const T& x) { first = new LinkNode<T>(x); }

List( List<T>& L); //复制构造函数 ~List(){ makeEmpty(); }

void makeEmpty(); //将链表置为空表

int Length() const;

LinkNode<T> *getHead() const { return first; }

LinkNode<T> *Search(T x); //搜索含x元素

LinkNode<T> *Locate(int i); //定位第i个元素

bool getData(int i, T &x); //取出第i元素值 void setData(int i, T &x);

bool Insert (int i, T &x); //在第i元素后插入x bool Remove(int i, T &x); //删除第i个元素，x返回该元素值

bool IsEmpty() const

{ return first->link == NULL ? true : false; }

void Sort(); //排序

void input();

void output();

List<T>& operator=(List<T>& L);

};

template <class T>

void List<T>::makeEmpty()

{ LinkNode<T> *q;

while (first->link != NULL)

{ q = first->link; //保存被删结点

first->link = q->link; //从链上摘下该结点

delete q; //删除

}

}；

template <class T>

int List<T> :: Length ( ) const {

ListNode<T> *p = first->link;

int count = 0;

while ( p != NULL ) //逐个结点检测

{ p = p->link; count++; }

return count;

}

template <class T>

LinkNode<T> *List<T>::Search(T x)

{

LinkNode<T> *current = first->link;

while ( current != NULL && current->data != x ) current current->link;

return current;

};

template <class T>

LinkNode<T> *List<T>::Locate ( int i )

{

if (i < 0) return NULL; //i不合理

LinkNode<T> *current = first; int k = 0;

while ( current != NULL && k < i )

{ current = current->link; k++; }

return current; };

template <class T>

bool List <T>::getData(int i, T& x) //取出链表中第i个元素的值 { if ( i <= 0 ) return false;

LinkNode<T> *current = Locate(i);

if ( cunent == NULL ) return false;

else { x = current->data; return true; }

template <class T>

void List <T>::setData(int i, T& x) //给链表中第i个元素的赋值x { if ( i <= 0 ) return;

LinkNode<T> *current = Locate(i);

if ( cunent == NULL ) return;

else current->data = x; }

template <class T>

bool List<T>::Insert (int i, T& x) =

//将新元素 x 插入在链表中第 i 个结点之后。

{ LinkNode<T> *current = Locate(i);

if (current == NULL) return false; //无插入位置 LinkNode<T> *newNode = new LinkNode<T>(x); if ( newNode == NULL )

{ cerr<<“内存分配错误！”<<endl; exit(1);} newNode->link = current->link; //链入 current->link = newNode;

return true; //插入成功

};

template <class T>

bool List<T>::Remove (int i, T& x )

//删除链表第i个元素, 通过引用参数x返回元素值

{ LinkNode<T> *current = Locate(i-1);

if ( current == NULL || current->link == NULL) return false;

LinkNode<T> *del = current->link;

current->link = del->link;

x = del->data; delete del;

return true;

};

template < class T >

void List< T >::output()

{ LinkNode< T > *current = first->link;

while ( current !=NULL )

{ cout<<current->data<<endl;

current = current->link;

}

}

template < class T >

void List <T> ::inputFront (T endTag)

{ LinkNode<T> *newNode; T val;

makeEmpty();

cin>>val;

while (val != endTag)

{ newNode = new LinkNode<T>(val);

if ( newNode == NULL )

{ cerr<<“内存分配错误！”<<endl; exit(1);} newNode->link = first->link;

first->link = newNode;

cin >> val;

}

};

1. 习题作业2.17：设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

#include<iostream.h>

Template<class Type>

void List<type>::Inverse(){

If(first==NULL)return;

ListNode<Type>*p=first->link,*pr=NULL;

While(p!=NULL){

First->link=pr; //逆转first指针

Pr=first;first=p;p=p->link; //指针前移

}

First->link=pr;

}

1. 完成习题作业4.15：编写一个算法frequency，统计在你一个输入字符串中各个不同字符串出现的频度。用适当的测试数据来验证这个算法。

#include<iostream.h>

template <class Type > void List <Type>:: Tnerse() {

if (first== NULL )return ;

ListNode <Type > * p=first->link ; *pr =NULL ;

While (p !=NULL ) {

First->link =pr ;

Pr =first ;first =p ;p =p->link;

}

first ->link =pr ;

}

实验报告3

n阶二项式系数（用队列实现）

【目的】理解队列操作的算法和程序实现，学会使用队列解决问题。

【问题描述】计算并输出n阶二项式系数。

【数据结构】用顺序存储的队列class Queue对象暂存求得的二项式系数。

【算法描述】

本题特点是递推式计算。计算求得的二项式系数可以摆成一个三角形，称为“杨辉三角形”。

应用程序为YangHui ( int n )函数。

初始的两个系数1由常量赋值，以后每一个新系数由语句q.EnQueue ( s+t ) 产生并插入

队列。s和t分别表示新系数左肩上和右肩上的系数。新系数插入队列后，t值赋给s，出队一个数据赋给t，再进行下一个系数的计算，如此循环。在上下行的换行处插入一个0，以产生边上的1。

计算工作由二重循环实现，外循环for ( int i=1; i<=n; i++ )控制产生n行系数。内循环for ( int j=1; j<=i+2; j++ )控制按行输出系数。每行系数的个数与行序号存在对应关系，如i表示行号，则第i行系数个数为i+2。

杨辉三角形生成

#include <stdio.h>

#include <iostream.h>

#include <assert.h>

template <class Type> class Queue { //循环队列的类定义

public:

Queue ( int=20 );

~Queue ( ) { delete [ ] elements; }

void EnQueue ( const Type & item);//元素入队

Type DeQueue ( ); //元素出队

Type GetFront ( ); //取队首元素

void MakeEmpty ( ) { front = rear = 0; } //置队列空

int IsEmpty ( ) const

{ return front == rear; }

int IsFull ( ) const

{ return (rear+1) % maxsize == front; }

int Length ( ) const //求队列长度 { return (rear-front+maxsize) % maxsize;} private:

int rear, front; //队尾和队首

Type *elements; //队列元素存储空间

int maxsize; //队列最大长度

};

template <class Type> Queue<Type>::

Queue ( int sz ) : front (0), rear (0), maxsize (sz) { elements = new Type[maxsize];

assert ( elements != 0 );

}

template <class Type> void Queue<Type>::

EnQueue ( const Type & item ) {//元素item入队 assert ( !IsFull ( ) ); rear = (rear+1) % maxsize;

elements[rear] = item;

}

template <class Type>

Type Queue<Type>::DeQueue ( ) {//队首元素出队，若成功返回元素值 assert ( !IsEmpty ( ) );

front = ( front+1) % maxsize;

return elements[front];

}

template <class Type>

Type Queue<Type>::GetFront ( ) { //取队首元素，若成功返回元素值 assert ( !IsEmpty ( ) );

return elements[front];

}

void YangHui ( int n ) { //计算并打印n行二项展开式系数 Queue <int> q; //建立队列并初始化 q.MakeEmpty ( ); //队列置空

q.EnQueue (1); q.EnQueue (1); //第一行系数入队 int s = 0; //s为下一个系数左肩上的数

for ( int i=1; i<=n; i++ ) { //逐行计算，共n行

cout << endl; //当前输出行结束，换行

q.EnQueue (0); //下一行系数开始前插入一个0

for ( int j=1; j<=i+2; j++ ) { //计算下一行，系数个数为i+2 int t = q.DeQueue ( ); //t为下一个系数右肩上的数 q.EnQueue ( s+t ); //s+t计算出下一个系数并入队

s = t; //迭代取值，为求下一个系数做准备 if ( j != i+2 ) cout << s << ' '; //输出一个系数 }

}

}

void main(){

int n;

n=6;

YangHui(n); //求n行二项展开式系数

cout<<endl;

}

字符串运算和朴素的模式匹配

【实验目的】理解字符串运算的原理，掌握主要算法的实现。本实验主要内容是要求编写并调试朴素的模式匹配。

【问题描述】字符串模式匹配：给定任意一个长度为a的字符串A和一个长度为b的字符串B（a>b），串A为目标（Target），串B为模式（pattern），要求在字符串A中查找（匹配）是否有与字符串B相等的子串。如果匹配成功，返回B在A中的起始位置，否则匹配不成功，返回-1。

【数据结构】按顺序表数据结构定义字符串类，其数据成员中的一维数组ch为字符串存储空间。本例提供的主要操作有求字符串的长度，提取子串，判断两个串是否相等、是否不相等，字符串是否为空串，字符串复制，字符串连接，求串的失效函数值，模式匹配等。

用循环链表求解以下问题。

设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，??，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n，s和m，求出这n个人的出局序列。