數據結構實驗報告

數據結構實驗報告1

一.實驗內容：

實現哈夫曼編碼的生成算法。

二.實驗目的：

1、使學生熟練掌握哈夫曼樹的生成算法。

2、熟練掌握哈夫曼編碼的方法。

三.問題描述：

已知n個字符在原文中出現的頻率，求它們的哈夫曼編碼。

1、讀入n個字符，以及字符的權值，試建立一棵Huffman樹。

2、根據生成的Huffman樹，求每個字符的Huffman編碼。並對給定的待編碼字符序列進行編碼，並輸出。

四.問題的實現

(1)郝夫曼樹的存儲表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //動態分配數組存儲郝夫曼樹

郝夫曼編碼的存儲表示

typedef char* *HuffmanCode;//動態分配數組存儲郝夫曼編碼

(2)主要的實現思路：

a.首先定義郝夫曼樹的存儲形式，這裏使用了數組

b.用select遍歷n個字符，找出權值最小的兩個

c.構造郝夫曼樹HT，並求出n個字符的'郝夫曼編碼HC

總結

1.基本上沒有什麼太大的問題，在調用select這個函數時，想把權值最小的兩個結點的序號帶回HuffmanCoding，所以把那2個序號設置成了引用。

2.在編程過程中，在什麼時候分配內存，什麼時候初始化花的時間比較長

3.最後基本上實現後，發現結果仍然存在問題，經過分步調試，發現了特別低級的輸入錯誤。把HT[i]ht=HT[s1]ht+HT[s2]ht;中的s2寫成了i

附：

//動態分配數組存儲郝夫曼樹

typedef struct{

int weight; //字符的權值

int parent,lchild,rchild;

}HTNode,*HuffmanTree;

//動態分配數組存儲郝夫曼編碼

typedef char* *HuffmanCode;

//選擇n個(這裏是k=n)節點中權值最小的兩個結點

void Select(HuffmanTree &HT,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && HT[i]nt!=0)i++;

//下面選出權值最小的結點，用s1指向其序號

s1=i;

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

{

if(HT[i]nt==0&&HT[i]ht

}

//下面選出權值次小的結點，用s2指向其序號

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

{

if(HT[i]nt==0&&i!=s1)break;

}

s2=i;

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

{

if(HT[i]nt==0&&i!=s1&&HT[i]ht

}

}

//構造Huffman樹，求出n個字符的編碼

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n個葉子n-1個結點

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用，預分配m+1個單元

HuffmanTree p=HT+1;

w++; //w的號單元也沒有值，所以從號單元開始

for(i=1;i<=n;i++,p++,w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i,++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

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

{

Select(HT,i-1,s1,s2); //選出當前權值最小的

HT[s1]nt=i;

HT[s2]nt=i;

HT[i]ld=s1;

HT[i]ld=s2;

HT[i]ht=HT[s1]ht+HT[s2]ht;

}

//從葉子到根逆向求每個字符的郝夫曼編碼

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個字符編碼的頭指針變量

cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間

cd[n-1]='';//編碼結束符

for(i=1;i<=n;i++) //逐個字符求郝夫曼編碼

{

start=n-1; //編碼結束符位置

for(c=i,f=HT[i]nt;f!=0;c=f,f=HT[f]nt) //從葉子到根逆向求編碼

{

if(HT[f]ld==c)cd[--start]='0';

else

cd[--start]='1';

}

HC[i]=(char*)malloc((n-start)*sizeof(char)); //爲第i個字符編碼分配空間

strcpy(HC[i],&cd[start]);//從cd複製編碼到HC

}

free(cd); //釋放工作空間

}

void main

{ int n,i;

int* w; //記錄權值

char* ch; //記錄字符

HuffmanTree HT;

HuffmanCode HC;

cout<<"請輸入待編碼的字符個數n=";

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //記錄權值，號單元未用

ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號單元未用

cout<<"依次輸入待編碼的字符data及其權值weight"<

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

{

cout<<"data["<

}

數據結構實驗報告2

一、實驗目的及要求

1)掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們。

本實驗訓練的要點是“棧”和“隊列”的觀點;

二、實驗內容

1) 利用棧，實現數制轉換。

2) 利用棧，實現任一個表達式中的語法檢查(選做)。

3) 編程實現隊列在兩種存儲結構中的基本操作(隊列的初始化、判隊列空、入隊列、出隊列);

三、實驗流程、操作步驟或核心代碼、算法片段

順序棧：

Status InitStack(SqStack &S)

{

=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!)

return ERROR;

=;

ksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free();

return OK;

}

Status ClearStack(SqStack &S)

{

=;

return OK;

}

