周總結&lt;7&gt;

這周和3位朋友一起完成了系運動會的視訊，感受很多，也學到很多。

周次	學習時間	新編代碼行數	部落格量	學到知識點
14	20	100	1	Html頁面設計；虛拟機；（C語言）最小生成樹與最短路徑

Html案例：

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<head>

</head>

div{

width: 600px; /*不設定高度使其高度自适應*/

border:1px solid #CCC;

margin:0px auto;

}

#a{

height:50px;

border:1px solid #999;

line-height: 2em;

margin:0px;

#b{

height:350px;

border:1px solid #0CC;

#c{

border:1px solid #096;

</style>

<body>

<div>

<div id="b">middle</div>

<div id="c">bottom</div>

</div>

</body>

</html>

C語言：

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_VEX_NUM 100 //最大頂點數

#define MAX_EDGE_NUM 200

typedef int WeightType; //邊的權值類型

typedef char *VexType; //頂點資料類型

typedef struct ENode{

int vex1,vex2;

WeightType w;

}ENode;

typedef struct{

int vexnum,edgenum;

VexType vexlist[MAX_VEX_NUM];

ENode edgelist[ MAX_EDGE_NUM];

}ELGraph;

#define MinEdge 32767

/********************************************************/

//Prim算法的最小生成樹

