배열이란? 배열의 선언? - 배열과 포인터의 관계? 문자열이란? 문자배열 연결 리스트

Presentation on theme: "배열이란? 배열의 선언? - 배열과 포인터의 관계? 문자열이란? 문자배열 연결 리스트"— Presentation transcript:

1 배열이란? 배열의 선언? - 배열과 포인터의 관계? 문자열이란? 문자배열 연결 리스트
배열과 연결 리스트 배열이란? 배열의 선언? - 배열과 포인터의 관계? 문자열이란? 문자배열 연결 리스트

2 배열이란 배열 배열의 선언 배열의 원소 배열의 끝을 지나 값을 저장할 경우 동일한 자료형을 저장하는 장소들의 모임
배열내의 각각의 저장 장소 변위(offset)을 지정하여 접근 배열의 끝을 지나 값을 저장할 경우 항의 존재 유무를 검사하지 않는다 “offset X 각 원소의 크기” 위치에 무조건 저장 형 배열의이름 [항의개수] ; long LongArray[25] ; LongArray[0] ~ LongArray[24]

3 #include <iostream> using namespace std; int main() {
long sentinelOne[3]; long TargetArray[25]; long sentinelTwo[3]; for (int i=0; i<3; i++) sentinelOne[i] = sentinelTwo[i] = 0; for (i=0; i<25; i++) TargetArray[i] = 0; cout <<"Test 1: \n"; cout <<"TargetArray[0]: "<<TargetArray[0] << "\n"; cout <<"TargetArray[24]: “<<TargetArray[24]<<"\n\n"; for (i = 0; i<3; i++) cout << "sentinelOne[" << i << "]: "; cout << sentinelOne[i] << "\n"; cout << "sentinelTwo[" << i << "]: "; cout << sentinelTwo[i]<< "\n"; } list 13.2

4 cout << "\nAssigning...";
for (i = 0; i<=25; i++) TargetArray[i] = 20; cout << "\nTest 2: \n"; cout << "TargetArray[0]: " << TargetArray[0] << "\n"; cout << "TargetArray[24]: " << TargetArray[24] << "\n"; cout << "TargetArray[25]: " << TargetArray[25] << "\n\n"; for (i = 0; i<3; i++) { cout << "sentinelOne[" << i << "]: "; cout << sentinelOne[i]<< "\n"; cout << "sentinelTwo[" << i << "]: "; cout << sentinelTwo[i]<< "\n"; } return 0;

5 배열의 초기화 (X) (O) array 크기 = sizeof( IntegerArray )
={쉼표로 분리된 초기값들} int IntegerArrary[5] = { 10, 20, 30, 40, 50 } ; int IntegerArrary[5] = { 10, 20, 30, 40, 50 } ; int IntegerArrary[5] = { 10, 20, 30, 40, 50, 60 } ; (X) int IntegerArrary[5] = { 10, 20} ; (O) int IntegerArrary[ ] = { 10, 20, 30, 40, 50 } ; array 크기 = sizeof( IntegerArray ) / sizeof( IntegerArray[0] ) ;

6 기타 배열명 배열의 차원 (사용자 정의)객체의 배열 같은 범위 내에서 같은 변수명이나 배열명과 겹쳐서는 안됨
배열명은 배열을 가지고 있는 메모리의 주소 ( 제일 첫번째 원소의 주소 ) 배열의 차원 상수형 또는 나열형 변위는 변수가 가능하나 선언 시 배열의 크기는 변수가 되어서는 안됨 (사용자 정의)객체의 배열 모든 객체(내장+사용자 정의)는 배열에 저장 가능

7 #include <iostream>
using namespace std; class CAT { public: CAT() { itsAge = 1; itsWeight=5; } ~CAT() {} int GetAge() const { return itsAge; } int GetWeight() const { return itsWeight; } void SetAge(int age) { itsAge = age; } private: int itsAge; int itsWeight; }; int main() CAT Litter[5]; for (int i = 0; i < 5; i++) Litter[i].SetAge(2*i +1); for (i = 0; i < 5; i++){ cout << "Cat #" << i+1<< ": "; cout << Litter[i].GetAge() << endl; } return 0;

