#include "stdio.h"
#define m 100
#define QueueSize 100 //假定預(yù)分配的隊列空間最多為100個元素 
typedef struct info{
	int row;
	int col;
}Position; 
typedef Position DataType ; //假定隊列元素的數(shù)據(jù)類型為字符
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));//申請新結(jié)點
	p->data=x;
	p->next=NULL;
    if(IsEmpty(Q))
		Q->front=Q->rear=p;  //將x插入空隊列
	else 
	{ //x插入非空隊列的尾
		Q->rear->next=p;     //*p鏈到原隊尾結(jié)點后
		Q->rear=p;           //隊尾指針指向新的尾
	}
}
//出隊列
DataType DeQueue(LinkQueue *Q)
{
	DataType x;
	QueueNode *p;
	if(IsEmpty(Q))
	{
		printf("隊列為空");//下溢
		exit(1);
	}
	p=Q->front;                   //指向?qū)︻^結(jié)點
	x=p->data;                    //保存對頭結(jié)點的數(shù)據(jù)
	Q->front=p->next;             //將對頭結(jié)點從鏈上摘下
    if(Q->rear==p)//原隊中只有一個結(jié)點，刪去后隊列變空，此時隊頭指針已為空
		Q->rear=NULL;
	free(p);   //釋放被刪隊頭結(jié)點
	return x;  //返回原隊頭數(shù)據(jù)
}
// 取隊列頂元素
DataType Front(LinkQueue *Q)
{
	if(IsEmpty(Q))
	{
		printf("隊列為空"); //下溢,退出運行
		exit(1);
	}
	return Q->front->data;
}
void IdentifyLable()
{// 初始化“圍墻”
	int NumOfNbrs = 4; // 一個像素的相鄰像素個數(shù)
	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++) {
					// 檢查當(dāng)前像素的所有相鄰像素
						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);
	} //結(jié)束if 和for
}
void main()
{
	IdentifyLable();
}