数据结构 | 每日一练（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);

}//结束算法