8 다차원 배열 n n 차원의 배열은 n개의 첨자를 가짐 다차원 배열 초기화
형 배열의이름 [항의개수][항의갯수] … [항의개수] ; n SQUARE Board[8][8] ; int Array[4][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } ; Array[0][ ] Array[1][ ] int Array[4][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12} } ;

9 포인터 배열 (포인터가 저장된 배열) 포인터 배열 사용 예 각 객체는 자유 기억 공간에 저장
그 포인터(자유 기억 공간의 주소)를 포인터 배열에 저장 제한된 스택 메모리의 공간을 절약

10 #include <iostream> using namespace std; class CAT { public:
CAT() { itsAge = 1; itsWeight=5; } ~CAT() {} int GetAge() const { return itsAge; } int GetWeight() const { return itsWeight; } void SetAge(int age) { itsAge = age; } private: int itsAge; int itsWeight; }; list 13.6

11 int main() { CAT * Family[500]; int i; CAT * pCat; for (i = 0; i < 500; i++) pCat = new CAT; pCat->SetAge(2*i +1); Family[i] = pCat; } cout << "Cat #" << i+1 << ": "; cout << Family[i]->GetAge() << endl; return 0;

12 자유기억공간에 배열 선언 CAT *Family = new CAT [500] ; CAT *pCat = Family ;
배열을 가지고 있는 포인터가 반환 포인터의 연산은 다음 객체를 가리키도록 연산됨 자유 기억 공간의 배열 지우기 CAT * Family = new CAT[ 500 ] ; CAT *Family = new CAT [500] ; CAT *pCat = Family ; pCat->SetAge(10) ; // Family[0] pCat++; pCat ->SetAge(20) ; // Family[1] delete [ ] Family ;

13 포인터와 배열명 FamilyOne은 500개의 Cat 배열
Family = &FamilyOne[ 0 ] FamilyTwo 는 500개의 Cat에 대한 포인터를 저장하는 배열 (포인터 배열) FamilyThree는 자유기억공간상에 500개의 Cat 배열의 처음을 가리키는 포인터 Cat FamilyOne[ 500 ] ; Cat * FamilyTwo[ 500 ] ; Cat * FamilyThree = new Cat [ 500 ] ;

14 #include <iostream> class CAT { public:
CAT() { itsAge = 1; itsWeight=5; } ~CAT(); int GetAge() const { return itsAge; } int GetWeight() const { return itsWeight; } void SetAge(int age) { itsAge = age; } private: int itsAge; int itsWeight; }; CAT :: ~CAT() // cout << "Destructor called!\n"; } list 13.7

15 int main() { CAT * Family = new CAT[500]; int i; for (i = 0; i < 500; i++) Family[i].SetAge(2*i +1); } std::cout << "Cat #" << i+1 << ": "; std::cout << Family[i].GetAge() << std::endl; delete [] Family; return 0;

16 Char 배열 (문자 배열) 문자열 초기화되지 않은 문자 배열 생성 가능 널(‘\0’) 문자로 끝나는 문자의 배열
널 (‘\0’) 문자 : 문자열의 끝임을 표시 초기화되지 않은 문자 배열 생성 가능 cin을 통하여 문자 배열 채우기 가능 공백 문자를 입력의 끝으로 간주하는 문제 cin.get( char *, int , char = ‘\n’ ) 채워야 할 버퍼 입력 최대 문자 수 입력 종료 문자 char Greeting [ ] = { ‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘ ‘, ‘W’, ‘o’, ‘r’, ‘l’, ‘d’, ‘\0’ } ; char Greeting [ ] = “Hello World” ;

