C++어떻게 광의 표 의 상세 한 설명 을 실현 합 니까?

다음은 몇 가지 간단 한 광의 표 모델 을 제시 합 니 다.

 
위의 그림 에서 볼 수 있 듯 이 광의 표 의 노드 유형 은 모두head,value,sub세 가지 가 있다.여기 서 매 거 진 유형 을 설정 하고 매 거 진 변 수 를 이용 하여 각 노드 의 유형 을 기록한다.

enum Type
{
  HEAD,  //   
  VALUE, //   
  SUB,  //    
};

모든 노드 는 자신의 유형 과next지침 이 있 습 니 다.그 밖 에 이 노드 가VALUE유형 이 라면 공간 을 분배 하여 이 노드 의 유효 치 를 저장 해 야 합 니 다.그러나 이 노드 가 SUB 형식 이 라면 포인터 가 서브 시트 의 머리 를 가리 키 는 것 을 정의 해 야 합 니 다.
이곳 에서 우 리 는 연합 으로 이 문 제 를 해결 할 수 있다.
(연합(또는 공동체)은 서로 다른 데이터 형식 구성원 간 에 저장 공간 을 공유 하 는 방법 이 고 연합 체 대상 은 같은 시간 에 한 구성원 만 저장 할 수 있다)
구조 노드:

struct GeneralizedNode
{
  Type _type;    // 1.  
  GeneralizedNode* _next; //2.          
  union
  {
    char _value;  // 3.   
    GeneralizedNode* _subLink;   // 3.       
  };
   
  GeneralizedNode(Type type = HEAD, char value = '0')
  :_value(value)
  ,_type(type)
  , _next(NULL)
  {
    if (_type == SUB)
    {
      _subLink = NULL;
    }
  }
};

광의 표 의 정의 및 기본 동작:

class Generalized
{
public:
  //       ,       
  Generalized();
  //     ，        
  Generalized(const char* str);
  //     
  void Print();
  //        
  size_t Amount();
  //        
  size_t Depth();
  //    
  Generalized(const Generalized& g);
  ////        
  Generalized& operator=(const Generalized& g);
  ////    
  ~Generalized();
 
protected:
  void _Print(GeneralizedNode* head);
  GeneralizedNode* _CreatList(const char*& str);
  size_t _Amount(GeneralizedNode* head);
  GeneralizedNode* _Copy(GeneralizedNode* head);
  void _Destory(GeneralizedNode* head);
protected:
  GeneralizedNode* _head;  //        
};

광의 표를 만 들 고 순환 재 귀 를 초기 화 합 니 다.문자열 을 옮 겨 다 닐 때 문 자 를 만나면 값 노드 를 만 들 고'('를 만나면 재 귀적 으로 하위 표를 만 듭 니 다.')'를 만나면 현재 하위 표 의 생 성 을 끝내 고 현재 하위 표 의 머리 지침 을 되 돌려 줍 니 다.　

GeneralizedNode* _CreatList(const char*& str)
{
  assert(*str == '(');
  GeneralizedNode* head = new GeneralizedNode(HEAD,'0');
  GeneralizedNode* cur = head;
  str++;
  while (str != '\0')
  {
    if ((*str >= '0'&&*str <= '9') || (*str >= 'a'&&*str <= 'z') || (*str >= 'A'&&*str <= 'Z'))
    {
      cur->_next = new GeneralizedNode(VALUE, *str);
      cur = cur->_next;
    }
    else if (*str == '(')
    {
      cur->_next = new GeneralizedNode(SUB);
      cur = cur->_next;
      cur->_subLink = _CreatList(str);
    }
    else if (*str == ')')
    {
      return head;
    }
    str++;
  }
  return head;
}

인쇄 광의 표:노드 의 유형 이 SUB 일 때 재 귀 합 니 다.마지막 으로 인쇄 가 끝 날 때마다 괄호 를 인쇄 하 는 것 을 잊 지 마 세 요.

