[SWEA] 18. ᄏᄏᄏᄏᄏᄏᄏᄏᄏᄏᄏ

最大割当回数がわかっていれば→メモリプール
一般変数head、tailの使用
2. 実戦授業
2.1 動的割当てではなく静的割当ての使用(C++)
Pro テストのために、動的な割り当てではなく、メモリプール(内蔵プール)を使用して静的な割り当てを行うよう求められます.アルゴリズムの問題を解くには、次のように仮定します.

ユーザーは100000人います.

ユーザーにデータを割り当てる準備をします.

1人のユーザに複数のデータを割り当てることができる.

割当額は最大50,000回実行する.

この場合、ユーザーには50000個のデータがある可能性があります.そのため、ユーザー構造に50000個の値を格納できる配列を作成できます.ユーザは100000であるため、配列のサイズは100000 x 50000である.しかし、このように実施すれば 配列が大きすぎる これにより、メモリ容量の問題が発生します.
動的割当てを使用して問題を解決する場合は、メモリをオンデマンドで割り当てるだけで済むため、最大50000個のスペースしか割り当てられません. 使用 メモリの問題を解決します.さらに,これらの動的割り当てよりも効率的な方法がある.これがメモリプールです.最大割当回数が分かるため、動的割当ではなく50000個のデータを使用して事前に宣言し、必要に応じてこれらのデータを使用することができます.この場合、動的割当てを使用する場合よりも実行時間が速く、実施が比較的簡単である.

#include < iostream >

usingnamespace std;

int memPoolCnt;

struct Node {
int value;
	Node* prev;
} node[50000];

struct User {
	Node* data;
} user[100000];

int main() {
	memPoolCnt = 0;//초기화

// 첫 번째 데이터 추가
	Node* tmp1 = &node[memPoolCnt++];// 메모리 풀에서 가져옴
	tmp1->value = 1;
	tmp1->prev = user[0].data;
	user[0].data = tmp1;

// 두 번째 데이터 추가
	Node* tmp2 = &node[memPoolCnt++];// 메모리 풀에서 가져옴
	tmp2->value = 2;
	tmp2->prev = user[0].data;
	user[0].data = tmp2;

return 0;
}

上記の例では、各ユーザは、メモリの問題を解決するために接続リストとしてデータを格納します.割り当てに必要なスペースは最大50,000個です. メモリプールを事前に割り当て、必要に応じてインポートして使用しました.動的割当てを書き込む場合は、1つのケースを開始するたびに新しいインスタンスを作成し、そのケースの終了時に削除する必要があります.ただし、動的割り当てではなくメモリプールを使用する場合は、 mempPoolcnt=0でCaseを初期化でき、追加料金はかかりません. 実際 開発時に動的割当てを使用する必要があるかもしれませんが、アルゴリズムの問題を解決する際には、これらの静的割当てを使用することが実行時間に有利です. これらの技術によって リンクリストノード 既存の配列を再作成したり削除したりすることなく、既存の配列で簡単に初期化できます.
2.2 実際のテストで実施
リンクリストは試験で最もよく使われるデータ構造です.実装は難しくありませんが、エラーが発生しやすいので、最初から正しい実装練習を行う必要があります.まず、リンクリストのナビゲーションコードを見てみましょう.

// Single linked list

/*
struct ListNode {
	int idx; // list의 key
	int data; // list에 담긴 data
	ListNode* next; // 다음 node
}

ListNode *list;
*/

ListNode* getNode(int _idx) {
	ListNode* ptr = list;

while(ptr->next) {// ptr->next가 null이 아니라면
		if (ptr->next->idx == _idx)break;// 동일한 idx를 발견하면 loop 종료

		ptr = ptr->next;// ptr은 다음 node를 가리킨다.
	}

return ptr;
}

このコードは、idxを受信し、idxに一致するノードの前のノードを返すコードである.while loopがptr->nextに書き込まれる理由は、大きく2つあります.まずsingle link listでは、以前のノードの情報を理解できません.したがって、ノード接続を変更または削除する必要がある場合は、そのノードの前のノードで操作を実行する必要があります.したがって、前のノードが返されます.第2に、次のノードが空の場合、ループが終了します. ただし、headがnullの場合、whileの条件文がnull->nextでこのコードにアクセスするため、セグメントエラーが発生します.したがって、headがnullであるかどうかを確認する必要があります.

