本文目錄一覽：
c語言中什麼結構用來測試某個特定的變量或表達式是否等於每一個假設
用分支結構可以做到
也就是所說的開關語句
switch case。
這個是用來專門做整型常數的判斷的。
c語言數據結構（考題，測試你的能力）－－編寫源代碼
P88 稀疏矩陣十字鏈表相加算法如下：
/*假設ha為A稀疏矩陣十字鏈表的頭指針，hb為B稀疏矩陣十字鏈表的頭指針*/
#includestdio.h
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};
struct linknode creatlindmat( ) /*建立十字鏈表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf(“請輸入稀疏矩陣的行、列數及非零元個數\n”);
scanf(“%d%d%d”,m,n,t);
if (mn) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm-i=m; hm-j=n;
cp[0]=hm;
for (i=1; i=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p-i=0; p-j=0;
p-rptr=p; p-cptr=p;
cp[i]=p;
cp[i-1]-k.next=p;
}
cp[s]-k.next=hm;
for( x=1;x=t;x++)
{ printf(“請輸入一個三元組(i,j,v)\n”);
scanf(“%d%d%d”,i,j,k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p-i=i; p-j=j; p-k.v=k;
/*以下是將p插入到第i行鏈表中 */
q=cp[i];
while ((q-rptr!=cp[i]) ( q-rptr-jj))
q=q-rptr;
p-rptr=q-rptr;
q-rptr=p;
/*以下是將P插入到第j列鏈表中*/
q=cp[j];
while((q-cptr!=cp[j]) ( q-cptr-ii))
q=q-cptr;
p-cptr=q-cptr;
q-cptr=p;
}
return hm;
}
/* ha和hb表示的兩個稀疏矩陣相加，相加的結果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha-i!=hb-i)||(ha-j!=hb-j))
printf(“矩陣不匹配,不能相加\n”);
else
{ p=ha-k.next; n=ha-j;
for (i=1;i=n; i++)
{ hl[i]=p;
p=p-k.next;
}
ca=ha-k.next; cb=hb-k.next;
while(ca-i==0)
{pa=ca-rptr; pb=cb-rptr;
qa=ca;
while(pb-j!=0)
{ if((pa-jpb-j)(pa-j!=0))
{ qa=pa; pa=pa-rptr;}
else if ((pa-jpb-j)||(pa-j==0)) /*插入一個結點*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p-i=pb-i; p-j=pb-j;
p-k.v=pb-k.v;
qa-rptr=p; p-rptr=pa;
qa=p; pb=pb-rptr;
j=p-j; q=hl[j]-cptr;
while((q-ip-i)(q-i!=0))
{ hl[j]=q; q=hl[j]-cptr;}
hl[j]-cptr=p; p-cptr=q;
hl[j]=p;
}
else
{pa-k.v=pa-k.v+pb-k.v;
if(pa-k.v==0) /*刪除一個結點*/
{ qa-rptr=pa-rptr;
j=pa-j; q=hl[j]-cptr;
while (q-ipa-i)
{hl[j]=q; q=hl[j]-cptr;}
hl[j]-cptr=q-cptr;
pa=pa-rptr; pb=pb-rptr;
free(q);
}
else
{ qa=pa; pa=pa-rptr;
pb=pb-rptr;
}
}
}
ca=ca-k.next; cb=cb-k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*輸出十字鏈表*/
{ struct linknode *p,*q;
p=ha-k.next;
while(p-k.next!=ha)
{ q=p-rptr;
while(q-rptr!=p)
{ printf(“%3d%3d%3d\t”,q-i,q-j,q-k.v);
q=q-rptr;
}
if(p!=q)
printf(“%3d%3d%3d”,q-i,q-j,q-k.v);
printf(“\n”);
p=p-k.next;
}
q=p-rptr;
while(q-rptr!=p)
{ printf(“%3d%3d%3d\t”,q-i,q-j,q-k.v);
q=q-rptr;
}
if(p!=q)
printf(“%3d%3d%3d”,q-i,q-j,q-k.v);
printf(“\n”);
}
void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一個十字鏈表ha*/
hb=creatlindmat( ); /*生成另一個十字鏈表hb*/
printf(“A:\n”); /*輸出十字鏈表ha*/
print(ha);printf(“\n”);
printf(“B:\n”); /*輸出十字鏈表hb*/
print(hb);printf(“\n”);
hc=matadd(ha,hb); /*十字鏈表相加*/
printf(“A+B:\n”); /*輸出相加後的結果*/
print(hc);printf(“\n”);
}
P94 數據類型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}
P95 數據類型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
P96 求廣義表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS-atom==0) //有子表
{ dep=depth(LS-ds.slink);
if(depmax) max=dep;
}
LS=LS-link;
}
return max+1;
}
P96 廣義表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf(“%c”,ch);
if(ch==’#’)
LS=NULL;
else if(ch=='(‘)
{LS=(struct node*)malloc(sizeof(struct node));
LS-atom=0;
creat(LS-ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS-atom=1;
LS-ds.data=ch;
}
scanf(“%c”,ch);
if(LS==NULL);
else if(ch==’,’)
creat(LS-link);
else if((ch==’)’)||(ch==’;’))
LS-link=NULL;
}
P97 輸出廣義表print(LS)
void print(struct node1 *LS)
{
if(LS-atom==0)
{
printf(“(“);
if(LS-ds.slink==NULL)
printf(“#”);
else
print(LS-ds.slink);
}
else
printf(“%c “,LS-ds.data);
if(LS-atom==0)
printf(“)”);
if(LS-link!=NULL)
{
printf(“;”);
print(LS-link);
}
}
P98 該算法的時間複雜度為O(n)。整個完整程序如下：
#includestdio.h
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};
void creat(struct node1 LS) /*建立廣義表的單鏈表*/
{
char ch;
scanf(“%c”,ch);
if(ch==’#’)
LS=NULL;
else if(ch=='(‘)
{LS=(struct node1*)malloc(sizeof(struct node1));
LS-atom=0;
creat(LS-ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS-atom=1;
LS-ds.data=ch;
}
scanf(“%c”,ch);
if(LS==NULL);
else if(ch==’,’)
creat(LS-link);
else if((ch==’)’)||(ch==’;’))
LS-link=NULL;
}
void print(struct node1 LS) /*輸出廣義單鏈表*/
{
if(LS-atom==0)
{
printf(“(“);
if(LS-ds.slink==NULL)
printf(“#”);
else
print(LS-ds.slink);
}
else
printf(“%c”,LS-ds.data);
if(LS-atom==0)
printf(“)”);
if(LS-link!=NULL)
{
printf(“;”);
print(LS-link);
}
}
int depth(struct node1 LS) /*求廣義表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS-atom==0)
{ int dep=depth(LS-ds.slink);
if(depmax) max=dep;
}
LS=LS-link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立廣義表的單鏈表*/
print(p); /*輸出廣義單鏈表*/
dep=depth(p); /*求廣義表的深度*/
printf(“%d\n”,dep);
}
第六章 樹
P109 二叉鏈表的結點類型定義如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;
P109 三叉鏈表的結點類型定義如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;
P112 C語言的先序遍歷算法：
void preorder (tnodetype *t)
/*先序遍歷二叉樹算法，t為指向根結點的指針*/
{ if (t!=NULL)
{printf(“%d “,t-data);
preorder(t-lch);
preorder(t-rch);
}
}
P113 C語言的中序遍歷算法：
void inorder(tnodetype *t)
/*中序遍歷二叉樹算法，t為指向根結點的指針*/
{
if(t!=NULL)
{inorder(t-lch);
printf(“%d “,t-data);
inorder(t-rch);
}
}
P113 C語言的後序遍歷算法：
void postorder(tnodetype *t)
/*後序遍歷二叉樹算法，t為指向根結點的指針*/
{
if(t!=NULL)
{ postorder(t-lch);
postorder(t-rch);
printf(“%d “,t-data);
}
}
P114 如果引入隊列作為輔助存儲工具，按層次遍歷二叉樹的算法可描述如下：
void levelorder(tnodetype *t)
/*按層次遍歷二叉樹算法，t為指向根結點的指針*/
{tnodetype q[20]; /*輔助隊列*/
front=0;
rear=0; /*置空隊列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根結點入隊*/
}
while (front!=rear)
{ front++;
t=q [front];
printf (“%c\n”,t-data);
if (t-lch!=NULL) /*t的左孩子不空，則入隊*/
{ rear++;
q [rear]=t-lch;
}
if (t-rch!=NULL) /*t的右孩子不空，則入隊*/
{ rear++;
q [rear]=t-rch;
}
}
}
P115 以中序遍歷的方法統計二叉樹中的結點數和葉子結點數，算法描述為：
void inordercount (tnodetype *t)
/*中序遍歷二叉樹，統計樹中的結點數和葉子結點數*/
{ if (t!=NULL)
{ inordercount (t-lch); /*中序遍歷左子樹*/
printf (“%c\n”,t-data); /*訪問根結點*/
countnode++; /*結點計數*/
if ((t-lch==NULL)(t-rch==NULL))
countleaf++; /*葉子結點計數*/
inordercount (t-rch); /*中序遍歷右子樹*/
}
}
P115 可按如下方法計算一棵二叉樹的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍歷二叉樹，並計算二叉樹的深度*/
{ if (t!=NULL)
{ printf (“%c\n”,t-data); /*訪問根結點*/
j++;
if (kj) k=j;
preorderdeep (t-lch,j); /*先序遍歷左子樹*/
preorderdeep (t-rch,j); /*先序遍歷右子樹*/
}
}
P117 線索二叉樹的結點類型定義如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右標誌域*/
}
P117 中序次序線索化算法
void inorderxs (struct nodexs *t)
/*中序遍歷t所指向的二叉樹，並為結點建立線索*/
{ if (t!=NULL)
{ inorderxs (t-lch);
printf (“%c\n”,t-data);
if (t-lch!=NULL)
t-ltag=0;
else { t-ltag=1;
t-lch=pr;
} /*建立t所指向結點的左線索，令其指向前驅結點pr*/
if (pr!=NULL)
{ if (pr-rch!=NULL)
pr-rtag=0;
else { pr-rtag=1;
pr-rch=p;
}
} /*建立pr所指向結點的右線索，令其指向後繼結點p*/
pr=p;
inorderxs (t-rch);
}
}
P118 在中根線索樹上檢索某結點的前驅結點的算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的前驅結點*/
{ if (q-ltag==1)
p=q-lch;
else { r=q-lch;
while (r-rtag!=1)
r=r-rch;
p=r;
}
return (p);
}
P119 在中根線索樹上檢索某結點的後繼結點的算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的後繼結點*/
{ if (q-rtag==1)
p=q-rch;
else { r=q-rch;
while (r-ltag!=1)
r=r-lch;
p=r;
}
return (p);
}
P120 算法程序用C語言描述如下：
void sortBT(BT *t,BT *s) /*將指針s所指的結點插入到以t為根指針的二叉樹中*/
{ if (t==NULL) t=s; /*若t所指為空樹，s所指結點為根*/
else if (s-data t-data)
sortBT(t-lch,s); /*s結點插入到t的左子樹上去*/
else
sortBT(t-rch,s); /*s結點插入到t的右子樹上去*/
}
P121 二叉排序樹結點刪除算法的C語言描述如下：
void delnode(bt,f,p)
/*bt為一棵二叉排序樹的根指針，p指向被刪除結點，f指向其雙親*/
/*當p=bt時f為NULL*/
{ fag=0; /*fag=0時需修改f指針信息，fag=1時不需修改*/
if (p-lch==NULL)
s=p-rch; /*被刪除結點為葉子或其左子樹為空*/
else if (p-rch==NULL)
s=p-lch;
else { q=p; /*被刪除結點的左、右子樹均非空*/
s=p-lch;
while (s-rch!=NULL)
{ q=s;
s=s-rch;
} /*尋找s結點*/
if (q=p)
q-lch=s-lch;
else q-rch=s-lch;
p-data=s-data; /*s所指向的結點代替被刪除結點*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改雙親指針*/
{ if (f=NULL)
bt=s; /*被刪除結點為根結點*/
else if (f-lch=p)
f-lch=s;
else f-rch=s;
DISPOSE(p); /*釋放被刪除結點*/
}
}
第七章 圖
P134 用鄰接矩陣表示法表示圖，除了存儲用於表示頂點間相鄰關係的鄰接矩陣外，通常還需要用一個順序表來存儲頂點信息。其形式說明如下：
# define n 6 /*圖的頂點數*/
# define e 8 /*圖的邊(弧)數*/
typedef char vextype; /*頂點的數據類型*/
typedef float adjtype; /*權值類型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;
P135 建立一個無向網絡的算法。
CREATGRAPH(ga) /*建立無向網絡*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;in;i++ )
ga -vexs[i]＝getchar(); /*讀入頂點信息，建立頂點表*/
for(i＝0;in;i++ )
for(j＝0;jn;j++)
ga -arcs[i][j]＝0; /*鄰接矩陣初始化*/
for(k＝0;ke;k++) /*讀入e條邊*/
(scanf(“％d％d％f”,I,j,w); /*讀入邊(vi,vj)上的權w */
ga -arcs[i][j]＝w;
ga – arcs[j][i]＝w;
}
} /*CREATGRAPH*/
P136 鄰接表的形式說明及其建立算法：
typedef struct node
{int adjvex; /*鄰接點域*/
struct node * next; /*鏈域*/
}edgenode; /*邊表結點*/
typedef struct
{vextype vertex; /*頂點信息*/
edgenode link; /*邊表頭指針*/
}vexnode; /*頂點表結點*/
vexnode ga[n];
CREATADJLIST(ga) /*建立無向圖的鄰接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;in;i++＝ /*讀入頂點信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*邊表頭指針初始化*/
}
for(k＝0;ke;k++＝ /*建立邊表*/
{scanf(“％d％d”,i,j); /*讀入邊(vi , vj)的頂點對序號*/
s＝malloc(sizeof(edgenode)); /*生成鄰接點序號為j的表結點*s */
s- adjvex＝j;
s- – next：＝ga[i].Link;
ga[i].1ink＝s; /*將*s插入頂點vi的邊表頭部*/
s＝malloc(size0f(edgende)); /*生成鄰接點序號為i的邊表結點*s */
s -adjvex＝i;
s -next＝ga[j].1ink;
ga[j].1ink＝s; /*將*s插入頂點vj的邊表頭部*/
}
} /* CREATADJLIST */
P139 分別以鄰接矩陣和鄰接表作為圖的存儲結構給出具體算法，算法中g、g1和visited為全程量，visited的各分量初始值均為FALSE。
int visited[n] /*定義布爾向量visitd為全程量*/
Graph g; /*圖g為全程量*/
DFS(i) /*從Vi+1出發深度優先搜索圖g，g用鄰接矩陣表示*/
int i;
{ int j;
printf(“node：％c＼n” , g.vexs[i]); /*訪問出發點vi+1 */
Visited[i]＝TRUE; /*標記vi+l已訪問過*/
for (j＝0;jn;j++) /*依次搜索vi+1的鄰接點*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的鄰接點vj+l未曾訪問過，則從vj+l出發進行深度優先搜索*/
} /*DFS*/
vexnode gl[n] /*鄰接表全程量*/
DFSL(i) /*從vi+l出發深度優先搜索圖g1，g1用鄰接表表示*/
int i;
{ int j;
edgenode * p;
printf(“node：％C\n” ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{
if(! Vistited[p -adjvex])
DFSL(p – adjvex); /*從vi+1的未曾訪問過的鄰接點出發進行深度優先搜索*/
p＝p – next; /*找vi+l的下一個鄰接點*/
}
} /* DFSL */
P142 以鄰接矩陣和鄰接表作為圖的存儲結構，分別給出寬度優先搜索算法。
BFS(k) /＊從vk+l出發寬度優先搜索圖g，g用鄰接矩陣表示，visited為訪問標誌向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空隊Q */
printf(“％c＼n”，g.vexs[k]); /*訪問出發點vk+l*x/
visited[k]＝TRUE; /*標記vk+l已訪問過*/
ENQUEUE(Q，K); /*已訪問過的頂點(序號)入隊列*/
While(!EMPTY(Q)) /*隊非空時執行*/
{i＝DEQUEUE(Q); /*隊頭元素序號出隊列*/
for(j＝0;jn;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf(“％c＼n” , g.vexs[j]); /*訪問vi+l的未曾訪問的鄰接點vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*訪問過的頂點入隊*/
}
}
} /* BFS */
BFSL(k) /*從vk+l出發寬度優先搜索圖g1，g1用鄰接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf(“％c＼n” , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{ if( ! visited[p – adjvex]) /*訪問vi+l的未訪問的鄰接點*/
{ printf{“％c＼n” , g1[p – adjvex].vertex};
visited[p – adjvex]＝TRUE;
ENQUEUE(Q,p – adjvex); /*訪問過的頂點入隊*/
}
p＝p – next; /*找vi+l的下一個鄰接點*/
}
}
} /*BFSL*/
P148 在對算法Prim求精之前，先確定有關的存儲結構如下：
typdef struct
{Int fromvex，endvex; /*邊的起點和終點*/
float length; /*邊的權值*/
} edge;
float dist[n][n]; /*連通網絡的帶權鄰接矩陣*/
edgeT[n-1]; /*生成樹*/
P149 抽象語句(1)可求精為：
for(j=1;jn;j++) /*對n-1個藍點構造候選紫邊集*/
{T[j-1].fromvex＝1}; /*紫邊的起點為紅點*/
T[j-1].endvex＝j+1; /*紫邊的終點為藍點*/
T[j-1].1ength＝dist[0][j]; /*紫邊長度*/
}
P149 抽象語句(3)所求的第k條最短紫邊可求精為：
min＝max; /*znax大於任何邊上的權值*/
for (j＝k;jn-1;j++) /*掃描當前候選紫邊集T[k]到T[n-2]，找最短紫邊*/
if(T[j].1engthmin)
{min＝T[j].1ength;m＝j; /*記錄當前最短紫邊的位置*/
}
P149 抽象語句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交換*/
v＝T[kl.Endvex]; /* v是剛被塗紅色的頂點*/
P149 抽象語句(5)可求精為：
for(j＝k+1;jn-1;j++) /*調整候選紫邊集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫邊的長度*/
if(dT[j].1ength) /*新紫邊的長度小於原最短紫邊*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫邊取代原最短紫邊*/
}
}
P150 完整的算法：
PRIM() /*從第一個頂點出發構造連通網絡dist的最小生成樹，結果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;jn;j++) /*構造初始候選紫邊集*/
{T[j-1].formvex＝1; /*頂點1是第一個加入樹中的紅點*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;kn-1;k++) /*求第k條邊*/
{min＝max;
for(j＝k;jn-1;j++) /*在候選紫邊集中找最短紫邊*/
if(T[j].1engthmin)
{min＝T[j].1ength;
m＝j;
} /*T[m]是當前最短紫邊*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交換後，T[k]是第k條紅色樹邊*/
v＝T[k].endvex ; /* v是新紅點*/
for(j＝k+1;jn-1;j++) /*調整候選紫邊集*/
{d＝dist[v-1][T[j].endvex-1];
if(dT[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */
P151 Kruskl算法的粗略描述：
T＝(V,φ);
While(T中所含邊數n-1)
{從E中選取當前最短邊(u,v);
從E中刪去邊(u,v);
if((u,v)併入T之後不產生迴路，將邊(u,v)併入T中;
}
P153 迪傑斯特拉算法實現。算法描述如下：
#define max 32767 /*max代表一個很大的數*/
void dijkstra (float cost[][n],int v)
/*求源點v到其餘頂點的最短路徑及其長度*/
{ v1=v-1;
for (i=0;in;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;in;i++)
s[i]=0; /*s數組初始化為空*/
s[v1]=1; /*將源點v歸入s集合*/
for (i=0;in;i++)
{ min=max;
for (j=0;jn;j++)
if (!s[j] (dist[j]min))
{ min=dist[j];
k=j;
} /*選擇dist值最小的頂點k+1*/
s[k]=1; /*將頂點k+1歸入s集合中*/
for (j=0;jn;j++)
if (!s[j](dist[j]dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各頂點的dist值*/
pre[j]=k+1; /*k+1頂點是j+1頂點的前驅*/
}
} /*所有頂點均已加入到S集合中*/
for (j=0;jn;j++) /*打印結果*/
{ printf(“%f\n%d”,dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf(“%d”,p);
p=pre[p-1];
}
}
}
P155 弗洛伊德算法可以描述為：
A(0)[i][j]=cost[i][j]; //cost為圖的鄰接矩陣
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
P155 弗洛伊德算法實現。算法描述如下：
int path[n][n]; /*路徑矩陣*/
void floyd (float A[][n],cost[][n])
{ for (i=0;in;i++) /*設置A和path的初值*/
for (j=0;jn;j++)
{ if (cost[i][j]max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;kn;k++)
/*做n次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑上*/
for (i=0;in;i++)
for (j=0;jn;j++)
if (A[i][j](A[i][k]+A[k]
C語言結構體的問題，主要是個小測試
點號和箭頭是不同的，
點號表示是直接引用，其表示操作對象是左邊這個對象本身。所以都是針對實體來操作的。
箭頭表示是間接引用，其表示操作對象是左邊所指向的對象。所以操作對象是指針。
你這裡申明了是一個指針，所以一定是使用箭頭的。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/160843.html
微信掃一掃 
支付寶掃一掃 