void _Print(GeneralizedNode* head)
{
  if (head == NULL)
  {
    cout << "Generalized table is NULL" << endl;
    return;
  }
  GeneralizedNode* cur = head;
  while (cur)
  {
    if (cur->_type == HEAD)
    {
      cout << '(';
    }
    else if (cur->_type == VALUE)
    {
      cout << cur->_value;
      if (cur->_next)
      {
        cout << ',';
      }
    }
    else if (cur->_type == SUB)
    {
      _Print(cur->_subLink);
      if (cur->_next)
      {
        cout << ',';
      }       
    }
    cur = cur->_next;
  }
  cout << ')';
}

값 노드 의 개수 가 져 오기:count변 수 를 설정 하고 값 노드 를 만나면 1 을 추가 합 니 다.SUB 노드 를 만나면 재 귀 하고 반환 값 을 추가 합 니 다count

size_t _Amount(GeneralizedNode* head)
{
  GeneralizedNode* begin = head;
  size_t count = 0;
  while (begin)
  {
    if (begin->_type == VALUE)
    {
      count++;
    }
    if (begin->_type == SUB)
    {
      count += _Amount(begin->_subLink);
    }
    begin = begin->_next;
  }
  return count;
}

일반화 표 의 깊이:변수 dp 와 max 를 설정 하여 현재 서브 시트,즉 현재 SUB 노드 가 가리 키 는 서브 시트 의 깊이 와 이 층 의 모든 SUB 노드 에서 깊이 가 가장 큰 서브 시트 의 깊이 를 기록 합 니 다.

size_t _Depth(GeneralizedNode* head)
{
  if (_head == NULL)
  {
    return 0;
  }
  size_t dp=0;
  GeneralizedNode* cur = head;
  size_t max = 0;
  while (cur)
  {
    if (cur->_type == SUB)
    {
      dp=_Depth(cur->_subLink);
      if (max < dp)
      {
        max = dp;
      }
    }
    cur = cur->_next;
  }
  return max+1;
}

광의 표 삭제:노드 를 순서대로 옮 겨 다 니 며 하위 표 재 귀 를 만 나 하위 표 의 노드 delete 를 완성 한 후 현재 층 으로 돌아 가 계속 옮 겨 다 닙 니 다.

void _Destory(GeneralizedNode* head)
{
  if (head == NULL)
  {
    return;
  }
  while (head)
  {
    GeneralizedNode* begin = head->_next;
    if (head->_type == SUB)
    {
      _Destory(head->_subLink);
    }
    delete head;
    head = begin;
  }
}

실례 시범
정의:
광의 표 는 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 의 표 미 라 고 부른다.
④ 광의 표 는 재 귀 정의 이다.
그림 예:

코드 구현:

[cpp] view plain copy
#include <iostream> 
 
using namespace std; 
 
//           
enum NodeType 
{ 
  HEAD_TYPE,//      
  VALUE_TYPE,//      
  SUB_TYPE//     
}; 
 
//            
struct GeneraListNode 
{ 
  NodeType _type;//     
  GeneraListNode *_next;//              
 
  //               ，                
  //           ，                      
  union{ 
    char _value; 
    GeneraListNode *_subLink; 
  }; 
 
  GeneraListNode(NodeType type = HEAD_TYPE, char value = '\0') 
    :_type(type) 
    ,_next(NULL) 
  { 
    if (type == VALUE_TYPE) 
    { 
      _value = value; 
    }else if(type == SUB_TYPE) 
    { 
      _subLink = NULL; 
    } 
 
  } 
 
}; 
 
class GeneraList 
{ 
private: 
  GeneraListNode *_link;//             
public: 
  GeneraList(const char *str) 
    :_link(NULL) 
  { 
    _CreateGeneraList(_link, str);//            
  } 
 
  ~GeneraList() 
  {} 
public: 
  void Print();//              
  int Size();//                  
  int Depth();//                
private: 
  void _CreateGeneraList(GeneraListNode *& link, const char *& str); 
  bool _IsValue(const char ch);//                   
  int _Size(GeneraListNode *head);//                
  int _Depth(GeneraListNode *head);//              
  void _Print(GeneraListNode *link);//              
}; 
 