17 #include <iostream> int main() { char buffer[80];
std::cout << "Enter the string: "; std::cin >> buffer; std::cout << "Here is's the buffer: “ << buffer << std::endl; return 0; } list 13.8 #include <iostream> using namespace std; int main() { char buffer[80]; cout << "Enter the string: "; cin.get(buffer, 79); cout << "Here's the buffer: " << buffer << endl; return 0; } list 13.9

18 문자열 함수 #include <string.h>
strcpy( char * des, const char * src ) 문자열 복사 strncpy( char *des, const char * src, unsigned int num ) num개의 문자열 복사 strlen ()

19 #include <iostream> #include <string.h> int main() {
const int MaxLength = 80; char String1[ ] = "No man is an island"; char String2[MaxLength+1]; strncpy(String2,String1,MaxLength); std::cout << "String1: " << String1 << std::endl; std::cout << "String2: " << String2 << std::endl; return 0; } list 13.11

20 String class 문자열을 표현하기 위한 class 필요한 만큼의 정확한 메모리를 할당하고 유지
operator [ ] ( USHORT offset ) offset 번째의 문자 값 반환 operator + ( const String & ) 두 문자열을 연결 operator += ( const String & ) 두 문자열을 연결하여 원래의 문자에 덮어 씀

21 #include <iostream> #include <string.h>
using namespace std; class String { public: String(); String(const char *const); String(const String &); ~String(); char & operator[ ] (unsigned short offset); char operator[ ] (unsigned short offset) const; String operator+ (const String&); void operator+= (const String&); String & operator= (const String &); unsigned short GetLen()const { return itsLen; } const char * GetString() const { return itsString; } private: String (unsigned short); char * itsString; unsigned short itsLen; }; list 13.12

22 String::String() { itsString = new char[1]; itsString[0] = '\0'; itsLen=0; } String::String(unsigned short len) itsString = new char[len+1]; for (unsigned short i = 0; i<=len; i++) itsString[i] = '\0'; itsLen=len; String::String(const char * const cString) itsLen = strlen(cString); itsString = new char[itsLen+1]; for (unsigned short i = 0; i<itsLen; i++) itsString[i] = cString[i]; itsString[itsLen]='\0';

23 String::String (const String & rhs)
{ itsLen=rhs.GetLen(); itsString = new char[itsLen+1]; for (unsigned short i = 0; i<itsLen;i++) itsString[i] = rhs[i]; itsString[itsLen] = '\0'; } String::~String () delete [ ] itsString; itsLen = 0;

24 String& String::operator=(const String & rhs)
{ if (this == &rhs) return *this; delete [ ] itsString; itsLen=rhs.GetLen(); itsString = new char[itsLen+1]; for (unsigned short i = 0; i<itsLen;i++) itsString[i] = rhs[i]; itsString[itsLen] = '\0'; } char & String::operator[ ](unsigned short offset) if (offset > itsLen) return itsString[itsLen-1]; else return itsString[offset]; char String::operator[ ](unsigned short offset) const

25 String String::operator+(const String& rhs)
{ unsigned short totalLen = itsLen + rhs.GetLen(); String temp(totalLen); unsigned short i; for ( i= 0; i<itsLen; i++) temp[i] = itsString[i]; for (unsigned short j = 0; j<rhs.GetLen(); j++, i++) temp[i] = rhs[j]; temp[totalLen]='\0'; return temp; } void String::operator+=(const String& rhs) unsigned short rhsLen = rhs.GetLen(); unsigned short totalLen = itsLen + rhsLen; String temp(totalLen); for (i = 0; i<itsLen; i++) temp[i] = rhs[i-itsLen]; *this = temp;

