test.txt

在线教育网

void inorder(bitreptr r)
{
	if(r != NULL){
		inorder(r->lchild);
		visit(r);
		inorder(r->rchild);
	}
}
void postorder(bitreptr r)
{
	if(r != NULL){
		postorder(r->lchild);
		postorder(r->rchild);
		visit(r);
	}
}
		
long f(int n)
/* 计算n！，假定输入n>=0 */
{
	if(n==0)
		return (1);
	else
		return (n*f(n-1));
}
int f1(int n)
/* 计算n!的循环算法，假定输入n>=0 */
{
	y=1;/* 计算y = f(0) */
	for(i = 1;i <= n;i ++)
		y = y * i;
	return(y);
}
int b(int n)
/* 计算Fib(n)的递归算法 */
{
	if(n == 0) return (0);
	else if(n==1) return (1);
	else	return (b(n-1) + b(n-2));
}

int b1(int n)
{
	if(n == 0) return 0;
	else{
		x = 0;
		y = 1;
	for(i = 2;i <= n;i ++){
	z = y;
	y = x + y;
	x = z;
	}
	return (y);
}
}
while(栈不空)
{
	s = 栈顶元素；
	退栈；
	while(s != NULL){		/*根或左右子树不空时继续遍历*/
		visit(s);		
		s -> rchild 进栈；	/*保存右指针*/
		s = s -> lchild;	/*准备遍历左子树*/
	}
}	

void preorder(bitreptr t)
{
	bitreptr stack[stacksize];
	int top;
top = 0;
stack[top] = t;
while(top >= 0){
	s = stack[top];
	top --;
	while(s != NULL){
		visit(s);
		top ++;
		stack[top] = s -> rchild;
		s = s -> lchild;
	}
}
}

typedef struct tagnode{
	int child;
	struct tagnode *next;
}node, *link;
typedef struct{
	datatype data;
	link headptr;
}headnode;
typedef headnode childlink[axnode];

typedef struct{
	datatype data;
	int parent;
	link headptr;
}headnode l;

#define size 		/*结点数*/
typedef struct{
	datatype data;  /*数据域*/
	int parent;	/*双亲域（静态指针域）*/
}node;
typedef node statlist[size]; /*静态双亲链表*/

char classify1(float x)
/*依给定标准将测检x区分成相应的质量等级作为返回值*/
{
	if(x < 5) return ('E');
	else if(x < 6) return ('D');
	else if(x < 7) return ('C');
	else if(x < 8) return ('B');
	else	return ('A');
}

typedef struct{
	float wt
int parent,lchild,rchild;
}node;
typedef node hftree[2*n-1];

void huffman(int k,float W[k],hftree T)
/* 求给定权值W的哈夫曼树T */
{
	int i,j,x,y;
float m,n;
for(i = 0;i < 2*k-1;i ++){
	T[i].parent = -1;
	T[i].lchild = -1;
	T[i].rchild = -1;
	if(i < m)
		T[i].wt = W[i];
	else
		T[i].wt = 0;
}
for(i = 0;i < k-1;i ++){
	x = 0;
	y = 0;
	m = maxint;
	n = maxint;
	for(j = 0;j < k+i;j ++)
		if((T[j].wt < m)&&(T[j].parent==-1)){
			n = m;
y = x;
m = T[j].wt;
x = j;
}
	else if((T[j].wt<n)&&(T[j].parent == -1)){
		n = T[j].wt;
y=j;
}
T[x].parent = k + i;
T[y].parent = k + i;
T[k+i].wt = m + n;
T[k+i].lchild = x;
T[k+i].rchild = y;
}
}

#define vnum 20
typedef struct graph{
	VertexType vexs[vnum];		/*顶点信息*/
	int arcs[vnum][vnum];		/*邻接矩阵*/
	int vexnum,arcnum;		/*顶点数，弧（边）数*/
}GraphTp;

#define vnum 20
typedef 	int	GraphTp[vnum][vnum]
******************************************
#define 	INT_MAX 	32767
typedef struct graph{
	VertexType vexs[vnum];
	WeightType arcs[vnum][vnum];
	int vexnum,arcnum;
}GraphTp;

***********************************

void CreatGraph(GraphTp *ga)
{
	int i,j,n,e,w;
	char ch;
	scanf("%d %d",&n,&e);			/*读入顶点个数和边数*/
	ga -> vexnum = n;
	ga -> arcnum = e;
	for(i = 0;i < ga -> vexnum;i ++){       /*读入顶点信息*/
		scanf("%c",&ch);
		ga -> vexs[i] = ch;
	}
	for(i = 0;i < ga->vexnum;i ++)
		for(j = 0;j < ga->vexnum;j++)
			ga -> arcs[i][j] = INT_MAX; /*初始化邻接矩阵*/
	for(k = 0;k < ga->arcnum;k ++){
		scanf("%d %d %d",&i,&j,&w);         /*读入边（顶点对）和权值*/
		ga -> arcs[i][j] = w;
		ga -> arcs[j][i] = w;
	}
}
*******************************************
#define vnum 20
typedef struct arcnode{
	int adjvex;			/*下一条弧（边）的弧头（始点）编号*/
	struct arcnode *nextarc;	/*指向下一条弧（边）的指针*/
}ArcNodeTp;
typedef struct vexnode{
	int vertex;			/*顶点编号*/	
	ArcNodeTp *firstarc;		/*指向第一条弧（边）的指针*/
}AdjList[vnum];
typedef struct graph{
	AdjList adjlist;
	int vexnum,arcnum;		/*顶点和弧（边）的个数*/
}GraphTp;

