ln22.c

有关数据结构的一些例子。用C语言编写的。非常有价值的程序。对初学者有指导借鉴意义。

#include "stdio.h"
#include "malloc.h"
#include "graphics.h"
#define n 4
#define e 5
#define z 6
#define tn 6
#define TRUE 1
#define max 1000
#define NULL 0

typedef char vextype;
typedef int adjtype;
typedef int datatype;


typedef struct tnode
{
	int adjvex;
	struct tnode *next;
}tnode;

typedef struct
{
	vextype vertex;
	int id;
	tnode *link;
}vext;

vext dig[ tn ];


typedef struct nn
{
	datatype data;
	struct nn *next;
}linklist;


typedef struct
{
	vextype vexs[ n ];
	adjtype arcs[ n ][ n ];
}graph;

graph *ga, g;

typedef struct node
{
	int adjvex;
	struct node *next;
}edgenode;

typedef struct
{
	vextype vertex;
	edgenode *link;
}vexnode;

vexnode gg[ n ];

typedef struct
{
	linklist *front, *rear;
}queue;

queue *q;

typedef struct
{
	int dist[ z ][ z ];
}web;

web wb;


typedef struct
{
	int fromvex, endvex;
	float length;
}edge;

edge T[ z - 1 ];

void SET( q )
queue *q;
{
	q->front = malloc( sizeof( linklist ) );
	q->front->next = NULL;
	q->rear = q->front;
}

int EMPTY( q )
queue *q;
{
	if( q->front == q->rear )
		return( 1 );
	else
		return( 0 );
}

void ENQUEUE( q, x )
queue *q;
datatype x;
{
	q->rear->next = malloc( sizeof( linklist ) );
	q->rear = q->rear->next;
	q->rear->data = x;
	q->rear->next = NULL;
}

datatype DEQUEUE( q )
queue *q;
{
	linklist *s;
	if( EMPTY( q ) )
	{
		printf("\n 队为空! ");
		return NULL;
	}
	else
	{
		s = q->front;
		q->front = q->front->next;
		free( s );
		return( q->front->data );
	}
}

int i;

void CREATF()
{
	int i, j, ee, k;
	for( i = 0; i < z; i++ )
		for( j = 0; j < z; j++ )
		{
			wb.dist[ i ][ j ] = max;
			if( i == j )
				wb.dist[ i ][ j ] = 0;
		}
	getchar();
	printf("\n 设连通有向网络的顶点为5,边数为7 ");
	getchar();
	printf("\n 各边权值关系如下: ");
	printf("\n (1)=====>(2): 10 ");
	printf("\n (1)=====>(4): 30 ");
	printf("\n (1)=====>(5): 100 ");
	printf("\n (2)=====>(3): 50 ");
	printf("\n (3)=====>(5): 10 ");
	printf("\n (4)=====>(3): 20 ");
	printf("\n (4)=====>(5): 60 ");
	for( k = 0; k < 7; k++ )
	{
		printf("\n 输入边（Vi,Vj）的顶点对的序号（输入数字1至5）及 该边上的权值: ");
		scanf("%1d%1d%d", &i, &j, &ee );
		wb.dist[ i ][ j ] = ee;
	}
}


void CREATD()
{
	int j, ee, k;
	for( i = 0; i < e; i++ )
		for( j = 0; j < e; j++ )
			wb.dist[ i ][ j ] = max;
	getchar();
	for( k = 0; k < 7; k++ )
	{
		printf("\n 输入边（Vi,Vj）的顶点对的序号（输入数字1至5）及 该边上的权值: ");
		scanf("%1d%1d%d", &i, &j, &ee );
		wb.dist[ i - 1 ][ j - 1 ] = ee;
	}
}

