4-10.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#define m 100
#define QueueSize 100 //假定预分配的队列空间最多为100个元素 
typedef struct info{
	int row;
	int col;
}Position; 
typedef Position DataType ; //假定队列元素的数据类型为字符
typedef struct node{
	DataType data;
	struct node *next;
}QueueNode;
typedef struct{
	QueueNode *front;  //头指针
	QueueNode *rear;
}LinkQueue;
int pixel[m][m];
// 置队列空
void Initial(LinkQueue *Q)
{//将顺序队列置空
    Q->front=Q->rear=NULL;
} 
//判队列空
int IsEmpty(LinkQueue *Q)
{
    return Q->front==NULL&&Q->rear==NULL;
}
//进队列
void EnQueue(LinkQueue *Q,DataType x)
{//将元素x插入链队列尾部
	QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
	p->data=x;
	p->next=NULL;
    if(IsEmpty(Q))
		Q->front=Q->rear=p;  //将x插入空队列
	else 
	{ //x插入非空队列的尾
		Q->rear->next=p;     //*p链到原队尾结点后
		Q->rear=p;           //队尾指针指向新的尾
	}
}
//出队列
DataType DeQueue(LinkQueue *Q)
{
	DataType x;
	QueueNode *p;
	if(IsEmpty(Q))
	{
		printf("队列为空");//下溢
		exit(1);
	}
	p=Q->front;                   //指向对头结点
	x=p->data;                    //保存对头结点的数据
	Q->front=p->next;             //将对头结点从链上摘下
    if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空
		Q->rear=NULL;
	free(p);   //释放被删队头结点
	return x;  //返回原队头数据
}
// 取队列顶元素
DataType Front(LinkQueue *Q)
{
	if(IsEmpty(Q))
	{
		printf("队列为空"); //下溢,退出运行
		exit(1);
	}
	return Q->front->data;
}
void IdentifyLable()
{// 初始化“围墙”
	int NumOfNbrs = 4; // 一个像素的相邻像素个数
	int r,c,i;
	LinkQueue Q;
	int id = 1; //图元i d
	Position here, nbr;
	Position offset[4] ;
	for (i = 0; i <= m+1; i++)
	{
		pixel[0][i]=pixel[m+1][i] = 0; // 底和顶
		pixel[i][0]=pixel[i][m+1] = 0; // 左和右
	}
	// 初始化offset
	offset[0].row = 0; 
	offset[0].col = 1; // 右
	// 初始化offset
	offset[0].row = 0; 
	offset[0].col = 1; // 右第6章队列2 0 5
	offset[1].row = 1; 
	offset[1].col = 0; // 下
	offset[2].row = 0; 
	offset[2].col = -1; // 左
	offset[3].row = -1; 
	offset[3].col = 0; // 上
	// 扫描所有像素
	for (r=1; r <= m; r++){ //图像的第r 行
		for (c=1; c <= m; c++) //图像的第c 列
			if (pixel[r][c] == 1) {// 新图元}
				pixel[r][c] = ++id; // 得到下一个i d
				here.row = r; 
				here.col = c;
				do {// 寻找其余图元
					for (i = 0; i < NumOfNbrs; i++) {
					// 检查当前像素的所有相邻像素
						nbr.row = here.row + offset[i].row;
						nbr.col = here.col + offset[i].col;
						if (pixel[nbr.row][nbr.col]==1) {
							pixel[nbr.row][nbr.col]=id; 
							EnQueue(&Q,nbr);
						}
					} // end of if and for
					//还有未探索的像素吗?
					if (IsEmpty(&Q)) break;
						DeQueue(&Q); //一个图元像素
				} while(1);
	} //结束if 和for
}
void main()
{
	IdentifyLable();
}