資料結構實驗報告
一.實驗內容:
實現哈夫曼編碼的生成演算法。
二.實驗目的:
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;
實驗測試結果及結果分析
(一)測試結果
(二)結果分析
(略)
實驗總結
(略)