第一篇：中國地質大學數據結構實習報告

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.在這次實習中我們除了感到累，更重要的是我們同時也感受到了運用智慧的樂趣、團結協作的快樂、成功在規定時間之內到達目的地歡喜。

誤我們組失去了許多時間，最后我們終于決定往螞蟻峰走，這時得到另一些組已經到達使我們不免有一些喪氣，經過一個十字路口時，往前就有一個點，可是這是一座挖空的山，我們想碰碰運氣可是終究找不到，回到十字路口，這時我們這個合并組分別往相反的方向走！當我們感覺我們走的方向是對的時，我們跑步前進，不，可以說是狂奔！過往的山中美景、田園風光都被我們忽略了，我們的目標只有一個——老林科所。