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

1、編號：時間：2021年3月19日數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 想必學(xué)計(jì)算機(jī)專業(yè)的同學(xué)都知道數(shù)據(jù)結(jié)構(gòu)是一門比較重要的課程，那么，下面是自查報(bào)告網(wǎng)我給大家整理收集的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告，供大家閱讀參考。 一、實(shí)驗(yàn)?zāi)康募耙?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)任一個表達(dá)式中的語法檢查(選做)。 3) 編程實(shí)現(xiàn)隊(duì)列在兩種存儲結(jié)構(gòu)中的基本操作(隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、出隊(duì)列); 三、實(shí)驗(yàn)流程、操作步驟或核心代碼、算法片段 順序棧： stat

2、us 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

3、) 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.stacksiz

4、e+=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(s

5、qstack 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上面一個. p-; printf(%d ,*p); return ok; status compare(sqstack s) int flag,ture=ok,false=erro

6、r; elemtype e,x; initstack(s); flag=ok; printf(請輸入要進(jìn)?；虺鰲５脑兀?; while(x= getchar)!=#flag) switch (x) case (: case : case : if(push(s,x)=ok) printf(括號匹配成功!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 (

7、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.f

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

9、; 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); i

10、f(!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; /只有一個元素時(不存在指向尾指針) free (p); retur

11、n ok; status queuetraverse(linkqueue q) queueptr p,q; if( queueempty(q)=ok) printf(這是一個空隊(duì)列!n); return error; p=q.front-next; while(p) q=p; printf(%d-n,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)

12、; q.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,qelemtype e) if(q.front=q.rear) return error; e=q.baseq.front; q.front=(q.front+1)%maxqsize; return ok; in

13、t 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(這是一個空隊(duì)列!); while(q.front%maxqsize!=q.rear

14、) printf(%d- ,q.baseq.front); q.front+; return ok; 一.實(shí)驗(yàn)內(nèi)容： 實(shí)現(xiàn)哈夫曼編碼的生成算法。 二.實(shí)驗(yàn)?zāi)康模?1、使學(xué)生熟練掌握哈夫曼樹的生成算法。 2、熟練掌握哈夫曼編碼的方法。 三.問題描述： 已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。 1、讀入n個字符，以及字符的權(quán)值，試建立一棵huffman樹。 2、根據(jù)生成的huffman樹，求每個字符的huffman編碼。并對給定的待編碼字符序列進(jìn)行編碼，并輸出。 四.問題的實(shí)現(xiàn) (1)郝夫曼樹的存儲表示 typedef struct unsigned int weight; unsig

15、ned int parent,lchild,rchild; htnode,*huffmantree; /動態(tài)分配數(shù)組存儲郝夫曼樹 郝夫曼編碼的存儲表示 typedef char* *huffmancode;/動態(tài)分配數(shù)組存儲郝夫曼編碼 (2)主要的實(shí)現(xiàn)思路： a.首先定義郝夫曼樹的存儲形式，這里使用了數(shù)組 b.用select遍歷n個字符，找出權(quán)值最小的兩個 c.構(gòu)造郝夫曼樹ht，并求出n個字符的郝夫曼編碼hc 總結(jié) 1.基本上沒有什么太大的問題，在調(diào)用select這個函數(shù)時，想把權(quán)值最小的兩個結(jié)點(diǎn)的序號帶回huffmancoding，所以把那2個序號設(shè)置成了引用。 2.在編程過程中，在什么時候

16、分配內(nèi)存，什么時候初始化花的時間比較長 3.最后基本上實(shí)現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級的輸入錯誤。把hti.weight=hts1.weight+hts2.weight;中的s2寫成了i 附： /動態(tài)分配數(shù)組存儲郝夫曼樹 typedef struct int weight; /字符的權(quán)值 int parent,lchild,rchild; htnode,*huffmantree; /動態(tài)分配數(shù)組存儲郝夫曼編碼 typedef char* *huffmancode; /選擇n個(這里是k=n)節(jié)點(diǎn)中權(quán)值最小的兩個結(jié)點(diǎn) void select(huffmantree ht

17、,int k,int s1,int s2) int i; i=1; while(i=k hti.parent!=0)i+; /下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號 s1=i; for(i=1;i=k;i+) if(hti.parent=0hti.weight /下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號 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樹，求出n個字符的編碼 void huffmancoding(huffmant

18、ree 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個結(jié)點(diǎn) ht=(huffmantree)malloc(m+1)*sizeof(htnode); /0號單元未用，預(yù)分配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); /選出當(dāng)前權(quán)值最小的 hts1.parent=i; hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; /從葉子到根逆向求每個字符的郝夫曼編碼 hc=(huffmancode