/*假设ha为A稀疏矩阵十字链表的头指针，hb为B稀疏矩阵十字链表的头指针*/
#include<stdio.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 (m>n) s=m else s=n
hm=(struct linknode*)malloc(sizeof(struct linknode))
hm->i=mhm->j=n
cp[0]=hm
for (i=1i<=si++)
{ 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=1x<=tx++)
{printf("请输入一个三元组(i,j,v)\n")
scanf("%d%d%d",&i,&j,&k)
p=(struct linknode*)malloc(sizeof(struct linknode))
p->i=ip->j=j p->k.v=k
/*以下是将p插入到第i行链表中 */
q=cp[i]
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr
p->rptr=q->rptr
q->rptr=p
/*以下是将P插入到第j列链表中*/
q=cp[j]
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
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]
inti , j, n
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩阵不匹配,不能相加\n")
else
{ p=ha->k.nextn=ha->j
for (i=1i<=ni++)
{ hl[i]=p
p=p->k.next
}
ca=ha->k.nextcb=hb->k.next
while(ca->i==0)
{pa=ca->rptr pb=cb->rptr
qa=ca
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{qa=pa pa=pa->rptr}
else if ((pa->j>pb->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=ppb=pb->rptr
j=p->jq=hl[j]->cptr
while((q->i<p->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->i<pa->i)
{hl[j]=q q=hl[j]->cptr}
hl[j]->cptr=q->cptr
pa=pa->rptr pb=pb->rptr
free(q)
}
else
{ qa=papa=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(dep>max) 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)。整个完整程序如下：
#include<stdio.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(dep>max) 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 (k<j) 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＝0i<ni++ )
ga ->vexs[i]＝getchar() /*读入顶点信息，建立顶点表*/
for(i＝0i<ni++ )
for(j＝0j<nj++)
ga ->arcs[i][j]＝0 /*邻接矩阵初始化*/
for(k＝0k<ek++) /*读入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=oi<ni++＝/*读入顶点信息*/
(ga[i].vertex＝getchar()
ga[i].1ink＝NULL /*边表头指针初始化*/
}
for(k＝0k<ek++＝/*建立边表*/
{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＝0j<nj++) /*依次搜索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＝0j<nj++)
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=1j<nj++) /*对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＝kj<n-1j++)/*扫描当前候选紫边集T[k]到T[n-2]，找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1engthm＝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+1j<n-1j++)/*调整候选紫边集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1] /*新紫边的长度*/
if(d<T[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=1j<nj++) /*构造初始候选紫边集*/
{T[j-1].formvex＝1 /*顶点1是第一个加入树中的红点*/
T[j-1].endvex＝j+1
T[j-1].length＝dist[o][j]
}
for(k＝0k<n-1k++) /*求第k条边*/
{min＝max
for(j＝kj<n-1j++)/*在候选紫边集中找最短紫边*/
if(T[j].1ength<min)
{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+1j<n-1j++)/*调整候选紫边集*/
{d＝dist[v-1][T[j].endvex-1]
if(d<T[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=0i<ni++)
{ dist[i]=cost[v1][i] /*初始化dist*/
if (dist[i]<max)
pre[i]=v
else pre[i]=0
}
pre[v1]=0
for (i=0i<ni++)
s[i]=0 /*s数组初始化为空*/
s[v1]=1 /*将源点v归入s集合*/
for (i=0i<ni++)
{ min=max
for (j=0j<nj++)
if (!s[j] &&(dist[j]<min))
{ min=dist[j]
k=j
} /*选择dist值最小的顶点k+1*/
s[k]=1 /*将顶点k+1归入s集合中*/
for (j=0j<nj++)
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=0j<nj++) /*打印结果*/
{ 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=0i<ni++) /*设置A和path的初值*/
for (j=0j<nj++)
{ if (cost[i][j]<max)
path[i][j]=j
else { path[i][j]=0
A[i][j]=cost[i][j]
}
}
for (k=0k<nk++)
/*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0i<ni++)
for (j=0j<nj++)
if (A[i][j]>(A[i][k]+A[k]