Status StackEmpty(SqStack S)

{

if(==)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return ;

}

Status GetTop(SqStack S,ElemType &e)

{

if(>=ksize)

{

=(ElemType *)realloc(,(ksize+STACKINCREMENT)*sizeof(ElemType));

if(!) return ERROR;

=+ksize;

ksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(>=ksize)

{

=(ElemType *)realloc(,(ksize+STACKINCREMENT)*sizeof(ElemType));

if(!)

return ERROR;

=+ksize;

ksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(==)

return ERROR;

e=*;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

p=(ElemType *)malloc(sizeof(ElemType));

if(!p) return ERROR;

p=;

while(p!=)//上面一個...

{

p--;

printf("%d ",*p);

}

return OK;

}

Status Compare(SqStack &S)

{

int flag,TURE=OK,FALSE=ERROR;

ElemType e,x;

InitStack(S);

flag=OK;

printf("請輸入要進棧或出棧的元素：");

while((x= getchar)!='#'&&flag)

{

switch (x)

{

case '(':

case '[':

case '{':

if(Push(S,x)==OK)

printf("括號匹配成功! ");

break;

case ')':

if(Pop(S,e)==ERROR || e!='(')

{

printf("沒有滿足條件 ");

flag=FALSE;

}

break;

case ']':

if ( Pop(S,e)==ERROR || e!='[')

flag=FALSE;

break;

case '}':

if ( Pop(S,e)==ERROR || e!='{')

flag=FALSE;

break;

}

}

if (flag && x=='#' && StackEmpty(S))

return OK;

else

return ERROR;

}

鏈隊列：

Status InitQueue(LinkQueue &Q)

{

t ==

(QueuePtr)malloc(sizeof(QNode));

if (!t) return ERROR;

t->next = NULL;

return OK;

}

Status DestoryQueue(LinkQueue &Q)

{

while(t)

{

=t->next;

free(t);

t=;

}

return OK;

}

Status QueueEmpty(LinkQueue &Q)

{

if(t->next==NULL)

return OK;

return ERROR;

}

Status QueueLength(LinkQueue Q)

{

int i=0;

QueuePtr p,q;

p=t;

while(p->next)

{

i++;

p=t;

q=p->next;

p=q;

}

return i;

}

Status GetHead(LinkQueue Q,ElemType &e)

{

QueuePtr p;

p=t->next;

if(!p)

return ERROR;

e=p->data;

return e;

}

Status ClearQueue(LinkQueue &Q)

{

QueuePtr p;

while(t->next )

{

p=t->next;

free(t);

t=p;

}

t->next=NULL;

->next=NULL;

return OK;

}

Status EnQueue(LinkQueue &Q,ElemType e)

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof (QNode));

if(!p)

return ERROR;

p->data=e;

p->next=NULL;

->next = p;

=p; //p->next 爲空

return OK;

}

Status DeQueue(LinkQueue &Q,ElemType &e)

{

QueuePtr p;

if (t == )

return ERROR;

p = t->next;

e = p->data;

t->next = p->next;

if ( == p)

= t; //只有一個元素時(不存在指向尾指針)

free (p);

return OK;

}

Status QueueTraverse(LinkQueue Q)

{

QueuePtr p,q;

if( QueueEmpty(Q)==OK)

{

printf("這是一個空隊列! ");

return ERROR;

}

p=t->next;

while(p)

{

q=p;

printf("%d<- ",q->data);

q=p->next;

p=q;

}

return OK;

}

循環隊列：

Status InitQueue(SqQueue &Q)

{

=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

if(!)

exit(OWERFLOW);

t==0;

return OK;

}

Status EnQueue(SqQueue &Q,QElemType e)

{

if((+1)%MAXQSIZE==t)

return ERROR;

[]=e;

=(+1)%MAXQSIZE;

return OK;

}

Status DeQueue(SqQueue &Q,QElemType &e)

{

if(t==)

return ERROR;

e=[t];

t=(t+1)%MAXQSIZE;

return OK;

}

int QueueLength(SqQueue Q)

{

return(t+MAXQSIZE)%MAXQSIZE;

}

Status DestoryQueue(SqQueue &Q)

{

free();

return OK;

}

Status QueueEmpty(SqQueue Q) //判空

{

if(t ==)

return OK;

return ERROR;

}

Status QueueTraverse(SqQueue Q)

{

if(t==)

printf("這是一個空隊列!");

while(t%MAXQSIZE!=)

{

printf("%d<- ",[t]);

t++;

}

return OK;

}

數據結構實驗報告3

《數據結構與算法》實驗報告

專業 班級 姓名 學號

