「リスト」(List)-arrayListについて

リストを理解して並べ替えることで実現(C++)
次の記事:リンクリストを理解し、リストを実装

リスト#リスト#

リストは私たちの日常生活でよく使われる資料構造の一つです.例えば、買い物に使う買い物リスト、願い事などの願い事リスト.現実的には,特別な場合でなければ,リスト内のデータ間の順序は重要ではない.しかし、コンピュータ上で実施する場合、通常はindexによってデータ間の順序を設定する必要がある.

リストADT

リストadtは、データの挿入、削除、2つの要素間のすべてのコンテンツの交換、すべてのコンテンツの消去、リストにデータが存在するかどうかを確認し、リスト内のすべての要素を表示するなど、多くの機能を含むことができる.今回の記事では、挿入機能、削除機能、空の機能があるかどうかを確認する機能、要素の総数を表す機能、すべての要素を表す機能の5つだけを実現します.

// c++ code
#include<iostream>
#include<string>
using namespace std;

class List {

	// 구현 방법에 따라 앞과 뒤에 추가 구현부가 있을 수 있습니다.

public:

	void add() {
		// 삽입 함수 구현부
	};

	void del() {
		// 삭제 함수 구현부
	};

	bool isEmpty() { // 리스트가 비어있는지 확인하는 함수
		if ()// 리스트가 비어있을 때 true 반환
			return true;
		else
			return false;
	};

	void displayAll() {
		// 리스트의 모든 요소를 콘솔 화면에 출력하는 함수
	};

	// 구현 방법에 따라 앞과 뒤에 추가 구현부가 있을 수 있습니다.

};

int main() { // 리스트를 사용하는 부분입니다. 쇼핑리스트로 이용한다고 가정합시다.

	List list1;
	cout << "쇼핑리스트에 넣을 항목을 입력하시오";
	// 쇼핑리스트에 항목을 입력하는 부분, list1.add()를 통해 사용

	cout << "집에 있는 물건들을 살펴보고 삭제할 물건들은 삭제합시다.\n";
	cout << "삭제할 항목 : ";
	// 항목을 삭제하는 부분, list1.del()을 통해 사용

	cout << "장 볼 리스트를 출력합니다.";
	// 장 볼 리스트를 출력하는 부분, isEmpty()와 displayAll()을 통해 사용 가능

アレイ実装

リストadtを並べて実現しましょう.まず、入力した文字列を配列に保存する必要があります.したがって、文字列配列と配列内のアイテム数を含む整数変数が含まれます.

// c++ with array
#include<iostream>
#include<string>
using namespace std;

class List {
private:

	string shoppingList[100];
	int length = 0;

ユーザーは、リストが配列で構成されているかどうか分からないかもしれませんが、リストは使用可能である必要がありますのでprivateと宣言します.以下に、実装部を挿入します.

public:

	void add(string str) {
		shoppingList[length] = str;
		length++;
	};
  

legent変数を使用して、入力した値をショッピングリストの最後に挿入し、長さを増やします.
挿入とは異なり、関数を削除するプロセスは少し複雑です.下図の説明を見て、コードを書きましょう.

配列の原則は、特定のインデックスの値を削除してから、セルに入力し、次の値を移動することです.コードで表示:

	void del(string str) {
		if (isEmpty()) { cout << "리스트가 비어있습니다!"; return; }

		for (int i = 0; i < length; i++) {
			if(shoppingList[i] == str)
				for (int j = i; j < length; j++) {
					shoppingList[j] = shoppingList[j + 1];
				}
		}
	};

削除する値が配列に存在する場合は、内部のfor文から値を削除し、スペースを前にドラッグします.
すべての要素を出力する関数を見てみましょう.

	bool isEmpty() {
		if (length == 0)
			return true;
		else
			return false;
	};

	void displayAll() {
		cout << "쇼핑리스트 목록입니다.\n";
		for (int i = 0; shoppingList[i].size() != 0; i++) {
			cout << i + 1 << ". " << shoppingList[i] << endl;
		}
	};

};

リストの実装はアレイを介して完了しました.リストの実装部分を見て、実際のmain関数での使用状況を見てみましょう.

// c++ with array
#include<iostream>
#include<string>
using namespace std;

class List {
private:
	string shoppingList[100];
	int length = 0;

public:

	void add(string str) {
		shoppingList[length] = str;
		length++;
	};

	void del(string str) {
		if (isEmpty()) { cout << "리스트가 비어있습니다!"; return; }

		for (int i = 0; i < length; i++) {
			if(shoppingList[i] == str)
				for (int j = i; j < length; j++) {
					shoppingList[j] = shoppingList[j + 1];
				}
		}
	};

	bool isEmpty() {
		if (length == 0)
			return true;
		else
			return false;
	};

	void displayAll() {
		cout << "쇼핑리스트 목록입니다.\n";
		for (int i = 0; shoppingList[i].size() != 0; i++) {
			cout << i + 1 << ". " << shoppingList[i] << endl;
		}
	};

};

int main() {

	List list1;
	cout << "쇼핑리스트에 넣을 항목을 입력하시오. (최대 100개 입력 가능, 다음 단계로 넘어가려면 q 입력)\n";
	cout << "입력할 항목 : ";
	for (int i = 0; i < 100; i++) {
		string t;
		cin >> t;
		if (t == "q") break;
		list1.add(t);
	}

	cout << "집에 있는 물건들을 살펴보고 삭제할 물건들은 삭제합시다.(다음 단계로 넘어가려면 q 입력)\n";
	cout << "삭제할 항목 : ";
	for (int i = 0; i < 100; i++) {
		string t;
		cin >> t;
		if (t == "q") break;
		list1.del(t);
	}

	cout << "장 볼 리스트를 출력합니다.\n";
	list1.displayAll();
}

アレイ実装のメリットとデメリット

以上のように、アレイごとの実装は容易であり、idx閲覧速度が速いなどの利点がある.
ただし、リストに1つ以上の要素を入れると問題が発生します.C++では,静的割当てでも動的割当てでも実装される配列には,その大きさを超える値を含めることはできない.また、削除などの方法でゴミスペースが空になると、データが削除された後も後のデータを前に移動する必要があるため、時間の複雑さが増す.
次の記事では、リンクリストの定義とリストadtの実装について説明します.