[정상] 광의 표 의 기본 조작 실현

광의 표 의 네 가지 특징: (1) 광의 선형 표;(2) 원소 복합 성;(3) 원소 귀속 성;(4) 요소 공유 성
    광의 표 의 상기 네 가지 특징 은 그의 사용 가치 와 응용 효과 에 큰 역할 을 했다.광의적 표 의 구 조 는 상당히 유연 하여 선형 표, 배열, 나무 와 방향 도 등 각종 자주 사용 하 는 데이터 구 조 를 호 환 할 수 있다.2 차원 배열 의 줄 이나 열 을 하위 표 로 처리 할 때 2 차원 배열 은 광의 표 이다.광의 표 에서 요소 의 공유 와 재 귀 를 제한 하면 광의 표 와 나무 가 대응 합 니 다.광의 표 의 재 귀 를 제한 하고 데이터 공 유 를 허용 하면 광의 표 와 그림 이 대응 된다.
   광의적 표 의 기본 동작 은 다음 과 같다. (1) 광의적 표 만 들 기 (나 는 머리 꼬리 링크 를 저장 구조 로 한다).(2) 시계 머리 를 취한 다.(3) 표 의 끝 을 취한 다.(4) 광의 표 의 깊이 를 구한다.(5) 광의 표 의 길 이 를 구하 고 (5) 광의 표 원자 개 수 를 구한다.
(6) 광의 표 등 을 복제한다.
  현재 전체 코드 를 여기에 붙 여서 나중에 복습 하기 편리 하 다.(코드 에 약간의 오류 가 있 을 수 있 습 니 다. 보시 면 지적 해 주 십시오. 감사합니다!)
(1), 저장 구조 와 함수 정의 (함수 정의. h)
#include<iostream>
#include<stdio.h>
using namespace std;
#define MaxLength 60
typedef struct{
char str[MaxLength];
int length;
}SString;
typedef char AtomType;
typedef enum{ ATOM, LIST } ElemTag;//ATOM=0,    ,LIST=1,    
typedef struct Node
{
ElemTag tag;                //   tag             
union
{
AtomType atom;      //AtomType        ,        
struct
{
struct Node *hp, *tp;        //hp    ,tp    
}ptr;
};
}*GList, GLNode;
//     
void StrAssign(SString *S, char cstr[]);    //     
int StrEmpty(SString S);                    //     
void StrCopy(SString *T, SString S);        //     
void StrClear(SString *S);                  //     
int StrLength(SString S);                   //     
int StrCompare(SString S, SString T);       //     
int StrInsert(SString *S, int pos, SString T);//     
int StrDelete(SString *S, int pos, int len);  //     
int StrCat(SString *T, SString S);            //     
int StrIndex(SString S, int pos, SString T);  //     
int StrReplace(SString *S, SString T, SString V);//     
void StrPrint(SString S);                        //     
int SubString(SString *Sub, SString S, int pos, int len);  //     
//       
void Error(char *s);                    //      
void CreateList(GList *L, SString S);   //        
void Init_GList(GList &GL);             //        
void CopyList(GList *T, GList L);       //       
int GListLength(GList L);               //        
int GListDepth(GList L);			    //        
int CountAtom(GList L);                 //              
void PrintGList(GList L);               //         
void GetHead(GList L);               //        
void GetTail(GList L);                //        
void DistributeString(SString *Str, SString *HeadStr);
//      str      :HSTR      ‘,’,     ,SRE      
(2). 함수 실현 (함수 실현. cpp)
#include "stdafx.h"
#include<iostream>
#include<string>
#include<stdio.h>
#include"      .h"
//       
//       
void StrAssign(SString *S, char str[])
{
	int i;
	for (i = 0; str[i] != '\0'; i++)
		S->str[i] = str[i];   //   cstr        S  
	S->length = i;
}
//       ,     1,    0  
int StrEmpty(SString S)
{
	if (S.length == 0)
		return 1;
	else
		return 0;
}
//         
int StrLength(SString S)
{
	return S.length;
}
//        
void StrCopy(SString *T, SString S){
	int i;
	for (i = 0; i<S.length; i++)  //  S       T  
		T->str[i] = S.str[i];
	T->length = S.length;       //  S       T  
}

int StrCompare(SString S, SString T)
{   //        
	int i;
	for (i = 0; i<S.length&&i<T.length; i++)//           
	{
		if (S.str[i] != T.str[i])        //        ,            
			return (S.str[i] - T.str[i]);
	}
	return (S.length - T.length); //      ,             
}