*********************************************
CreatAdjlist(GraphTp *ga)
{
	int n,e,i,j,k;
	ArcNodeTp *p;
	scanf("%d %d",n,e);		/*读入顶点和边数*/
	ga -> vexnum = n;
	ga -> arcnum = e;
	for(i = 0;i < n;i++){
		ga -> adjlist[i].vertex = i;
	}
	ga -> adjlist[i].firstarc = NULL;
	for(k = 0;k < e;k ++){
		scanf("%d %d",&i,&j);
		p = (ArcNodeTp *)malloc(sizeof(ArcNodeTp));
		p -> adjvex = j;
		p -> next = ga -> adjlist[i].firstarc;
		ga -> adjlist[i].firstarc = p;

	}
}
****************************
5.3
************************
Dfs(GraphTp g,int v)
{
	访问v；
	visited[v] = 1；	/*置已访问标志*/
	找出g中v的第一个邻接点w；
	while w存在{
		if w 未被访问
			Dfs(g,w);
		w = g中v的下一个邻接点；
	}
}
*********************************
Dfs(GraphTp g,int v)
{
	ArcNodeTp *p;
	printf("%d",v);				/*访问顶点*/
	visited[v] = 1;				/*置已访问标志*/
	p = g.adjlist[v].fistarc;
	while(p != NULL){
		if(!visited[p->adjvex])
			Dfs(g,p->adjvex);
		p = p -> nextarc;
	}
}
	
*******************************************
Bfs(GraphTp g,int v)
{
	InitQueue(&Q);			/*初始化队列*/
	访问v；
	visited[v] = 1;			/*置已访问标志*/
	EnQueue(&Q,v);			/*被访问过的顶点入队列*/
	while(!EmptyQueue(Q)){
		OutQueue(&Q,&v);	/*被访问过的顶点出队列*/
		找出g中v的第一个邻接点w;
		while w 存在{
			if w未被访问{
				访问w;
				visited[w] = 1;		/*置已访问标志*/
				EnQueue(&Q,w);		/*被访问过的顶点入队列*/
			}
		w = g中v的下一个邻接点;
		}
	}
}

******************************************************

Bfs(GraphTp g,int v)
{
	QueptrTp Q;
	ArcNodeTp *p;
	InitQueue(&Q);
	printf("%d",v);
	visited[v] = 1;
	Enqueue(&Q,&v);
	while(!EmptyQueue(Q)){
		OutQueue(&Q,&v);
		p = g.adjlist[v].fistarc;
		while(p != NULL){
			if(!visited[p->adjvex]){
				printf("%d",p->adjvex);
				visited[p->adjvex] = 1;
				EnQueue(&Q,p->adjvex);
			}
			p = p -> nextarc;
		}
	}
}
************************************************************
int visited[vnum];
Count_Component(GraphTp g)
{
	int count;
	for(v = 0;v < g.vexnum;v ++)
		visited[v] = 0;				/*初始化visited数组*/
	count = 0;
	for(v = 0;v < g.vexnum;v ++)
		if(!visited[v]){
			count ++;
			printf("连通分量%d包含以下顶点：",count);
			Dfs(g,v);
			printf("\n");
		}
	printf("共有%d个连通分量\n",count);
}
****************************************
5.4
****************************************
struct{
	int adjvex;
	int lowcost;
}closedge[Vnum]
算法如下：
prim(GraphTg g,int u)
{
	int v,k,j,min;
	for(v = 0;v < g.vexnum;v ++)				/*初始化*/
		if(v != u){
			closedge[v].adjvex = u;
			closedge[v].lowcost = g.adjlist[u,v];
		}
	closedge[u],lowcost = INT_MAX;
	for(k = 0;k < g.vexnum;k ++){
		min = closedge[k].lowcost;
		v = k;
		for(j = 0;j < g.vexnum;j ++)			/*找最小值的边*/
			if(close[j].lowcost < min){
				min = close[j].lowcost;
				v = j;
			}
		printf("%d %d\n",closedge[v].adjvex,v);
		closedge[v].lowcost = INT_MAX;
		for(j = 0;j < g.vexnum;j ++)				
			if (g.adjlist[v][j] < closedge[j].lowcost){
				closedge[j].lowcost = g.adjlist[v][j];
				closedge[j].adjvex = v;
			}
	}
}
		
***************************************************
5.5
***************************************************
Top_Sort(GraphTp g)
{
	建立入度为0的顶点栈S;
	m = 0;
	while(!EmptyStack(s)){
		S出栈->v;
		输出v；
		m ++;
		w = 图g中顶点v的第一个邻接点;
		while w 存在{
			w的入度--；
			if(w的入度==0）
				w入S栈;
			w = 图g中顶点v的下一个邻接点；
		}
	}
	if(m < n)
		printf("图中有环\n");
}
********************************************************
typedef struct vexnode{
	VertexType vertex;
	int in;				/*这里增加一个入度域in*/
	ArcNodeTp *firstarc;
}AdjList[vnum];
typedef struct graph{
	AdjList adjlist;
	int vexnum,arcnum;
}GraphTp;
拓扑排序算法如下：
Top_Sort(GraphTp g){
	LStackTp *S;
	ArcNodeTp *p;
	int m,i,v;
	InitStack(S);
	for(i = 0;i < g.vexnum;i ++)
	if (g.adjlist[i].in == 0)
		Push(S,i);
	m = 0;
	while(!EmptyStack(S)){
		Pop(S,&v);
		printf("%d",v);
		m ++;
		p = g.adjlist[i].firstarc;
		while(p != NULL){
			(g.adjlist[p->adjvex].in) --;
			if(g.adjlist[p->adjvex].in == 0)
				Push(S,p->adjvex);
				p = p->nextarc;
			}
	}
	if(m < g.vexnum)
		return 0;
	else
		return 1;
}
*******************************************************************