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