[C++ 정리] 배열(Array)과 연결리스트(Linked List) 2015-06-18

배열 : 정해진 크기만큼만 선언을 할 수 있다. 이는 연결된 메모리를 보장해준다. 하지만 이는 유연하게 프로그래밍을 하는데는 제약이 있다.

array
장점

* 구현이 간단하다.
* 연결된 메모리상에 존재하므로 중간 데이터에 빠르게 접근할 수 있다. 
  ex> array[3] 으로 'D'에 접근할 수 있다.

단점

* 크기를 고정해야 하기 때문에 사용될 것을 고려하여 할당해야 하고 이는 불필요한 메모리를 차지한다.
* 중간 데이터의 삽입 또는 삭제가 일어난다면 뒤에 데이터를 전부 변경해야만(메모리상에서 한칸씩 밀거나 당긴다) 하기 때문에 비효율적이다.

연결리스트 : 크기에 대한 제약없어 유연하게 활용할 수 있지만 연결된 메모리가 아니기 때문에 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.

linkedlist
장점

* 필요할때마다 메모리를 동적으로 할당하기 때문에 메모리 효율적이다.
* 중간에 데이터를 삽입 또는 삭제 하더라도 다른 데이터에 영향을 주지 않아 효율적이다.
  Ex> 'D'를 삭제하려면 'C'에서의 링크를 'E'로 변경만 하면 된다.

단점

* 구현이 복잡하다.
* 중간의 데이터에 접근하기 위해서는 이전 노드를 모두 거쳐야만 접근할 수 있다.
  Ex> 'D'에 접근하려면 'B', 'C'를 거쳐야만 한다.

연결리스트의 종류

> 단일 연결 리스트(Singly Linked List)

singlylinkedlist

typedef struct node
{
    struct node* next;
    void* data;
}Node;

* 노드가 다음노드를 가리킨다.
> 이중 연결 리스트(Doubly Linked List)

doublylinkedlist

typedef struct node
{
    struct node* prev;
    struct node* next;
    void* data;
}Node;

* 각 노드들이 이전과 다음노드를 가리킨다.
> 다중 연결 리스트(Multiply Linked List)

multiplylinkedlist

typedef struct node
{
    vector<struct node *> pointers;
    void* data;
}Node;

* 각 노드가 2개이상의 노드를 가리킨다.
> 원형 연결 리스트(Circular Linked List)

circularlinkedlist

* 리스트의 마지막 노드가 멀리있는 다른 노드(보통 첫번째 노드)를 가리키고 있는 형태이다.
* 원형 이중 연결 리스트(circular doubly linked list)의 경우는 첫번째 노드의 prev는 마지막 노드를, 마지막 노드의 next는 첫번째 노드를 가리킨다.

<링크 : 위키문서(Linked list)> 참조

[C++ 정리] 3. 문자열 다루기 (C/C++조합) 2015-06-17

C style로 개발된 코드을 연동해야하는 경우 C++과 조합하는 형태로 개발되어야 한다.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <windows.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	char* strCStyle = "TEST STRING";
	string strCppStyle;

	// 바로 대입하여 사용가능하다.
	strCppStyle = strCStyle;
	cout << "strcpy : " << strCppStyle << "\n";

	// Cstyle과 같은 형태로 접근이 가능하다.
	strCppStyle[0] = 'A';
	cout << "strcpy : " << strCppStyle << "\n";

	// string 객체에는 문자열 + 기타 정보를 포함하고 있다.
	// 완전히 동일한 형태의 문자열값을 얻어오기 위해서는 c_str() 를 사용한다.
	const char* strTmp = NULL;
	strTmp = strCppStyle.c_str();
	cout << "strcpy : " << strTmp << "\n";

	// string 객체는 길이 제한이 없어 더욱 안정적이다.
	char cString[20];
	string cppString;
	
	// 19자 이상의 문자열을 입력하면 다른 메모리 영역을 덮어버려 심각한 문제가 발생한다.
	// - 악의적인 공격에 사용될 수 있다.
	cin >> cString;
	cout << "cin(C) : " << cString << "\n";

	// 길어도 상관없다.
	cin >> cppString;
	cout << "cin(CPP) : " << cppString << "\n";

	
	char cStringLine[20];
	string cppStringLine;

	// 메모리영역이 덮어지는 문제를 해결하려면 getline 함수를 사용하도록 하자.
	// - getline 함수는 입력된 문자를 20바이트가 넘지 않게 잘라서 저장한다.
	cin.getline(cStringLine, 20);
	cout << "getline(C) : " << cStringLine << "\n";

	getline(cin, cppStringLine);
	cout << "getline(CPP) : " << cppStringLine << "\n";

	return 0;
}

* C++ 의 string 객체에서 C style의 문자열을 변형하는 방법을 제공한다.
* string 객체를 사용하므로서 안정적으로 문자열을 활용할 수 있다.

[C++ 정리] 2. 문자열 다루기 (C++스타일) 2015-06-17

기본 제공하는 자료형이 아닌 string 객체를 사용해 문자열을 다루는데 이는 간단하고 명료하다.

#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	// 원본 문자열
	string orgString = "TEST STRING";
	
	cout << "STRING_LENGTH : " << orgString.size() << "\n";

	// 대상 문자열 & 복사
	string tarString = orgString;

	// 문자열 출력
	cout << "ORG_STRING : " << orgString << "\n";
	cout << "TAR_STRING : " << tarString << "\n";

	// 문자열 비교
	if (tarString == orgString){
		cout << "compare \"" << orgString << "\" :::: \"" << tarString << "\" indentical.\n";
	}
	else
	{
		cout << "compare \"" << orgString << "\" :::: \"" << tarString << "\" not indentical.\n";
	}

	// 문자열 결합
	string addString = "+ADD STRING";
	addString = orgString + addString;
	cout << "ADD_STRING : " << addString << "\n";

	// 문자열 찾기
	int stringIndex = addString.find("+ADD");
	// - 배열과 동일하게 생각하여 +ADD는 12번째 즉, 인덱스 11에 위치한다.
	cout << "FIND_STRING : " << stringIndex << "\n";

	// 문자열 자르기
	string cutString = addString.substr(12, 3);
	// - 대상 문자열의 12번째 부터 3자리의 글자를 읽어온다.
	cout << "CUT_STRING : " << cutString << "\n";

	return 0;
}

* <링크 : C스타일 문자열다루기>와 비교해 훨씬 간단명료해지고 많은 기능을 지원해줌을 알 수 있다.