void CREATW()
{
	int j, ee, k;
	for( j = 0; j < z*z; j++ )
		wb.dist[ i ][ j ] = max;
	getchar();
	for( k = 0; k < 10; k++ )
	{
		printf("\n 输入边（Vi,Vj）的顶点对的序号（输入数字1至6）及 该边上的权值: ");
		scanf("%1d%1d%1d", &i, &j, &ee );
		wb.dist[ i - 1 ][ j - 1 ] = ee;
		wb.dist[ j - 1 ][ i - 1 ] = ee;
	}
}


void CREATG()
{
	int i, j, k;
	printf("\n 输入4个顶点的字符: ");
	for( i = 0; i < n; i++ )
		g.vexs[ i ] = getchar();
	for( i = 0; i < n; i++ )
		for( j = 0; j < n; j++ )
			g.arcs[ i ][ j ] = 0;
	getchar();
	for( k = 0; k < e; k++ )
	{
		printf("\n 输入边（Vi,Vj）的顶点对的序号（输入数字1至4）: ");
		scanf("%1d%1d", &i, &j );
		g.arcs[ i - 1][ j - 1 ] = 1;
		g.arcs[ j - 1 ][ i - 1 ] = 1;
	}
}


void CREATA()
{
	int i, j, k;
	edgenode *s;
	printf("\n 输入4个顶点的字符: ");
	for( i = 0; i < n; i++ )
	{
		gg[ i ].vertex = getchar();
		gg[ i ].link = NULL;
	}
	getchar();
	for( k = 0; k < e; k++ )
	{
		printf("\n 输入边（Vi,Vj）的顶点对的序号（输入数字1至4）: ");
		scanf("%1d%1d", &i, &j );
		s = malloc( sizeof( edgenode ) );
		s->adjvex = j - 1;
		s->next = gg[ i - 1 ].link;
		gg[ i - 1 ].link = s;
		s = malloc( sizeof( edgenode ) );
		s->adjvex = i - 1;
		s->next = gg[ j - 1 ].link;
		gg[ j - 1 ].link = s;
	}
}


void CREATT()
{
	int i, j, k;
	tnode *s;
	printf("\n 输入6个顶点的字符信息: ");
	for( i = 0; i < tn; i++ )
	{
		dig[ i ].vertex = getchar();
		dig[ i ].link = NULL;
	}
	getchar();
	printf("\n 设该有向连通网络边数为8 ");
	getchar();
	printf("\n 输入各顶点的入度: ");
	for( i = 0; i < tn; i++ )
		scanf("%1d", &dig[ i ].id );

	getchar();
	for( k = 0; k < 8; k++ )
	{
		printf("\n 输入边（Vi,Vj）的顶点对的序号（输入数字1至6）: ");
		scanf("%1d%1d", &i, &j );
		s = malloc( sizeof( tnode ) );
		s->adjvex = j - 1;
		s->next = dig[ i - 1 ].link;
		dig[ i - 1 ].link = s;
		s = malloc( sizeof( tnode ) );
		s->adjvex = i - 1;
		s->next = dig[ j - 1 ].link;
		dig[ j - 1 ].link = s;
	}
}



int visited[ n ];

void SETNULL()
{
	int i;
	for( i = 0; i < n; i++ )
		visited[ i ] = 0;
}

void DFS( i )
int i;
{
	int j;
	printf("\n 顶点: %c\n", g.vexs[ i ] );
	visited[ i ] = TRUE;
	for( j = 0; j < n; j++ )
		if( ( g.arcs[ i ][ j ] == 1 ) && ( !visited[ j ] ) )
			DFS( j );
}


void BFS( k )
int k;
{
	int i, j;
	SET( q );
	printf("\n 顶点: %c \n", g.vexs[ k ] );
	visited[ k ] = TRUE;
	ENQUEUE( q, k );
	while( !EMPTY( q ) )
	{
		i = DEQUEUE( q );
		for( j = 0; j < n; j++ )
			if( ( g.arcs[ i ][ j ] == 1 ) && ( !visited[ j ] ) )
			{
				printf("\n 顶点: %c \n", g.vexs[ j ] );
				visited[ j ] = TRUE;
				ENQUEUE( q, j );
			}
	}
}


