プログラミングC: 投稿 16 – 建設キュー (キュー)

[qads]

キュー (キュー) ストアに使用されるデータ構造がFIFOの下でオブジェクトの動作である (英語で頭字語: ファーストアウトでファースト), 意味する “ファーストアウトで” キューの中, オブジェクトは、任意の時点でのキューに追加することができ, しかし、キューから抜け出すためには、最初のオブジェクトに追加許可されます. オブジェクトを追加することは常にキューの最後で行われ、常に要素が待ち行列の先頭から除去され.

キュー

1. アレイにインストールキュー

AT ALL スタック, 我々は、使用して、スタック内の要素の数を数えることができる 1 カウント (カウント) 簡単にするため, このセクションでは、私は構造そのキューカウンタを使用します.

#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu

struct Queue
{
	int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
	item Data[Max]; //Mang cac phan tu
	int count; //dem so phan tu cua Queue
};

1.1 空のキューを初期化します.

私たちはフロントに空のキューの位置を作成する必要があります開始するには 0, 背面 -1, 約COUT 0.

void Init (Queue &Q) //khoi tao Queue rong
{
	Q.Front = 0; //phan tu dau
	Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
	Q.count = 0; //so phan tu bang 0
}

1.2 キューが空のチェック, フル

中空フルチェックだけでなく、カウントをチェックする 0 とmax

int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

int Isfull (Queue Q) //kiem tra Queue day
{
	if (Q.count == Max) //so phan tu = Max => day
		return 1;
	return 0;
}

1.3 キューの最後に要素を追加する (押す)

後方位置が増加する 1 位置に関するデータを提供

押す

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	if (Isfull(Q)) printf("Hang doi day !");
	else
	{ 
		Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
		Q.count++; //tang so phan tu len
	}
}

1.4 最初の要素キューを削除する (ポップ)

空のキューをチェックした最初の, ループ内の最初の行の行の要素を動かす行っempty'reされていない場合 (キューのように購入する際に) その後リアを削減し、カウントダウン.

ポップ

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else
	{
		item x = Q.Data[Q.Front];
		for (int i=Q.Front; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
			Q.Data[i] = Q.Data[i+1];
		Q.Rear--; // giam vi tri phan tu cuoi xuong
		Q.count--;//giam so phan tu xuong
		return x; //tra ve phan tu lay ra
	}
}

1.5 最初の要素キューを表示

item Qfront (Queue Q) //xem thong tin phan tu dau hang
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else return Q.Data[Q.Front];
}

1.6 ラウンドキュー (キュー円形)

我々は、キューベースのアレイ上に構築したよう, とを参照してください。 1 欠点は、我々はフロントの背後にあるすべての要素を移動する必要がある最初の要素削除キューです. これを改善するために、我々は、アレイを見ることができます 1 分子配列ランク円と.

円形の

その後、我々は追加することができます, 単に要素を削除, しかし、配列の最後に要素リアとフロントを追加および削除するときに、それは注意すべきである (マックス-1). マックスの分周フロントとリア超過スプレッドを克服するために、. フロントとリアマックスは位置に戻りますので、もし 0.

void Push_Circular(Queue &Q, item x) //them phan tu vao cuoi hang doi vong
{
	if (Isfull(Q)) printf("Hang doi day !");
	else 
	{
		Q.Data[(++Q.Rear) % Max] = x; 
		//tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0
		Q.count++; //tang so phan tu len
	}
}

int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong
{
	if (Isempty(Q)) printf("Hang doi rong !");
	item x = Q.Data[Q.Front];
	Q.Front = (Q.Front++) % Max; // tang vi tri phan dau tien len, neu dang o Max-1 thi ve 0
	Q.count--;//giam so phan tu xuong
	return x; //tra ve phan tu lay ra
}

1.7 完全なプログラム (完全なコード)

#include <stdlib.h>
#include <stdio.h>

#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu

struct Queue
{
	int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
	item Data[Max]; //Mang cac phan tu
	int count; //dem so phan tu cua Queue
};

void Init (Queue &Q); //khoi tao Queue rong
int Isempty(Queue Q); //kiem tra Queue rong
int Isfull(Queue Q); //kiem tra Queue day
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
int Qfront (Queue Q); //xem thong tin phan tu dau hang doi 
void Push_Circular(Queue &Q, item x); //them phan tu vao cuoi hang doi vong
int Pop_Circular(Queue &Q); //Loai bo phan tu khoi dau hang doi vong
void Input (Queue &Q); //Nhap 
void Output(Queue Q); //Xuat 

