자료구조 배열 사용

배열을 사용해 게임 엔트리를 저장한다. 배열은 간단히 데이터의 저장 용도로 많이 사용된다. 배열에 어떤 데이터를 저장할 지 생각해보자.

먼저 점수(score)를 저장하고, 이 점수를 얻은 사람의 이름(name)을 저장한다. 

 

//const 등 일부 유형의 데이터는 선언과 동시에 초기화가 필요하다. const 변수에는 값을 할당할 수 없다. 이 문제를 해결하기 위해 초기화 리스트를 사용.

#include<iostream>
#include<vector>
using namespace std;

class GameEntry{
public:
    GameEntry(const string& n="",int s = 0);
    string getname() const; //const method를 사용해 메소드 안에서는 변수값을 바꿀 수 없음, const method 안에서는 const가 아닌 메소드를 부를 수 없음.
    int getscore() const;
private:
    string name;
    int score;
};


//초기화 리스트 사용. name을 const n으로,score를 s로 할당
GameEntry::GameEntry(const string& n,int s):name(n),score(s){}

string GameEntry::getname() const{
    return name;
}
int GameEntry::getscore() const{
    return score;
}

//vector 사용해보기
//게임의 높은 점수들을 저장한다.
class Scores{
public:
    Scores(int maxEnt = 10);
    ~Scores();
    void add(const GameEntry& e);
    GameEntry remove(int i) //0<=i<=numEntries -1
        throw(IndexOutOfBounds);    //i범위 넘으면 예외 발생

private:
    int maxEntries; //엔트리의 최대 숫자
    int numEntries; //엔트리의 실제 숫자
    GameEntry* entries;
};

//생성자 정의
Scores::Scores(int maxEnt){
    maxEntries = maxEnt;    //최대 사람 수,maxEntries 개수만 유지됨.
    entries = new GameEntry[maxEntries];    //새로운 사람 생성
    numEntries = 0; //사람 수를 0으로 초기화
}

Scores::~Scores(){
    delete[] entries;
}

//삽입
void Scores::add(const GameEntry& e){
    int newScore = e.getScore();    //추가될 점수를 가져와
    if(numEntries == maxEntries){   //배열이 꽉차 있다면
        if(newScore <= entries[maxEntries-1].getScore())    //추가될 점수와 마지막 점수를 비교해
            return; 
        else numEntries++;  //배열이 꽉차 있지 않다면 추가
    }

    int i = numEntries-2;   //마지막 엔트리 옆
    while(i >= 0 && newScore > entries[i].getScore()){
        entries[i+1] = entries[i];  //하나 씩 오른쪽으로 옮김
        i--;
    }
    entries[i+1] = e;   //빈공간에 e 넣기
}

GameEntry Scores::remove(int i) throw(IndexOutOfBounds){
    if((i < 0) || (i >= numEntries))    //부적절한 값
        throw IndexOutOfBounds("Invalid index");
    GameEntry e = entries[i];   //부적절한 값 저장
    for(int j=i+1;j<numEntries;j++)
        entries[j-1] = entries[j];  //엔트리 왼쪽으로 이동
    numEntries--;   //엔트리 개수 줄이기
    return e;   //부적절한 값 반환
}

 

삽입 정렬

#include<iostream>
using namespace std;

int main(){
    int **M = new int*[n];  //행의 포인터로 이루어진 배열. 각 행의 위치를 포인터로 지정(*),값의 포인터(**) 
    for(int i = 0;i<n;i++){
        M[i] = new int[m];
    }

    //배열 반환
    for(int i = 0;i<n;i++){
        delete[] M[i];
    }
    delete[] M;


}

 

단일 링크드 리스트

배열은 정해진 크기 내에서 간단하게 저장하고 순회할 수 있지만 단점이 존재한다. 크기를 바꾸거나(vector로 해결가능) 순서를 변경하는 등 변화에 대해서는 취약하다. 

이번엔 링크드 리스트를 구현한다. 노드를 선형적으로 순서화된 형태이다.

 

#include<iostream>
#include<string>

using namespace std;

class StringNode{
    string elem;
    StringNode * next;

friend class SLinkedList;   //뒤에서 구현할 SLinkedList : 생성자,소멸자 삽입삭제 기능을 제공하는 클래스
};

class SLinkedList{
    StringNode * head;

public:
    SLinkedList();
    ~SLinkedList();
    bool empty() const;
    const string& front() const;
    void addFront(const string& e);
    void removeFront();
};

//head를 NULL로 초기화
SLinkedList::SLinkedList():head(NULL){} //초기화 리스트는 const에 대해서만 사용하는거 아닌가?

//head가 NULL인지 확인
bool SLinkedList::empty() const{
    if(head == NULL)
        return 0;
    else return 1;
}

//앞에서부터 삭제
SLinkedList::~SLinkedList(){
    while(!empty())
        removeFront();
}

//값 리턴
const string& SLinkedList::front() const{
    return head->elem;
}

void SLinkedList::addFront(const string& e){
    StringNode *NewNode = new StringNode;
    
    NewNode->elem = e;  //원래는 N
    NewNode->next = head;
    head = NewNode;
}

void SLinkedList::removeFront(){
    StringNode *ret = head;
    head = head->next;
    delete ret;
}

int main(){
    return 0;
}