技术标签: 浙大版《数据结构(第2版)》题目集 散列表 c语言 数据结构
请编写程序,对一段英文文本,统计其中所有不同单词的个数,以及词频最大的前10%的单词。
所谓“单词”,是指由不超过80个单词字符组成的连续字符串,但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线,其它字符均认为是单词分隔符。
输入给出一段非空文本,最后以符号#
结尾。输入保证存在至少10个不同的单词。
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写,例如“PAT”和“pat”被认为是同一个单词。
随后按照词频递减的顺序,按照词频:单词
的格式输出词频最大的前10%的单词。若有并列,则按递增字典序输出。
This is a test.
The word "this" is the word with the highest frequency.
Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this...#
this line should be ignored.
23
5:this
4:is
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdbool.h>
#define MAXTABLESIZE 110 //允许开辟的最大散列表长度
typedef char elementType[16]; //关键词类型用字符串
typedef struct listNode *list;//单链表
struct listNode{
//链表结点定义
elementType data; //存放单词
int count; //单词个数
list next; //结点指针
};
typedef struct tableNode *hashTable;//散列表类型
struct tableNode{
//散列表结点定义
int tableSize; //表的最大长度
list heads; //指向链表头结点的数组
};
typedef struct{
//结构数组
elementType data; //存放单词
int count; //单词个数
}wordFre;
/*函数声明*/
int nextPrime(int n);//大于n的最小素数
hashTable createTable(int tableSize);//建立散列表
int hash(const char *key,int tableSize);//散列函数
list find(hashTable H,elementType key); //查找
void insert(hashTable H,elementType key);//插入
void destroyTable(hashTable H); //释放空间
bool isLower(char ch); //是否是小写字母
bool isUpper(char ch); //是否是大写字母
bool isDigit(char ch); //是否是数字
void show(hashTable H);//输出
void swap(wordFre *wf1,wordFre *wf2);//结构体数据交换
int main()
{
hashTable H;
H=createTable(100);
char ch,str[16]={
0};
int i=0,flag=0;
while((ch=getchar())!='#') //读到#结束
{
/*如果是小写字母或者数字或者下划线*/
if(isLower(ch)||isDigit(ch)||ch=='_')
{
flag=1;
if(i<15)
str[i++]=ch;
}
/*如果是大写字母转换成小写*/
else if(isUpper(ch))
{
flag=1;
if(i<15)
str[i++]=ch+32;
}
/*否则是单词分隔符*/
else
{
if(flag)
{
str[i]=0;
insert(H,str);
i=flag=0;
}
}
}
if(flag)//最后一个单词处理
{
str[i]=0;
insert(H,str);
}
show(H);
destroyTable(H);
system("pause");
return 0;
}
int nextPrime(int n)
{
int i,flag=1,p=(n%2)?n+2:n+1;
while(p<=MAXTABLESIZE)
{
for(i=2;i<=sqrt(p);i++)
{
if(p%2==0)
{
flag=0;
break;
}
}
if(flag) break;
else p+=2;
}
return p;
}
hashTable createTable(int tableSize)//建立散列表
{
hashTable H;
int i;
H=(hashTable)malloc(sizeof(struct tableNode));
H->tableSize=nextPrime(tableSize);//保证散列表最大长度是素数
H->heads=(list)malloc(H->tableSize*sizeof(struct listNode));//分配链表头结点数组
for(i=0;i<H->tableSize;i++) //初始化表头结点
{
H->heads[i].data[0]='\0';
H->heads[i].count=0;
H->heads[i].next=NULL;
}
return H;
}
int hash(const char *key,int tableSize)//散列函数
{
unsigned h=0; //散列函数值,初始化为0
while(*key!='\0')//位移映射
{
h=(h<<5)+*key;
key++;
}
return h%tableSize;
}
list find(hashTable H,elementType key)
{
list p;
int pos=hash(key,H->tableSize);//初始散列位置
p=H->heads[pos].next; //从该链表的第1个结点开始
while(p&&strcmp(p->data,key))//当未到表尾,并且key未找到时
{
p=p->next;
}
return p; //此时p或者指向找到的结点,或者为NULL
}
void insert(hashTable H,elementType key)
{
list p,newCell;
int pos;
p=find(H,key);
if(!p) //单词未找到,可以插入
{
newCell=(list)malloc(sizeof(struct listNode));
strcpy(newCell->data,key);
newCell->count=1; //第一次插入,设置单词数为1
pos=hash(key,H->tableSize);
/* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
newCell->next=H->heads[pos].next;
H->heads[pos].next=newCell;
}
else //单词已存在
{
p->count++; //单词数加1
}
}
void destroyTable(hashTable H)
{
int i;
list p,tmp;
/* 释放每个链表的结点 */
for(i=0;i<H->tableSize;i++)
{
p=H->heads[i].next;
while(p)
{
tmp=p->next;
free(p);
p=tmp;
}
}
free(H->heads); //释放头结点数组
free(H); //释放散列表结点
}
bool isLower(char ch)
{
if(ch>='a'&&ch<='z')
return true;
else
return false;
}
bool isUpper(char ch)
{
if(ch>='A'&&ch<='Z')
return true;
else
return false;
}
bool isDigit(char ch)
{
if(ch>='0'&&ch<='9')
return true;
else
return false;
}
void show(hashTable H)
{
wordFre wf[10000];//定义一个结构数组,用来存储单词和个数
/*wordCount表示单词总数,outputWordCount表示需要输出的单词个数*/
int i,j,flag,wordCount=0,outputWordCount;
// int t1;
// elementType t2;
list p;
/*遍历散列表,将单词及个数放入结构数组中,并统计单词总数*/
for(i=0;i<H->tableSize;i++)
{
p=H->heads[i].next;
while(p)
{
wf[wordCount].count=p->count;
strcpy(wf[wordCount].data,p->data);
wordCount++;
p=p->next;
}
}
outputWordCount=wordCount/10;//求出需要输出的单词个数
printf("%d\n",wordCount); //输出单词总个数
/*冒泡排序*/
for(i=0;i<wordCount-1;i++)
{
flag=0;
for(j=wordCount-1;j>i;j--) //一次冒泡
{
/*词频不同交换*/
if(wf[j-1].count<wf[j].count)
{
swap(&wf[j-1],&wf[j]);
flag=1;
}
/*词频相同,字典序不同交换*/
else if(wf[j-1].count==wf[j].count&&strcmp(wf[j-1].data,wf[j].data)>0)
{
swap(&wf[j-1],&wf[j]);
flag=1;
}
}
if(flag==0) break;//全程无交换
}
for(i=0;i<outputWordCount;i++)
{
printf("%d:%s\n",wf[i].count,wf[i].data);
}
}
void swap(wordFre *wf1,wordFre *wf2)
{
int t1;
elementType t2;
t1=wf1->count;
wf1->count=wf2->count;
wf2->count=t1;
strcpy(t2,wf1->data);
strcpy(wf1->data,wf2->data);
strcpy(wf2->data,t2);
}
文章浏览阅读1.7k次。 关于:va_list,va_start,va_arg的3篇文章(ZZ) 文章1:C语言中变长参数(va_list,va_start,va_arg)沉思录 转载自:http://blog.sina.com.cn/s/print_3e7df0e5010005il.html 一.引言: C语言中关于变长参数的使用很简单,无非是如下的框架。是否可以不用宏而编写处理变长参数的函数呢?答案是肯定的,本文作了一些处浅探讨,不足之处望各位批评指正。 使用宏的程序框架:#include
文章浏览阅读163次。传统组织如何转型敏捷组织 我一直在想我的客户已经成功地从基于项目/资源效率的组织转变为基于产品/流程效率的组织。 他们有以下共同点: 资深人士使经理们可以安全地进行实验。 他们创建了非常小的实验(经理或团队,或一起)。 高级经理经常问这样的问题: 您需要我什么,才能转到产品组织,我们在那儿优化产品流向客户的流程以及员工的满意度? 这是一个大问题。 这也是一个引人入胜的问..._组织转型
文章浏览阅读1k次,点赞6次,收藏9次。在Angular中,依赖注入被广泛应用于组件、服务、指令等场景,本文将详细解析Angular中的依赖注入。在Angular中,依赖注入是指将服务或值注入到组件、指令、管道等对象中,使得这些对象可以在运行时动态地获取和使用这些服务或值。依赖注入的原理主要是通过将对象的依赖关系显式地定义在一个容器中(通常是服务提供者),然后在对象被实例化时,由容器负责将这些依赖关系注入到对象中。依赖扫描:通过Angular的依赖注入系统,可以自动扫描组件、服务和指令中的依赖关系,并将其自动注入到相应的对象中。_angular依赖注入使用
文章浏览阅读329次。效果一HTML<div class="zh-loading"><ul><li></li><li></li><li></li><li></li></ul></div>CSSweb前端开发学习Q-q-u-n:784783012 ,分享学习的方法和需..._前端按钮添加缓冲样式
文章浏览阅读882次,点赞16次,收藏15次。大家好,本文将围绕python网站开发模板展开说明,python网站模板下载是一个很多人都想弄明白的事情,想搞清楚python制作的网站需要先了解以下几个事情。
文章浏览阅读996次。python作为一门编程语言长期受到IT,科学工作者的青睐。其众多优秀的开源库大大缩短了程序编写工作者的工作量,而且对于许多科学运算库(或包)经历长期的更新和改进,运算效率得到很大提升。对于一个初级的程序猿,如果自己去实现一些运算过程,实现后的效率肯定远不及稳定包中的实现过程。matplotlib是一个近似于Matlab绘图的开源库,具备很强的绘图功能,可能只有你想不到的图不能通过matplotl..._python坐标轴添加自定义符号
文章浏览阅读2.6k次。许多企业不是在丢弃基于VMware的现有系统,而是在慢慢向微软的Hyper-V虚拟机管理程序迁移。微软在简化管理这两个虚拟化平台的任务,因为最新版本的System Center 2012 R2虚拟机管理器(VMM)让你可以借助单一管理平台,管理VMware和Hyper-V。所以,现在你还可以使用VMM,将虚拟机从VMware平台迁移到Hyper-V平台。不过也可以等待Hyper-V v_win 7 vmware 与 hyper 冲突
文章浏览阅读699次,点赞5次,收藏13次。X-AnyLalbeing 中同样提供了丰富的快捷键,极大提升标注效率。大家可根据自己的习惯通过修改当前设备的用户根目录下的#Linux#Windows默认的快捷键设置可以参考 github 主页示意图。对于中已提供的内置模型,可参考以下操作:创建配置文件进入项目工程,查看所需的配置文件查看配置文件配置文件需要遵循以下格式,以stride: 32classes:- person- bicycle- car..._xanylabelling下载
文章浏览阅读3.4k次。在sql语句中,我们难免会用到单引号嵌套的时候,但是直接嵌套肯定是不行的,java中用反斜杠做转义符也是不行的,在sql中是用单引号来做转义符的。比如下面例子是存储过程里查询时的语句示例exec cndoup_getpageofrecords @pagesize=10,@currentpage=1,@columns='*',@tablename='ROOM',@condition='ROO_pgsql正则表达式以单引号嵌套单引号
文章浏览阅读3k次。前天老师上课布置了实验,分基础实验和拓展实验,基础实验就是按照老师的要求以及所给代码来编写,拓展实验是设计一个法国国旗,填满整个手机屏幕我写的代码是根据老师的代码稍作修改的,以上,得出结果为尽管是个渣渣但正在努力..._android手机移动开发
文章浏览阅读569次。静态计算图执行效率很高,但较难调试。而Autograph机制可以将动态图转换成静态计算图,兼收执行效率和编码效率之利。当然Autograph机制能够转换的代码并不是没有任何约束的,有一些编码规范需要遵循,否则可能会转换失败或者不符合预期。我们会介绍Autograph的编码规范和Autograph转换成静态图的原理。并介绍使用tf.Module来更好地构建Autograph。上篇我们介绍了Autograph的编码规范,本篇我们介绍Autograph的机制原理。...
文章浏览阅读1.5k次。13.2 网络编程技术 前面介绍了网络编程的相关基础知识,初步建立了网络编程的概念,但是实际学习网络编程还必须使用某种程序设计语言进行代码实现,下面就介绍一下网络编程的代码实现。13.2.1 网络编程步骤 按照前面的基础知识介绍,无论使用TCP方式还是UDP方式进行网络通讯,网络编程都是由客户端和服务器端组成。当然,B/S结构的编程中只需要实_网络编程 没有数据之后怎么操作