[数据结构与算法]数据结构实验（六）

liqueue

#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DataNode
{	
	ElemType data;
	struct DataNode *next;
} DataNode;				
typedef struct
{	
	DataNode *front;
	DataNode *rear;
} LinkQuNode;			
void InitQueue(LinkQuNode *&q)	
{	
	q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
	q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q)	
{
	DataNode *p=q->front,*r;
	if (p!=NULL)			
	{	r=p->next;
		while (r!=NULL)
		{	free(p);
			p=r;r=p->next;
		}
	}
	free(p);
	free(q);				
}
bool QueueEmpty(LinkQuNode *q)	
{
	return(q->rear==NULL);
}
void enQueue(LinkQuNode *&q,ElemType e)	
{	DataNode *p;
	p=(DataNode *)malloc(sizeof(DataNode));
	p->data=e;
	p->next=NULL;
	if (q->rear==NULL)		
		q->front=q->rear=p;
	else
	{	q->rear->next=p;	
		q->rear=p;
	}
}
bool deQueue(LinkQuNode *&q,ElemType &e)	
{	DataNode *t;
	if (q->rear==NULL)		
		return false;
	t=q->front;				
	if (q->front==q->rear)  
		q->front=q->rear=NULL;
	else					
		q->front=q->front->next;
	e=t->data;
	free(t);
	return true;
}

exp3-4

#include "liqueue.cpp"		

int main()
{
	ElemType e;
	LinkQuNode *q;
	printf("链队的基本运算如下:\n");
	printf("  (1)初始化链队”q\n");
	InitQueue(q);
	printf("  (2)依次进链队元素a,b,c\n");
	enQueue(q,'a');
	enQueue(q,'b');
	enQueue(q,'c');
	printf("  (3)链队为%s\n",(QueueEmpty(q)?"空":"非空"));
	if (deQueue(q,e)==0) 
		printf("\t提示：对空，不能出队\n");
	else
		printf("  (4)出队一个元素%c\n",e);
	printf("  (5)依次进链队元素d,e,f\n");
	enQueue(q,'d');
	enQueue(q,'e');
	enQueue(q,'f');
	printf("  (6)出链队序列");
	while (!QueueEmpty(q))
	{	deQueue(q,e);
		printf("%c ",e);
	}
	printf("\n");
	printf("  (7)释放链队\n");
	DestroyQueue(q);
	return 1;
}

exp3-5

#include <stdio.h>
#define M 4					
#define N 4					
#define MaxSize 100			
int mg[M+2][N+2]={			
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct 
{
	int i,j;
	int di;
} St[MaxSize],Path[MaxSize];	
int top=-1;						
int count=1;					
int minlen=MaxSize;				
void dispapath()				
{
	int k;
	printf("%5d: ",count++);	
	for (k=0;k<=top;k++)
		printf("(%d,%d) ",St[k].i,St[k].j);
	printf("\n");
	if (top+1<minlen)			
	{
		for (k=0;k<=top;k++)	
			Path[k]=St[k];
		minlen=top+1;			
	}
}
void dispminpath()				
{
	printf("最短路径如下:\n");
	printf("长度: %d\n",minlen);
	printf("路径: ");
	for (int k=0;k<minlen;k++)
		printf("(%d,%d) ",Path[k].i,Path[k].j);
	printf("\n");
}
void mgpath(int xi,int yi,int xe,int ye) 
{
	int i,j,i1,j1,di;
	bool find;
	top++;							
	St[top].i=xi;
	St[top].j=yi;
	St[top].di=-1;mg[xi][yi]=-1;	
	while (top>-1)					
	{
		i=St[top].i;j=St[top].j;di=St[top].di;
		if (i==xe && j==ye)			
		{
			dispapath();			
			mg[i][j]=0;				
			top--;					
			i=St[top].i;j=St[top].j;
			di=St[top].di;			
		}
		find=false;					
		while (di<4 && !find)	
		{	di++;
			switch(di)
			{
			case 0:i1=i-1; j1=j;   break;
			case 1:i1=i;   j1=j+1; break;
			case 2:i1=i+1; j1=j;   break;
			case 3:i1=i,   j1=j-1; break;
			}
			if (mg[i1][j1]==0) find=true;
		}
		if (find)					
		{	St[top].di=di;			
			top++;St[top].i=i1;St[top].j=j1;
			St[top].di=-1;			
			mg[i1][j1]=-1;			
		}
		else						
		{
			mg[i][j]=0;				
			top--;
		}
	}
	dispminpath();					
}
int main()
{
	printf("迷宫所有路径如下:\n");
	mgpath(1,1,M,N);
	return 1;
}