中国地质大学数据结构实习报告

第一篇：中国地质大学数据结构实习报告

Practice Report for Data Structures and Algorithm Analysis

Data Structures Course Report

Candidate: Student Number:

Major:

Communication Engineering Supervisor:

Wu rangzhong

China University of Geosciences(Wuhan)Wuhan, Hubei 430074, P.R.China

May 18, 2013

China University of Geosciences, Faculty of Mechanics and Electronic Information

删除程序代码

void DeletekTh(int position, pNode L){

pNode Tmp=L, TmpPre=NULL;

int i=0;

for(i=0;i

{

if(Tmp->next!=NULL)

{

TmpPre = Tmp;

Tmp=Tmp->next;

}

else if(Tmp->next==NULL && i

{

printf(“The Deletion position is invalid!n”);

return;

}

}

TmpPre->next=Tmp->next;

free(Tmp);}

这是程序主函数，以此来完成以上子函数的功能

#include #include #include “lianbiao.h”

int main(){

int i,x,position;pNode m;

pNode LinkLists;

{

printf(“输入元素来建立链表，0为结束输入的标志”);

LinkLists = CreateLinkLists();

printf(“链表为:”);

PrintLists(LinkLists);

}

printf(“选择你需要的操作，输入序号：n”);

printf(“

1.建立一个链表

n”);

printf(“

2.输出链表

n”);

}

2.数组实现线性表

用数组实现的功能和用链表表示的相同 部分子函数如下

//初始化顺序表：给出初始化长度

int initialArray(arrayList arrLst,int len)

{

arrLst->length=0;

arrLst->size=len;

arrLst->Array=(ElemType*)malloc(len*sizeof(ElemType));

if(arrlst->Array==NULL)

return 0;

else

return 1;

}

//删除顺序表

void deleteArray(arrayList arrLst)

{

arrLst->length=0;

arrLst->size=0;

free(arrLst->Array);

arrLst->Array=NULL;

}

//清空顺序表

void clearArray(arrayList arrLst)

{

}

printf(“n”);

}

//判断某个元素的位置

int locateElem(arrayList arrLst,ElemType e)

{

int i;

for(i=0;i

{

if(e==arrLst->Array[i])

return i;

}

return-1;

}

堆栈

主要是实现元素的进栈、出栈、判断栈中元素个数

堆栈的源函数 #include #include #include“duizhan.h”

STACK CreatStack(){

STACK S;

S=(STACK)malloc(sizeof(struct Stack));

if(S==NULL)

{

printf(“无法建立堆栈!”);

return 0;

}

S->top=-1;

return S;}

int IsFull(STACK S){

return(S->top==MAX-1);}

int IsEmpty(STACK S){

int StackLen(STACK S){

if(!IsEmpty(S))

return S->top;else

return 0;}

堆栈的主函数 #include #include #include“duizhan.h”

void main(){

STACK liliS;

liliS=CreatStack();

Push(1,liliS);

Push(2,liliS);

Push(3,liliS);

Pop(liliS);

Pop(liliS);

DisposeStack(liliS);} 设置断点可以看到栈中的元素

主函数 void main(){ STRING *Str, *Pat;int position=0;Str=(STRING *)malloc(sizeof(STRING));Pat=(STRING *)malloc(sizeof(STRING));char S_str[20]=“ababcabcacbab”;char P_str[20]=“abcac”;

Str->p_str = S_str;Str->length = strlen(S_str);Pat->p_str = P_str;Pat->length = strlen(P_str);

int *next=(int *)malloc(sizeof(int)*(Pat->length +1));

GetNext(Pat, next);position=IndexKMP(Str, Pat, next);

printf(“%dn”,position);}

显示两个字符串是在第6个元素开匹配的。

}

//插入新元素

M->data[p].i=row;

M->data[p].j=col;

M->data[p].e=e;

M->tu++;

return OK;

}

稀疏矩阵的的转置

Status TransposeSMatrix(const TSMatrix *M,TSMatrix *T){

int col,p,q;

T->mu=M->nu;

T->nu=M->mu;T->tu=M->tu;

if(T->tu){

q=1;

for(col=1;col<=M->mu;col++)

for(p=1;p<=M->tu;p++)

if(M->data[p].j==col){

T->data[q].i=M->data[p].j;

T->data[q].j=M->data[p].i;

T->data[q].e=M->data[p].e;

q++;

}

}

return OK;

}

稀疏矩阵的乘法

Status MultSMatrix(const TSMatrix *M,const TSMatrix *T,TSMatrix *Q){

int i,j,k,p;

ElemType m,t,s;

if(M->nu!=T->mu){

printf(“Sorry,these two matrice can't multiply.n”);

return ERROR;

}

Q->mu=M->mu;

Q->nu=T->nu;

Q->tu=0;

p=1;

for(i=1;i<=Q->mu;i++){

for(j=1;j<=Q->nu;j++){

s=0;

for(k=1;k<=M->nu;k++){

if(FALSE==FindElem(M,i,k,&m))

查找

采用的是快速查找法 源程序

#include #include “chazhao.h”

int SequenceSearch(int array[],int n,int x){

int i=0;

while(i

i++;

if(i==n)

return-1;

else

return i;} 建立一个数组后查找元素，输入元素后，返回元素所在数组的下标。

5用数组储存数据，在用冒泡法排序后将排序好的数组输出。

AVL树

程序主要是在向二叉树插入节点后，最终生成AVL树

AVL树中的单旋转

static Position SRL(Position K2)

{

Position K1 = NULL;

K1 = K2->left;

K2->left = K1->right;

K1->right = K2;

K2->height = MAX(Height(K2->left), Height(K2->right))+ 1;

K1->height = MAX(Height(K1->left), Height(K2))+ 1;

return K1;}

static Position SRR(Position K2)

{

Position K1 = NULL;

#else

Position K1 = NULL;

Position K2 = NULL;

K1 = K3->right;

K2 = K1->left;

K1->left = K2->right;

K2->right = K1;

K3->right = K2->left;

K2->left = K3;

return K2;

#endif

}

主程序

#include #include “avlTree.h”

void PrintTree(AvlTree T)

{

if(T!= NULL)

{

PrintTree(T->left);

printf(“h=%d, e=%dn”, T->height, T->ele);

PrintTree(T->right);

}

}

int main(void)

{

AvlTree T = NULL;

T = MakeEmpty(T);

T = Insert(3, T);

T = Insert(2, T);

T = Insert(1, T);

T = Insert(4, T);

T = Insert(5, T);

T = Insert(6, T);

T = Insert(7, T);

T = Insert(16, T);

T = Insert(15, T);

T = Insert(14, T);

T = Insert(13, T);

s->bottom=0;

s->top=0;

memset(s->printout,0,sizeof(int)*MAX_LEN);}

void push(mstack *s,int m){

s->printout[s->top++]=m;}

int pop(mstack *s){

return s->printout[--s->top];}

void InitGraph(Graph *g,int n){

int i,j;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

if(i==j)g->matrix[i][j]=0;

else g->matrix[i][j]=INFINITE;

}

for(i=1;i<=n;i++)

{

in[i]=0;

Len[i]=INFINITE;

path[i]=0;

} }

第二篇：数据结构实习报告(中国地质大学)

1、需求规格说明

【问题描述】

利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩解压缩软件。

【基本要求】

（1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。

（2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件。

（3）解压缩。打开已有压缩文件，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。

2．总体分析与设计

【设计思想】

将一待压缩的文件以二进制形式进行读写。压缩过程中，将待压缩文件一次性读入内存，随后对其中出现的字符进行判断和统计，将所得的字符频率创建HuffMan树，并对其进行编码，将源文件的字符用其HuffMan编码代替，组合成满字节写入压缩文件。【详细设计表示】

变 量 数据类型 Maxsize int *Key input_char KeyNum int *Huffman_node huffmantree 成员函数说明： char_judge 功能：判断字符出现的函数；

原型：bool char_judge(char c);//判断字符出现的函数； 返回类型：bool型 参数：c char型 [in] char_add

功能：添加新出现字符的函数； 原型：void char_add(char c);返回类型：无

参数：c char型 [in] CreateHuffTree 功能：创建哈夫曼树

原型：void CreateHuffTree();返回类型：无 参数：无

CreateHuffCode

功能：创建哈夫曼编码

原型：void CreateHuffCode();返回类型：无 参数：无

其它函数说明： ArrayOpp 功能：将一个字符数组中的1 字符顺序颠倒 原型：void ArrayOpp(char a[],int n)返回类型：无

参数：数组 a char型 [in&out] n int型

CompressFile 功能：压缩文件

原型：void CompressFile(FILE *ifp,FILE *ofp);//压缩 返回类型：无

参数：指针ifp FILE型 [in&out]

指针ofp FILE型 [in&out]

DecompressionFile 功能：解压文件

原型：void DecompressionFile(FILE *ifp,FILE *ofp);//解压 返回类型：无

参数：指针ifp FILE型 [in&out]

指针ofp FILE型 [in&out]

FindMax

功能：寻找数组中最大元素下标 原型：void FindMax(int index[],int n,int &flag);//寻找数组中最大元素下标 返回类型：无

参数：数组index int型 [in&out] n 数组长度 [in] flag int型 [in&out] 3． 编码

【遇到的问题及解决方法】（1）选取合适的数据结构

对于一个工程的实现，到底采用怎样的数据结构，应该考虑到程序的性能和代码的可读性。由于起初对工程的不熟，对于用什么样的数据结构来存储我一直都处在试探中，缺乏一种长久的考虑，这也使得后面的编码过程效率不高。最终冷静下来，自定义了一个文件类和两个辅助结构体，大体的实现框架在总体设计中已给出。

(2)哈夫曼树该如何建立

首先，字符的频率作为关键值，用一个循环，每次找出关键值最小的两个字符，将其组合加入到哈夫曼树中，同时将每个哈夫曼树节点用结构体huffman_node数组存放，每个节点都有其左右孩子和父节点的下标，这有便于后面的哈夫曼编码。(3)哈夫曼编码的具体实现

哈夫曼编码的具体实现方法：由于哈夫曼树的建立过程中为每个哈夫曼节点标明了左右孩子和父节点，可以从关键值开始，从下往上通过父节点与子节点的关系为子节点进行编码，如果父节点的左孩子是当前子节点，则子节点（含关键值）的哈夫曼编码标为0否则标为1，如此循环下去。这样得到每个叶节点对应的哈夫曼编码的逆序表示，且存放在数组bits中。然后用一个函数ArrayOpp将其逆序过来，从而真正得到哈夫曼编码。(4)文件的二进制形式读写操作及其压缩的实现

最主要的还是怎样实现文件的压缩，由于压缩文件中的字符是用其相应的哈夫曼编码代替的，如果只是把字符的哈夫曼编码（也使字符型的数组存放的）写入，将会适得其反，只有将相邻字符的编码组合成一个一个的字节数字写入才能达到节省空间的效果，例如：某字符哈夫曼编码为bits 1 1 1 1 1 1 1 这字符数组内容通过移位可转化为char型数128，如果满一个字节就写入，若未满则继续组合。

4．程序及算法分析

【压缩】

1、先整体扫描文本，统计文本的字符个数，种类，以及频率记录下来。

2、根据字符的频率生成相应的huffman树，生成huffman树之后再根据树的结构生成huffman编码。

3、生成压缩文件，文件头部分写入待压缩文件的字符个数，字符种类以及相应的频率，分别用int型，char型数组以及int型数组写入。

4、写入带压缩文件中每个字符对应的huffman编码，按位写入。

按位写入采用移位思想，满8位一写。如源文件中一段字符“ABC”,A的huffman编码为001,B的huffman编码为010，C的为11，刚好满8位。则定义一个unsigned char型变量如c_out（初值为0），用移位将c_out赋值使其机器编码为00101011，刚好8位，再将其作为一个字符写入压缩文件中，直至将带压缩文件的最后一个字符写满。要注意的是:若带压缩文件最后一个字符的huffman编码赋值给c_out后c_out不满8位，则将c_out的其余位都补0。

【解压】

1、读压缩文件的头部分，定义几个变量记录字符个数，种类以及对应的频率。

2、根据字符种类及频率生成huffman树。

3.继续循环读压缩文件每次读一个字符，每读一个字符根据其8位机器码来遍历huffman树，当遇到huffman树的叶子节点时终止，将叶子节点的字符写入解压后的新文件中。当读完最后一个字符后终止循环。

解压正文时每读一个字符，利用移位将该字符的8位机器码取出存入链表中，方便huffman树的遍历。【分析】

主要的程序集中在两个函数中：CompressFile和DecompressionFile考虑到程序的性能，在对文件的读写过程中，我选择在内存中对文件进行操作，在压缩时，将待压缩文件一次性读入内存，在解压文件时，将待解压文件一次性读入内存，而不是一个字节一个字节地读写文件。

5．小结

通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科，学习这门学科也是艰辛的，因为它比较难懂，但是这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。

这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为课本上的基础知识掌握不好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。

近两周的程序设计，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。

这次课程设计涉及对大量数据的处理，要做到精益求精，不能忽略任何一处，否则结果将会有很大的不同，总之，最大的感受就是完美源于细节！编程不仅要有一定的理论基础和实践经验，还需要一定的毅力和关注细节的习惯。这次对文件的压缩和解压的实习，使我的调试有了进一步的提高。同时也使我在编程中对文件的存储形式的采取有了一定的了解。希望在以后的实习中，我会有有进一步的提高。

6．附录

【部分核心代码】

void CompressFile(FILE *ifp,FILE *ofp){

if(!ifp){

cout<<“InPutFile cannot be

opened!”<

fseek(ifp, 0, SEEK_END);//定位到文件结尾处

int orignflen = ftell(ifp);char *orignfile=new char [orignflen+1];fseek(ifp,0,SEEK_SET);//定位到文件起始处

fread(orignfile,1,orignflen,ifp);//将文件内容一次性读到内存中

orignfile[orignflen]=0;

C_file file(512);char c;for(int i=0;i

c=orignfile[i];

if(!file.char_judge(c))//对原文件字符进行判断和统计

file.char_add(c);}

for(int i=1;i

cout<

} file.CreateHuffTree();//创建HuffMan树

file.CreateHuffCode();//创建HuffMan编码

//*******************************************************************// //写入文件信息

fseek(ifp,0,SEEK_SET);fwrite(&orignflen,sizeof(int),1,ofp);fwrite(&file.MaxSize,sizeof(int),1,ofp);fwrite(&file.KeyNum,sizeof(int),1,ofp);for(int i=1;i

fwrite(&file.Key[i].data,sizeof(char),1,ofp);

fwrite(&file.Key[i].count,sizeof(int),1,ofp);}

//*******************************************************************//

unsigned char o_c=0;//o_c中存入二进制的位数

int bitnum=0;

char x;

for(int k=0;k

c=orignfile[k];//从内存中取出源文件内容

for(int

i=1;i

{//在文件类对象中检索出相应的关键码

if

(c!=file.Key[i].data)continue;

else

{//将哈夫曼编码组合成char型数字

for(int

j=0;j

{

if(bitnum==8)

{//若满8位则构成一字节写入

fwrite(&o_c,1,1,ofp);

bitnum=0;

o_c=0;

}

x=file.huffman_node[i].bits[j];

if(x=='1')o_c=(o_c<<1)+1;

else o_c=o_c<<1;

bitnum++;

}

break;

}

} } while(bitnum<8)//最后一个字节未写满则补

{

o_c=o_c<<1;

bitnum++;} fwrite(&o_c,1,1,ofp);//将最后一个字节写入文件

fclose(ifp);fclose(ofp);cout<<“Already Compressed!”<

} void FindMax(int index[],int n,int &flag){//找出数组中最大值的下标 由flag返回

for(int i=1;i<=n;i++){

if(index[i]>=index[i+1])

{

flag=i;

}

else

flag=i+1;} }

void DecompressionFile(FILE *ifp,FILE *ofp){ unsigned char i_c=' ';char o_c=' ';

//**************************************************************// //读取压缩文件信息

fseek(ifp,0,SEEK_SET);int orignflen=0;int MaxSize=0;int KeyNum=0;

fread(&orignflen,sizeof(int),1,ifp);

char *depressfile;depressfile=new char[orignflen+1];

fread(&MaxSize,sizeof(int),1,ifp);

C_file file(MaxSize);

fread(&file.KeyNum,sizeof(int),1,ifp);

for(int i=1;i

fread(&file.Key[i].data,sizeof(char),1,ifp);

fread(&file.Key[i].count,sizeof(int),1,ifp);}

//**************************************************************// //重构HuffMan树和编码

file.CreateHuffTree();file.CreateHuffCode();

fseek(ifp, 12+((file.KeyNum-1)*5), SEEK_END);

long flen = ftell(ifp);char *compressfile=new char [flen+1];

fseek(ifp,0,SEEK_SET);fseek(ifp, 12+((file.KeyNum-1)*5), SEEK_SET);

char t_buff[255],z_buff[255];t_buff[0]=0;z_buff[0]=0;

//获取最长编码的长度

int *index;index=new int [file.KeyNum-1];int flag=0;for(int i=1;i

index[i]=file.huffman_node[i].count;} FindMax(index,file.KeyNum-1,flag);

int

p=file.huffman_node[flag].count;int curr_index=0;int l=0;while(true){

int i;

while(strlen(z_buff)

{//保证能够取到最长编码的全部内容

fread(&i_c,1,1,ifp);

itoa(i_c,t_buff,2);//将读取的一个（字符型）字节的内容转换为char型字符数组

strcat(z_buff,t_buff);

【参考资料】

}

for(i=1;i

if(memcmp(file.huffman_nod

e[i].bits,z_buff,file.huffman_node[i].count)==0)

break;

}

strcpy(z_buff,z_buff+file.huffman_node[i].count);

//获得目标字符并存入目标数组

o_c=file.Key[i].data;

depressfile[l++]=o_c;

if(l==orignflen)

{

break;

}

}

fseek(ofp,0,SEEK_SET);

fwrite(depressfile,1,l,ofp);//将解压后的文件一次性地写入文件

fclose(ifp);fclose(ofp);cout<<“Already DeCompressed!”<

}

《数据结构(用面向对象方法与C++语言描述)》 殷人昆 等编著，清华大学出版社 《数据结构题集》严蔚敏，吴伟民 编著，清华大学出版社 《数据结构及应用算法》严蔚敏，陈文博 编著，清华大学出版社

第三篇：中国地质大学(武汉)数据结构报告

Practice Report for Data Structures and Algorithm Analysis

Data Structures Course Report

Candidate:

吴泽光

Student Number: 20121001873 Major :

Communication Engineering Supervisor :

Wu rangzhong

China University of Geosciences(Wuhan)Wuhan, Hubei 430074, P.R.China

October 18, 2012

China University of Geosciences, Faculty of Mechanics and Electronic Information

一、线性表(用链表实现):

1、目的：

通过程序的运用，使得线性表的插入、删除等功能更加容易实现，节约了时间和精力。

2、程序说明：

typedef struct LNode * LinkList;typedef int Status;struct LNode { int data;struct LNode * next;};void Insert(LinkList &L,int i,int b);void Delete(LinkList &L,int i);int Length(LinkList &L);void Print_LinkList(LinkList &L);插入函数：

void Insert(LinkList &L,int i,int x){ LinkList p, q;p=L;q=(LinkList)malloc(sizeof(LNode));q->data=x;if(i==1){

q->next=p;L=q;} else

定义结构体。插入函数。删除函数。输出长度。输出线性表内容。

} {

} while(--i>1)p=p->next;q->next=p->next;p->next=q;

3、运行过程：

二、堆栈和队列

1、目的：

通过程序的运用，使得队列的插入、删除等功能更加容易实现，节约了时间和精力。

2、程序说明：

struct My_Queue {

int Element[MaxLength];int Length;int head;int rear;};定义结构体。int Head_Queue(My_Queue &Que);功能：返回队列头结点的值

参数：Que，引用类型，指向队列的头。

void Print_Queue(My_Queue &Que);输出队列的内容。void In_Queue(My_Queue &Que,int Element);输入队列。void Out_Queue(My_Queue &Que, int &Element);输出队列。主函数： void main(){

} My_Queue My_Fst_Que;My_Fst_Que.Length = 0;int data = 0;My_Fst_Que.head = My_Fst_Que.rear =0;Input_Queue(My_Fst_Que, 2);Print_Queue(My_Fst_Que);Input_Queue(My_Fst_Que, 4);Print_Queue(My_Fst_Que);Input_Queue(My_Fst_Que, 6);Print_Queue(My_Fst_Que);Input_Queue(My_Fst_Que, 8);Print_Queue(My_Fst_Que);Input_Queue(My_Fst_Que, 10);Print_Queue(My_Fst_Que);

Out_Queue(My_Fst_Que, data);Print_Queue(My_Fst_Que);Out_Queue(My_Fst_Que, data);Print_Queue(My_Fst_Que);Out_Queue(My_Fst_Que, data);Print_Queue(My_Fst_Que);Out_Queue(My_Fst_Que, data);data = Head_Queue(My_Fst_Que);Print_Queue(My_Fst_Que);

3、运行过程：

三、字符串的模式匹配

1、目的：

输入目标串和模式串，运用KMP算法判断是否匹配。

2、程序说明：

typedef struct String String_KMP;struct String { char * data;int length;};定义结构体。

int KMPMatch(String_KMP &s, String_KMP &t , int next[]);功能：用于检测返回值情况。主函数： void main(){

String_KMP s, p1;int *next_KMP, position=0;p1.data = “&&aaaaa”;

} p1.length = strlen(p1.data);s.data =“&&&aaaaabaabcwwww”;s.length = strlen(s.data);next_KMP=(int *)malloc(sizeof(int)* strlen(p1.data));next(p1, next_KMP);position = KMPMatch(s, p1 , next_KMP);if(position == 0)printf(“No match!n”);else printf(“The match position is %dn”, position);

3、运行过程：

1、匹配成功：

2、不能匹配：

四、稀疏矩阵（表示转置和乘法）

1、目的：

通过对矩阵的基本操作，了解多维数组的逻辑结构和存储结构。本程序是用三元数组表示矩阵，并进行相关的操作，将矩阵表示出来，以及快速转置的应用。

2、程序说明：

typedef struct { Triple data[MAXSIZE+1];int mu,nu,tu;} TSMatrix;

int InputMatrix(TSMatrix &M);void PrintM(TSMatrix M);void PrintM3(TSMatrix M);void trantup(TSMatrix M, TSMatrix &T);主函数： void main(){

} int a;TSMatrix M,T;a=InputMatrix(M);printf(“n按三元组方式输出:n”);PrintM3(M);printf(“n下面进行矩阵转置的操作：n”);system(“PAUSE”);system(“cls”);printf(“n要转置的矩阵为:n”);PrintM(M);trantup(M,T);printf(“n转置后的矩阵为:n”);PrintM(T);

3、运行过程：

五 AVL树实现

1、目的：

通过程序的运用，使得树的相关功能更加容易实现，节约了时间和精力。

2、程序说明：

求根深度的实现所用到的：

Status InitBiTree(SqBiTree T);Status CreateBiTree(SqBiTree T);Status BiTreeEmpty(SqBiTree T);int BiTreeDepth(SqBiTree T);Status Root(SqBiTree T,TElemType *e);

3、运行过程：

六、图的实现：

1、目的：

通过程序的运用，使得图的有关功能更加容易实现，节约了时间和精力。

2、程序说明：

实现图的输出和遍历用到的: void CreateGraph(Graph *ga);void DFS(Graph g,int i,bool visited[]);void DFSTraverse(Graph g);void BFSTraverse(Graph g,Queue *que);

3、运行过程：

七、排序（希尔排序与归并排序）：

1、目的：

通过程序的运用，使得数据的排序更加容易实现，节约了时间和精力。

2、程序说明：

1)希尔排序的具体实现: void ShellSort(RecType R[],int n){ int i,j,gap,k;RecType tmp;gap=n/2;while(gap>0){ for(i=gap;i

{ tmp=R[i];

j=i-gap;

while(j>=0 && tmp.key

{ R[j+gap]=R[j];

j=j-gap;}

R[j+gap]=tmp;

j=j-gap;}

printf(“gap=%d:”,gap);

for(k=0;k

printf(“%d ”,R[k].key);printf(“n”);gap=gap/2;} } 2)归并排序：

归并排序的实现所用到的：

int randGenerator(double vArray[],int n);int Merge(double vArray[],double Lr[],int i,int m,int n);int Msort(double vArray[],double Lr[],int s,int t);

3、运行过程：

总结

通过本次的实习，使我掌握了模块化设计方法，理解和运用结构化程序设计的思想和方法。提高了利用C语言进行程序设计能力。

第一次设计这么多程序，感觉压力很大，很难完成，虽然看起来设计流程感觉很轻松，但是正真完成的时候并不能通过程序表达出来。通过同学和老师的帮助最终还是完成了自己的程序设计，虽然程序还不是很完美，但能满足题目的各项要求，相信以后再次进行程序设计的时候会得心应手。

第四篇：中国地质大学(武汉)空间数据结构实习报告

空间数据结构实习报告

学生姓名：孙国欢 班 学 号：113131-05 指导老师：周琪

中国地质大学信息工程学院

2015年10月

线简化算法的程序实现及比较研究

一、实习内容：程序实现两种或以上的线简化算法，并比较各种算法的优劣。

二、实习要求：程序实现以下四种线简化算法中的两种或以上。

三、实习原理

i.基于点数的线简化算法（Num of points）

ii.基于长度的线简化算法（Length）

iii.基于角度的线简化算法（Angle）

iv.基于垂距的线简化算法(Perpendicular distance）

v.Douglas-Peucker（1988）

vi.Whirlpool（1980）

四、实习过程与成果

过程分析：

这次空间数据结构实习主要是围绕几个课上讲的基本算法和Douglas-Peucker、Whirlpool算法来实现线简化算法。

我做了基于点数的线简化算法、基于长度的线简化算法、基于角度的线简化算法、Douglas-Peucker和Whirlpool算法。

前三个算法的思想十分明确，是利用C++中的点的坐标结合基本函数可以实现。Douglas-Peucker算法的基本思路是对每条曲线的首末点虚线连接一条直线，求所有点与直线的距离并求出最大距离Dmax，再用Dmax与限差d相比较然后进行取舍。Whirlpool算法则是利用每个点设定r值画圆进行分类和取舍，成果展示：

基于点数的线简化算法 point=3

基于长度的线简化算法 length=40

基于角度的线简化算法 angle=90°

DP算法 垂距d=20

Whirlpool算法 r=40

基于点数的线简化算法 point=3

基于长度的线简化算法 length=60

基于角度的线简化算法 angle=75°

DP算法 垂距d=30

Whirlpool算法 r=50

---------------分界线------------------

基于点数的线简化算法 point=3

基于长度的线简化算法 length=50

基于角度的线简化算法 angle=60°

Whirlpool算法 r=40 DP算法得线简化结果为点（39,62）

-------分界线-------------------

基于点数的线简化算法 point=4

基于长度的线简化算法 length=40

基于角度的线简化算法 angle=90°

DP算法 垂距d=20

Whirlpool算法 r=30

--------分界线------------------

基于点数的线简化算法 point=3

基于长度的线简化算法 length=30

基于角度的线简化算法 angle=60°

DP算法 垂距d=30

Whirlpool算法 r=25

五、思考与感想

实习思考：

针对基于点数的线简化算法、基于长度的线简化算法、基于角度的线简化算法、Douglas-Peucker和Whirlpool算法，我共采取了五组实验数据，分别表示五种图形数据。源数据1是一个普通的弯折直线图，源数据2是一个起伏相当明显且角度多变的图形，源数据3是一个闭合的多边形，源数据4是一个近乎一端开口的矩形，源数据5是一个弯折且有重叠的折线图。

我认为这五种情况的线性矢量数据采用不同的线简化算法产生的结果也决然不同。其中值得一提的是源数据3（闭合多边形）在Douglas-Peucker算法下简化为一个点，这与DP算法的原理有关，所有除首尾的点被舍去因而结果简化完只有一个顶点。而源数据4（一端开口的近矩形）在基于角度的线简化算法去angle=90°时完全简化成一个矩形，也反映了基于角度的线简化算法的原理使其去了四方顶点。

比较我所探索的这五种线简化方法：基于点数的线简化算法、基于长度的线简化算法、基于角度的线简化算法、Douglas-Peucker和Whirlpool算法。我认为它们都具有鲜明的优劣势。

① 基于点数的线简化算法：取相对应的隔点数并保留首尾点，方便快捷但效果一般

② 基于长度的线简化算法：取相对应的点与点的距离并保留首尾点，刨去了冗余的点，简化效果良好。

③ 基于角度的线简化算法：取相对应的点与点的角度并保留首尾点，基本上择弯取直，简化效果良好。

④ Douglas-Peucker算法：求所有点与对每条曲线的首末点连接的直线的距离并求出最大距离Dmax，再用Dmax与垂距d比较后取舍。舍去了一些线性矢量数据上的点，形成了鲜明的结果，但是过程比较冗杂。⑤ Whirlpool算法：对设定的半径r给每个点作圆并进行取舍，使线性矢量数据的点的分布更加清晰，刨去了密集区的重复点，但不简便。

实习感想：

通过这次空间数据结构实习，我学到了很多。在此次实习中，我对这门课有了更加深刻的认识，学会了把所学的理论知识和实践联系起来。

对于我来说不仅是设计算法来实现线简化算法，最为珍贵的是在我准备这次实习所巩固的以前不熟悉的知识。它培养了我们由书面文字要求到转化这种要求到现实模型的能力，即很大程度上培养了我们的建模能力，分析问题，总结归纳问题的能力。这次实习也遇到了一些难关，但它们给了我们思索的机会。我们通过克服这一个个困难，让我们重新又对目前脑子里所掌握的知识进行审理，进行了再次的纠正或者完善，这些都是书本上学不来的。理论联系实际就在这里自然地得到实现。这对我们巩固已学知识，锻炼实践动手能力大有裨益。

在这次实习中，我觉得我最大的收获就是学会了为了实现这些算法，我该如何去构建这样的框架。实习的这几周，我从只理解书面上的线简化算法原理，到现在实现这样的过程，中间也遇到了很多困难和挫折。在程序的编写过程中，也出现了很多错误，经过我认真修改，查阅资料，向老师和同学们请教，终于把那些错误都改正过来，最终使程序能够结合要求的算法正确的运行。我再通过绘制excel表格来进一步了解各种不同的线简化算法会出现什么样的结果。所以说，这次实习不仅是让我学到了各种线简化算法的方法，更重要的是它提高了我理论转化为实践的能力。谢谢老师在空间数据结构实习过程中给予的帮助。最后祝老师工作顺利，身体健康。

学生姓名：孙国欢

班 学 号：113131-05

中国地质大学信息工程学院 2015年10月

第五篇：中国地质大学《生产实习报告》

生产实习目的测量学实习是测量学教学的重要组成部分，其目的使学生巩固、扩大和加深从课堂学到的理论知识，获得实际测量工作的初步经验和基本技能，进一步掌握测量仪器的操作方法，提高计算和绘图能力，对测绘小区域大比例尺地形图的全过程有一个全面和系统的认识，会认识地形图，能够根据给定的地形图在实际中寻找到图上所示的点，并在实习的过程中增强其独立工作与团队协作意识，为今后解决实际工作中的有关测量问题打下坚实的基础。学生通过本次实习应达到如下要求：

1.掌握经纬仪、视距尺等测量仪器的操作方法;

2.掌握地形测图的基本方法，能够具有初步测绘小区域大比例尺地形图的工作能力;

3.能够根据给定的地形图在实际中寻找到图上所示的点;

4.各小组分工明确、通过合作完成测量任务，增强独立工作能力与团队协

生产实习时间及地点

1.地形图测绘实习地点：中国地质大学北区南望山 时间：2011年10月15日至2011年10月16日.2.地形图识图实习地点：九峰山 时间：2011年10月19日

实习小组信息

组别：地空学院061113班 测量3组

指导老师：XX

组员：XX、XX、XX、XX、XX组员分工：

选点与跑尺：XX

记录与计算：XX/XX

描点与绘图：XX

实习内容

（一）大比例尺地形图的测绘：

1.地点：中国地质大学北区南望山

2.任务：通过两天的地形图测绘实习，每小组要取得200个左右的测点数据，并根据得到的数据完成一幅比例尺1：500，等高距1m的30cmx30cm的地形图

3.内容：（1）2011年10月14日下午，刘甜甜、鲁凯跟老师去踩点.我和其他组员到学校出版社领仪器（经纬仪），工具及用品的准备（包括测量记录手簿、2H绘图铅笔、三棱尺、半圆仪、图板、计算器、直尺等基本物品）；

（2）2011年10月14日晚上，我、XX/XX按照使测绘更加方便、有效、快捷的原则，根据测区位置，在图板上布设控制点;我先按图纸对角画两条对角线，然后等距量取四条对角边，连线，各取每10cm每条边取点连线得到30cmx30cm的图根，然后XX按比例尺计算出控制点的位置，最后XX在图上找出对应坐标位置点出控制点，最后完成了全部展点工作。

（3）过程：

测区面积有150mx 150m，中间有一座小山丘，山丘上面有一个房子、毕业墙、一个圆柱体。控制点是已知高程(海拔)的点，我们需要在这些控制点上架设经纬仪，以它们为基准来测它与其他位置点的高差，进而推算位置点的高程(海拔)。因为控制点的个数有限，尤其是位置好的控制点更是稀少，所以我们必须要有抢占有利控制点的意识与冲动。只有如此，我们的测绘才会更加高效。实习的前一天，所有人都在抢占有利控制点上做了充分准备。2011年10月15早上因为运动会耽误了一点时间所以到中午我们组才这全部到达南望山，因此有利的控制点基本被占领了！但是为期两天的测量实习就这样开始了！

第一天大家都没有一点经验，我们找到了山上的房子旁边的一个控制点——43号点，XX用

他新的对中、整平方法快速对中整平了可是他说要用直尺测量房子的边长，我认为不妥！因为这就是和用经纬仪测距违背了！我提出了疑义，我们去看书不断的摸索，最后提出一个到后面才知道是错的方法！就是用两个控制点定出一个点！一天到下午测不了几个碎步点，分工也很乱！有时后我们队员都不知道做什么，后来，我们换到离43号点较近的21号点，准备测量，可是从早上到现在我们的测量方法一直在变，一直有争议，在这两个点测到得数据也不懂怎么用！到这时天色准备暗下来了！

老师看到我们组的进度缓慢就叫一个测得快的组的一名组员来帮忙，听着这名同学讲解，我们明白了整个测量的基本过程：

1：将架设好的经纬仪对准另一个控制点，调节水平度盘使读数为零。

2：让选点跑尺的组员选好碎步点，是山坡的，一般应该在大概认为同一高度选出若干个碎步点，立尺。

3：让观察者将经纬仪转向标尺读出上丝读数、中丝读数、下丝读数、水平度盘读数、竖直度盘读数，让记录员记录

4：计算者计算出上丝读数减下丝读数、用公式计算出实际距离、高程、根据比例尺算出图上距离，填入手簿，同时告诉绘图者角度、图上距离和高程。

5：绘图者根据所得到的数据用半圆仪、直尺、铅笔绘出碎步点标出高程。

明白整个过程之后我们知道之前的数据都作废了！太阳开始落山，我们赶快行动，天色真的已经很黑了，连看度盘读数都只能用手机照明才能看清!就这样在天完全黑之后我们只完成两个控制点的测量，我们托着疲惫的身体回来了，我们组设最后一组回来的，但是我们已经完全清楚明天我们该做什么、该怎么做，相信我们明天一定能完成任务！

经过昨天的教训2011年10月16日这天早上6点我们就起床，早早的到达了北区南望山，这一天我们是第一组到达的!我们有明确的分工，明确的测量步骤，明确的测量路。我们的效率很高，第一个地点是上山的路口阶梯从6号点到22号点选择拐点....。就这样一片片山坡、山谷、低地....被我们选点、观察、记录、计算、绘图描绘出来了。

就这样到了两点我们因为早上都只吃了一个饼而体力不支了！个个脸色惨白，又不能休息，因为我们还有很多点没测。这时食堂只有面食了！我们只好轮流去吃，去了两个组员，就在这时我们发现39号点的数据全部有误，原来是所标的39号点本来就是有误的！我们很气愤，但是我们必须坚持，我们继续测到35号点终于测完了！这时我们已经累得趴在山坡上了！看看表离交仪器的时间还有一个小时,强忍着疲惫、饥饿、困意我们扛着感觉比以前重了很多的仪器到学校出版社交了，让我们感到欣慰的是还有许多组还没测完！

心得体会

1.经过这次实习让我感受到学会理论和实际的结合是很重要且是一个循序渐进的过程。要达到实践贯通，把课本知识很好的运用到实际中是会受到许多挫折的，比如我们组在实习第一天基本没什么收获。我作为计算员我用到的公式有：....., 式中Hi是碎步点高程，Da1是测站至碎步点的水平距离，k 视距乘常数；t为（尺间距）上丝、下丝读数之差；l为中丝读数；i为仪器高；a为竖直角。可是在实际计算时不能死搬硬套公式，比如a角是竖直角当这角是90度是用计算器算时是输入0度，当这角大于90度时用这角减去90度所得的角度加上负号在输入，小于是用90度减去所得读数直接输入，还有一些简便一点的计算方法也是实际操作后才慢慢摸索出来的，同样绘图员、记录员、观察员、跑尺选点员都会遇到不一样的实际问题。所以说实习是把我们从课本学到的知识用到实际的一个过程。

2.通过这次实习也让我感受到以前的艰苦条件下做一幅全国地形图是多么的困难和来之不易啊！也为我们作为地大人能为人们作出的贡献而感到自豪和敬佩！

(二)持图实地跑点实习：

1.地点：九峰山

2.任务：到达图上表示的指定地点中的至少5个，将实地编号标注到地图上.3.内容：

(1)全组成员集中分析地图，确定初始路线;

(2)按照初始路线寻找指定点;

(3)过程：

2011年10月19日晨，我们从中国地质大学出版社拿到的不再是经纬仪、三角架和视距尺，而是一张九峰山地区的地图。是一张已经泛黄的，1973年绘成的地图，上面采用的最接近成图时间的数据是1969年的。图上画了许多个框框，它们标注的就是我们组今天要到的地方。虽然每个小组的地图是一样的，但上面被标注的点却是不一样的。也就是说，我们的目的地可能有重合，但不会是每个目的地都一样。因此，各组之间几乎独立的，合作被限定在了组内。老师告诉我们，图上表示的一个池塘已经填掉了，变成了农田，有座桥已经不存在了，图上表示的湖北省林业科学研究所已经更改了地址。这加重了我们对这张地图的怀疑，其他的地方就没有变化吗?我们要找的点在实地被标注在电线杆、石板桥、池塘壁等地方，而且这些点上是有编号的，我们只有真正到过这些点才能知道它们的编号。按照要求，我们要把这些编号标注在地图上，我们要至少找到5个。

今天我们从地大出版社坐车出发到一个加油站下，这里就是潜力村也就是出发点。组员们捧着这张地图走向了一片未知区域。地图成了我们不会迷路的唯一保障。跟着大部队，我们翻过了第一座山，山的背后是公墓。很快我们到了第一个路口，我们要找的一个点在向东的方向，其他点在向西的方向，而且那个独立的点要翻过一座高山才会到达。分析了利弊后，我们决定放弃它。放弃它就意味着放弃大部队，我们组成了少数走向西道路的小组。对比了图上池塘的位置，我们终于找到了它，地图告诉我们，这里有地大的点。在一个田边的电线杆上，我们看到了“地大78”。这是我们的第一个成果。但是这次我们又犯了一个错误：我们把图上的点当作我们要找的点！费了很多时间在这附近找等到后来的一组来了问明之后才知道这本来就是我们要找的点！

沿着池塘边的公路，我们继续前行，过了1个比较大的村子。重新看了一遍地图，对比了实地，我们还问了当地的老乡，我们要找到一个祠堂然后找到一个村子，我们很快看到了远方我们要找的祠堂和村子。为了抄近路，我们进了稻田。秋天的稻田已是十分空旷，但湖北多湖的特点注定这里是泥泞的。选择了走农田，那么可能出现的点就只能在电线杆上。直到走出稻田，我们也没有发现要找的点。我们又经过了一个村子来到这村后一座小山，用地形图所给的正北方向结合刚升起不久的太阳代表的东边找到了有一个点就在这座村子旁的另一个村子里，确定之后我们飞奔去哪里，在途中碰上了另一个小组，我们就和并成一个组，在这个村我们顺利的找到了21号点，这点非常隐蔽而且也被破坏得很厉害.这时我们遇到一个艰难的选择，该是北走去曹家村，还是向西走去下刘村？去了下刘村就过了几个点，可是到了下刘村就接近目的地了！经过讨论我们决定还是去了下刘村，经过下刘村是我们问水库在哪里！老乡说要经过涵洞，我们就经过了涵洞，到了一片山林，我们非常艰难的穿过这片充满荆棘的山林又到了一片长满杂草的田野，过了这片田野，我们每个人的衣服、鞋带都插有许多不知名的刺！

我们到达水库时所有的组员又累又饿，在这里即找不到点也为往哪里走而迷茫，本来一个点找不到十几分钟就应该放弃，但是由于这个错我们一直以问当地的老乡为判断所走的方向是否正确，当我们找到100号点时，已经没有时间停留了，我们奔跑在途中找到145号点，往前走就是上山的小路，这就是老师说的通往老林科所的捷径！我们继续奔跑！体力好的跑在前面但也带着重物，同时不忘告诉后面的队员往哪里走，就这样看到一条马路上标有地大CUG字符，向下走看到一只锁着的狗一直在叫，最终看到了在老林科所等待的邹蓉老师，能看到

她真的很高兴！随后队员们全部到齐！然后跟随老师到达土桥村的一个已经废弃的大加油站，在这里能看到其他组，在这里和他们交流，等了十几分钟等到学校派来的车，坐上车，大家都累了，已经没有刚来时在车上的喧闹、许多人已经在这回校的车上进入梦乡！持图实地跑点实习就这样落下帷幕。

心得体会

1.经过这次跑点实习，是我认识到要准确看懂一幅地形图并能把它和实际地形正确符合起来确实是一件不容易的事

2.在跑点过程中队员之间一定要团结协作，不能有争执

3.在这次实习中我们除了感到累，更重要的是我们同时也感受到了运用智慧的乐趣、团结协作的快乐、成功在规定时间之内到达目的地欢喜。

误我们组失去了许多时间，最后我们终于决定往蚂蚁峰走，这时得到另一些组已经到达使我们不免有一些丧气，经过一个十字路口时，往前就有一个点，可是这是一座挖空的山，我们想碰碰运气可是终究找不到，回到十字路口，这时我们这个合并组分别往相反的方向走！当我们感觉我们走的方向是对的时，我们跑步前进，不，可以说是狂奔！过往的山中美景、田园风光都被我们忽略了，我们的目标只有一个——老林科所。