void Init (Queue &Q) //khoi tao Queue rong
{
	Q.Front = 0; //phan tu dau
	Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
	Q.count = 0; //so phan tu bang 0
}

int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

int Isfull (Queue Q) //kiem tra Queue day
{
	if (Q.count == Max) //so phan tu = Max => day
		return 1;
	return 0;
}

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	if (Isfull(Q)) printf("Hang doi day !");
	else
	{ 
		Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
		Q.count++; //tang so phan tu len
	}
}

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else
	{
		item x = Q.Data[Q.Front];
		for (int i=Q.Front; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
			Q.Data[i] = Q.Data[i+1];
		Q.Rear--; // giam vi tri phan tu cuoi xuong
		Q.count--;//giam so phan tu xuong
		return x; //tra ve phan tu lay ra
	}
}

item Qfront (Queue Q) //xem thong tin phan tu dau hang
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else return Q.Data[Q.Front];
}

void Push_Circular(Queue &Q, item x) //them phan tu vao cuoi hang doi vong
{
	if (Isfull(Q)) printf("Hang doi day !");
	else 
	{
		Q.Data[(++Q.Rear) % Max] = x; 
		//tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0
		Q.count++; //tang so phan tu len
	}
}

int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong
{
	if (Isempty(Q)) printf("Hang doi rong !");
	item x = Q.Data[Q.Front];
	Q.Front = (Q.Front++) % Max; // tang vi tri phan dau tien len, neu dang o Max-1 thi ve 0
	Q.count--;//giam so phan tu xuong
	return x; //tra ve phan tu lay ra
}


void Input (Queue &Q) //nhap hang doi
{
	int n;
	item x;
	do
	{
		printf("Nhap so phan tu cua Queue (<%d) :",Max);
		scanf("%d",&n);
	} while (n>Max || n<1);
	for (int i=0; i<n; i++)
	{
		printf("Nhap phan tu thu %d : ", i+1);
		scanf("%d",&x);
		Push(Q,x);
		Push_Circular(Q,x); //hang vong
	}
}

void Output(Queue Q)
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else
	{
		for (int i=Q.Front; i<=Q.Rear; i++)
		//for (int i=Q.Front, j=0; j<Q.count; j++, i = (i++) % Max) //hang vong
			printf("%d   ",Q.Data[i]);
		printf("\n");
	}
}

int main()
{
    Queue Q;
    Init(Q);
    Input(Q);
    Output(Q);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Queue rong");
    printf("\n2: Kiem tra Queue day");
    printf("\n3: Them phan tu vao Queue");
    printf("\n4: Xoa phan tu trong Queue");
    printf("\n5: Xuat Queue");
    printf("\n6: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(Q)) printf("Queue rong !");
				else printf ("Queue khong rong !");
				break;
			}
			case 2:
			{
				if (Isfull(Q)) printf("Queue day !");
				else printf ("Queue chua day !");
				break;
			}
			case 3:
			{
				item x;
				printf ("Nhap phan tu can chen vao Queue: ");
				scanf("%d",&x);
				Push(Q,x);
				//Push_Circular(Q,x); hang vong
				break;
			}
			case 4:
			{
				Pop(Q);
				//Pop_Circular(Q); hang vong
				break;
			}
			case 5: 
			{
				Output(Q);
				break;
			}
			case 6: break;
		}
    }while (lua_chon !=6);
    return 0;
}

リンクの冗長性

2. カーソルでキューの設定

キューポインタ

2.1 建築構造物

typedef int item; //kieu du lieu
struct Node
{
	item Data;
	Node * Next;
};
struct Queue
{
	Node * Front, *Rear; //Node dau va Node cuoi
	int count; //dem so phan tu
};

2.2 初期化.

NULLポインタのためのフロントとリアキューたちを初期化します, カウント= 0.

void Init(Queue &Q)
{
	Q.Front = Q.Rear = NULL;
	Q.count = 0;
}

2.3. 空のチェック

int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

2.4 作る 1 ノードP

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

2.5 キューの最後に要素を追加する

要素を追加するには, 空行があるかどうかをチェック, 行が空の場合、フロントとリアの両方の要素を含む、新しく作成されたPノードにXより指し. 1点を空でない場合リア>点PとリアP上の次のページ. カウントアップの増加 1

