광의 표 의 기본 조작

요 며칠 동안 을 배 웠 는데 그 중의 광의 표 에 의 해 어려워 졌 고 오늘 의 작은 연 구 를 통 해 알 아 보 았 습 니 다.
이것 은 광의 표 의 기본 개념 이다.
    광의 표 (Lists, 목록 이 라 고도 함) 는 선형 표 의 홍보 이다.즉, 광의 표 에서 표 요소 에 대한 원자 제한 을 풀 고 그들 이 자신의 구 조 를 가지 도록 허용 하 는 것 이다.1. 광의 표 정의    광의 표 는 n (n ≥ 0) 개 원소 a1, a2,..., ai,..., an 의 유한 서열 이다.  그 중:    ① ai - 또는 원자 또는 광의 표.　  ② 광의 표 는 보통 다음 과 같이 기록한다.              Ls=( a1，a2，…，ai，…，an)。 　　  ③ Ls 는 광의 표 의 이름 이 고 n 은 그 길이 이다.④ ai 가 광의 표 라면 Ls 의 자 표 라 고 부른다.  주의:    ① 광의 표 는 괄호 로 묶 고 쉼표 로 그 중의 요 소 를 구분한다.    ② 원자 와 광의 표를 구분 하기 위해 서 는 대문자 로 광의 표를 표시 하고 소문 자로 원 자 를 표시 한다.    ③ 광의 표 Ls 비 공 (n ≥ 1) 이 라면 al 은 LS 의 표 두 이 고 나머지 요소 로 구 성 된 표 (a1, a2,..., an) 는 Ls 의 표 미 라 고 부른다.   ④ 광의 표 는 재 귀적 으로 정 의 된 2. 광의 표 는 (1) 광의 표 는 ① E = ()     E 는 빈 시계 로 길이 가 0 이다.　　② L=(a，b)      L 은 길이 가 2 인 광의 표 로 두 요 소 는 모두 원자 이기 때문에 선형 표 ③ A = (x, L) = (x, (a, b) 이다.     A 는 길이 가 2 인 광의 표 이 고 첫 번 째 원 소 는 원자 x 이 며 두 번 째 원 소 는 자 표 L 이다.　　④ B=(A，y)=((x，(a，b))，y) 　     B 는 길이 가 2 인 광의 표 이 고 첫 번 째 원 소 는 자 표 A 이 며 두 번 째 원 소 는 원자 y 이다.　　⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))      C 의 길 이 는 2 이 고 두 요 소 는 모두 서브 시트 이다.　　⑥ D=(a，D)=(a，(a，(a，(…))))      D 의 길 이 는 2 이 고 첫 번 째 원 소 는 원자 이 며 두 번 째 원 소 는 D 자체 이 며 펼 친 후에 무한 한 광의 표 이다.(2) 광의 표 의 깊이 는 한 표 의 '깊이' 는 표 가 펼 쳐 진 후에 괄호 를 포함 하 는 층 수 를 말한다.  [예] 표 L, A, B, C 의 깊이 는 각각 1, 2, 3, 4 이 고 표 D 의 깊이 는 표시 이다.(3) 이름 이 있 는 광의 표 표시    만약 에 모든 표 에 이름 이 있다 고 규정 하면 표 의 이름 을 밝 히 고 그 구성 을 설명 하기 위해 표 의 앞 에 이 표 의 이름 을 붙 일 수 있다. 그래서 상례 의 각 표 는 ① E () ② L (a, b) ③ A (x, L (a, b) ④ B (A (x, L (a, b), y) ⑤ C (A (x, l (a, b), B (A (x, L (a, b), y) ⑥ D (a, D (a, D)) (4) 로 쓸 수 있다.광의 표 의 도형 표시 (a) 광의 표 의 도형 표시:   ① 그림 의 분기 결산 점 은 광의 표 에 대응한다.   ② 비 분기 결점 은 일반적으로 원자 이다.    ③ 그러나 빈 표 에 대응 하 는 것 도 비 분기 점 이다.[예] 아래 그림 은 몇 개의 광의 표 의 도형 표 시 를 보 여 주 었 다.              (b) 광의 표 의 도형 모양 구분:  ① 나무 에 대응 하 는 광의 표 는 순 표 라 고 하 는데 표 에 있 는 성분 의 공유 와 재 귀 ② 결점 공 유 를 허용 하 는 표 는 재 입 표 라 고 한다.  【 예 】 위의 그림 (d), 하위 표 A 는 공유 노드 로 C 의 요소 이자 하위 표 B 의 요소 입 니 다.③ 재 귀 를 허용 하 는 시 계 를 재 귀 표 라 고 한다.  [예] 위의 그림 (e), 표 D 는 자신의 서브 시계 이다.
(5) 재 귀 표, 재인 표, 순 표, 선형 표 간 의 관계 만족:          　  광의 표 는 선형 표 의 보급 일 뿐만 아니 라 나무의 보급 이기 도 하 다.3. 광의 표 연산    광의 표 는 선형 표 와 나무 에 대한 홍보 이 고 공유 와 재 귀 특성 을 가 진 광의 표 는 방향 도 (제7 장 참조) 와 대응 할 수 있 기 때문에 광의 표 의 대부분 연산 은 이러한 데이터 구조 상의 연산 과 유사 하 다.    여기 서 광의 표 의 두 가지 특수 한 기본 연산 만 논의 합 니 다.    표 두, 표 꼬리 의 정의 에 따라 알 수 있 듯 이 모든 비 공 광의 표 의 표 두 는 표 의 첫 번 째 요소 이 고 원자 일 수도 있 으 며 서브 표 일 수도 있 으 며 그 표 꼬리 는 반드시 서브 표 일 것 이다.  【 예 】      head(L)=a， tail(L)=(b)       head(B)=A， tail(B)=(y)   tail (L) 이 비어 있 지 않 기 때문에 계속 분해 할 수 있 습 니 다.      head(tail(L))=b， tail(tail(L))=()   비 공 표 A 와 (y) 에 대해 서도 계속 분해 할 수 있 습 니 다.  주의:    광의 표 (光 義 表) 와 () 는 다르다.전 자 는 길이 가 0 인 빈 표 로 표 머리 와 표 꼬리 의 연산 을 할 수 없다.한편, 후 자 는 길이 가 l 인 비 공 표 (이 표 의 유일한 요 소 는 빈 표 일 뿐) 로 이 를 분해 할 수 있 고 얻 은 표 머리 와 표 끝 은 모두 빈 표 () 이다.
코드 조작:

#include 
#include 
#include 
typedef char elemType; 

/************************************************************************/
/*                                 4                    */
/************************************************************************/ 
struct GNode{
    int tag;        /*    ： 0       ； 1        */
    union{
        elemType data;
        struct GNode *subList;
    };
    struct GNode *next;        /*            */ 
};  

/* 1.        */
int lenthGList(struct GNode *gl)
{
    if(gl != NULL){
        return 1 + lenthGList(gl->next);    
    }else{
        return 0;
    }    
} 

/* 2.        */
int depthGList(struct GNode *gl)
{
    int max = 0;
    /*       ，            */
    while(gl != NULL){
        if(gl->tag == 1){
            /*             */
            int dep = depthGList(gl->subList);
            /*  max                  */
            if(dep > max){
                max = dep;
            }
        }
        gl = gl->next;     /*  gl        */
    }
    return max + 1;        /*        */
}

/* 3.           */
int creatGList(struct GNode* *gl)//    ，            
{
    char ch;/*       ，      '＃'，'（'，'）'，','       */
    scanf("%c", &ch);
    /*     ＃，         */
    if(ch == '#'){
        *gl = NULL;
    }
    /*           *gl                */
    else if(ch == '('){
        *gl = malloc(sizeof(struct GNode));
        (*gl)->tag = 1;
        creatGList(&((*gl)->subList));
    }
    /*           *gl          */
    else{
        *gl = malloc(sizeof(struct GNode));
        (*gl)->tag = 0;
        (*gl)->data = ch;
    }
    /*                    */
    scanf("%c", &ch);
    /*  *gl  ，       */
    if(*gl == NULL){
        ;
    }
	else if( ch== '
')
	{
		printf("      
");
		(*gl)->next = NULL;
		return 0;
	}
    /*                */
    else if(ch == ','){
        creatGList(&((*gl)->next));
    }
    /*             *gl         */
    else if((ch == ')') || (ch == ';')){
        (*gl)->next = NULL;
    } 
    return 0;
}

/* 4.      */
int printGList(struct GNode *gl)
{
    /*          */
    if(gl->tag == 1){
        /*     ，       */
        printf("(");
        /*      ，   '#'   */
        if(gl->subList == NULL){
            printf("#");
        }
        /*      ，        */
        else{
            printGList(gl->subList);
        }
        /*           ，       */
        printf(")");
    }
    /*       ，         */
    else{
        printf("%c", gl->data);
    }
    /*           */
    if(gl->next != NULL){
        /*         */
        printf(", ");
        /*          */
        printGList(gl->next);
    }
    return 0;
}

int main()
{
    struct GNode *gl;
    printf("       ，        ");
    creatGList(&gl);
    printf("     ：");
    printGList(gl);
    printf("
");
    printf("      ：");
    printf("%d ", lenthGList(gl->subList));
    printf("      ：");
    printf("%d ", depthGList(gl->subList));
    system("pause");
    return 0;    
}