데이터 구조 실험의 검색 3: 나무의 종류 통계 - (트 리 방법 과 map 방법 찾기)

3634 단어 데이터 구조
위성 이미 징 기술 의 응용 에 따라 자연 자원 연구 기 구 는 모든 나무의 종 류 를 식별 할 수 있다.연구원 들 이 모든 나무의 수 를 통계 하고 모든 나무 가 전체 에서 차지 하 는 비율 을 계산 하 는 데 도움 을 주 십시오.
Input
테스트 데 이 터 를 입력 하 십시오.데이터 의 첫 번 째 줄 은 정수 N (n < = 100000) 을 제시 하고 N 은 나무의 수량 을 표시 합 니 다.이 어 N 줄 은 위성 이 관측 하 는 나무의 종류 이름 을 줄 마다 제시 했다. 나무의 이름 은 20 자 를 넘 지 않 는 문자열 이 고 문자열 은 영문 자모 와 빈 칸 으로 이 루어 져 대소 문 자 를 구분 하지 않 는 다.
Output
사전 순서에 따라 각종 나무의 종류 이름과 그 가 차지 하 는 백분율 을 출력 합 니 다. 중간 에 빈 칸 으로 간격 을 두 고 소수점 뒤에 두 개의 작은 수 를 유지 합 니 다.
Example Input
2
This is an Appletree
this is an appletree
Example Output
this is an appletree 100.00%
이 문 제 를 보 는 첫 번 째 아 이 디 어 는 맵 배열 을 이용 하여 일일이 비 추 는 것 입 니 다. 누가 stl 함 수 를 사용 하 는 지 테스트 할 수 없 기 때문에 먼저 정상 적 인 방법 인 가중 두 갈래 로 나 무 를 찾 는 방법 을 사용 합 니 다.
원리: 사전 순서에 따라 이 진 트 리 를 출력 하기 때문에 문자열 을 기반 으로 한 트 리 입 니 다.
삽입 규칙 은 삽 입 된 노드 의 문자열 이 문자열 비교 함수 strcmp () 에서 루트 값 root - > name 과 비교 하고 작은 것 은 루트 의 왼쪽 아이 에 게, 큰 것 은 오른쪽 아이 에 게, 루트 값 과 같 으 면 루트 값 의 가중치 + 입 니 다.
코드 는 다음 과 같 습 니 다:
#include
#include
#include
#include
#include
using namespace std;
struct node
{
    char name[25]; //mingzi
    int num;//quanzhi
    struct node *lchild, *rchild;
};
struct node *creat(struct node *root,char s[])
{
    if(!root)
    {
        root = new node;//      ,         ,   CE
        strcpy(root->name,s);
        root->num=1;
        root->lchild =root->rchild =NULL;
    }
    else
    {
        if(strcmp(root->name,s)==0)
        {
            root->num++;
        }
        else  if(strcmp(root->name,s)>0)
        {
            root->lchild = creat(root->lchild, s);
        }
        else if(strcmp(root->name,s)<0)
        {
            root->rchild = creat(root->rchild, s);
        }
    }
    return root;
};
void  midprint(struct node *root, int n) //         - -         
{
    if(root){
    midprint(root->lchild, n);
    printf("%s %.2lf%%
",root->name, 100*(double)root->num/n); midprint(root->rchild, n); } } int main() { char s[25]; int n; cin>>n; getchar(); struct node *root; root = NULL; for(int j=0; j='A' && s[i]<='Z') s[i]=s[i]-'A'+'a'; } root = creat(root,s); } //lchild-root---rchild midprint(root, n); }
2:
map 함수 맵 을 이용 하여 문자열 과 숫자의 일 일 대응 을 실현 하고 mp [1] = str1  mp [2] = str 2... 새로운 꼬치 strn 이 오 면  mp [1] - mp [k] (모두 k 개) 를 일치 시 킵 니 다. 이 문자열 이 포함 되 어 있 으 면 통 배열 함수 num [x] + (when - > map [x] = strn),  그렇지 않 으 면 mp [k + 1] = strn
이렇게 완성 한 후, 거품 정렬 을 이용 하여 mp [i] 배열 을 작은 것 부터 큰 것 까지 정렬 합 니 다 (num 배열 도 변화 에 따라 야 합 니 다)
그리고 출력 하면 됩 니 다. 코드 는 다음 과 같 습 니 다.
#include
#include
#include
#include 
#include
using namespace std;
mapmp;
int a[100100];
char s[100];
void become(int n)
{
    for(int i=0;i='A' && s[i]<='Z')
        {
            s[i]=s[i]-'A'+'a';
        }
    }
}
int main ()
{
    int n;
    scanf("%d",&n);
    getchar();
    memset(a,0,sizeof(a));
    int px=0;
    for(int i=0;i

좋은 웹페이지 즐겨찾기