押す

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	Node *P = MakeNode(x); //Neu Q rong
	if (Isempty(Q))
	{
		Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
	}
	else //Khong rong
	{ 
		Q.Rear->Next = P;
		Q.Rear = P;
	}
	Q.count ++ ; //tang so phan tu len
}

2.6 最初の要素キューを削除する

私は、キューが空にチェック, ヌルをチェックしない場合 1 とはるかに 1 要素, もしそこに 1 要素は、キューを初期化する, もしフロントのための次への複数のポイント. ダウンの削減数 1.
ポップ

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) 
	{
		printf("Hang doi rong !");
		return 0;
	}
	else
	{
		item x = Q.Front->Data;
		if (Q.count == 1) //neu co 1 phan tu
			Init(Q);
		else
			Q.Front = Q.Front->Next;
		Q.count --;
		return x; //tra ve phan tu lay ra
	}
}

2.7 完全なプログラム (完全なコード)

#include <stdlib.h>
#include <stdio.h>

typedef int item; //kieu du lieu
struct Node
{
	item Data;
	Node * Next;
};
struct Queue
{
	Node * Front, *Rear; //Node dau va Node cuoi
	int count; //dem so phan tu
};

void Init (Queue &Q); //khoi tao Queue rong
int Isempty(Queue Q); //kiem tra Queue rong
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
int Qfront (Queue Q); //xem thong tin phan tu dau hang doi 
Node *MakeNode(item x); //tao 1 Node
void Input (Queue &Q); //Nhap 
void Output(Queue Q); //Xuat 

void Init(Queue &Q)
{
	Q.Front = Q.Rear = NULL;
	Q.count = 0;
}
int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	Node *P = MakeNode(x); //Neu Q rong
	if (Isempty(Q))
	{
		Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
	}
	else //Khong rong
	{ 
		Q.Rear->Next = P;
		Q.Rear = P;
	}
	Q.count ++ ; //tang so phan tu len
}

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) 
	{
		printf("Hang doi rong !");
		return 0;
	}
	else
	{
		item x = Q.Front->Data;
		if (Q.count == 1) //neu co 1 phan tu
			Init(Q);
		else
			Q.Front = Q.Front->Next;
		Q.count --;
		return x; //tra ve phan tu lay ra
	}
}

void Input (Queue &Q) //nhap hang doi
{
    int i=0; 
    item x;
    do
    {
        i++;
        printf ("Nhap phan tu thu %d : ",i);
        scanf("%d",&x);
        if (x != 0) Push(Q,x);
    } while(x != 0); //nhap 0 de ket thuc
}

void Output(Queue Q)
{
	Node *P = Q.Front;
	while (P != NULL)
	{
		printf("%d   ",P->Data);
		P = P->Next;
	}
	printf("\n");
}

int main()
{
    Queue Q;
    Init(Q);
    Input(Q);
    Output(Q);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Queue rong");
    printf("\n2: Them phan tu vao Queue");
    printf("\n3: Xoa phan tu trong Queue");
    printf("\n4: Xuat Queue");
    printf("\n5: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(Q)) printf("Queue rong !");
				else printf ("Queue khong rong !");
				break;
			}
			case 2:
			{
				item x;
				printf ("Nhap phan tu can chen vao Queue: ");
				scanf("%d",&x);
				Push(Q,x);
				break;
			}
			case 3:
			{
				Pop(Q);
				break;
			}
			case 4: 
			{
				Output(Q);
				break;
			}
			case 5: break;
		}
    }while (lua_chon !=5);
    return 0;
}

リンクの冗長性

3. C言語でQueuが利用可能に使用してください

のような スタック·チョンC , キューが構築され、我々だけのみを使用.

#include <iostream>
#include <queue> // su dung queue

using namespace std;

int main() {
	queue <int> Q; // khai bao queue co kieu nguyen
	for (int i = 0; i < 10; i++) {
		Q.push(i * 78 + 26); // them phan tu vao queue
	}
	
	cout << "So luong phan tu trong queue: " << Q.size() << "\n";
	
	while (!Q.empty()) { // trong khi queue khong rong
		int x = Q.front(); 	// lay gia tri dau hang
		Q.pop(); 			// xoa gia tri dau hang
		cout << x << "  ";
	}
	
	cout << "\n";
	
	return 0;
}

4. キューの応用

キューは、再帰を除去するために使用されている, 組織は、幅とバックトラックに応じて検索処理を追跡, 徹底的な, オペレーティングシステムにおける組織管理及び流通過程, 組織キーボードバッファ.


[ポストをRPS-含ま=”2703″ ショートコード=”偽”]