首页 > 试题广场 >

如果现在要找出所有无效用户,那么针对上述的数据结构,写出代码

[问答题]
在一个交友网站上,一个用户可能将其他用户加为好友,同时也可能被别人加为好友,同时也可能两个用户互为好友。如何来设计一个数据结构来描述这种关系。如果现在要找出所有无效用户(即自己没有任何好友,也不是任何人的好友),那么针对上述的数据结构,写出代码,要求尽可能地节省数据存储空间和内存空间。
1.。感觉这是一个有向图结构,因为可能很稀疏,所以可以采用邻接表存储结构存储。。。。最后找出度为0的节点就是


发表于 2015-06-16 21:53:35 回复(1)
最好的方法应该就是并查集,这是一种特殊的树,方便查找,有兴趣可以去百度~
发表于 2015-06-15 23:06:57 回复(0)
class UserInfo {
public:
    struct UserInfoLinkNode {
        UserInfoLinkNode(UserInfo * ui){
            info = ui;
            next = NULL;
        }
        UserInfo * info;
        struct UserInfoLinkNode * next;
    };
    UserInfo(int id){
        FriendListHead = NULL;
        FriendListTail = NULL;
        FriendCount = 0;
        FriendCount1 = 0;
        Id = id;
    }
    
    void AddFriend(UserInfo * ui) {
        if ( NULL==ui ) {
            return ;
        }
        if ( NULL==FriendListHead ) {
            FriendListHead = FriendListTail = new UserInfoLinkNode(ui);
        }
        else {
            FriendListTail->next = new UserInfoLinkNode(ui);
            FriendListTail = FriendListTail->next;
        }
        ++FriendCount;
        ui->FriendCount1++;
    }
    
    void DelFriend(UserInfo * ui) {
        if ( NULL==ui || NULL==FriendListHead ) {
            return ;
        }
        struct UserInfoLinkNode * p = FriendListHead;
        struct UserInfoLinkNode * p1 = p;
        while( NULL!=p ) {
            if ( ui==p->info ) {
                ui->FriendCount1--;
                --FriendCount;
                if ( p1==p ) {
                    if ( FriendListHead==FriendListTail ) {
                        FriendListHead = FriendListTail = NULL;
                    }
                    else {
                        FriendListHead = FriendListHead->next;
                    }
                }
                else {
                    if ( p==FriendListTail ) {
                        FriendListTail = p1;
                        FriendListTail->next = NULL;
                    }
                    else {
                        p1->next = p->next;
                    }
                }
                delete p;
                break;
            }
            p1 = p;
            p = p->next;
        }
    }
    
    bool IsFriend(int id) {
        struct UserInfoLinkNode * p = FriendListHead;
        while( NULL!=p ) {
            if ( id==p->info->Id ) {
                return true;
            }
            p = p->next;
        }
        return false;
    }
    
    int Id;
    struct UserInfoLinkNode * FriendListHead;
    struct UserInfoLinkNode * FriendListTail;
    int FriendCount;
    int FriendCount1;
};

发表于 2015-06-18 18:02:55 回复(0)
public class User{
    private int id;
    List<User> yourfriends = new LinkedList<User>();//自己加的好友
    List<User> user = new LinkedList<User>();//被哪些用户加过
    //生成相应的set和get方法
}
发表于 2015-06-15 22:55:31 回复(0)
思路:使用并查集
描述:
1、对n个用户编号从0-n-1,开始单个人为一个集合
2、读入一个关系编号为p1,p2的人有此关系则把它们两个集合合并
3、重复第二步直到读入所有的关系
4、最后得到多个集合,若某集合只有一个元素(即一个人)则表明他是无效用户
发表于 2015-06-15 21:16:11 回复(0)