第一篇：中国地质大学(武汉)空间数据结构实习报告
空间数据结构实习报告
学生姓名：孙国欢 班 学 号：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月
第二篇：中国地质大学(武汉)数据结构报告
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语言进行程序设计能力。 第一次设计这么多程序，感觉压力很大，很难完成，虽然看起来设计流程感觉很轻松，但是正真完成的时候并不能通过程序表达出来。通过同学和老师的帮助最终还是完成了自己的程序设计，虽然程序还不是很完美，但能满足题目的各项要求，相信以后再次进行程序设计的时候会得心应手。 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 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 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 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 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 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++语言描述)》 殷人昆 等编著，清华大学出版社 《数据结构题集》严蔚敏，吴伟民 编著，清华大学出版社 《数据结构及应用算法》严蔚敏，陈文博 编著，清华大学出版社 中国地质大学（武汉）位于武汉东湖国家自主创新示范区腹地，东湖之畔，南望山麓，占地1700余亩。学校拥有国家4A级旅游景区——逸夫博物馆，是全国文明单位、湖北省最佳文明单位。校园环境优美，教育、科研、学术氛围浓厚，拥有现代化的教学楼群、图书馆、学生公寓和近万台随时上网的计算机等相关配套设施，为莘莘学子提供了良好的学习、生活和成长的环境。 办学思想 学校以温家宝总理为母校的题词“艰苦朴素，求真务实”作为校训。在总结办学经验、展望未来发展趋势的基础上，提出了“三步走”发展战略，其中将“建设地球科学一流、多学科协调发展的高水平大学”确立为办学的阶段性目标，将“建设地球科学领域世界一流大学”确立为办学的长远目标。学校坚持突出办学特色，完善学科体系，努力为解决我国和人类社会面临的资源环境问题提供高水平的人才和科技支撑。办学条件 学校现有教职员工3195人，其中，中国科学院院士8人，博士生导师183人，教授420人，副教授497人，俄罗斯自然科学院外籍院士5人，俄罗斯工程院外籍院士5人。国家“千人计划”入选4人，“长江学者奖励计划”特聘教授8人，国家杰出青年科学基金获得者9人，“楚天学者计划”入选教授29人。近年来，学校新增国家创新研究群体2个，教育部创新团队3个，国家级教学团队4个，国家级教学名师1人，湖北省教学名师7人。2008年，我校成秋明教授继我校赵鹏大院士之后，成为荣获国际数学地质学会最高奖——克伦宾奖的第二个亚洲人。 学校现有各类科研机构、实验室、研究院（所、中心）86个，其中国家重点实验室2个，国家地方联合工程实验室1个，省部级重点实验室、工程中心、人文社科研究基地15个。学校图书馆拥有丰富的文献资源，形成了以科技文献为主体、地球科学类文献为特色的馆藏体系。学校拥有纸质图书资料170.46万册，电子图书7000GB，期刊1500余种，中外文数据库20个。从20世纪50年代起，学校相继在周口店、北戴河、三峡等地建立了教学实习基地。其中周口店野外实习基地被誉为“地质工程师的摇篮”，已建成为“全国地质实验（实践）教学示范中心”和“国家基础学科人才培养能力（野外实践）基地”；依托三峡秭归实习基地建设了教育部长江三峡库区地质灾害研究中心，其影响辐射全国。 学科布局 学校大力构建以地球系统科学为主导的学科体系，积极发展应用科学、前沿科学，以及与社会经济发展密切相关的信息、纳米、材料、生物、能源、环保等新兴交叉学科。学校现有8个国家级重点学科和17个省部级重点学科，其中“地质资源与地质工程”与“地质学”2个一级学科全国排名第一；有17个学院(课部)、60个本科专业；拥有国家地质学理科人才培养基地和国土资源部地质工科人才培养基地；拥有9个博士后科研流动站，13个一级学科博士点和38个一级学科硕士点；有工程硕士、MBA、MPA、MFA、J.M等10个专业学位授予权，其中工程硕士专业包涵19个工程领域。 人才培养 学校拥有“学士－硕士－博士”完整的人才培养体系，有学生6.4万余人，其中全日制在校学生近2.5万人，非全日制专业学位研究生2800余人，成教及网络教育注册学生3.9万余人，各类留学生400余人。学校通过强化教学管理，深化教学改革，加大与国外高校联合培养的力度，创新推荐免试攻读硕士、博士学位研究生的机制，建立了创新人才和特殊人才的培养制度。学校已建成一大批国家级和省级精品课程，2004年学校以优异的成绩通过了教育部本科教学工作水平评估和湖北省研究生培养条件评估。学校与中国科学院9家科研院所、中国地质科学院组建了“科教战略联盟”，开展深度合作，联合培养本科生和研究生。学校设立了“李四光学院”和地球科学“菁英班”，致力于培养地学类拔尖创新人才。学校建立了国内一流的现代远程教育体系，广泛适应各类学生多元化、个性化的学习需求，学校远程继续教育学院连续多年在教育总评榜中被评为“十佳网络教育学院”。 学校按照“品德高尚、基础厚实、专业精深、知行合一”的人才培养要求，全面实施教育教学质量工程，启动了“卓越工程师教育培养计划”、国家大学生创新性实验计划、“李四光计划”、“池际尚计划”等。我校学生在具有广泛影响力的全国挑战杯大赛、数学建模大赛、电子设计大赛等高水平赛事中屡获佳绩。学校通过国家助学贷款政策每年为学生贷款达2000余万元，国家、学校、社会每年为我校学生提供的奖励资助金额达2500万元。学校除设立学生普遍享有的奖学金外，还设立了“地质之光奖学金”在内的50余项专项奖学金。 学校把弘扬优良体育传统与开展艰苦奋斗教育相结合，逐步形成了特色鲜明的体育体系。我校学生在国际国内重大体育比赛中，累计取得金牌150余枚，银铜牌350余枚，连续5届获得全国大学生运动会“校长杯”。2006年10月，学校成功举办第九届世界大学生羽毛球锦标赛。2012年5月，学校登山队成功登顶珠峰，成为我国第一支登上世界最高峰的大学登山队。 科学研究 学校历来十分重视科技工作。近5年，学校主持“973”项目及专题、“863”项目及子课题、国家自然科学基金和社会科学基金项目等各类国家级项目600余项，科研经费稳步增长。殷鸿福院士主持完成的确定全球二叠系-三叠系界线层型“金钉子”（国际标准）的科技成果荣获“2001年中国基础研究十大进展”、“2001中国高等学校十大科技进展”和“2001年中国十大科技新闻”的殊荣。我校师生以第一作者身份在国际杂志Nature上发表论文4篇。5年来，学校共有50项科研成果获得省部级以上科技奖励，其中，国家科技进步特等奖1项，国家自然科学二等奖2项，国家科技进步二等奖4项。学校主办的《地球科学》中文版被国际著名检索系统EI光盘版收录，英文版被国际著名检索系统SCIE收录，学报（社会科学版）进入《中文核心期刊要目总揽》和CSSCI。 学校科学研究始终面向国民经济建设主战场，服务经济社会发展，积极参与找矿突破战略行动，引领行业科技发展，培养和输送技术骨干和管理人才。学校作为唯一高校参与了中国大陆科学钻探工程，拥有军工项目科研生产完整资质，成立了2个“教育部深空探测联合研究中心”预研分中心，参与了“嫦娥工程”月球探测数据处理和月球应用研究，自主研发的MAPGIS软件成功应用于“神舟”系列载人航天搜救。学校坚持开展产学研合作，推进协同创新体系建设。2008年汶川大地震发生之后，学校及时组织科技赈灾专家组奔赴灾区，为灾区预防次生灾害、做好灾后重建与城镇选址等工作提供了技术支持。 国际交流 学校积极开展对外学术、科技和文化交流，先后与美国、法国、澳大利亚、俄罗斯等国家的100多所大学签订了友好合作协议。近年来，学校公派出国访问、留学，攻读硕士、博士学位的师生每年超过350人次，邀请来校访问、讲学、与会的境外专家每年超过300人次。学校2个项目被列入“高等学校学科创新引智计划”（即“111工程”），以我校为支撑建立了美国布莱恩特大学孔子学院、美国阿尔弗莱德大学孔子学院、保加利亚大特尔诺沃大学孔子学院，建成了“中匈联合环境科学与健康实验室”和“中美联合非开挖工程研究中心”。 桃李芬芳 60年来，学校人才辈出。毕业生中走出了以温家宝总理为代表的一大批社会管理精英，成长了以“嫦娥工程”首席科学家欧阳自远等为代表的29位两院院士，涌现了国家体育场馆“鸟巢”总工程师李久林为代表的一大批工程奇才……广大毕业生正以自身的努力为学校赢得荣誉、提供支持。同时，学校也将为解决经济社会可持续发展问题，谋求人类与地球的和谐发展做出更加卓越的贡献！第三篇：中国地质大学数据结构实习报告
第四篇：数据结构实习报告(中国地质大学)
第五篇：中国地质大学(武汉)
点击咨询 