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

1、第 PAGE21 頁(yè) 共 NUMPAGES21 頁(yè)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告想必學(xué)計(jì)算機(jī)專業(yè)的同學(xué)都知道數(shù)據(jù)結(jié)構(gòu)是一門比較重要的課程，那么，下面是第一WTT給大家整理收集的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告，供大家閱讀參考。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1一、實(shí)驗(yàn)?zāi)康募耙?)掌握棧和隊(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á)式中的語(yǔ)法檢查(選做)。3) 編程實(shí)現(xiàn)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作(隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、出隊(duì)列三、實(shí)驗(yàn)流程、操作步驟或核心代碼、算法片段順序棧：Status In

2、itStack(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.basereturn OK;Status ClearStack(SqStack S)S.top=S.base;return OK;Status StackEmpty(SqStack S)if(S.base=S.top)retu

3、rn 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;retur

4、n 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 ERR

5、OR;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 ”,*preturn OK;Status Compare(SqStack S)int flag,TURE=OK,FALSE=ERROR;ElemType e,x;InitStack(Sflag=OK;printf(“請(qǐng)輸入要進(jìn)?；虺鰲５脑兀骸眞hile(

6、x= getchar)!=#flag)switch (x)case (:case :case :if(Push(S,x)=OK)printf(“括號(hào)匹配成功!nn”break;case ):if(Pop(S,e)=ERROR | e!=()printf(“沒有滿足條件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)return OK;elsereturn ER

7、ROR;鏈隊(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.frontQ.front=Q.rear;return OK;Status QueueEmpty(LinkQueue Q)if(Q.front-next=NULL)return

8、 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-n

9、ext;free(Q.frontQ.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

10、= 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 (preturn OK;Status QueueTraverse(LinkQueue Q)QueuePtr p,q;if( QueueEmpty(Q)=OK)printf(“這是一個(gè)空隊(duì)列!n”return ERROR;p=Q.front-next;while(p)q=p;printf(“%ddataq=p-next;p=q;return O

11、K;循環(huán)隊(duì)列：Status InitQueue(SqQueue Q)Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)if(!Q.base)exit(OWERFLOWQ.front=Q.rear=0;return OK;Status EnQueue(SqQueue Q,QElemType e)if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue Q,QElemT

12、ype e)if(Q.front=Q.rear)return ERROR;e=Q.baseQ.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.basereturn OK;Status QueueEmpty(SqQueue Q) /判空if(Q.front =Q.rear)return OK;return ERROR;Status QueueTrav

13、erse(SqQueue Q)if(Q.front=Q.rear)printf(“這是一個(gè)空隊(duì)列!”while(Q.front%MAXQSIZE!=Q.rear)printf(“%d- ”,Q.baseQ.frontQ.front+;return OK;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告2一.實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)哈夫曼編碼的生成算法。二.實(shí)驗(yàn)?zāi)康模?、使學(xué)生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。三.問題描述：已知n個(gè)字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。1、讀入n個(gè)字符，以及字符的權(quán)值，試建立一棵Huffman樹。2、根據(jù)生成的Huffman樹，求每個(gè)字符的Huffman編碼。并對(duì)給定的待編

14、碼字符序列進(jìn)行編碼，并輸出。四.問題的實(shí)現(xiàn)(1)郝夫曼樹的存儲(chǔ)表示typedef structunsigned 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è)函

15、數(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ò)誤。把HTi.weight=HTs1.weight+HTs2.weight;中的s2寫成了i附：/動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼樹typedef structint weight; /字符的權(quán)值int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼編碼typedef char* *HuffmanCode;

16、/選擇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 HTi.parent!=0)i+;/下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號(hào)s1=i;for(i=1;i=k;i+)if(HTi.parent=0HTi.weight/下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號(hào)for(i=1;i=k;i+)if(HTi.parent=0i!=s1)break;s2=i;for(i=1;i=k;i+)if(HTi.parent=0i!=s1HTi.weight/構(gòu)造Huffman樹

17、，求出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;iweight=*w;p-parent=p-rchild=p-lchild=0;for(;iweigh

18、t=p-parent=p-rchild=p-lchild=0;for(i=n+1;i=m;i+)Select(HT,i-1,s1,s2 /選出當(dāng)前權(quán)值最小的HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/從葉子到根逆向求每個(gè)字符的郝夫曼編碼HC=(HuffmanCode)malloc(n+1)*sizeof(char*) /分配n個(gè)字符編碼的頭指針變量cd=(char*)malloc(n*sizeof(char) /分配求編碼的工作空間cdn-1=0;/編碼結(jié)束符for(i=1;i=n;i+) /逐個(gè)字符求郝夫曼編碼start=n-1; /編碼結(jié)束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /從葉子到根逆向求編碼if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*si