數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

本文格式為Word版下載后可任意編輯和復(fù)制第第頁(yè)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告想必學(xué)計(jì)算機(jī)專業(yè)的同學(xué)都知道數(shù)據(jù)結(jié)構(gòu)是一門比較重要的課程，那么，下面是我給大家整理收集的數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告，供大家閱讀參考。

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告1一、試驗(yàn)?zāi)康募耙?/p>

1)把握棧和隊(duì)列這兩種特別的線性表，熟識(shí)它們的特性，在實(shí)際問(wèn)題背景下敏捷運(yùn)用它們。

本試驗(yàn)訓(xùn)練的要點(diǎn)是“?！焙汀瓣?duì)列”的觀點(diǎn);

二、試驗(yàn)內(nèi)容

1)利用棧，實(shí)現(xiàn)數(shù)制轉(zhuǎn)換。

2)利用棧，實(shí)現(xiàn)任一個(gè)表達(dá)式中的語(yǔ)法檢查(選做)。

3)編程實(shí)現(xiàn)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作(隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、出隊(duì)列);

三、試驗(yàn)流程、操作步驟或核心代碼、算法片段

挨次棧：

StatusInitStack(SqStack&S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

returnERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}

StatusDestoryStack(SqStack&S)

{

free(S.base);

returnOK;

}

StatusClearStack(SqStack&S)

{

S.top=S.base;

returnOK;

}

StatusStackEmpty(SqStackS)

{

if(S.base==S.top)

returnOK;

returnERROR;

}

intStackLength(SqStackS)

{

returnS.top-S.base;

}

StatusGetTop(SqStackS,ElemType&e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

}

StatusPush(SqStack&S,ElemTypee)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

}

StatusPop(SqStack&S,ElemType&e)

{

if(S.top==S.base)

returnERROR;

e=*--S.top;

returnOK;

}

StatusStackTraverse(SqStackS)

{

ElemType*p;

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

if(!p)returnERROR;

p=S.top;

while(p!=S.base)//S.top上面一個(gè)...

{

p--;

printf("%d",*p);

}

returnOK;

}

StatusCompare(SqStack&S)

{

intflag,TURE=OK,FALSE=ERROR;

ElemTypee,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)匹配勝利!\n\n");

break;

case')':

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

{

printf("沒(méi)有滿意條件\n");

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))

returnOK;

else

returnERROR;

}

鏈隊(duì)列：

StatusInitQueue(LinkQueue&Q)

{

Q.front=Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)returnERROR;

Q.front->next=NULL;

returnOK;

}

StatusDestoryQueue(LinkQueue&Q)

{

while(Q.front)

{

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

returnOK;

}

StatusQueueEmpty(LinkQueue&Q)

{

if(Q.front->next==NULL)

returnOK;

returnERROR;

}

StatusQueueLength(LinkQueueQ)

{

inti=0;

QueuePtrp,q;

p=Q.front;

while(p->next)

{

i++;

p=Q.front;

q=p->next;

p=q;

}

returni;

}

StatusGetHead(LinkQueueQ,ElemType&e)

{

QueuePtrp;

p=Q.front->next;

if(!p)

returnERROR;

e=p->data;

returne;

}

StatusClearQueue(LinkQueue&Q)

{

QueuePtrp;

while(Q.front->next)

{

p=Q.front->next;

free(Q.front);

Q.front=p;

}

Q.front->next=NULL;

Q.rear->next=NULL;

returnOK;

}

StatusEnQueue(LinkQueue&Q,ElemTypee)

{

QueuePtrp;

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

if(!p)

returnERROR;

p->data=e;

p->next=NULL;

Q.rear->next=p;

Q.rear=p;//p->next為空

returnOK;

}

StatusDeQueue(LinkQueue&Q,ElemType&e)

{

QueuePtrp;

if(Q.front==Q.rear)

returnERROR;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)

Q.rear=Q.front;//只有一個(gè)元素時(shí)(不存在指向尾指針)

free(p);

returnOK;

}

StatusQueueTraverse(LinkQueueQ)