void DFSL( i )
int i;
{
	edgenode *p;
	printf("\n 顶点: %c\n ", gg[ i ].vertex );
	visited[ i ] = TRUE;
	p = gg[ i ].link;
	while( p != NULL )
	{
		if( !visited[ p->adjvex ] )
			DFSL( p->adjvex );
		p = p->next;
	}
}

void BFSL( k )
int k;
{
	int i;
	edgenode *p;
	SET( q );
	printf("\n 顶点: %c\n ",gg[ k ].vertex );
	visited[ k ] = TRUE;
	ENQUEUE( q, k );
	while( !EMPTY( q ) )
	{
		i = DEQUEUE( q );
		p = gg[ i ].link;
		while( p != NULL )
		{
			if( !visited[ p->adjvex ] )
			{
				printf("\n 顶点: %c\n ",gg[ p->adjvex ].vertex );
				visited[ p->adjvex ] = TRUE;
				ENQUEUE( q, p->adjvex );
			}
			p = p->next;
		}
	}
}


void Prim()
{
	int j, k, m, v, min, maxs = 10000;
	float d;
	edge ed;
	for( j = 1; j < z; j++ )
	{
		T[ j - 1 ].fromvex = 1;
		T[ j - 1 ].endvex = j + 1;
		T[ j - 1 ].length = wb.dist[ 0 ][ j ];
	}
	for( k = 0; k < z - 1; k++ )
	{
		min = maxs;
		for( j = k; j < z - 1; j++ )
			if( T[ j ].length < min )
			{
				min = T[ j ].length;
				m = j;
			}
		ed = T[ m ];
		T[ m ] = T[ k ];
		T[ k ] = ed;
		v = T[ k ].endvex;
		for( j = k + 1; j < z - 1; j++ )
		{
			d = wb.dist[ v - 1 ][ T[ j ].endvex - 1];
			if( d < T[ j ].length )
			{
				T[ j ].length = d;
				T[ j ].fromvex = v;
			}
		}
	}
}


void Print()
{
	int i;
	printf("\n\n\n Prim算法构成的最小生成树各顶点间关系为:");
	for( i = 0; i < z - 1; i++ )
	{
		printf("\n     (%d)========(%d)",T[ i ].fromvex, T[ i ].endvex );
	}
}


int P[ e ], S[ e ], D[ e ];


void DIJKSTRA( v )
int v;
{
	int i, j, k, v1, pre;
	int min, inf = max + 80;
	v1 = v - 1;
	for( i = 0; i < e; i++ )
	{
		D[ i ] = wb.dist[ v1 ][ i ];
		if( D[ i ] != max )
			P[ i ] = v;
		else
			P[ i ] = 0;
	}
	for( i = 0; i < e; i++ )
		S[ i ] = 0;
	S[ v1 ] = 1;
	D[ v1 ] = 0;
	for( i = 0; i < e - 1; i++ )
	{
		min = inf;
		for( j = 0; j < e; j++ )
			if( ( !S[ j ] ) && ( D[ j ] < min ) )
			{
				min = D[ j ];
				k = j;
			}
		S[ k ] = 1;
		for( j = 0; j < e; j++ )
			if( ( !S[ j ] ) && ( D[ j ] > D[ k ] + wb.dist[ k ][ j ] ) )
			{
				D[ j ] = D[ k ] + wb.dist[ k ][ j ];
				P[ j ] = k + 1;
			}
	}
	for( i = 0; i < e; i++ )
	{
		if( D[ i ] == max )
			printf("\n 最短距离为: MAX!\n   (%d)", i + 1 );
		else
			printf("\n 最短距离为: %d\n   (%d)", D[ i ], i + 1 );
		pre = P[ i ];
		while( pre != 0 )
		{
			printf(" <-- (%d)", pre );
			pre = P[ pre - 1 ];
		}
	}
}


int path[ z ][ z ], A[ z ][ z ];