//      
void GeneraList::_CreateGeneraList(GeneraListNode *& link, const char *& str) 
{ 
  //            ，                
  //                        
  GeneraListNode* head = new GeneraListNode(HEAD_TYPE, NULL); 
  head->_next = NULL; 
  link = head; 
  GeneraListNode* cur = link;//                           
  str++;//        ,      '(' 
   
  while(*str != '\0') 
  { 
    if(_IsValue(*str)){//             
      //        
      GeneraListNode* newNode = new GeneraListNode(VALUE_TYPE, *str); 
      newNode->_next = NULL; 
      cur->_next = newNode;//            
      cur = cur->_next;//     
      str++;//         
    }else if(*str == '('){//     '('       
      GeneraListNode* subLink = new GeneraListNode(SUB_TYPE, NULL); 
      subLink->_next = NULL; 
      cur->_next = subLink;//            
      cur = cur->_next; 
      _CreateGeneraList(cur->_subLink, str);//       
    }else if(*str == ')'){ 
      str++; 
      return;//    ')'          
    }else{ 
      str++;//            
    } 
  } 
} 
 
int GeneraList::Size() 
{ 
  return _Size(_link); 
} 
 
//            
int GeneraList::_Size(GeneraListNode *head) 
{ 
  int size = 0; 
  GeneraListNode *cur = head; 
  while(cur != NULL){ 
    if(cur->_type == VALUE_TYPE){ 
      ++size;//       size   
    }else if(cur->_type == SUB_TYPE){ 
      size += _Size(cur->_subLink);//         
    } 
    cur = cur->_next; 
  } 
  return size; 
} 
 
int GeneraList::Depth() 
{ 
  return _Depth(_link); 
} 
int GeneraList::_Depth(GeneraListNode *head) 
{ 
  int depth = 1,maxDepth = 1;//depth        ，maxDepth          
  GeneraListNode *cur = head; 
  while(cur != NULL){ 
    if(cur->_type == SUB_TYPE){ 
      depth += _Depth(cur->_subLink); 
    } 
    if(depth > maxDepth){//       
      maxDepth = depth; 
      depth = 1;//        
    } 
    cur = cur->_next; 
  } 
  return maxDepth; 
} 
 
void GeneraList::Print() 
{ 
  _Print(_link); 
  cout<<endl; 
} 
 
//      
void GeneraList::_Print(GeneraListNode *link) 
{ 
  GeneraListNode *cur = link;//         
  while(cur != NULL){ 
    if(cur->_type == VALUE_TYPE){ 
      cout<<cur->_value; 
      if(cur->_next != NULL) 
      { 
        cout<<','; 
      } 
    }else if(cur->_type == HEAD_TYPE){ 
      cout<<"("; 
    }else if(cur->_type == SUB_TYPE){ 
      _Print(cur->_subLink);//         
      if(cur->_next != NULL)//                 ',' 
      { 
        cout<<","; 
      } 
    } 
    cur = cur->_next; 
  } 
  cout<<")"; 
} 
 
bool GeneraList::_IsValue(const char ch) 
{ 
  if(ch >= 'a' && ch <= 'z' || 
    ch >= 'A' && ch <= 'Z' || 
    ch >= '0' && ch <= '(') 
  { 
    return true; 
  } 
  return false; 
} 

테스트 코드

[cpp] view plain copy
#include"GeneraList.hpp" 
 
//     
void Test1() 
{ 
  GeneraList genList("()"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//      
void Test2() 
{ 
  GeneraList genList("(a,b)"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//      
void Test3() 
{ 
  GeneraList genList("(a,b,(c,d))"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//      
void Test4() 
{ 
  GeneraList genList("(a,b,(c,d),(e,(f),h))"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//       
void Test5() 
{ 
  GeneraList genList("(((),()),())"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
 
int main() 
{ 
  Test1(); 
  Test2(); 
  Test3(); 
  Test4(); 
  Test5(); 
  return 0; 
} 

실행 결과

총결산
이상 은 C++광의 표 의 상세 한 설명 을 어떻게 실현 하 는 지 에 관 한 모든 내용 입 니 다.필요 한 사람 에 게 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 면 댓 글 을 달 아 토론 하 시기 바 랍 니 다.