【正文】 ch? if(T){ Push(S,T173。data)? if(!T173。lchildamp。amp。!T173。rchild)//如果左指針和右指針同時為空，才說明該節(jié)點為葉子節(jié)點PrintStack(S)? else { AllPath(T173。lchild,S)? AllPath(T173。rchild,S)? } Pop(S,amp。ch)? } } 4．參考代碼為：BiThrTreepre?voidPreThreading(BiThrTreep)//先序線索化 { if(p){ if(!p173。lchild){ p173。LTag=Thread?p173。lchild=pre? //前驅線索 } if(!pre173。rchild){ pre173。RTag=Thread?pre173。rchild=p? //后繼線索 } pre=p? if(p173。LTag==Link)PreThreading(p173。lchild)?//左子樹線索化 if(p173。RTag==Link)— 3—教學過程及內容PreThreading(p173。rchild)?//右子樹線索化} } BiThrTreePreOrderThreading(BiThrTreeT)//先序線索二叉樹 { BiThrTreethrt? if(!(thrt=(BiThrTree)malloc(sizeof(BiThrNode))))returnNULL? thrt173。LTag=Link?thrt173。RTag=Thread?//建頭結點 thrt173。rchild=thrt?//右指針回指 if(!T)thrt173。lchild=thrt?//空二叉樹 else { thrt173。lchild=T? pre=thrt?PreThreading(T)?//先序遍歷進行先序線索化pre173。rchild=thrt?pre173。RTag=Thread?//最后一個結點線索化 thrt173。rchild=pre? } returnthrt?} voidPreOrderTraverse_Thr(BiThrTreethrt)//先序遍歷二叉樹 { BiThrTreep?printf(“先序遍歷結果為：”)? p=thrt173。lchild? while(p!=thrt){ printf(“%3c”,p173。data)? while(p173。LTag==Link){ p=p173。lchild?printf(“%3c”,p173。data)? } p=p173。rchild? } printf(“n”)? }— 4— 授課進度第13周，第24次課（2學時）授課題目(教學章、節(jié)實驗六哈夫曼樹 或主題)授課日期016年11月23日（11 2月22日）.理解哈夫曼樹的特征及其應用。，構造哈夫曼樹，并用構造的哈夫曼樹進行編 2 碼和譯碼。教學 目標 ，使學生對數(shù)據(jù)結構的應用有更深層次的理解。教學 。重點。教學 難點請選擇你授課時所采用的教學方法（在括號中畫“√”）：講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學談話法﹝﹞，實驗法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學輔導法﹝﹞，練習方法法（習題或操作課）﹝√﹞，讀書指導法﹝﹞，聽說法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實習作業(yè)法﹝﹞，其他﹝﹞ 教學實物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標本手段﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè)[ 1]李素若，陳萬華，:中國水利水電出版社，2014.[ 2]李素若，陳萬華，:中國水利水 請選擇你授課時所采用的教學手段（在括號中畫“√”）：參考電出版社，教學過程及內容一、實驗內容1．哈夫曼樹問題。利用哈夫曼編碼進行通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)進行預先編碼；在接受端將傳來的數(shù)據(jù) 進行解碼（復原）對于雙工信道（即可以雙向傳輸?shù)男诺溃慷硕家幸粋€完整的編/譯碼 系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)?；疽?；（1）從終端讀入字符集大小為n（即字符的個數(shù)），逐一輸入n個字符和相應的n個權 值（即字符出現(xiàn)的頻度），建立哈夫曼樹，進行編碼，最后輸出并存于文件hfmtree中。2）利用已建好的哈夫曼編碼文件hfmtree，對鍵盤輸入的正文進行譯碼。輸出字符正（文，再輸出該文的二進制碼。3）測試數(shù)據(jù)。（(n=27)和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹。并實現(xiàn)以下報文的譯碼和輸出：“THISPROGRAMISMYFAVORITE”。2．思考題：利用哈夫曼樹及哈夫曼編碼的原理編寫一個算法，n個自然數(shù)之間經(jīng)過加 減運算后結果最小的值是多少。注意：只能進行加減運算，且最后結果和運算的中間結果不 能為負。二、實驗指導 include include include include typedefstruct unsignedint unsignedint {weight? parent,lchild,rchild?} HTNode,*HuffmanTree? typedefchar **HuffmanCode? typedefstruct{ unsignedint s1? unsignedint s2?} MinCode?MinCodeSelect(HuffmanTreeHT,unsignedintn)?HuffmanCodeHuffmanCoding(HuffmanTree*H1,unsignedint*w,char*ch,unsignedintn)//求哈夫曼樹及哈夫曼編碼，將哈夫曼編碼寫入文本文件 {— 1—教學過程及內容unsignedinti,s1=0,s2=0? HuffmanTreep,HT? HuffmanCodeHC? char *cd? unsignedintf,c,start,m? MinCodemin? FILE*fp?if((fp=fopen(“”,“wt”))==NULL){ printf(“!”)? exit(1)? } if(nHT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))? for(p=HT,i=0?iweight=*w?p173。parent=0? p173。lchild=0?p173。rchild=0? } for(?iweight=0?p173。parent=0? p173。lchild=0?p173。rchild=0?} for(i=n+1?iHT[s1].parent=i?HT[s2].parent=i? HT[i].lchild=s1?HT[i].rchild=s2?HT[i].weight=HT[s1].weight+HT[s2].weight?} HC=(HuffmanCode)malloc((n+1)*sizeof(char*))? cd=(char*)malloc(n*sizeof(char*))? cd[n173。1]=39。39。? for(i=1?iif(HT[f].lchild==c)cd[173。173。start]=39。039。?— 2—教學過程及內容elsecd[173。173。start]=39。139。?HC[i]=(char*)malloc((n173。start)*sizeof(char))? strcpy(HC[i],amp。cd[start])? } free(cd)?for(i=1?i} MinCodeSelect(HuffmanTreeHT,unsignedintn)//求權值的最小值和次最小值 { unsignedintmin,secmin? unsignedinttemp? unsignedinti,s1,s2? MinCodecode? s1=1?s2=1?for(i=1?i} for(?is2=i? break?} for(i=1?i— 3—教學過程及內容s2=i?} =s1? =s2? returncode?} voidTranscodeing(intn,char*Char_Code,char*Huffman_Code)//從文本文件中讀取哈夫曼編碼，并字符編碼轉為哈夫曼編碼 { FILE*fp?charstr[215],ch[50]={39。39。}? HuffmanCodeHC=NULL? inti=0,len,j,k?HC=(HuffmanCode)malloc((n+1)*sizeof(char*))? if((fp=fopen(“”,“rt”))==NULL){ printf(“!”)? exit(1)? } while(!feof(fp)){ memset(str,0,sizeof(str))? fgets(str,215,fp)? if(str[0]==0)break? len=strlen(str)? ch[i]=str[0]?HC[i]=(char*)malloc((len173。1)*sizeof(char*))? memcpy(HC[i],amp。str[1],len173。2)? HC[i][len173。2]=0? i++? } fclose(fp)? i=0?k=0?while(Char_Code[i]!=39。39。){ for(j=0?j— 4—教學過程及內容free(HC)? } intmain(){ HuffmanTreeHT=NULL? HuffmanCodeHC=NULL? unsignedint*w=NULL,i,n?charch[50]={39。39。},Huffman_Code[1024]={39。39。}?charChar_Code[]=“THISPROGRAMISMYFAVORITE”? printf(“Inputn:n”)? scanf(“%d”,amp。n)?w=(unsignedint*)malloc((n+1)*sizeof(unsignedint))? w[0]=0?printf(“Enterweight,character:n”)? for(i=1?iTranscodeing(n,Char_Code,Huffman_Code)? printf(“%sn”,Huffman_Code)? free(w)? return0? }— 5— 授課進度第14周，第26次課（2學時）授課題目(教學章、節(jié)實驗七圖的遍歷（Ⅰ）或主題)授課日期016年11月30日（11 2月29日）.掌握圖常用的鄰接矩陣存儲存儲結構。，即深度優(yōu)先遍歷和廣度優(yōu) 2 先遍歷。教學 目標。教學 。重點。教學 難點請選擇你授課時所采用的教學方法（在括號中畫“√”）：講授法﹝﹞，討論法﹝﹞，演示法﹝﹞，案例法﹝﹞，發(fā)現(xiàn)法﹝﹞，探究法﹝﹞，教學談話法﹝﹞，實驗法﹝√﹞，參觀法﹝﹞，考察法﹝﹞，自學輔導法﹝﹞，練習方法法（習題或操作課）﹝√﹞，讀書指導法﹝﹞，聽說法﹝﹞，寫生法﹝﹞，視唱 法﹝﹞，工序法（技能課）﹝﹞，實習作業(yè)法﹝﹞，其他﹝﹞ 教學實物﹝﹞，多媒體﹝﹞，投影﹝﹞，影像﹝﹞，CAI課件﹝﹞，PPT﹝√﹞，標本手段﹝﹞，掛圖﹝﹞，模型﹝﹞，其他﹝﹞ 討 論、思考 題、作業(yè)[ 1]李素若，陳萬華，:中國水利水電出版社，2014.[ 2]李素若，陳萬華，:中國水利水 請選擇你授課時所采用的教學手段（在括號中畫“√”）：參考電出版社，教學過程及內容一、實驗內容圖的鄰接矩陣存儲結構如下：defineMaxVerNum100//設置鄰接矩陣的最大頂點數(shù) typedefcharVertexType?//設置圖的頂點信息為字符//設置邊上權值為整型 typedefintEdgeType?typedefstruct{ VertexTypevexs[MaxVerNum]?//圖的頂點信息表EdgeTypeedges[MaxVerNum][MaxVerNum]?//圖的鄰接矩陣//圖的頂點數(shù)和邊數(shù) intn,e?MGraph?//圖的鄰接矩陣表示結構定義 } 1．鍵盤輸入數(shù)據(jù)，建立一個圖的鄰接矩陣，并進行圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。二、實驗指導．參考代碼為： 1 include include defineMaxVerNum100//設置鄰接矩陣的最大頂點數(shù) typedefcharVertexType?//設置圖的頂點信息為整型//設置邊上權值為整型 typedefintEdgeType?typedefstruct{ VertexTypevexs[MaxVerNum]?//圖的頂點信息表EdgeTypeedges[MaxVerNum][MaxVerNum]?//圖的鄰接矩陣//圖的頂點數(shù)和邊數(shù) intn,e?MGraph?//圖的鄰接矩陣表示結構定義 } typedefenum{FALSE,TRUE}boolean? booleanvisited[MaxVerNum]?//頂點訪問標記向量 structlinkqueuenode { intdata? structlinkqueuenode*next? } ?typedefstruct { structlinkqueuenode*front? structlinkqueuenode*rear? linkque? } voidInitQueue(linkque*q){ structlinkqueuenode*p? p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode))? p173。next=NULL?— 1—教學過程及內容q173。front=p?q173。rear=p?} intQueueEmpty(linkqueq){ inti?if(==)i=1? elsei=0? return(i)? } voidEnQueue(linkque*q,intx){ structlinkqueuenode*p? p=