int StrInsert(SString *S, int pos, SString T)
{//      。 S  pos     T        
	int i;
	if (pos<0 || pos - 1>S->length){    //       ,  0  
		Error("       ");
		return 0;
	}
	if (S->length + T.length <= MaxLength){    //     ,       ≤MaxLength,   T       S   
		for (i = S->length + T.length - 1; i >= pos + T.length - 1; i--) //     T , S pos        len     
			S->str[i] = S->str[i - T.length];
		for (i = 0; i<T.length; i++)  //     S   
			S->str[pos + i - 1] = T.str[i];
		S->length = S->length + T.length;
		return 1;
	}
	else if (pos + T.length <= MaxLength){   //     ,         S ,  S           
		for (i = MaxLength - 1; i>T.length + pos - i; i--)      // S pos                 
			S->str[i] = S->str[i - T.length];
		for (i = 0; i<T.length; i++)      // T   S   
			S->str[i + pos - 1] = T.str[i];
		S->length = MaxLength;
		return 0;
	}
	else{      //     ,  T        S ,T           
		for (i = 0; i<MaxLength - pos; i++) // T     S ,         S      
			S->str[i + pos - 1] = T.str[i];
		S->length = MaxLength;
		return 0;
	}
}
int StrDelete(SString *S, int pos, int len)
{//  S   pos   len     
	int i;
	if (pos<0 || len<0 || pos + len - 1>S->length){
		Error("       ,  len   ");
		return 0;
	}
	else{
		for (i = pos + len; i <= S->length - 1; i++)
			S->str[i - len] = S->str[i];
		S->length = S->length - len;
		return 1;
	}
}
//        
int StrCat(SString *T, SString S)
{
	int i, flag;
	if (T->length + S.length <= MaxLength){
		for (i = T->length; i<T->length + S.length; i++)
			T->str[i] = S.str[i - T->length];
		T->length = T->length + S.length;
		flag = 1;
	}
	else if (T->length<MaxLength){
		for (i = T->length; i<MaxLength; i++)
			T->str[i] = S.str[i - T->length];
		T->length = MaxLength;
		flag = 0;
	}
	return flag;
}
//        
int SubString(SString *Sub, SString S, int pos, int len)
{
	int i;
	if (pos<0 || len<0 || pos + len - 1>S.length)
	{
		Error("  pos len   ");
		return 0;
	}
	else
	{
		for (i = 0; i<len; i++)
			Sub->str[i] = S.str[i + pos - 1];
		Sub->length = len;
		return 1;
	}
}
//        
int StrIndex(SString S, int pos, SString T)  //BF    
{
	int i, j;
	if (StrEmpty(T))
		return 0;
	i = pos;
	j = 0;
	while (i<S.length&&j<T.length){
		if (S.str[i] == T.str[j]){
			i++;
			j++;
		}
		else{
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= T.length)
		return i - j + 1;
	else
		return 0;
}
//        
int StrReplace(SString *S, SString T, SString V)
{
	// S    T   V  
	int i;
	int flag;
	if (StrEmpty(T))
		return 0;
	i = 0;
	do{
		i = StrIndex(*S, i, T);//  T S      
		if (i){
			StrDelete(S, i, StrLength(T));    //     T  
			flag = StrInsert(S, i, V);       // i    V  
			if (!flag)
				return 0;
			i += StrLength(V);
		}
	} while (i);
	return 1;
}
//        
void StrClear(SString *S){
	S->length = 0;
}
//      
void StrPrint(SString S){
	int i;
	for (i = 0; i<S.length; i++){
		cout << S.str[i];
	}
	cout << endl;
}

//         
void Error(char *s)                       //      
{
	cout << s << endl;
	exit(1);
}

void  GetHead(GList L)
//           
{
	if (L == NULL)   Error("       !");
	GLNode *Head = L->ptr.hp;
	if (Head->tag == ATOM)
		cout << "  :" << Head->atom << endl;
	else
	{
		cout << "  :";
		PrintGList(Head);
		cout << endl;
	}
}
void  GetTail(GList L)
//         
{
	if (L == NULL)   Error("       !");
	GLNode *tail = L->ptr.tp;
	cout << "  :";
	PrintGList(tail);
	cout << endl;
}
int GListLength(GList L)
//         
{
	int length = 0;
	GLNode *p = L;
	if (p == NULL)  return 0;
	else
	{
		length = GListLength(p->ptr.tp);
	}
	return length + 1;

}
int GListDepth(GList L)
//         
{
	int max, depth;
	GLNode *p;
	if (!L)                          //       ,   1
		return 1;
	if (L->tag == ATOM)                 //        ,   0
		return 0;
	for (max = 0, p = L; p; p = p->ptr.tp)         //       
	{
		depth = GListDepth(p->ptr.hp);
		if (max<depth)
			max = depth;
	}
	return (max + 1);
}
int CountAtom(GList L)//            ,   
{
	int n1, n2;
	if (L == NULL) return 0;
	if (L->tag == ATOM) return 1;
	n1 = CountAtom(L->ptr.hp);           //         
	n2 = CountAtom(L->ptr.tp);           //         
	return (n1 + n2);
}
void CopyList(GList *T, GList L)
//        。    L       T
{
	if (!L)                          //       , T   
		*T = NULL;
	else
	{
		*T = (GList)malloc(sizeof(GLNode));   // L  , T       
		if (*T == NULL)
			Error("      !");
		(*T)->tag = L->tag;
		if (L->tag == ATOM)            //    
			(*T)->atom = L->atom;
		else                        //      
		{
			CopyList(&((*T)->ptr.hp), L->ptr.hp);
			CopyList(&((*T)->ptr.tp), L->ptr.tp);
		}
	}
}
void DistributeString(SString *Str, SString *HeadStr)
//  Str       ,HeadStr           ,Str       
{
	int len, i, k;
	SString Ch, Ch1, Ch2, Ch3;
	len = StrLength(*Str);                //len Str   
	StrAssign(&Ch1, ",");                //   ','、'(' ')'    Ch1,Ch2 Ch3
	StrAssign(&Ch2, "(");
	StrAssign(&Ch3, ")");
	SubString(&Ch, *Str, 1, 1);            //Ch  Str      
	for (i = 1, k = 0; i <= len&&StrCompare(Ch, Ch1) || k != 0; i++) //  Str         
	{
		SubString(&Ch, *Str, i, 1);        //  Str      
		if (!StrCompare(Ch, Ch2))         //        '(',  k 1
			k++;
		else if (!StrCompare(Ch, Ch3))    //       ')',  k  1
			k--;
	}
	if (i <= len)                           // Str   ',',   i-1   
	{
		SubString(HeadStr, *Str, 1, i - 2);  //HeadStr   Str','    
		SubString(Str, *Str, i, len - i + 1);  //Str   Str','    
	}
	else                                // Str    ','
	{
		StrCopy(HeadStr, *Str);          //  Str       HeadStr
		StrClear(Str);                  //   Str
	}
}
void CreateList(GList *L, SString S)
//           
{
	SString Sub, HeadSub, Empty;
	GList p, q;
	StrAssign(&Empty, "()");
	if (!StrCompare(S, Empty))            //                   
		*L = NULL;
	else
	{
		if (!(*L = (GList)malloc(sizeof(GLNode))))     //          
			Error("      !");
		if (StrLength(S) == 1)                         //      ,              
		{
			(*L)->tag = ATOM;
			(*L)->atom = S.str[0];
		}
		else                                        //     
		{
			(*L)->tag = LIST;
			p = *L;
			SubString(&Sub, S, 2, StrLength(S) - 2);     // S        ,     Sub
			do
			{
				DistributeString(&Sub, &HeadSub);    // Sub             HeadSub Sub
				CreateList(&(p->ptr.hp), HeadSub);    //         
				q = p;
				if (!StrEmpty(Sub))                  //      ,     p,        p
				{
					if (!(p = (GLNode *)malloc(sizeof(GLNode))))
						Error("      !");
					p->tag = LIST;
					q->ptr.tp = p;
				}
			} while (!StrEmpty(Sub));
			q->ptr.tp = NULL;
		}
	}
}
void PrintGList(GList L)
//        
{
	if (!L)  cout << "()";
	else
	{
		if (L->tag == ATOM)
			cout << L->atom;
		else
		{
			cout << '(';
			GLNode *p = L;
			while (p)
			{
				PrintGList(p->ptr.hp);
				p = p->ptr.tp;
				if (p)  cout << ',';
			}
			cout << ')';
		}
	}
}
(3) 주 함수 테스트 (주 함수 테스트. cpp)
#include "stdafx.h"
#include<iostream>
#include<stdio.h>
#include"      .h"

int _tmain(int argc, _TCHAR* argv[])
{
	GList L, T;
	SString S;
	char str[60];
	int depth, length;
	cout << "      :" << endl;
	cin >> str;
	StrAssign(&S, str);                //        S
	CreateList(&L, S);                  //       L
	cout << "     L    :" << endl;
	PrintGList(L);                     //         
	cout << endl;
	cout << "   L   :" << endl;
	GetHead(L);
	cout << "   L   :" << endl;
	GetTail(L);
	cout << "   L       :" << CountAtom(L) << endl;
	length = GListLength(L);          //       
	cout << "   L   :" << length << endl;
	depth = GListDepth(L);            //       
	cout << "   L   :" << depth << endl;
	CopyList(&T, L);
	cout << "    L       T   T    :" << endl;
	PrintGList(T);
	return 0;
}

좋은 웹페이지 즐겨찾기