26 int main() { String s1("initial test"); cout << "S1:\t" << s1.GetString() << endl; char * temp = "Hello World"; s1 = temp; char tempTwo[20]; strcpy(tempTwo,"; nice to be here!"); s1 += tempTwo; cout << "tempTwo:\t" << tempTwo << endl; cout << "S1[4]:\t" << s1[4] << endl; s1[4]='x'; cout << "S1[999]:\t" << s1[999] << endl;

27 String s2(" Another string");
cout << "My Break\n"; s3 = s1+s2; cout << "S3:\t" << s3.GetString() << endl; String s4; s4 = "Why does this work?"; cout << "S4:\t" << s4.GetString() << endl; return 0; }

28 연결리스트 (Linked List) 데이터 포인터 데이터와 포인터의 쌍으로 이루어지는 자료 구조 노드 연결 리스트의 종류
데이터를 필요한 만큼 쓸 수 있음 삽입과 삭제가 용이 노드 포인터는 연결된 다른 노드를 가리킴 첫 번째 노드를 헤더( Header ) 마지막 노드를 테일( Tail ) 연결 리스트의 종류 단방향 연결 ( Singly linked ) 양방향 연결 ( Doubly linked ) 트리 ( Tree ) 데이터 포인터

29 연결리스트 (Linked List) 단방향 연결 : Singly linked 양방향 연결 : Doubly linked 데이터
포인터 포인터 포인터 포인터 데이터 데이터 데이터 데이터 포인터 포인터 포인터 포인터 포인터 포인터 포인터 포인터

30 연결리스트 (Linked List) 트리 (Tree) 데이터 포인터 포인터 데이터 데이터 포인터 포인터 포인터 포인터 데이터

31 #include <iostream> using namespace std;
enum { kIsSmaller, kIsLarger, kIsSame}; class Data { public: Data(int val):myValue(val){ } ~Data(){ } int Compare(const Data &); void Show() { cout << myValue << endl; } private: int myValue; }; int Data::Compare(const Data & theOtherData) if (myValue < theOtherData.myValue) return kIsSmaller; if (myValue > theOtherData.myValue) return kIsLarger; else return kIsSame; } list 13.13

32 class Node { public: Node(){ } virtual ~Node(){ } virtual Node * Insert(Data * theData)=0; virtual void Show( ) = 0; private: }; class InternalNode: public Node InternalNode(Data * theData, Node * next); ~InternalNode() { delete myNext; delete myData; } virtual Node * Insert(Data * theData); virtual void Show( ) myData->Show(); myNext->Show(); } Data * myData; Node * myNext;

33 InternalNode::InternalNode(Data * theData, Node * next):
myData(theData),myNext(next) { } Node * InternalNode::Insert(Data * theData) int result = myData->Compare(*theData); switch(result) case kIsSame: case kIsLarger: InternalNode * dataNode = new InternalNode(theData, this); return dataNode; case kIsSmaller: myNext = myNext->Insert(theData); return this;

34 class TailNode : public Node
{ public: TailNode(){ } ~TailNode(){ } virtual Node * Insert(Data * theData); virtual void Show() { } private: }; Node * TailNode::Insert(Data * theData) InternalNode * dataNode = new InternalNode(theData, this); return dataNode; }

35 class HeadNode : public Node
{ public: HeadNode(); ~HeadNode() { delete myNext; } virtual Node * Insert(Data * theData); virtual void Show() { myNext->Show(); } private: Node * myNext; }; HeadNode::HeadNode() myNext = new TailNode; } Node * HeadNode::Insert(Data * theData) myNext = myNext->Insert(theData); return this;

36 class LinkedList { public: LinkedList(); ~LinkedList() { delete myHead; } void Insert(Data * theData); void ShowAll() { myHead->Show(); } private: HeadNode * myHead; }; LinkedList::LinkedList() myHead = new HeadNode; } void LinkedList::Insert(Data * pData) myHead->Insert(pData);

37 int main() { Data * pData; int val; LinkedList ll; for (;;) cout << "What value? (0 to stop): "; cin >> val; if (!val) break; pData = new Data(val); ll.Insert(pData); } ll.ShowAll(); return 0;