[정상] 광의 표 의 기본 조작 실현
광의 표 의 상기 네 가지 특징 은 그의 사용 가치 와 응용 효과 에 큰 역할 을 했다.광의적 표 의 구 조 는 상당히 유연 하여 선형 표, 배열, 나무 와 방향 도 등 각종 자주 사용 하 는 데이터 구 조 를 호 환 할 수 있다.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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.