数据结构 | 每日一练（69）
数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1．设键盘输入 n 个英语单词，输入格式为 n, w 1 , w 2 , …,w n ,其中 n 表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：
（1）如果单词重复出现，则只在链表上保留一个。。
（2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k(k<=n)个单词）。
正确答案
ps：||代表注释
1.[题目分析] 本题链表结点的数据域存放英文单词，可用字符数组表示，单词重复出现时，链表中只保留一个，单词是否相等的判断使用strcmp函数，结点中增设计数域，统计单词重复出现的次数。
typedef struct node
{ int freg；∥频度域，记单词出现的次数。
char word[maxsize]；∥maxsize是单词中可能含有的最多字母个数。
struct node *next；
}node, *LinkedList;
(1)LinkedList creat（）
∥建立有n（n>0）个单词的单向链表，若单词重复出现，则只在链表中保留一个。
{LinkedList la；
la=（LinkedList）malloc（ sizeof（node））；∥申请头结点。
la->next=null； ∥链表初始化。
for（i=1；i<=n；i++） ∥建立n个结点的链表
{scanf（“%s”，a）； ∥a是与链表中结点数据域同等长度的字符数组。
p=la->next；pre=p; ∥p是工作指针,pre是前驱指针。
while（p!=null）
if（strcmp(p->data，a）==0) {p->freg++； break；} ∥单词重复出现,频度增1。
else {pre=p；p=p->next；} ∥指针后移。
if（p==null） ∥该单词没出现过，应插入。
{p=（LinkedList）malloc（ sizeof（node））；
strcopy（p->data，a）；p->freg=1；p->next=null；pre->next=p；
} ∥将新结点插入到链表最后。
}∥结束 for循环。
return（la）；
}∥结束creat算法。
(2) void CreatOut（ ）∥建立有n个单词的单向链表，重复单词只在链表中保留一个,最后输出频度最高的k个单词。
{LinkedList la；
la=（LinkedList）malloc（ sizeof（node））；∥申请头结点。
la->next=null； ∥链表初始化。
for（i=1；i<=n；i++） ∥建立n个结点的链表
{scanf（“%s”，a）； ∥a是与链表中结点数据域同等长度的字符数组。
p=la->next；pre=p; ∥p是工作指针,pre是前驱指针。
while（p!=null）
if（strcmp(p->data，a)==0)
{p->freg++； ∥单词重复出现,频度增1。
pre->next=p->next; ∥先将p结点从链表上摘下，再按频度域值插入到合适位置
pre=la; q=la->next;
while(q->freg>p->freg) (pre=q; q=q->next; )
pre->next=p; p->next=q; ∥将p结点插入到合适位置
}
else {pre=p；p=p->next；} ∥指针后移。
if（p==null） ∥该单词没出现过，应插入到链表最后。
{p=（LinkedList）malloc（ sizeof（node））；
strcopy（p->data，a）；p->freg=1；p->next=null；pre->next=p；
}∥ if 新结点插入。
}∥结束 for循环建表。
int k,i=0;
scanf(“输入要输出单词的个数%d”,&k);
p=la->next;
while (p && i<k) ∥输出频度最高的k个单词
{printf（“第%3d个单词%s出现%3d次\n”，++i，p->data，p->freg）；
p=p->next;
}
if (!p)
printf(“给出的%d值太大\n”,k);
}//结束算法