{

QueuePtrp,q;

if(QueueEmpty(Q)==OK)

{

printf("這是一個(gè)空隊(duì)列!\n");

returnERROR;

}

p=Q.front->next;

while(p)

{

q=p;

printf("%ddata);

q=p->next;

p=q;

}

returnOK;

}

循環(huán)隊(duì)列：

StatusInitQueue(SqQueue&Q)

{

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base)

exit(OWERFLOW);

Q.front=Q.rear=0;

returnOK;

}

StatusEnQueue(SqQueue&Q,QElemTypee)

{

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;

}

StatusDeQueue(SqQueue&Q,QElemType&e)

{

if(Q.front==Q.rear)

returnERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;

}

intQueueLength(SqQueueQ)

{

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

StatusDestoryQueue(SqQueue&Q)

{

free(Q.base);

returnOK;

}

StatusQueueEmpty(SqQueueQ)//判空

{

if(Q.front==Q.rear)

returnOK;

returnERROR;

}

StatusQueueTraverse(SqQueueQ)

{

if(Q.front==Q.rear)

printf("這是一個(gè)空隊(duì)列!");

while(Q.front%MAXQSIZE!=Q.rear)

{

printf("%dQ.front++;

}

returnOK;

}

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告2一.試驗(yàn)內(nèi)容：

實(shí)現(xiàn)哈夫曼編碼的生成算法。

二.試驗(yàn)?zāi)康模?/p>

1、使同學(xué)嫻熟把握哈夫曼樹的生成算法。

2、嫻熟把握哈夫曼編碼的方法。

三.問(wèn)題描述：

已知n個(gè)字符在原文中消失的頻率，求它們的哈夫曼編碼。

1、讀入n個(gè)字符，以及字符的權(quán)值，試建立一棵Huffman樹。

2、依據(jù)生成的Huffman樹，求每個(gè)字符的Huffman編碼。并對(duì)給定的待編碼字符序列進(jìn)行編碼，并輸出。

四.問(wèn)題的實(shí)現(xiàn)

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

typedefstruct{

unsignedintweight;

unsignedintparent,lchild,rchild;

}HTNode,*HuffmanTree;//動(dòng)態(tài)安排數(shù)組存儲(chǔ)郝夫曼樹

郝夫曼編碼的存儲(chǔ)表示

typedefchar**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.基本上沒(méi)有什么太大的問(wèn)題，在調(diào)用select這個(gè)函數(shù)時(shí)，想把權(quán)值最小的兩個(gè)結(jié)點(diǎn)的序號(hào)帶回HuffmanCoding，所以把那2個(gè)序號(hào)設(shè)置成了引用。

2.在編程過(guò)程中，在什么時(shí)候安排內(nèi)存，什么時(shí)候初始化花的時(shí)間比較長(zhǎng)

3.最終基本上實(shí)現(xiàn)后，發(fā)覺(jué)結(jié)果仍舊存在問(wèn)題，經(jīng)過(guò)分步調(diào)試，發(fā)覺(jué)了特殊低級(jí)的輸入錯(cuò)誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫成了i

附：

//動(dòng)態(tài)安排數(shù)組存儲(chǔ)郝夫曼樹

typedefstruct{

intweight;//字符的權(quán)值

intparent,lchild,rchild;

}HTNode,*HuffmanTree;

//動(dòng)態(tài)安排數(shù)組存儲(chǔ)郝夫曼編碼

typedefchar**HuffmanCode;

//選擇n個(gè)(這里是k=n)節(jié)點(diǎn)中權(quán)值最小的兩個(gè)結(jié)點(diǎn)

voidSelect(HuffmanTree&HT,intk,int&s1,int&s2)

{inti;

i=1;

while(i//下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號(hào)

s1=i;

for(i=1;i{

if(HT[i].parent==0&&HT[i].weight

}

//下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號(hào)

for(i=1;i{

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

}

s2=i;

for(i=1;i{

if(HT[i].parent==0&&i!=s1&&HT[i].weight

}

}

//構(gòu)造Huffman樹，求出n個(gè)字符的編碼

voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)

{

intm,c,f,s1,s2,i,start;

char*cd;

if(nm=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è)單元

HuffmanTreep=HT+1;

w++;//w的號(hào)單元也沒(méi)有值，所以從號(hào)單元開頭

for(i=1;i{

p->weight=*w;

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

}

for(;i{

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

}

for(i=n+1;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].weig