　　實驗項目

實驗一 二叉樹的應用

　實驗目的

1、進一步掌握指針變量的含義及應用。

2、掌握二叉樹的結構特徵，以及各種存儲結構的特點及使用範圍。

3、掌握用指針類型描述、訪問和處理二叉樹的運算。

　實驗內容

題目1:編寫一個程序，採用一棵二叉樹表示一個家譜關係。要求程序具有如下功能：

（1）用括號表示法輸出家譜二叉樹，

（2）查找某人的所有兒子，

（3）查找某人的所有祖先。

算法設計分析

（一）數據結構的定義

爲了能夠用二叉樹表示配偶、子女、兄弟三種關係，特採用以下存儲關係，則能在二叉樹上實現家譜的各項運算。

二叉樹型存儲結構定義爲：

typedef struct SNODE

{char name[MAX]; //人名

struct SNODE *left;//指向配偶結點

struct SNODE *right; //指向兄弟或子女結點

}FNODE;

（二）總體設計

實驗由主函數、家譜建立函數、家譜輸出函數、兒子查找函數、祖先查找函數、結點定位函數、選擇界面函數七個函數共同組成。其功能描述如下：

（1）主函數：統籌調用各個函數以實現相應功能

void main()

（2）家譜建立函數：與用戶交互建立家族成員對應關係

void InitialFamily(FNODE *&head) //家譜建立函數

（3）家譜輸出函數：用括號表示法輸出家譜

輸出形式爲：父和母（子1和子妻1（孫1），子2和子妻2（孫2））

void PrintFamily(FNODE *head) //家譜輸出函數

（4）兒子查找函數：在家譜中查找到某人所有的子女並輸出，同時也能辨別出其是否爲家族成員與是否有子女

void FindSon(FNODE *b,char p[]) //兒子查找函數

（5）祖先查找函數：在家譜中查找到某人所有的祖先並輸出，同時也能辨別出其是否爲家族中成員。

int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數

（6）結點定位函數：在家譜中找到用戶輸入人名所對應的結點。

FNODE *findnode(FNODE *b,char p[]) //結點定位函數

（7）選擇界面函數：爲便於編寫程序，將用戶選擇部分獨立爲此函數。

void PRINT(int &n)

（三）各函數的詳細設計：

void InitialFamily(FNODE *&head) //家譜建立函數

1：首先建立當前人的信息，將其左右結點置爲空，

2：然後讓用戶確定其是否有配偶，如果沒有配偶，則當前程序結束，

3：如果有則建立其配偶信息，並將配偶結點賦給當前人的左結點；

4：再讓用戶確定其是否有子女，如果有則遞歸調用家譜建立函數建立子女結點，並將其賦給配偶結點的下一個右結點。

5：如無，則程序結束

void PrintFamily(FNODE *head) //家譜輸出函數

1：首先判斷當前結點是否爲空，如果爲空則結束程序；

2：如果不爲空，則輸出當前結點信息，

3：然後判斷其左結點（配偶結點）是否爲空，如不爲空則輸出“和配偶信息。

4：再判斷配偶結點的右結點是否爲空，如不爲空則遞歸調用輸出其子女信息，最後輸出“）”；

5：當配偶結點爲空時，則判斷其右結點（兄弟結點）是否爲空

6：如果不爲空，則輸出“，”，並遞歸調用輸出兄弟信息

　7程序結束

FNODE *findnode(FNODE *b,char p[]) //結點定位函數

1：當前結點是否爲空，爲空則返回空；

2：如果和查找信息相同，則返回當前結點；

3：如不然，則先後遞歸訪問其左結點，再不是則遞歸訪問右結點

void FindSon(FNODE *b,char p[]) //兒子查找函數

1：在家譜中定位到要查找的結點，如無則輸出“查找不到此人”

2：判斷其配偶結點與子女結點是否爲空，爲空則輸出“無子女”

3：不爲空則輸出其配偶結點的所有右結點（子女結點）。

int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數

1：先在家譜中定位到要查找的結點，如爲空輸出“不存在此人”，程序結束

2：先將父母結點入棧，當棧爲空時程序結束，

3：棧不爲空時，判斷棧頂元素是否已訪問過，

4：訪問過，再判斷是否爲查找結點，如是則輸出棧中保存的其祖先結點，並濾過其兄弟結點不輸出；不是查找結點，則退棧一個元素

5：未訪問過，則取當前棧頂元素，置訪問標誌——1，同時取其右結點

6：棧不爲空或當前所取結點不爲空時，轉到2；

實驗測試結果及結果分析

（一）測試結果

（二）結果分析

（略）

實驗總結

（略）