[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 2.6 스트링 추상 데이타 타입 연습문제

1,2,3,4,5번 문제 전체 코드
//String.h의 헤더파일

#ifndef String
#include <iostream>
using namespace std;

class String {
private:
    char* str;
    int len;
    int* f;

public:
    String(char* init, int m) :len(m) {
        str = new char[m + 1];
        f = new int[m];

        for (int i = 0; i < m; i++)
            str[i] = init[i];

        str[m] = '\0'; //문자열의 끝은 항상 널이다
        FailureFunction();
    }

    ~String() {
        if (str != NULL) {
            delete[]str;
            str = NULL;
        }

        if (f != NULL) {
            delete[]f;
            f = NULL;
        }
    }

    String(const String& t) :len(t.len) {
        str = new char[t.len + 1];
        f = new int[t.len];

        for (int i = 0; i < len; i++)
            str[i] = t.str[i];

        str[len] = '\0';
        FailureFunction();
    }

    int Length();
    String Concat(String t);
    String SubStr(int i, int j);
    int Find(String pat);
    int FastFind(String pat);
    void FailureFunction();
    void Frequency();
    String Delete(int start, int end);
    String CharDelete(char c);
    String Replace(String w, String x);
    int Compare(String& s, String& t);

    friend ostream& operator<<(ostream& os, const String& t);
};

#endif // !String

 
//Functions.cpp의 함수기능 구현 소스파일

#include <iostream>
#include "String.h"
using namespace std;

int String :: Length() {
        return len;
    }

String String :: Concat(String t) { //문자열을 합친다 C언어의 strcat
    char* s = new char[Length() + t.Length() + 1];
    int idx = 0;

    for (int i = 0; i < Length(); i++) {
        s[idx++] = str[i];
    }

    for (int i = 0; i < t.Length(); i++) {
        s[idx++] = t.str[i];
    }

    s[idx] = '\0'; //문자열의 끝

    String copy(s, idx); //동적할당 메모리 반환 위해
    delete[]s;
    s = NULL;

    return copy;
}

String String :: SubStr(int i, int j) { //this에서 i, i+1, ..., i+j-1의 위치에 있는 j개의 스트링 반환
    char* subStr = new char[j + 1];
    int idx = 0;

    for (int k = i; k < i + j; k++)
        subStr[idx++] = str[k]; //문자열의 일부분

    subStr[idx] = '\0';

    String copy(subStr, idx);
    delete[]subStr;
    subStr = NULL;

    return copy;
}

int String :: Find(String pat) {
    for (int start = 0; start <= Length() - pat.Length(); start++) {
        int j;
        for (j = 0; (j < pat.Length()) && (str[start + j] == pat.str[j]); j++)
        if (j == pat.Length())
            return start; 
    }
    return -1;
}

int String :: FastFind(String pat) {
    int posP = 0, posS = 0;
    int lengthP = pat.Length(), lengthS = Length();
    while ((posP < lengthP) && (posS < lengthS))
        if (pat.str[posP] == str[posS]) {
            posP++;
            posS++;
        }
        else {
            if (posP == 0)
                posS++;
            else 
                posP = pat.f[posP - 1] + 1;
        }

    if (posP < lengthP)
        return -1;
    else
        return posS - lengthP;
}

void String :: FailureFunction() {
    int lengthP = Length();
    f[0] = -1;

    for (int j = 1; j < lengthP; j++) {
        int i = f[j - 1];

        while ((*(str + j) != *(str + i + 1)) && (i >= 0))
            i = f[i];

        if (*(str + j) == *(str + i + 1))
            f[j] = i + 1;
        else
            f[j] = -1;
    }
}

void String :: Frequency() { //1번 문제
    int alphabet[26] = { 0, };

    for (int i = 0; i < Length(); i++) {
        if (str[i] >= 'a' && str[i] <= 'z') {
            alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
        }
        else if (str[i] >= 'A' && str[i] <= 'Z') {
            alphabet[str[i] - 65]++; //A=65
        }
    }

     cout << "문자열: " << str << "의 문자 빈도수" << endl;
     for (int i = 0; i < 26; i++) {
        if (alphabet[i] != 0)
            cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
     }
}

String String::Delete(int start, int end) { //2번 문제
    char* t = new char[Length() + 1];
    int idx = 0;

    for (int i = 0; i < Length(); i++) { //i가 start보다 크거나 같고 end보다 같거나 작으면 t배열에 복사 x
        if ((i >= start) && (i <= end))
            continue;
        else
            t[idx++] = str[i];
    }

    String copy(t, idx); //char인 t를 반환할 수 없어서 string타입으로 copy후 반환

    return copy;
}

String String :: CharDelete(char c) { //3번 문제
    char* t = new char[Length() + 1];
    int idx = 0;

    for (int i = 0; i < Length(); i++) {
        if (str[i] == c)
            continue;
        else
            t[idx++] = str[i];
    }

    String copy(t, idx);

    return copy;
}

String String::Replace(String w, String x) { //4번문제
    int start = FastFind(w); //fastfind로 this에 스트링 w가 있는 위치 반환

    cout << "문자열 " << w << "를 문자열 " << x << "로 대체" << endl;

    String copy = SubStr(0, start); //this에 0번부터 스트링 w가 시작되는 부분까지 문자열 반환
    String copy2 = copy.Concat(x); //this에서 스트링w가 시작되기 전의 문자열과 스트링x를 합침
    String copy3 = SubStr(start + w.Length(), Length()); //this에서 스트링w 뒷부분 문자열 반환
    String result = copy2.Concat(copy3);

    return result;
}

int String::Compare(String& s, String& t) {
    char* copy = new char[s.Length() + 1];
    char* copy2 = new char[s.Length() + 1];
    int i;

    for (i = 0; i < s.Length(); i++)
        copy[i] = s.str[i];
    for (i = 0; i < t.Length(); i++)
        copy2[i] = t.str[i];

    
    if (s.Length() < t.Length()) // (0≤i<m, m<n)이고 xi=yi 인 경우는 x<y이므로 -1 반환. 
        return -1;    // (m<n이 이미 s의 스트링 길이가 t 스트링 길이보다 짧다는 뜻)
    else if (s.Length() == t.Length()) {
        int equal = 0;
        for (i = 0; i < s.Length(); i++) {
            if ((copy[i] != copy2[i]) && (copy[i] > copy2[i])) {
                equal++;
                break;
            }
            else if ((copy[i] != copy2[i]) && (copy[i] < copy2[i])) {
                equal--;
                break;
            }
        }
        if (equal == 0)
            return 0;
        else if (equal > 0)
            return 1;
        else
            return -1;
    }
    else
        return 1;
}

ostream& operator<<(ostream& os, const String& t) {
    os << t.str << endl;
    return os;
}

 
// main.cpp의 메인 소스 화일

#include "String.h"
#include <iostream>
using namespace std;

int main(void)

{
    char s[] = "";
    int len;
    int start, end;

    cout << "문자열을 입력하세요 : ";
    cin >> s;
    cout << "문자열의 길이를 입력하세요 : ";
    cin >> len;

    String str(s, len);

    str.Frequency();
    cout << endl;

    cout << "지울 문자열의 시작과 끝을 입력하세요 :";
    cin >> start >> end;
    String del = str.Delete(start, end);
    cout << del << endl;

    char c;
    cout << "지울 문자열 1개를 입력하세요 : ";
    cin >> c;
    String Cdel = str.CharDelete(c);
    cout << Cdel << endl;

    char a[] = "";
    char b[] = "";
    int alen, blen;
    cout << "서브 스트링 w를 입력하세요 : ";
    cin >> a;
    cout << "서브 스트링 w의 길이를 입력하세요 : ";
    cin >> alen;
    cout << "대체할 스트링 x를 입력하세요 : ";
    cin >> b;
    cout << "대체할 스트링 x의 길이를 입력하세요 : ";
    cin >> blen;
    String w(a, alen);
    String x(b, blen);
    
    String replace = str.Replace(w, x);

    char p[] = "apple";
    char q[] = "applejam";
    String str1(p, 5);
    String str2(q, 8);
    int result = str1.Compare(str, str2);
    if (result > 0)
        cout << str1 << "이 " << str2 << "보다 크다" << endl;
    else if (result == 0)
        cout << str1 << "과 " << str2 << "는 동일한 문자열이다." << endl;
    else
        cout << str1 << "이" << str2 << "보다 작다" << endl;

    return 0;
}

 
//출력

* 맨 마지막에 Replace 출력 값이 왜 그런지는 저도 모르겠습니다 ...
* 디버깅 오류라는데 해결 방법을 모르겠음 ..
* 아시는 분은 저를 살려주십쇼 ..
 
 
1. 입력으로 스트링을 받아들여서 스트링 내에 각기 다른 문자가 나타나는 횟수를 구하는 함수 String::Frequency를 작성하라. 적절한 데이터를 이용하여 이 함수를 테스트 하라.
 

void String :: Frequency() { //1번 문제
    int alphabet[26] = { 0, };

    for (int i = 0; i < Length(); i++) {
        if (str[i] >= 'a' && str[i] <= 'z') {
            alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
        }
        else if (str[i] >= 'A' && str[i] <= 'Z') {
            alphabet[str[i] - 65]++; //A=65
        }
    }

     cout << "문자열: " << str << "의 문자 빈도수" << endl;
     for (int i = 0; i < 26; i++) {
        if (alphabet[i] != 0)
            cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
     }
}

* Function.cpp 소스화일에서 일부분 발췌. (전체 코드는 맨 위에)
* 아스키코드 이용하여 구현
* 참고 : https://jaimemin.tistory.com/144
 
 
 
 
2. 스트링과 2개의 정수 start, length를 입력으로 받는 함수 String::Delete를 작성하라. 이 함수 start에서 시작해서 length만큼 문자를 원래 스트링에서 제거한 새로운 스트링을 반환하여야 한다.
 

String String::Delete(int start, int end) {
    char* t = new char[Length() + 1];
    int idx = 0;

    for (int i = 0; i < Length(); i++) { //i가 start보다 크거나 같고 end보다 같거나 작으면 t배열에 복사 x
        if ((i >= start) && (i <= end))
            continue;
        else
            t[idx++] = str[i];
    }

    String copy(t, idx); //char인 t를 반환할 수 없어서 string타입으로 copy후 반환

    return copy;
}

* Function.cpp 소스화일에서 일부분 발췌. (전체 코드는 맨 위에)
 
* 참고 : https://jaimemin.tistory.com/144
 
 
 
 
3. 스트링과 하나의 문자 c를 입력으로 받는 함수 String::CharDelete를 작성하라. 이 함수는 스트링에서 문자 c가 나타나는 경우 모두 제거한 나머지 스트링을 반환 한다.
 

String String :: CharDelete(char c) { //3번 문제
    char* t = new char[Length() + 1];
    int idx = 0;

    for (int i = 0; i < Length(); i++) {
        if (str[i] == c)
            continue;
        else
            t[idx++] = str[i];
    }

    String copy(t, idx);

    return copy;
}

* Function.cpp 소스화일에서 일부분 발췌. (전체 코드는 맨 위에)
* 2번 문제만 참고하고 3번은 2번 보면서 스스로 썼음 .. 감격..
 
 
 
 
4. 주어진 스트링에서 서브스트링 w를 스트링 x로 별도의 공간을 사용하지 않고 그 자리에서 대치 시키는 함수를 작성하라. w는 x와 크기가 같이 않을 수 있음에 유의하라. 이 함수의 복잡도는 어떻게 되는가?
 

String String::Replace(String w, String x) { //4번 문제
    int start = FastFind(w); //fastfind로 this에 스트링 w가 있는 위치 반환

    cout << "문자열 " << w << "를 문자열 " << x << "로 대체" << endl;

    String copy = SubStr(0, start); //this에 0번부터 스트링 w가 시작되는 부분까지 문자열 반환
    String copy2 = copy.Concat(x); //this에서 스트링w가 시작되기 전의 문자열과 스트링x를 합침
    String copy3 = SubStr(start + w.Length(), Length()); //this에서 스트링w 뒷부분 문자열 반환
    String result = copy2.Concat(copy3);

    return result;
}

* Function.cpp 소스화일에서 일부분 발췌. (전체 코드는 맨 위에)
* 참고 : https://jaimemin.tistory.com/144
 
 
 
 
5.

 

int String::Compare(String& s, String& t) {
    char* copy = new char[s.Length() + 1];
    char* copy2 = new char[s.Length() + 1];
    int i;

    for (i = 0; i < s.Length(); i++)
        copy[i] = s.str[i];
    for (i = 0; i < t.Length(); i++)
        copy2[i] = t.str[i];

    
    if (s.Length() < t.Length()) // (0≤i<m, m<n)이고 xi=yi 인 경우는 x<y이므로 -1 반환. 
        return -1;    // (m<n이 이미 s의 스트링 길이가 t 스트링 길이보다 짧다는 뜻)
    else if (s.Length() == t.Length()) {
        int equal = 0;
        for (i = 0; i < s.Length(); i++) {
            if ((copy[i] != copy2[i]) && (copy[i] > copy2[i])) {
                equal++;
                break;
            }
            else if ((copy[i] != copy2[i]) && (copy[i] < copy2[i])) {
                equal--;
                break;
            }
        }
        if (equal == 0)
            return 0;
        else if (equal > 0)
            return 1;
        else
            return -1;
    }
    else
        return 1;
}

* Function.cpp 소스화일에서 일부분 발췌. (전체 코드는 맨 위에)

* 출력에서 오류 디버깅 오류? 나도 이유를 모르겠음 ㅜ
* 참고 : https://jaimemin.tistory.com/144 

 

 

7. 다음의 각 패던에 대해 실패 함수를 계산하라.