ENode * Prim_MST(ELGraph *g){

int edgeflags[MAX_EDGE_NUM],vexflags[MAX_VEX_NUM];

int i,j,k1,k2;

for(i=0;i<MAX_EDGE_NUM;i++)

edgeflags[i]=-1;

for(i=0;i<MAX_VEX_NUM;i++)

vexflags[i]=-1;

vexflags[0]=0;//先交第一個頂點

int nvex=1;

int eposi=-1,vposi=-1;

WeightType tmp;

for(i=1;i<MAX_VEX_NUM;i++){

tmp=MinEdge;

for(j=0;j<MAX_EDGE_NUM;j++){//循環擷取i頂點的每一條邊

if(edgeflags[j]!=-1) continue; //此邊已加入集合，則取下一條邊

for(k1=0;k1<i;k1++){

if(g->edgelist[j].vex1==vexflags[k1]){ //此邊的頂點已在集合中否？

// vposi=k1;

break;//是，退出

}

} //k1==i 表示此vex1頂點在TV集合中

for(k2=0;k2<i;k2++){

if(g->edgelist[j].vex2==vexflags[k2]){//此邊的另一個頂點已在集合中否？

// vposi=k2;

break;//是，退出

if(k1==i && k2==i) //此邊的兩個頂點都在集合中,則形成回路，不能使用此邊

continue;

if(k1!=i && k2!=i) //此邊的兩個頂點都不在集合中,不能使用此邊

//此邊隻有一個頂點在集合中，

if(g->edgelist[j].w<tmp){//此邊的權是否最小

tmp=g->edgelist[j].w;//是，暫時儲存此權

eposi=j; //暫時儲存此邊

//暫時儲存此邊不在集合中的一個頂點

if(k1==i)

vposi=g->edgelist[j].vex1;

if(k2==i)

vposi=g->edgelist[j].vex2;

vexflags[i]=vposi;//把此邊不在集合中的頂點加到集合中

edgeflags[eposi]=1;//标記此邊已使用，即此邊加到集合中。

ENode *pen=(ENode*)malloc(sizeof(ENode)*(g->vexnum-1));

k1=0;

int n=g->vexnum-1;

for(i=0;i<MAX_EDGE_NUM ;i++){

if(edgeflags[i]==1)

{ pen[k1++]=g->edgelist[i];

if(k1==n)

break;

return pen;

//Kruskal算法的最小生成樹

//根據邊的權值從小到大排序

void Sort(ENode *pen,int n){ //pen為邊集，n為邊的個數

int i,j;

WeightType tmp=pen[0].w;

int posi=0;

ENode etmp;

for(i=0;i<n-1;i++){

posi=i;tmp=pen[i].w;

for(j=i+1;j<n;j++){

if(pen[j].w<tmp){

tmp=pen[j].w;posi=j;

etmp=pen[i]; pen[i]=pen[posi];pen[posi]=etmp;

}

ENode* Kruskal_MST(ELGraph *gl)

{

int *vset=(int *)malloc(sizeof(int)*gl->vexnum);

//存放最小生成樹的n-1條邊

ENode *pen=(ENode *)malloc(sizeof(ENode) * (gl->vexnum-1));

int i;

for(i=0;i<gl->vexnum;i++) vset[i]=i; //每個頂點單獨一個連通分量

Sort(gl->edgelist,gl->edgenum); //根據邊的權值從小到大排序

int s=0,j=0;

int c1,c2;

while(s < gl->vexnum-1 && j< gl->edgenum){

c1=gl->edgelist[j].vex1;c2= gl->edgelist[j].vex2;//取邊的兩個頂點

if(vset[c1] !=vset[c2])//判斷兩個頂點的連通分量相同否？

{ //若兩個頂點的連通分量不相同，則将該邊加入到pen邊集中

pen[s].vex1=c1;pen[s].vex2=c2;pen[s].w=gl->edgelist[j].w;

s++;

for(i=0;i<gl->vexnum;i++)

if(vset[i]==vset[c2])

vset[i]=vset[c1];//将兩個不同頂點的連通分量合并成一個連通分量

j++;//取下一條邊

free(vset);

//free(pen);

return pen;

/********************************************************/

//輸出與頂點v相連的頂點及其邊的權值,gl為原圖，pen為最小生成樹

void PrintV(ELGraph *gl, ENode *pen, VexType v)

int i,posi=-1;

for(i=0;i<gl->vexnum;i++){

if(strcmp(v,gl->vexlist[i])==0)

{ posi=i;

break;

}

if(posi==-1){

printf("無此頂點%s資料\n",v);

return;

printf("頂點%s",v);

for(i=0;i<gl->vexnum-1;i++){

if(pen[i].vex1==posi){

printf("與%s頂點相連的權值為%d ",gl->vexlist[pen[i].vex2],pen[i].w);

if(pen[i].vex2==posi){

printf("與%s頂點相連的權值為%d ",gl->vexlist[pen[i].vex1],pen[i].w);

printf("\n");

int main(int argc, char* argv[])

printf("303 柳曉雅最小生成樹\n");

ELGraph g;

ENode *pe=g.edgelist;

g.vexnum=7;

g.edgenum=10;

g.vexlist[0]="v0"; g.vexlist[1]="v1";g.vexlist[2]="v2";

g.vexlist[3]="v3";g.vexlist[4]="v4";g.vexlist[5]="v5";

g.vexlist[6]="v6";

pe[0].vex1=0; pe[0].vex2=5; pe[0].w=8;

pe[1].vex1=0; pe[1].vex2=6; pe[1].w=16;

pe[2].vex1=1; pe[2].vex2=2; pe[2].w=6;

pe[3].vex1=1; pe[3].vex2=3; pe[3].w=5;

pe[4].vex1=2; pe[4].vex2=3; pe[4].w=9;

pe[5].vex1=2; pe[5].vex2=5; pe[5].w=13;

pe[6].vex1=3; pe[6].vex2=4; pe[6].w=16;

pe[7].vex1=3; pe[7].vex2=6; pe[7].w=12;

pe[8].vex1=4; pe[8].vex2=5; pe[8].w=15;

pe[9].vex1=4; pe[9].vex2=6; pe[9].w=7;

/* g.edgelist[0].vex1=0;g.edgelist[0].vex2=1;g.edgelist[0].w=10;

g.edgelist[1].vex1=0;g.edgelist[1].vex2=4;g.edgelist[1].w=9;

g.edgelist[2].vex1=0;g.edgelist[2].vex2=5;g.edgelist[2].w=15;

g.edgelist[3].vex1=1;g.edgelist[3].vex2=2;g.edgelist[3].w=1;

g.edgelist[4].vex1=1;g.edgelist[4].vex2=3;g.edgelist[4].w=6;

g.edgelist[5].vex1=1;g.edgelist[5].vex2=5;g.edgelist[5].w=11;

g.edgelist[6].vex1=2;g.edgelist[6].vex2=3;g.edgelist[6].w=6;

g.edgelist[7].vex1=3;g.edgelist[7].vex2=4;g.edgelist[7].w=8;

g.edgelist[8].vex1=3;g.edgelist[8].vex2=5;g.edgelist[8].w=4;

g.edgelist[9].vex1=4;g.edgelist[9].vex2=5;g.edgelist[9].w=13;

ENode *pen=Prim_MST(&g);

ENode *pen2= Kruskal_MST(&g);

char ss[100];

while(1){

printf("請輸入頂點資料,輸入0退出:");

scanf("%s",ss);

if(ss[0]=='0') break;

printf("Prim 算法生成樹: ");

PrintV(&g, pen, ss);

printf("Kruskal算法生成樹:");

PrintV(&g, pen2, ss);

printf("\n");

free(pen);

free(pen2);

return 0;

周總結&lt;7&gt;

周總結<7>