关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
(c语言)浙大数据结构Mooc作者答案集

---

---

---

原题题目

---

---

---

闲谈

通过这次散列表 以及之前看到一篇博客说的
觉得很有道理
有思路 和 做出来 是两码事
做出来 和 几乎没怎么调bug的做出来 是两码事
确实是这样的
而且也发现自己有比较多的问题吧
比如忘记了字符串在最后会多一个\0
还有 经常会忘记 取地址符！scanf的时候
这些都是习惯 和 思路 希望自己之后做代码的时候能够更认真一点吧

---

---

---

思路

详细思路可以参照 陈越姥姥视频的讲解
电话聊天狂人 陈越姥姥讲解
感觉其实就是熟悉哈希表的基本操作 其他也就没什么了。
我认为注意的点只有你上机 自己去对你的函数进行调试
你才会知道你哪些部分 思路或者代码 你习惯性认为是怎么样的
所以下面就直接给出代码
对于部分地方给出注释

---

---

---

代码实现

#include <stdio.h>
#include <stdlib.h>//包含atoi malloc函数
#include <math.h>//包含sqrt函数
#include <string.h>
#define MAXD 1000000
//麻了 我忘了字符串最后会加一个\0 导致超出空间 注意！需要+1
#define MAXNUMBER 12

//链表基本结构
typedef struct list
{
    int count;
    char telenumber[MAXNUMBER];
    struct list *Next;
} *LNode;

//哈希表
typedef struct Map
{
    int size;
    LNode Head;
} *HashMap;

//创建新质数
int NewPrime(int numbers)
{
    int i,j,temp;
    for(i=numbers+1;i<MAXD;i+=2)
    {
        temp = sqrt(i);
        for(j=2;j<=temp;j++)
            if(i%j == 0)
                break;
        if(j == temp + 1)
            return i;
    }
}

//返回值
int Hash(char *key,int p)
{
    return (atoi(key+MAXNUMBER-5) % p);
}

//在哈希表中找位置
LNode Find(HashMap H,char* str)
{
    int pos = Hash(str,H->size);
    LNode position = H->Head[pos].Next;
    while(position)
    {
        if(!strcmp(str,position->telenumber))
            break;
        else
            position = position->Next;
    }
    return position;
}

//插入函数
void Insert(char* str,HashMap H)
{
    int pos;
    LNode position;
    position = Find(H,str);
    if(!position)
    {
        position = (LNode)malloc(sizeof(struct list));
        pos = Hash(str,H->size);
        strcpy(position->telenumber,str);
        if(position->telenumber)
        {
            position->count = 1;
            position->Next = H->Head[pos].Next;
            H->Head[pos].Next = position; 
        }
    }
    else
        position->count++;
    return;
}

//创造哈希表
HashMap CreateHashMap(int numbers)
{
    int i;
    HashMap H;
    char str[MAXNUMBER];
    H = (HashMap)malloc(sizeof(struct Map));
    H->size = NewPrime(2*numbers);
    H->Head = (LNode)malloc(H->size *sizeof(struct list));
    for(i=0;i<H->size;i++)
    {
        H->Head[i].Next = NULL;
        H->Head[i].count = 0;
        H->Head[i].telenumber[0] ='\0'; 
    }
    for(i=0;i<2*numbers;i++)
    {
        scanf("%s",&str);
        Insert(str,H);
    }
    return H;
}

//输出函数
void Print(HashMap H)
{
    LNode position;
    int i,maxcount = 0,friends = 0;
    char minnumber[MAXNUMBER];
    for(i=0;i < H->size;i++)
    {
        position = H->Head[i].Next;
        while(position)
        {
            if(position->count > maxcount)
            {
                maxcount = position->count;
                strcpy(minnumber,position->telenumber);
                friends = 1;
            }
            else if(position->count == maxcount)
            {
                friends++;
                if(strcmp(position->telenumber,minnumber)<0)
                    strcpy(minnumber,position->telenumber);
            }
            position = position->Next;
        }
    }
    printf("%s %d",minnumber,maxcount);
    if(friends>1)
    printf(" %d",friends);
    return;
}

//主函数
int main()
{
    HashMap H;
    int numbers,test;
    char str[MAXNUMBER];
    scanf("%d",&numbers);
    H = CreateHashMap(numbers);
    Print(H);
    return 0;
}

---

---

---

结束语

感觉也没什么想讲的
多学多做吧