【文章內(nèi)容簡介】 //后序遍歷(bitree *p *sl[100]； int s2[100]，top=0，b； p=root； do {while(p!=NULL) {s1[top]=p；s2[top++]=0； p=plchild；) if(top0) (b=s2[top]； p=s1[top]； if(b==0) {sl[top]=p；s2[top++]=l； p=prchild；} else{coutpdata””。 p=NULL； } }}while(top0)；}/ /建立二叉鏈表參考前述程序//按照層次遍歷二叉鏈表includetypedef char elemtype；struct bitree{ elemtype data； //結(jié)點信息bitree *lchild，*rchild； //左右孩子}。//按層次遍歷二叉樹(建立二叉鏈表同前)void lorder(bitree *t) { bitree q[100]，*p； //q代表隊列int f,r。 //f，r類似于隊列頭、尾指針q[1]=t； f=r=l；cout”按層次遍歷二叉樹的結(jié)果為：”。while if==r){ p=q[f]； f++； //出隊 coutpdata””。 if(Plchild!=NULL) { r++；q[r]=plchild；} //入隊 if prchild!=NULLl． { r++； q[r]=prchild。} //入隊 } coutendl； } void main() {bitree *t； t=create0； //建立二叉鏈表 lorder(t)； //：按層次遍歷二叉樹 }//將二叉樹的左右子樹進行交換void leftOright(bitree *r){bitree *root=r。 if (root!=NULL){ leftOright(rootlchild)。 leftOright(rootrchild)。 bitree *t=rootlchild。 rootlchild=rootrchild。 rootrchild=t。}}//主函數(shù) void main(){bitree *root；root=create()； //建立二叉鏈表coutendlendl”左右子樹交換前的遍歷結(jié)果”endl；cout”先序遍歷的結(jié)果”endl； preorder(root)；coutendl； cout”中序遍歷的結(jié)果”endl；inorder(root)；coutendl：cout”后序遍歷的結(jié)果”endl；postorder(root)；coutendl；}leftTOright(root)；coutendlendl”左右子樹交換后的遍歷結(jié)果”endl；cout”先序遍歷的結(jié)果”endl；preorder(root)；coutendl；cout”中序遍歷的結(jié)果”endl；inorder(root)；coutendl；cout”后序遍歷的結(jié)果”endl；postorder(root)；coutendl；} 六、選作實驗,29,7,8,14,23,3,11，建立哈夫曼樹，輸出哈夫曼編碼。，試輸入一串二進制編碼，輸出它的哈夫曼譯碼。算法提示：將建立哈夫曼樹、實現(xiàn)哈夫曼編、哈夫曼譯碼都定義成子函數(shù)的形式，然后在主函數(shù)調(diào)用它們。建立哈夫曼樹時，將哈夫曼樹的結(jié)構(gòu)定義為一個結(jié)構(gòu)型的一維數(shù)組，每個元素含有四項：雙親、左孩子、右孩子。給定的權(quán)值可以從鍵盤輸入，要輸出所建立的哈夫曼樹，只要輸出哈夫曼樹的一維數(shù)組中全部元素即可。要實現(xiàn)哈夫曼編碼，只要在所建立的哈夫曼樹上進行二進制編碼：往左走，編碼為0，往右走，編碼為1，然后將從根結(jié)點到樹葉中所有0、l排列起來，則得到該樹葉的哈夫曼編碼。哈夫曼編碼可以用一個結(jié)構(gòu)型的一維數(shù)組保存，每個元素包含：編碼、編碼的開始位置、編碼所對應(yīng)的字符等3項。哈夫曼譯碼，就是將輸入的編碼還原成對應(yīng)的字符。實驗四 圖的遍歷操作一、 實驗?zāi)康模?. 掌握圖的含義。2. 掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結(jié)構(gòu)。3. 理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲結(jié)構(gòu)。二、實驗內(nèi)容： 從以下2和4中各選擇一項內(nèi)容 1. 建立無向圖的鄰接矩陣，并實現(xiàn)插入、刪除邊的功能。2. 建立有向圖的鄰接表，并實現(xiàn)插入、刪除邊的功能。3. 建立一個包含6個結(jié)點的圖，并實現(xiàn)該圖的深度優(yōu)先搜索遍歷。4. 建立一個包含6個結(jié)點的圖，并實現(xiàn)該圖的廣度優(yōu)先搜索遍歷。三、實驗要求： 1. 根據(jù)實驗內(nèi)容編程，上機調(diào)試、得出正確的運行程序。2. 寫出實驗報告（包括源程序和運行結(jié)果）。四、實驗學(xué)時：4學(xué)時五、實驗步驟： ，建立一新文件；2. 參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。① 內(nèi)容1的知識要點：圖由一個非空的頂點的集合和一個描述頂點之間關(guān)系(邊)的集合組成。它可以定義為G=(V，E)。其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。對于實際問題，需要根據(jù)具體圖的結(jié)構(gòu)特點以及所要實施的操作，選擇建立合適的存儲結(jié)構(gòu)。圖的存儲結(jié)構(gòu)包括鄰接矩陣和鄰接表。 鄰接矩陣：用一維數(shù)據(jù)組存儲圖中頂點的信息，用矩陣表示圖中各頂點之間的相鄰關(guān)系。它屬于靜態(tài)存儲方法。鄰接表：鄰接表存儲方法是一種順序存儲與鏈?zhǔn)酱鎯ο嘟Y(jié)合的存儲方法。順序存儲部分用來保存圖中頂點的信息，鏈?zhǔn)酱鎯Σ糠钟脕肀４鎴D中邊的信息。//鄰接矩陣的存儲結(jié)構(gòu)typedef struct {int vertex；}node；typedef struct {int adj； }arc；typedef struct {node node[maxnode]； arc arcs[maxnode][maxnode]；}graph；//實現(xiàn)插入、刪除邊的操作void ins_arc(graph *g，int v，int w) {garcs[v][w].adj=l； return； } void del_arc(graph *g，int v，int w) {garc[v][w].adj=0； retum。 } //內(nèi)容1參考程序 define maxnode 40 define null 0 includestdio．h typedef struct st_arc {int adjvex； int weight； struct st_arc *nextrac；}arode； typedef struct {int vertex； struct st_arc *firstarc；}vernode； typedef vernode adjlist[maxnode]； void del_arc(vernode g[]，int v，int w) //刪除從頂點v到頂點w的邊 {arode *rl,*r2； rl=g[v]．frrstarc；r2=rl；while(r1!=nullamp。amp。r1adjvex!=w){r2=rl。rl=rlnextarc；}if (rl==null){printf(”no edge vw．”)；return；}elseif(r1==r2) //當(dāng)只有一個邊結(jié)點時g[v].firstarc=r1nextarc；else r2nextarc=r1nextarc； //有多個邊結(jié)點時rl=g[w].firstarc；r2=rl；while(r1!=nullamp。amp。r1adjvex!=v) //在以v為頭結(jié)點的鏈表中，刪除相應(yīng)的 //邊結(jié)點{r2=rl；rl＝rlnextarc；｝if (rl=＝null){printf(”no edge vw.”)；return；}elseif(r1==r2)g[w].firstarc=rlnextarc；elser2nextarc=r1nextarc；}void print(vernode g[]，int n) //打印圖中各結(jié)點的結(jié)構(gòu){arode *q；int i；printf(”adjacency list of the graph：\n”)；for(i=0；in；i++) {printf(”\t%d\t”，i)； printf(”%d\t”，g[i].vertex)；q=g[i].firstarc；while(q!=null){printf(”%d\t”，qadjvex)；printf(”%d\t”，qweight)；q=qnextarc； } printf(”\n”)； } }main() {int i，j，n，k，w，v； arode *p，*q； adjlist g； printf(”Input node： ”)； //輸入圖中頂點個數(shù) scanf(”%d”，amp。n)； for(k=0；kn；k++) //輸入邊值和權(quán)值 {printf(”node%d=”，k)； scanf(“%d”，＆g[k].vertex)； g[k].firstarc=null； //對順序存儲部分初始化 } for(；；) //輸入各邊，并將對應(yīng)的邊結(jié)點插入到鏈表中 {printf(”Insert edgeij，w：”) scanf(”%d”，＆i)； scanf(”%d”，＆j)； scanf(”%d”，＆w)； if（i==1amp。＆j=＝1amp。amp。w=1) break； q=(arode*)malloc(sizeof(arode))； qadjvex=j； qweight=w； qnextarc=g[i].firstarc； //頭指針指向新的邊結(jié)點 g[i].firstarc=q； p=(arode*)malloc(sizeof(arode))； pnextarc=g[i].firstarc； g[i].firstarc=q； p=(arode*)malloc(sizeof(arode))； padjvex=i； pweight=w； pnextarc=g[j].firstarc； g[j].firstarc=p； } print(g，n)； printf(”Delete edge Vw：”)；scanf(”%d%d”，＆v，amp。w)；del_arc(g，v，w)；print(g，n)；}② 內(nèi)容2的知識要點：構(gòu)造有向圖鏈接表與無向圖鏈接表的算法區(qū)別是：無向圖兩結(jié)點無向?qū)ε?，因而鄰接表有一定的對偶性；有向圖兩結(jié)點間有向無對偶關(guān)系，因而建立鄰接表時應(yīng)根據(jù)輸入的頂點及邊的有向關(guān)系建立(當(dāng)箭頭方向離開結(jié)點為有關(guān)，當(dāng)箭頭方向指向結(jié)點為無關(guān))。//內(nèi)容2的參考程序//有向圖鏈表的存儲結(jié)構(gòu)為：typedef struct st_arc {int aajvex； //存放依附于該邊的另一頂點在一維數(shù)組中的序號int weight； //存放和該邊有關(guān)的信息，如權(quán)值等struct st_arc *nextarc； //依附于該頂點的下一個邊結(jié)點的指針}arode；typedef struct{int vertex； //存放與頂點有關(guān)的信息struct st_arc*firstarc；}vernode； //存儲頂點信息typedef vernode adjlist[maxnode]；//參考程序見內(nèi)容1③ 內(nèi)容3的知識要點：深度優(yōu)先搜索遍歷圖的算法：首先訪問指定的起始頂點v0，從vo出發(fā)，訪問vo的一個未被訪問過的鄰接頂點w1，再從w1出發(fā)，訪問w1的一個未被訪問的頂點w2，然后從w2出發(fā)，訪問w2的一個未被訪問的鄰接頂點w3，依此類推，直到一個所有鄰接點都被訪問過為止。圖采用鄰接表作存儲結(jié)構(gòu)，圖的深度優(yōu)先遍歷次序為 ①→②→④→⑤→⑥→③參考程序運行過程中，深度優(yōu)先遍歷時指針p的移動方向示意如圖下所示，圖中ppppp5和p6為深度優(yōu)先遍歷圖的各結(jié)點時，指針p的移動次序。//內(nèi)容3的參考程序define