ListNode* getNode(int _idx) {
	ListNode* ptr = list;

if (ptr ==nullptr)return 0;// head가 null일 경우, null을 return

while(ptr->next) {
if (ptr->next->idx == _idx)break;

		ptr = ptr->next;
	}

return ptr;
}

だからheadがNULLかどうかをチェックするif文が追加されましたしかし、これにもいくつかの問題があります.getNode()関数で受信したノード情報を使用してノードを挿入、削除、または変更する場合は、getNode()からNULLポインタだけを返すのはよくありません.これは,他の関数においてもNULLによる類似の問題を扱う必要があるためである.
しかし、headとtailはこれらの問題を解決するのに役立ちます.

// Single linked list/*

struct ListNode {
	int idx = -1;
	int data;
	ListNode* next;
}

//ListNode *list;		// 기존 list는 포인터였다.
ListNode head, tail;	// head, tail은 일반 변수로 선언
*/

ListNode* getNode(int _idx) {
	ListNode* ptr = &head;

while(ptr->next) {
if (ptr->next->idx == _idx || ptr->next->idx == -1)break;

		ptr = ptr->next;
	}

return ptr;// head, tail은 일반 변수라서 null이 반환되는 경우는 없음.
}

この場合、新しいノードの追加は考慮されません.まだあります. nodeの変更または削除が必要な場合 nodeはtailであることに注意してください.すなわち、Dummy変数headとtailをリンクリストの先頭と末尾に配置し、接続リストの順序を常にhead->nextからtail内にする.したがって、Segmentation Fault 発生を避ける.方式はいろいろありますので、それぞれおなじみの方法で行えばいいです次は、新しいノードを追加するコードです.

// Single linked list#include < stdio.h >

#define MAXN 1000

struct ListNode {
int idx = -1;
int data;
	ListNode* next;

// myAlloc은 구조체 변수를 초기화하고 해당 변수의 주소를 반환한다.
	ListNode* myAlloc(int _idx,int _data, ListNode* _next) {
		idx = _idx;
		data = _data;
		next = _next;

returnthis;// 현재 구조체 변수의 주소 반환.
	}
} buffer[MAXN];

int bufferCnt = 0;

//ListNode *list;
ListNode head, tail;

void init() {
	bufferCnt = 0;
	head.next = &tail;
}

ListNode* getNode(int _idx) {
	ListNode* ptr = &head;

while (ptr->next) {
if (ptr->next->idx >= _idx || ptr->next->idx == -1)break;

		ptr = ptr->next;
	}

return ptr;
}

int main() {
	init();

for (int i = 0; i < 10; ++i) {
int idx, data;
		scanf("%d %d", &idx, &data);

		ListNode* ptr = getNode(idx);

// 새 node 추가
		ptr->next = buffer[bufferCnt++].myAlloc(idx, data, ptr->next);
	}

return 0;
}

挿入のために追加された部分は、構造体内部のmyAllocとmainです.次に、既存のノードのコードを変更します.

// Single linked list#include < stdio.h >#define MAXN 1000struct ListNode {
int idx = -1;
int data;
	ListNode* next;

	ListNode* myAlloc(int _idx,int _data, ListNode* _next) {
		idx = _idx;
		data = _data;
		next = _next;

returnthis;
	}
} buffer[MAXN];

int bufferCnt = 0;

//ListNode *list;
ListNode head, tail;

void init() {
	bufferCnt = 0;
	head.next = &tail;
}

ListNode* getNode(int _idx) {
	ListNode* ptr = &head;

while (ptr->next) {
if (ptr->next->idx >= _idx || ptr->next->idx == -1)break;

		ptr = ptr->next;
	}

return ptr;
}

void update(ListNode* ptr,int _data) {
	ptr->next->data = _data;

return;
}

int main() {
	init();

for (int i = 0; i < 10; ++i) {
int idx, data;
		scanf("%d %d", &idx, &data);

		ListNode* ptr = getNode(idx);
		ptr->next = buffer[bufferCnt++].myAlloc(idx, data, ptr->next);
	}

for (int i = 0; i < 10; ++i) {
int idx, newData;
		scanf("%d %d", &idx, &newData);

		ListNode* ptr = getNode(idx);
// node data를 수정if (ptr->next->idx == idx && ptr->next->idx != -1) update(ptr, newData);
	}

return 0;
}

