데이터 구조의 문자열 (MFC 의 CString 시 뮬 레이 션)

일련의 정의
문자열: 0 개 이상 의 문자 로 구 성 된 유한 시퀀스 입 니 다.
문자열: 문자열 의 임의의 연속 문자 로 구 성 된 하위 시퀀스 를 이 문자열 의 하위 문자열 이 라 고 합 니 다.
주 문자열: 문자열 에 해당 하 는 문자열 을 포함 합 니 다.(문자열 에 비해)
   빈 칸 문자열: 하나 이상 의 빈 칸 으로 구 성 된 문자열 입 니 다. (빈 칸 만 있 으 면)
   빈 문자열: 문자열 의 길이 가 0 일 때.(첫 번 째 문 자 는 '또는' / 0 '입 니 다.)
문자열 이 같 습 니 다: 문자열 의 길이 가 같 고 문자열 의 각 대응 위치 에 있 는 문자 가 같 습 니 다.
   문자열 설명: s = "a1a 2a 3.................................................................(n. 꼬치 길이 라 고 함)
   문자열 의 열: s = "this is string example";s = ""；
특징: 구 성 된 요 소 는 문자 여야 합 니 다.
2. 직렬 과 선형 표 의 차이:
1. 직렬 의 논리 구조 와 선형 표 는 매우 비슷 하지만 직렬 의 데이터 대상 은 문자 집합 으로 제약 된다.
   2. 꼬치 의 기본 조작 과 선형 표 는 큰 차이 가 있다.
   3. 꼬치 의 기본 작업 에서 보통 '꼬치 의 전체' 를 조작 대상 으로 한다.
3. 코드 데모:
이 열 은 MFC 의 CString 을 모방 합 니 다.

#include <stdio.h>
#include<stdlib.h>
#define OK 1
#define  FALSE 0
typedef int Status;
int OVERFLOW=0;
typedef struct{
char* ch;
int length;
}HString;
Status StrAssign(HString &T, char* chars){//  T   
                                                                                                                                                               
    if(!T.length)free(T.ch);//    T.ch    ，T.ch  null
    char *c= chars;//c     chars   
    //printf("%s", c);
    for(int i = 0; *c; i++,c++);//   c   chars         chars
    if(!i){T.ch = NULL; T.length = 0;}
        else{
        if(!(T.ch = (char*)malloc(i*sizeof(char))))
            exit(OVERFLOW);
        T.ch = chars;
        //printf("
 chars is %s, T.ch is %s
", chars, T.ch);
        T.length = i;
                                                                                                                                                               
        }
    return OK;
}//   
int StrLength(HString S){
    return S.length;
}
int StrCompare(HString S, HString T){
    if(S.length == T.length){
        for(int i = 0; i < S.length; i++){
        if(*(S.ch + i) != *(T.ch + i)) return *(S.ch + i) - *(T.ch + i);
        }
    }
    return S.length - T.length;
}
Status ClearString(HString &S){
    //*S.ch = '\0';
    S.ch =NULL;
//  }
    S.length = 0;
    return OK;
}
Status Concat(HString &T, HString S1, HString S2){
    if(T.ch)ClearString(T);
    if(!(T.ch = (char*)malloc((S1.length + S2.length + 1)*sizeof(char))))
        exit(OVERFLOW);
    for(int j = 0; j < S1.length; j++)(*(T.ch + j)) = (*(S1.ch++));
    T.length = S1.length + S2.length;
    for(int i = S1.length; i < T.length; i ++){*(T.ch + i) = *(S2.ch++);}
    *(T.ch + T.length) = '\0';
    return OK;
}
Status SubString(HString &Sub, HString S, int pos, int  len){//   pos    ，len S.length - pos + 1
                                                                                                                                                               
    if(pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1)return FALSE;
    if(Sub.ch)ClearString(Sub);
    if(!len){Sub.ch = NULL; Sub.length = 0;}
    else{
    Sub.ch = (char*)malloc((len + 1) * sizeof(char));
    for(int i = 0; i < len; i++){
    //Sub.ch[i] = S.ch[pos + i-1];
    *(Sub.ch + i) = *(S.ch + pos + i-1);
    }
    *(Sub.ch + len) = '\0';
    Sub.length = len;
    }
return OK;
}
int index(HString s, HString t, int pos){//    
    int i = pos;
    int j = 1;
    HString S = s;
    S.ch = s.ch + i-1;
    HString T =t;
    while(i <= s.length && j <= t.length){
        char strs = *(S.ch++);
        char strt = *(T.ch++);
        if(strs == strt){++i; ++j;}
        else{i = i -j + 2;
        S.ch = s.ch + i-1;
        T.ch = t.ch;
                                                                                                                                                                   
        j = 1;
        }
                                                                                                                                                                   
    }
    if(j > T.length)return (i - T.length);
    else return 0;
}
int main(){
HString S;
char* s;//    char *s = ""       
s =new char;//     new char [1]
printf("   S.CH 
");
scanf("%s", s);
StrAssign(S, s);
HString T;
char* t;
t = new char;
printf("   T.CH 
");
scanf("%s", t);
StrAssign(T, t);
printf("
");
printf("**************************
");
HString W;
Concat(W, S, T);
printf("     W.ch = %s
", W.ch);
printf("**************************
");
printf("**************************
");
HString Sub;
int Pos, len;
printf("          pos,  len(pos,len  ):
");
scanf("%d,%d", &Pos, &len);
SubString(Sub, S, Pos, len);
printf("      Sub.ch = %s
", Sub.ch);
printf("**************************
");
printf("
");
printf("**************************
");
printf("StrCompare value is %d
", StrCompare(S,T));
printf("**************************
");
int pos = 1;
int time = 1;
while(pos != 0){
pos = index(S, T, pos);
if(pos != 0){printf("pos at %d index, show %d times
", pos , time); pos+=1; time++;}
if(time == 1)printf("no elem find
");
}
ClearString(S);
return 0;
}

4. 지식 점 회고
   꼬치, 빈 꼬치 등의 정의,
   직렬 과 선형 표 의 차이
   CString 모델 구현
5. 학습 확장
직렬 의 논리 구조 와 기본 조작
직렬 순차 저장
(정적, 동적 ― 더미 분배 저장 소)
직렬 식 저장 소
패턴 매 칭
(단순 일치)