数据结构源代码(C语言描述)(7)

if (k

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 (\ 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 insertbst(t,s)

/*将指针s所指的结点插入到以t为根指针的二叉树中*/ { if (t==NULL)

t=s; /*若t所指为空树，s所指结点为根*/ else if (s->data < t->data)

insertbst(t->lch,s); /*s结点插入到t的左子树上去*/ else

insertbst(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); /*释放被删除结点*/ 数据结构源代码归纳(三)

2008年08月01日 星期五 23:47

第七章 图

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;i

ga ->vexs[i]＝getchar(); /*读入顶点信息，建立顶点表*/ for(i＝0;i

ga ->arcs[i][j]＝0; /*邻接矩阵初始化*/ for(k＝0;k

(scanf(\％d％d％f\/*读入边(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;i

ga[i].1ink＝NULL; /*边表头指针初始化*/ }

for(k＝0;k

{scanf(\％d％d\/*读入边(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(\：％c＼n\/*访问出发点vi+1 */ Visited[i]＝TRUE； /*标记vi+l已访问过*/

for (j＝0;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(\：％C\\n\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;j

if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))

{printf(\％c＼n\/*访问vi+l的未曾访问的邻接点vj+l */ visited[j]＝TRUE;

ENQUEUE(Q,j); /*访问过的顶点入队*/ } }

} /* BFS */

BFSL(k) /*从vk+l出发宽度优先搜索图g1，g1用邻接表表示*/ int k { int i;