第一篇：中國地質大學(武漢)空間數據結構實習報告

空間數據結構實習報告

學生姓名：孫國歡 班 學 號：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 #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++語言描述)》 殷人昆 等編著，清華大學出版社 《數據結構題集》嚴蔚敏，吳偉民 編著，清華大學出版社 《數據結構及應用算法》嚴蔚敏，陳文博 編著，清華大學出版社

第五篇：中國地質大學(武漢)

中國地質大學（武漢）位于武漢東湖國家自主創新示范區腹地，東湖之畔，南望山麓，占地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位兩院院士，涌現了國家體育場館“鳥巢”總工程師李久林為代表的一大批工程奇才……廣大畢業生正以自身的努力為學校贏得榮譽、提供支持。同時，學校也將為解決經濟社會可持續發展問題，謀求人類與地球的和諧發展做出更加卓越的貢獻！