數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1
一.實(shí)驗(yàn)內(nèi)容：
實(shí)現(xiàn)哈夫曼編碼的生成算法。
二.實(shí)驗(yàn)?zāi)康模?/strong>
1、使學(xué)生熟練掌握哈夫曼樹的生成算法。
2、熟練掌握哈夫曼編碼的方法。
三.問題描述：
已知n個(gè)字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。
1、讀入n個(gè)字符，以及字符的權(quán)值，試建立一棵Huffman樹。
2、根據(jù)生成的Huffman樹，求每個(gè)字符的Huffman編碼。并對(duì)給定的待編碼字符序列進(jìn)行編碼，并輸出。
四.問題的實(shí)現(xiàn)
(1)郝夫曼樹的存儲(chǔ)表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼樹
郝夫曼編碼的存儲(chǔ)表示
typedef char* *HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼編碼
(2)主要的實(shí)現(xiàn)思路：
a.首先定義郝夫曼樹的存儲(chǔ)形式，這里使用了數(shù)組
b.用select遍歷n個(gè)字符，找出權(quán)值最小的兩個(gè)
c.構(gòu)造郝夫曼樹HT，并求出n個(gè)字符的郝夫曼編碼HC
總結(jié)
1.基本上沒有什么太大的問題，在調(diào)用select這個(gè)函數(shù)時(shí)，想把權(quán)值最小的兩個(gè)結(jié)點(diǎn)的序號(hào)帶回HuffmanCoding，所以把那2個(gè)序號(hào)設(shè)置成了引用。
2.在編程過程中，在什么時(shí)候分配內(nèi)存，什么時(shí)候初始化花的時(shí)間比較長(zhǎng)
3.最后基本上實(shí)現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級(jí)的.輸入錯(cuò)誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫成了i
附：
//動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼樹
typedef struct{
int weight; //字符的權(quán)值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼編碼
typedef char* *HuffmanCode;
//選擇n個(gè)(這里是k=n)節(jié)點(diǎn)中權(quán)值最小的兩個(gè)結(jié)點(diǎn)
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i<=k && HT[i].parent!=0)i++;
//下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號(hào)
s1=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&HT[i].weight
}
//下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號(hào)
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&i!=s1)break;
}
s2=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&i!=s1&&HT[i].weight
}
}
//構(gòu)造Huffman樹，求出n個(gè)字符的編碼
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個(gè)葉子n-1個(gè)結(jié)點(diǎn)
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號(hào)單元未用，預(yù)分配m+1個(gè)單元
HuffmanTree p=HT+1;
w++; //w的號(hào)單元也沒有值，所以從號(hào)單元開始
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); //選出當(dāng)前權(quán)值最小的
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//從葉子到根逆向求每個(gè)字符的郝夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個(gè)字符編碼的頭指針變量
cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間
cd[n-1]='';//編碼結(jié)束符
for(i=1;i<=n;i++) //逐個(gè)字符求郝夫曼編碼
{
start=n-1; //編碼結(jié)束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //從葉子到根逆向求編碼
{
if(HT[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char)); //為第i個(gè)字符編碼分配空間
strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼到HC
}
free(cd); //釋放工作空間
}
void main
{ int n,i;
int* w; //記錄權(quán)值
char* ch; //記錄字符
HuffmanTree HT;
HuffmanCode HC;
cout<<"請(qǐng)輸入待編碼的字符個(gè)數(shù)n=";
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //記錄權(quán)值，號(hào)單元未用
ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號(hào)單元未用
cout<<"依次輸入待編碼的字符data及其權(quán)值weight"<
for(i=1;i<=n;i++)
{
cout<<"data["<
}
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告2
一、實(shí)驗(yàn)?zāi)康募耙?/strong>
1)掌握棧和隊(duì)列這兩種特殊的'線性表，熟悉它們的特性，在實(shí)際問題背景下靈活運(yùn)用它們。
本實(shí)驗(yàn)訓(xùn)練的要點(diǎn)是“�！焙汀瓣�(duì)列”的觀點(diǎn);
二、實(shí)驗(yàn)內(nèi)容
1) 利用棧，實(shí)現(xiàn)數(shù)制轉(zhuǎn)換。
2) 利用棧，實(shí)現(xiàn)任一個(gè)表達(dá)式中的語法檢查(選做)。
3) 編程實(shí)現(xiàn)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作(隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、出隊(duì)列);
三、實(shí)驗(yàn)流程、操作步驟或核心代碼、算法片段
順序棧：
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(SqStack &S)
{
free(S.base);
return OK;
}
Status ClearStack(SqStack &S)
{
S.top=S.base;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.base==S.top)
return OK;
return ERROR;
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
Status GetTop(SqStack S,ElemType &e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Push(SqStack &S,ElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackTraverse(SqStack S)
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=S.top;
while(p!=S.base)//S.top上面一個(gè)...
{
p--;
printf("%d ",*p);
}
return OK;
}
Status Compare(SqStack &S)
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
printf("請(qǐng)輸入要進(jìn)�；虺鰲５脑兀�");
while((x= getchar)!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf("括號(hào)匹配成功! ");
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;
}
鏈隊(duì)列：
Status InitQueue(LinkQueue &Q)
{
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
if(Q.front->next==NULL)
return OK;
return ERROR;
}
Status QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
if(!p)
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
while(Q.front->next )
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->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;
Q.rear->next = p;
Q.rear=p; //p->next 為空
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front; //只有一個(gè)元素時(shí)(不存在指向尾指針)
free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
if( QueueEmpty(Q)==OK)
{
printf("這是一個(gè)空隊(duì)列! ");
return ERROR;
}
p=Q.front->next;
while(p)
{
q=p;
printf("%d<- ",q->data);
q=p->next;
p=q;
}
return OK;
}
循環(huán)隊(duì)列：
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
exit(OWERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
int QueueLength(SqQueue Q)
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空
{
if(Q.front ==Q.rear)
return OK;
return ERROR;
}
Status QueueTraverse(SqQueue Q)
{
if(Q.front==Q.rear)
printf("這是一個(gè)空隊(duì)列!");
while(Q.front%MAXQSIZE!=Q.rear)
{
printf("%d<- ",Q.base[Q.front]);
Q.front++;
}
return OK;
}
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告3
《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)報(bào)告
專業(yè) 班級(jí) 姓名 學(xué)號(hào)
實(shí)驗(yàn)項(xiàng)目
實(shí)驗(yàn)一 二叉樹的應(yīng)用
實(shí)驗(yàn)?zāi)康?/strong>
1、進(jìn)一步掌握指針變量的含義及應(yīng)用。
2、掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及使用范圍。
3、掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。
實(shí)驗(yàn)內(nèi)容
題目1:編寫一個(gè)程序，采用一棵二叉樹表示一個(gè)家譜關(guān)系。要求程序具有如下功能：
�。�1）用括號(hào)表示法輸出家譜二叉樹，
�。�2）查找某人的所有兒子，
�。�3）查找某人的所有祖先。
算法設(shè)計(jì)分析
�。ㄒ唬⿺�(shù)據(jù)結(jié)構(gòu)的定義
為了能夠用二叉樹表示配偶、子女、兄弟三種關(guān)系，特采用以下存儲(chǔ)關(guān)系，則能在二叉樹上實(shí)現(xiàn)家譜的各項(xiàng)運(yùn)算。
二叉樹型存儲(chǔ)結(jié)構(gòu)定義為：
typedef struct SNODE
{char name[MAX]; //人名
struct SNODE *left;//指向配偶結(jié)點(diǎn)
struct SNODE *right; //指向兄弟或子女結(jié)點(diǎn)
}FNODE;
（二）總體設(shè)計(jì)
實(shí)驗(yàn)由主函數(shù)、家譜建立函數(shù)、家譜輸出函數(shù)、兒子查找函數(shù)、祖先查找函數(shù)、結(jié)點(diǎn)定位函數(shù)、選擇界面函數(shù)七個(gè)函數(shù)共同組成。其功能描述如下：
（1）主函數(shù)：統(tǒng)籌調(diào)用各個(gè)函數(shù)以實(shí)現(xiàn)相應(yīng)功能
void main()
�。�2）家譜建立函數(shù)：與用戶交互建立家族成員對(duì)應(yīng)關(guān)系
void InitialFamily(FNODE *&head) //家譜建立函數(shù)
�。�3）家譜輸出函數(shù)：用括號(hào)表示法輸出家譜
輸出形式為：父和母（子1和子妻1（孫1），子2和子妻2（孫2））
void PrintFamily(FNODE *head) //家譜輸出函數(shù)
�。�4）兒子查找函數(shù)：在家譜中查找到某人所有的子女并輸出，同時(shí)也能辨別出其是否為家族成員與是否有子女
void FindSon(FNODE *b,char p[]) //兒子查找函數(shù)
�。�5）祖先查找函數(shù)：在家譜中查找到某人所有的祖先并輸出，同時(shí)也能辨別出其是否為家族中成員。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數(shù)
�。�6）結(jié)點(diǎn)定位函數(shù)：在家譜中找到用戶輸入人名所對(duì)應(yīng)的結(jié)點(diǎn)。
FNODE *findnode(FNODE *b,char p[]) //結(jié)點(diǎn)定位函數(shù)
�。�7）選擇界面函數(shù)：為便于編寫程序，將用戶選擇部分獨(dú)立為此函數(shù)。
void PRINT(int &n)
（三）各函數(shù)的詳細(xì)設(shè)計(jì)：
void InitialFamily(FNODE *&head) //家譜建立函數(shù)
1：首先建立當(dāng)前人的'信息，將其左右結(jié)點(diǎn)置為空，
2：然后讓用戶確定其是否有配偶，如果沒有配偶，則當(dāng)前程序結(jié)束，
3：如果有則建立其配偶信息，并將配偶結(jié)點(diǎn)賦給當(dāng)前人的左結(jié)點(diǎn)；
4：再讓用戶確定其是否有子女，如果有則遞歸調(diào)用家譜建立函數(shù)建立子女結(jié)點(diǎn)，并將其賦給配偶結(jié)點(diǎn)的下一個(gè)右結(jié)點(diǎn)。
5：如無，則程序結(jié)束
void PrintFamily(FNODE *head) //家譜輸出函數(shù)
1：首先判斷當(dāng)前結(jié)點(diǎn)是否為空，如果為空則結(jié)束程序；
2：如果不為空，則輸出當(dāng)前結(jié)點(diǎn)信息，
3：然后判斷其左結(jié)點(diǎn)（配偶結(jié)點(diǎn)）是否為空，如不為空則輸出“和配偶信息。
4：再判斷配偶結(jié)點(diǎn)的右結(jié)點(diǎn)是否為空，如不為空則遞歸調(diào)用輸出其子女信息，最后輸出“）”；
5：當(dāng)配偶結(jié)點(diǎn)為空時(shí)，則判斷其右結(jié)點(diǎn)（兄弟結(jié)點(diǎn)）是否為空
6：如果不為空，則輸出“，”，并遞歸調(diào)用輸出兄弟信息
7程序結(jié)束
FNODE *findnode(FNODE *b,char p[]) //結(jié)點(diǎn)定位函數(shù)
1：當(dāng)前結(jié)點(diǎn)是否為空，為空則返回空；
2：如果和查找信息相同，則返回當(dāng)前結(jié)點(diǎn)；
3：如不然，則先后遞歸訪問其左結(jié)點(diǎn)，再不是則遞歸訪問右結(jié)點(diǎn)
void FindSon(FNODE *b,char p[]) //兒子查找函數(shù)
1：在家譜中定位到要查找的結(jié)點(diǎn)，如無則輸出“查找不到此人”
2：判斷其配偶結(jié)點(diǎn)與子女結(jié)點(diǎn)是否為空，為空則輸出“無子女”
3：不為空則輸出其配偶結(jié)點(diǎn)的所有右結(jié)點(diǎn)（子女結(jié)點(diǎn)）。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數(shù)
1：先在家譜中定位到要查找的結(jié)點(diǎn)，如為空輸出“不存在此人”，程序結(jié)束
2：先將父母結(jié)點(diǎn)入棧，當(dāng)棧為空時(shí)程序結(jié)束，
3：棧不為空時(shí)，判斷棧頂元素是否已訪問過，
4：訪問過，再判斷是否為查找結(jié)點(diǎn)，如是則輸出棧中保存的其祖先結(jié)點(diǎn)，并濾過其兄弟結(jié)點(diǎn)不輸出；不是查找結(jié)點(diǎn)，則退棧一個(gè)元素
5：未訪問過，則取當(dāng)前棧頂元素，置訪問標(biāo)志——1，同時(shí)取其右結(jié)點(diǎn)
6：棧不為空或當(dāng)前所取結(jié)點(diǎn)不為空時(shí)，轉(zhuǎn)到2；
實(shí)驗(yàn)測(cè)試結(jié)果及結(jié)果分析
�。ㄒ唬y(cè)試結(jié)果
（二）結(jié)果分析
（略）
實(shí)驗(yàn)總結(jié)
�。裕�
【數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告】相關(guān)文章：
c數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告07-01
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 圖07-01
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告總結(jié)07-01
北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告07-01
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)五07-01
北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 圖07-01
北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告線性表07-01
實(shí)驗(yàn)報(bào)告芯片解剖實(shí)驗(yàn)報(bào)告07-03
實(shí)驗(yàn)報(bào)告10-13