7-49 打印学生选课清单 (25分)

 

 解题思路:(此前用哈希表存储学生选课信息,最后一个测试点超时,或者内存超限)

后在网上翻看其他大能写的文章,受益颇多

注意到学生姓名的组成是3个大写字母+1个数字,故可开辟一个四维结构体数组指针,使学生姓名映射到唯一地址,也省去了用哈希函数要解决冲突的时间消耗问题

解法一、将学生的选课清单用二叉排序树结构存储,中序遍历输出即可

#include <stdio.h>
#include <malloc.h>

typedef struct TNode {
    int CourseNo;
    struct TNode *Left,*Right;
}*Tree;

typedef struct Node {
    int num;
    struct TNode *Next;
} Node;

typedef char Element[5];

Tree BuildBiSearchTree(Tree T,int CourseNo);
void Trav(Tree T);
void Out(Node *head);

int main(int argc,char **argv) {
    int i,j,k,t;
    int n,m;
    int CourseNo,Num;
    Element Name;

    Node *List[26][26][26][10];
    for(i=0; i<26; i++) {
        for(j=0; j<26; j++) {
            for(k=0; k<26; k++) {
                for(t=0; t<10; t++) {
                    List[i][j][k][t]=NULL;
                }
            }
        }
    }
    scanf("%d %d",&n,&m);
    for(i=0; i<m; i++) {
        scanf("%d %d",&CourseNo,&Num);
        for(j=0; j<Num; j++) {
            scanf("%s",Name);
            if(List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']==NULL)
            {
                List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']=malloc(sizeof(struct Node));
                List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']->num=0;
                List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']->Next=NULL;
            }
            List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']->num++;
            List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']->Next
                =BuildBiSearchTree(List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']->Next,CourseNo);
        }
    }

    for(i=0; i<n; i++) {
        scanf("%s",Name);
        printf("%s",Name);
        if(List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']!=NULL)
        Out(List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0']);
        else
        printf(" 0");
        printf("
");
    }
}

Tree BuildBiSearchTree(Tree T,int CourseNo) {
    if(!T) {
        T=malloc(sizeof(struct TNode));
        T->CourseNo=CourseNo;
        T->Left=T->Right=NULL;
    } else if(CourseNo<T->CourseNo)
        T->Left=BuildBiSearchTree(T->Left,CourseNo);
    else
        T->Right=BuildBiSearchTree(T->Right,CourseNo);
    return T;
}
void Trav(Tree T) {
    if(T) {
        Trav(T->Left);
        printf(" %d",T->CourseNo);
        Trav(T->Right);
    }
}
void Out(Node *head) {
    printf(" %d",head->num);
    if(head->Next) {
        Tree T=head->Next;
        Trav(T);
    }

}

解法二、将学生的选课清单用单链表结构存储(插入排序)

#include <stdio.h>
#include <malloc.h>

typedef struct Node {
    int Course;
    struct Node *Next;
}Node;
typedef
char Element[5]; Node *Insert(Node *sort,int k); void Out(Node *head,int N); int main(int argc,char **argv) { int i,j,k,t; int n,m; int CourseNo,Num; Element Name; Node *List[26][26][26][10]; for(i=0; i<26; i++) { for(j=0; j<26; j++) { for(k=0; k<26; k++) { for(t=0; t<10; t++) { List[i][j][k][t]=NULL; } } } } scanf("%d %d",&n,&m); for(i=0;i<m;i++) { scanf("%d %d",&CourseNo,&Num); for(j=0;j<Num;j++) { scanf("%s",Name); List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0'] =Insert(List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0'],CourseNo); } } for(i=0;i<n;i++) { scanf("%s",Name); printf("%s",Name); Out(List[Name[0]-'A'][Name[1]-'A'][Name[2]-'A'][Name[3]-'0'],0); printf(" "); } } Node *Insert(Node *sort,int k) { if(!sort||sort->Course<k) { Node *n=malloc(sizeof(struct Node)); n->Course=k; n->Next=sort; return n; } else if(sort->Course!=k) sort->Next=Insert(sort->Next,k); return sort; } void Out(Node *head,int N) { if(head) { Out(head->Next,++N); printf(" %d",head->Course); } else printf(" %d",N); }

 

原文地址:https://www.cnblogs.com/snzhong/p/12665777.html