C++学習ノートday 18---データ構造とアルゴリズム
30324 ワード
キュータイプのデータ構造:キュータイプは先進的な先出データ構造であり、キューのヘッダからデータを取り出し、キューの最後にデータを格納するしかない.配列ベースで実装される2つのキューについて説明します.キューの操作方法(関数)を示します.一方向キュー:
≪ループ・キュー|Loop Queue|emdw≫:ループ・キューのポイントは、キュー・ヘッダと末尾のループをどのように処理するかです.次のコードでは、キュー・ヘッダの下付きスケール値が加算されるたびにキュー長を超えたかどうかを判断し、超えた場合はキューの先頭と末尾の下付きスケールからキュー長を減算します.キューヘッダとテールの下付きスケール値がintタイプの上限を超えないことを確認します(ヘッダとテールは常に加算され、何度もループした後に必ずintタイプの上限を超えます).
チェーンテーブルタイプのデータ構造チェーンテーブルのタイプは、実は1つのノードから構成されており、チェーンテーブル自体の構造体はチェーンテーブルのヘッダノードのみを記録している.各ノードには、現在のノードに格納されているデータと、次のノードへのノードポインタが記録されます.もちろん,ノードの構造体に前のノードを記録するポインタを加えることも可能である.そうすると、1つのノードに前のノードのアドレスと後のノードのアドレスが記録され、双方向チェーンテーブルになります.双方向チェーンテーブルの利点は,チェーンテーブルの末尾処理に際して,チェーンテーブルのヘッダ点からチェーンテーブルの末尾まで遍歴する必要がなく,再処理するのではなく,ノードの前方ポインタにより,直接末尾から処理を開始できることである.双方向チェーンテーブルを操作する方法(関数)を次に示します.
#include"queue.h"
typedef struct{
int buf[SIZE];
int head;// , ，head> tail
int tail;//
}queue;
//
void queue_init(queue* p_queue){
p_queue->head = 0;
p_queue->tail = 0;
}
//
void queue_deinit(queue* p_queue){
p_queue->head = 0;
p_queue->tail = 0;
}
//
int queue_size(const queue* p_queue){
return p_queue->tail - p_queue->head;
}
//
int queue_full(const queue* p_queue){
if (p_queue->tail >= SIZE)
return 1;
else
return 0;
}
//
int queue_empty(const queue* p_queue){
if(p_queue->head == p_queue->tail)
return 1;
else
return 0;
}
//
int queue_push(queue* p_queue,int value){
if(queue_full(p_queue))
return 0;
p_queue->buf[p_queue->tail] = value;
p_queue->tail += 1;
return 1;
}
//
int queue_pop(queue* p_queue,int* p_value){
if(queue_empty(p_queue))
return 0;
*p_value = p_queue->buf[p_queue->head];
p_queue->head += 1;
return 1;
}
// ，
int queue_front(const queue* p_queue,int* p_value){
if(queue_empty(p_queue))
return 0;
*p_value = p_queue->buf[p_queue->head];
return 1;
}
≪ループ・キュー|Loop Queue|emdw≫:ループ・キューのポイントは、キュー・ヘッダと末尾のループをどのように処理するかです.次のコードでは、キュー・ヘッダの下付きスケール値が加算されるたびにキュー長を超えたかどうかを判断し、超えた場合はキューの先頭と末尾の下付きスケールからキュー長を減算します.キューヘッダとテールの下付きスケール値がintタイプの上限を超えないことを確認します(ヘッダとテールは常に加算され、何度もループした後に必ずintタイプの上限を超えます).
#include"queuep.h"
typedef struct{
int num[SIZE];
int head;
int tail;
}queuep;
//
void queuep_init(queuep* p_queue){
p_queue->head = 0;
p_queue->tail = 0;
}
//
void queuep_deinit(queuep* p_queue){
p_queue->head = 0;
p_queue->tail = 0;
}
//
int queuep_size(const queuep* p_queue){
return p_queue->tail - p_queue->head;
}
//
int queuep_full(const queuep* p_queue){
if((p_queue->tail - p_queue->head) == SIZE)
return 1;
else
return 0;
}
//
int queuep_empty(const queuep* p_queue){
if(p_queue->head == p_queue->tail)
return 1;
else
return 0;
}
//
int queuep_push(queuep* p_queue,int value){
if(queuep_full(p_queue))
return 0;
// ， SIZE
p_queue->num[p_queue->tail % SIZE] = value;
p_queue->tail++;
return 1;
}
//
int queuep_pop(queuep* p_queue,int* p_value){
if(queuep_empty(p_queue))
return 0;
// ， ， ， ， ， 。
*p_value = p_queue->num[p_queue->head % SIZE];
p_queue->head++;
if(p_queue->head == SIZE){
p_queue->tail -= SIZE;
p_queue->head -= SIZE;
}
return 1;
}
// ，
int queuep_front(const queuep* p_queue,int* p_value){
if(queuep_empty(p_queue))
return 0;
*p_value = p_queue->num[p_queue->head%SIZE];
return 1;
}チェーンテーブルタイプのデータ構造チェーンテーブルのタイプは、実は1つのノードから構成されており、チェーンテーブル自体の構造体はチェーンテーブルのヘッダノードのみを記録している.各ノードには、現在のノードに格納されているデータと、次のノードへのノードポインタが記録されます.もちろん,ノードの構造体に前のノードを記録するポインタを加えることも可能である.そうすると、1つのノードに前のノードのアドレスと後のノードのアドレスが記録され、双方向チェーンテーブルになります.双方向チェーンテーブルの利点は,チェーンテーブルの末尾処理に際して,チェーンテーブルのヘッダ点からチェーンテーブルの末尾まで遍歴する必要がなく,再処理するのではなく,ノードの前方ポインタにより,直接末尾から処理を開始できることである.双方向チェーンテーブルを操作する方法(関数)を次に示します.
//
void link_init(link* p_link){
p_link->head.p_next = &(p_link->tail);
p_link->head.p_prev = NULL;
p_link->tail.p_prev = &(p_link->head);
p_link->tail.p_next = NULL;
p_link->p_cur = NULL;
}
//
void link_deinit(link* p_link){
p_link->p_cur = NULL;
while(p_link->head.p_next != &(p_link->tail)){
node* p_first = &(p_link->head);
node* p_mid = p_first->p_next;
node* p_last = p_mid->p_next;
p_first->p_next = p_last;
p_last->p_prev = p_first;
free(p_mid);
p_mid = NULL;
}
}
//
int link_size(const link* p_link){
int count = 0;
const node* temp = {0};
temp = &(p_link->head);
while(temp->p_next != &(p_link->tail)){
count++;
temp = temp->p_next;
}
return count;
}
//
int link_empty(const link* p_link){
if(p_link->head.p_next == &(p_link->tail))
return 1;
return 0;
}
//
int link_full(const link* p_link){
return 0;
}
//
int link_add_head(link* p_link,int value){
node* p_first = NULL,*p_mid = NULL,*p_last = NULL;
node* p_node = NULL;
p_link->p_cur = NULL;
p_node = (node*)malloc(sizeof(node));
if(!p_node) return 0;
p_node->num = value;
p_node->p_next = NULL;
p_node->p_prev = NULL;
p_first = &(p_link->head);
p_mid = p_first->p_next;
p_last = p_mid->p_next;
p_node->p_next = p_mid;
p_mid->p_prev = p_node;
p_node->p_prev = p_first;
p_first->p_next = p_node;
return 1;
}
//
int link_add_tail(link* p_link,int value){
node* p_first = NULL,*p_mid = NULL,*p_last = NULL,*p_temp = NULL;
node* p_node = NULL;
p_link->p_cur = NULL;
p_node = (node*)malloc(sizeof(node));
if(!p_node) return 0;
p_node->num = value;
p_node->p_next = NULL;
p_node->p_prev = NULL;
p_first = p_link->tail.p_prev;
p_mid = p_first->p_next;
p_last = p_mid->p_next;
p_first->p_next = p_node;
p_node->p_prev = p_first;
p_node->p_next = p_mid;
p_mid->p_prev = p_node;
return 1;
}
//
int link_insert(link* p_link,int value){
node* p_first = NULL,*p_mid = NULL,*p_last = NULL,*p_temp = NULL;
node* p_node = NULL;
p_link->p_cur = NULL;
p_node = (node*)malloc(sizeof(node));
if(!p_link) return 0;
p_node->num = value;
p_node->p_next = NULL;
p_node->p_prev = NULL;
for(p_temp = &(p_link->head);p_temp != &(p_link->tail);p_temp = p_temp->p_next){
p_first = p_temp;
p_mid = p_first->p_next;
p_last = p_mid->p_next;
if(((p_first->num < p_node->num) && (p_mid->num > p_node->num)) || p_mid == &(p_link->tail)){
p_first->p_next = p_node;
p_node->p_prev = p_first;
p_node->p_next = p_mid;
p_mid->p_prev = p_node;
break;
}
}
return 1;
}
//
int link_remove_head(link* p_link){
p_link->p_cur = NULL;
if(link_empty(p_link)) return 0;
node* p_first = &(p_link->head);
node* p_mid = p_first->p_next;
node* p_last = p_mid->p_next;
p_first->p_next = p_last;
p_last->p_prev = p_first;
free(p_mid);
p_mid = NULL;
return 1;
}
//
int link_remove_tail(link* p_link){
p_link->p_cur = NULL;
if(link_empty(p_link)) return 0;
node* p_last = &(p_link->tail);
node* p_mid = p_last->p_prev;
node* p_first = p_mid->p_prev;
p_first->p_next = p_last;
p_last->p_prev = p_first;
free(p_mid);
p_mid = NULL;
return 1;
}
//
int link_remove(link* p_link,int value){
p_link->p_cur = NULL;
if(link_empty(p_link)) return 0;
node* p_temp = {0};
for(p_temp = &(p_link->head);p_temp != &(p_link->tail);p_temp = p_temp->p_next){
node* p_first = p_temp;
node* p_mid = p_first->p_next;
node* p_last = p_mid->p_next;
if(p_mid->num == value && p_mid != &(p_link->tail)){
p_first->p_next = p_last;
p_last->p_prev = p_first;
free(p_mid);
p_mid = NULL;
return 1;
}
}
return 0;
}
//
int link_get_head(const link* p_link,int* value){
if(link_empty(p_link)) return 0;
const node* p_first = &(p_link->head);
const node* p_mid = p_first->p_next;
const node* p_last = p_mid->p_next;
*value = p_mid->num;
return 1;
}
//
int link_get_tail(const link* p_link,int* value){
if(link_empty(p_link)) return 0;
const node* p_last = &(p_link->tail);
const node* p_mid = p_last->p_prev;
const node* p_first = p_mid->p_prev;
*value = p_mid->num;
return 1;
}
//
int link_get(const link* p_link,int num,int* value){
int count = 0;
const node* p_temp = {0};
if(link_empty(p_link)) return 0;
for(p_temp = &(p_link->head);p_temp != &(p_link->tail);p_temp = p_temp->p_next){
const node* p_first = p_temp;
const node* p_mid = p_first->p_next;
const node* p_last = p_mid->p_next;
if(num == count && p_mid != &(p_link->tail)){
*value = p_mid->num;
return 1;
}
count++;
}
return 0;
}
//
void link_begin(link* p_link){
p_link->p_cur = &(p_link->head);
}
// ，
int link_next(link* p_link,int* p_value){
if(p_link->p_cur == NULL) return 0;
p_link->p_cur = p_link->p_cur->p_next;
if(p_link->p_cur == &(p_link->tail)){
p_link->p_cur = NULL;
return 0;
}
else{
*p_value = p_link->p_cur->num;
return 1;
}
}