Update やっぱり単純tailではありません.idxに一致する最初のノードのデータを変更しています.最後に、既存のノードを削除するコードを見てみましょう.

// Single linked list#include < stdio.h >#define MAXN 1000struct ListNode {
int idx = -1;
int data;
	ListNode* next;

	ListNode* myAlloc(int _idx,int _data, ListNode* _next) {
		idx = _idx;
		data = _data;
		next = _next;

returnthis;
	}
} buffer[MAXN];

int bufferCnt = 0;

//ListNode *list;
ListNode head, tail;

void init() {
	bufferCnt = 0;
	head.next = &tail;
}

ListNode* getNode(int _idx) {
	ListNode* ptr = &head;

while (ptr->next) {
if (ptr->next->idx >= _idx || ptr->next->idx == -1)break;

		ptr = ptr->next;
	}

return ptr;
}

void update(ListNode* ptr,int _data) {
	ptr->next->data = _data;

return;
}

void remove(ListNode* ptr) {
	ptr->next = ptr->next->next;
}

int main() {
	init();

for (int i = 0; i < 10; ++i) {
int idx, data;
		scanf("%d %d", &idx, &data);

		ListNode* ptr = getNode(idx);
		ptr->next = buffer[bufferCnt++].myAlloc(idx, data, ptr->next);
	}

for (int i = 0; i < 10; ++i) {
int idx, newData;
		scanf("%d %d", &idx, &newData);

		ListNode* ptr = getNode(idx);
if (ptr->next->idx == idx && ptr->next->idx != -1) update(ptr, newData);
	}

for (int i = 0; i < 10; ++i) {
int idx;
		scanf("%d", &idx);

		ListNode* ptr = getNode(idx);
// node 삭제if (ptr->next->idx == idx && ptr->next->idx != -1) remove(ptr);
	}

return 0;
}

まずsingle link listの削除コードです.とても単純前のノードの次のノードを削除先の次のノードとして保存します.二重リンクリストの追加と削除コードは次のとおりです.

//Double linked liststruct ListNode {
int idx = -1;
int data;
	ListNode* prev;
	ListNode* next;

	ListNode* myAlloc(int _idx,int _data, ListNode* _prev, ListNode* _next) {
		idx = _idx;
		data = _data;
		prev = _prev;
		next = _next;
		_next->prev =this;// 현재 node를 다음 node의 이전 node로 연결.returnthis;
	}
} buffer[MAXN];

int bufferCnt = 0;

ListNode* getNode(int _idx) {
	ListNode* ptr = &head;

while (ptr->next) {
if (ptr->next->idx >= _idx || ptr->next->idx == -1)break;

		ptr = ptr->next;
	}

return ptr;
}

// ptr <--> ptr->next <--> ptr->next->nextvoid remove(ListNode* ptr) {
	ListNode* tmp = ptr->next;

	ptr->next = tmp->next;// ptr --> ptr->next->next
	tmp->next->prev = ptr;// ptr <-- ptr->next->next
}

int main() {
	init();

for (int i = 0; i < 10; ++i) {
int idx, data;
		scanf("%d %d", &idx, &data);

		ListNode* ptr = getNode(idx);
		ptr->next = buffer[bufferCnt++].myAlloc(idx, data, ptr, ptr->next);
	}

for (int i = 0; i < 10; ++i) {
int idx;
		scanf("%d", &idx);

		ListNode* ptr = getNode(idx);
// node 삭제if (ptr->next->idx == idx && ptr->next->idx != -1) remove(ptr);
	}

return 0;
}

Double linked list 削除も簡単です. headとtailを使用しているのでNULLチェックは不要です.head、tailを使用しない場合は、削除した次のノードがNULLであることを確認する必要があります.シングルリンクリストでは問題はありませんが、ダブルリンクリストでptr->next->nextがNULLの場合、NULL->prevでアクセスしてパーティション化に失敗するため、ptr->next->nextがNULLであるかどうかを最初に確認する必要があります.
問題の条件によって、それから自分のよく知っている方法で実施すればいいです.