分别利用线性表和二叉排序树来实现单词频率的统计，实现低频词的过滤，并比较两种方法的效率
作者&投稿：徐戚 （若有异议请与网页底部的电邮联系）
你是哪个学校的啊= =
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<time.h>
#define maxqsize 9000
typedef struct vnode{
char word[16];
int count;
vnode* next;
}*linklist;
typedef struct tree{
char word[16];
int count;
tree *lcchild,*rcchild;
}*Bitree,*queueelem;
typedef struct queue{
queueelem *data;
int rear,front,tag;//tag 为判断队的状态1为满 0为空
};
void inordertraverse(Bitree r,FILE* fp)//中序遍历输出结果到文档
{
if(r==NULL)return;
inordertraverse(r->lcchild,fp);
printf("%-16s%3d\n",r->word,r->count);
fprintf(fp,"%-16s%3d\n",r->word,r->count);
inordertraverse(r->rcchild,fp);
}
void initqueue(queue &q){
q.data=(queueelem *)malloc(maxqsize*sizeof(queueelem));
q.tag=q.front=q.rear=0;
return;
}
void enqueue(queue &q,queueelem e)
{
if(q.tag==1)return;
q.data[q.rear]=e;
q.rear=(q.rear+1)%maxqsize;
if(q.rear==q.front)q.tag=1;
else q.tag=2;
}
void dequeue(queue &q,queueelem &e)
{
if(q.tag==0)return;
e=q.data[q.front];
q.front=(q.front+1)%maxqsize;
if(q.rear==q.front)q.tag=0;
else q.tag=2;
}
linklist head;
Bitree root=(Bitree)malloc(sizeof(tree)),root2;
int main()
{
void start();
start();
}
void start()
{
int i;
void biao();
void bitree();
while(true)
{
system("cls");
printf("统计低频词汇\n");
printf("1.线性表\n");
printf("2.二叉排序树\n");
printf("3.退出\n");
printf("键入数字1－3，选择需要进入的功能界面\n");
printf("\n");
while(scanf("%d",&i),i<1&&i>3);
switch(i)
{
case 1:biao();break;
case 2:bitree();break;
case 3:return;
}
}
}
void biao()
{
void basl();
system("cls");
int i;
void jm1();
void jm2();
while(true)
{
system("cls");
printf("统计低频词汇\n");
printf("1.连续执行并显示时间\n");
printf("2.分步执行\n");
printf("3.计算ASL\n");
printf("4.返回主菜单\n");
printf("\n");
while(scanf("%d",&i),i<1&&i>4);
switch(i)
{
case 1:jm1();break;
case 2:jm2();break;
case 3:basl();break;
case 4:return;
}
}
}
void bread()
{
char a [99999];
FILE* fp=fopen("D:\\data\\InFile.txt","r");
//if(fp)printf("读取文件成功\n");
char ch[35],str[16];linklist p,q;int i,j;
head=(linklist)malloc(sizeof(vnode));
head->next=NULL;
while(~fscanf(fp,"%s",ch))
{
j=0;
for(i=0;;i++)
if(isalpha(ch[i]))str[j++]=ch[i];
else if(j)
{
str[j]=0;
for(j=0;str[j];j++)
if(isupper(str[j]))str[j]+=32;
for(p=head;p->next;p=p->next)
if(strcmp(str,p->next->word)==0)break;
if(p->next)p->next->count++;
else{
q=(linklist)malloc(sizeof(vnode));
//printf("%s\n",str);
strcpy(q->word,str);
q->count=1;
p->next=q;q->next=NULL;
}
j=0;if(!ch[i])break;
}
else if(!ch[i])break;
}
fclose(fp);
void boutput();
boutput();
}
void bdel()
{
linklist p=head,q;
while(p->next)
if(p->next->count<5)
{
q=p->next;p->next=q->next;
//free(q);
}
else p=p->next;
//printf("s%\n",p);
}
void bsort()
{
linklist p,q,r;
q=head->next->next;head->next->next=NULL;
while(q)
{
r=q;q=q->next;
for(p=head;p->next;p=p->next)
if(r->count>p->next->count)break;
r->next=p->next;p->next=r;
}
}
void boutput()
{
bsort();
linklist p=head->next;
FILE* fp=fopen("D:\\data\\File1.txt","w");
while(p)
{
printf(" %-15s\t%d\n",p->word,p->count);
//printf("%d",&basl);
fprintf(fp," %-15s\t%d\n",p->word,p->count);
p=p->next;
}
if(fp)printf("已成功写入文件File1，路径为D:\\data\\File1.txt，请自行查看\n");
fclose(fp);
}
void jm1()
{
time_t now=clock();
bread();
bdel();
boutput();
time_t f=clock();
FILE *fp=fopen("D:\\data\\File1.txt","a");
fprintf(fp,"时间为%.3fs\n",(double)(f-now)/CLOCKS_PER_SEC);
fclose(fp);
printf("时间为%.3fs\n",(double)(f-now)/CLOCKS_PER_SEC);
system("pause");
}
void jm2()
{
void basl();
int i;
while(true)
{
system("cls");
printf("统计低频词汇\n");
printf("1.统计单词\n");
printf("2.删除低频单词\n");
printf("3.输出剩余单词及频率\n");
printf("4.计算ASL\n");
printf("5.返回上一级\n");
printf("\n");
while(scanf("%d",&i),i<1&&i>5);
switch(i)
{
case 1:bread();system("pause");break;
case 2:bdel();system("pause");break;
case 3:boutput();system("pause"); break;
case 4:basl();system("pause");break;
case 5:return;
}
}
}
void bitree()
{
void sasl();
system("cls");
int i;
void bitree1();
void bitree2();
while(true)
{
system("cls");
printf("\n统计低频词汇\n");
printf("1.连续执行并显示时间\n");
printf("2.分步执行\n");
printf("3.计算ASL\n");
printf("4.返回主菜单\n");
printf("\n");
while(scanf("%d",&i),i<1&&i>3);
switch(i)
{
case 1:bitree1();break;
case 2:bitree2();break;
case 3:sasl();break;
case 4:return;
}
}
}
void sread()
{
FILE* fp=fopen("D:\\data\\InFile.txt","r");
char ch[35],str[16];Bitree p,q;int i,j,flag=1;
while(~fscanf(fp,"%s",ch))
{
for(i=0,j=0;;i++)
if(isalpha(ch[i]))str[j++]=ch[i];
else if(j)
{
str[j]=0;
for(j=0;str[j];j++)
if(isupper(str[j]))str[j]+=32;
p=root;
if(flag)
{
strcpy(p->word,str);
p->count=1;p->lcchild=NULL;
p->rcchild=NULL;flag=0;
}
else while(true)
{
int k=strcmp(p->word,str);
if(k==0){p->count++;break;}
else if(k<0&&p->rcchild){
p=p->rcchild;continue;
}
else if(k<0){
q=(Bitree)malloc(sizeof(tree));
strcpy(q->word,str);
printf("%s ",str);
q->count=1;
p->rcchild=q;q->lcchild=NULL;
q->rcchild=NULL;
break;
}
else if(p->lcchild){
p=p->lcchild;continue;
}
else{
q=(Bitree)malloc(sizeof(tree));
strcpy(q->word,str);
printf("%s ",str);
q->count=1;
p->lcchild=q;q->lcchild=NULL;
q->rcchild=NULL;break;
}
}
j=0;if(!ch[i])break;
}
else if(!ch[i])break;
}
if(fp)printf("读取文件成功\n");
fclose(fp);
inordertraverse(root,0);
}
void inserttree(Bitree p)
{
printf(" %-15s\t%d\n",p->word,p->count);
Bitree q=(Bitree)malloc(sizeof(tree));
strcpy(q->word,p->word);
q->count=p->count;
q->lcchild=NULL;
q->rcchild=NULL;
if(!root2){
root2=q;
return;
}Bitree r=root2;
while(true)
{
if(p->count<r->count&&r->rcchild){
r=r->rcchild;continue;
}
if(p->count<r->count){
r->rcchild=q;
break;
}
if(p->count>=r->count&&r->lcchild){
r=r->lcchild;continue;
}
r->lcchild=q;
break;
}
}
void bitree(Bitree r)
{
if(r){
if(r->count>4)inserttree(r);
if(r->lcchild)bitree(r->lcchild);
if(r->rcchild)bitree(r->rcchild);
}
}
void del()
{
bitree(root);
root=root2;
}
void output()
{
FILE* fp=fopen("D:\\data\\File2.txt","w");
//printf("%s\n",root2);
//printf("已删除\n");
fprintf(fp,"%s\n",root2,fp);
inordertraverse(root2,fp);
//while(r)
// {
// printf(" %-15s\t%d\n",r->word,r->count);
// fprintf(fp," %-15s\t%d\n",r->word,r->count);
// r=r->next;
// }
if(fp)printf("已成功写入文件File2，路径为D:\\data\\File2.txt，请自行查看\n");
fclose(fp);
}
void bitree1()
{
time_t now=clock();
sread();
del();
output();
void sasl();
sasl();
time_t f=clock();
FILE *fp=fopen("D:\\data\\File2.txt","a");
fprintf(fp,"时间为%.3fs\n",(double)(f-now)/CLOCKS_PER_SEC);
fclose(fp);
printf("时间为%.3fs\n",(double)(f-now)/CLOCKS_PER_SEC);
system("pause");
}
void bitree2()
{
int i;void sasl();
while(true)
{
system("cls");
printf("低频词过滤\n");
printf("1.统计单词\n");
printf("2.删除低频单词\n");
printf("3.输出剩余单词及频率\n");
printf("4.计算ASL\n");
printf("5.返回上一级\n");
printf("\n");
while(scanf("%d",&i),i<1&&i>5);
switch(i)
{
case 1:sread();system("pause");break;
case 2:del();system("pause");break;
case 3:output();system("pause"); break;
case 4:sasl();break;
case 5:return;
}
}
}
void basl()
{
linklist p=head;
float asl;
int wn=0;
while(p->next)
{
wn++;
p=p->next;
}
asl=((float)wn+1)/2.0;
printf("ASL值为:%.3f\n",asl);
//fprintf("ASL值为：%.3f\n",asl)
system("pause");
}
void shu(Bitree p,int qu,int &wn,float &sl)
{
if(p){
wn++;sl+=qu;
shu(p->lcchild,qu+1,wn,sl);
shu(p->rcchild,qu+1,wn,sl);
}
}
void sasl()
{
int qu=1,wn=0;float asl=0;
shu(root,qu,wn,asl);
printf("ASL值为:%.3f\n",asl/wn);
system("pause");｝
分太少了。300分可以考虑。
线性结构的定义
线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。非线性结构，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。一、线性结构：1、线性结构作为最常用的数据结构，其特点是数据元素...
以下数据结构中,不属于线性数据结构的是( )。
【答案】：C 栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，因此栈又称后进先出表或先进后出表；队列可看作是插入在一端进行，删除在另一端进行的线性表，因此队列又称先进先出表或后进后出表。二叉树不属于线性结构。
以下哪些是线性表()。
【答案】：B、C 二叉树、图、树和集合都是非线性结构，栈、队列、线性表都是线性结构。
数据结构怎么这么难啊
刚好有空，跟你大概说说线性表吧。数据结构一般说的结构只有两种，一种是线性，一种就是非线性。线性包含：队列（也就是线性表）、堆栈。非线性的是二叉树。线性表跟数组的区别在于，数组记录的只是一个数或者字符，而线性表就是字面上的意思，是一个记录相对较全面的信息页。打个比方，类似你的同学...
学习数据结构是不是和学过的C语言程序设计很有关联?
数据结构讲述计算机中数据的组织方式，如线性表、链表、二叉树等，这些学校通常讲述算法的思路多谢，上机实现的部分少些。但是如果你程序设计语言不过关的话，以后计算机专业课程的学习将会痛苦万分，如果你是一个对计算机编程感兴趣的人，我希望你能好好看待学习计算机知识这样一个难得机会，如果你不喜欢的话...
数据结构面试题整理学生收藏
(2)线性结构:数据元素之间是一对一的关系——线性表、栈、队列 (3)树形结构:数据元素之间是一对多的关系 (4)图状结构:数据元素之间是多对多的关系。 物理结构包括顺序存储结构和链式存储结构。 二、解释一下顺序存储与链式存储 顺序存储结构是用一段连续的存储空间来存储数据元素,可以进行随机访问,访问效率较高。
数据结构笔试题
C 顺序表的空间利用率高于链表D 在链表中 每个结点只有一个链域带头结点的单链表head为空的判断条件是( B )A head=NIL ? B head >next=NIL...C 链表存储结构和数组 D 线性存储结构和非线性存储结构按照二叉树的定义 具有 个结点的二叉树有(? C? )种 A ? B ? C ? D 二叉树的结构如下图...
求遍历二叉树实验报告一份
printf("该二叉树的叶子结点个数为: %d\\n",leaf(bt));printf("该二叉树的形状为：\\n");int nLayer=0;PrintTree(bt,nLayer);} 请输入数据：AB.DF..G..C.E.H..结果：实验总结：通过学习数据结构，发现数据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、...
计算机二级基础题
(2) 以下数据结构中不属于线性数据结构的是___。(C) A. 队列 B. 线性表 C. 二叉树 D. 栈 (3) 在一棵二叉树上第5层的结点数最多是___。(B) A. 8 B. 16 C. 32 D. 15 (4) 下面描述中,符合结构化程序设计风格的是___。(A) A. 使用顺序、选择和重复(循环)三种基本控制结构表示程序的...
我是湖南邵阳职业技术学院的专科学生,学的是计算机科学与技术...
6) 两种遍历算法分别使用的数据结构(栈和队列)7) 利用图的遍历解决简单的应用问题第九章 查找一、学习目的和要求本章的目的是介绍线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。重点掌握顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。难点是二叉排序树上...
邸泉华佗： #include <stdio.h>#include <stdlib.h>#include <iostream.h> struct tree//声明树的结构 { struct tree *left,*right; int data; }; typedef struct tree treenode;//声明新类型树结构 typedef treenode *b_tree;//声明二叉树链表 //插入二叉树节点 b_tree insert_...
马关县13794501133： 借助二叉排序树实现排序 - ？
邸泉华佗： 本题的一个完整的c程序如下,程序在win-tc和Dev-c++下都调试通过.#include ＂stdlib.h＂#include ＂stddef.h＂#define OK 1#define ERROR 0typedef int keytype;typedef stru...
马关县13794501133： 利用二叉排序树对顺序表进行排序 (1)生成一个顺序表L;(2)对所生成的顺序表L构造二叉排序树(3)利用栈结构 - ？
邸泉华佗： 用C或C++语言实现的功能:(1)生成一个顺序表L;(2)对所生成的顺序表L构造二叉排序树(3)利用栈结构实现中序遍历二叉排序树; (4)中序遍历所构造的二叉排序树将记录由小到大输出.
马关县13794501133： C语言线性表——分别用顺序表和单链表实现A∩B.这是我个人失误,将满意答案给错人了,特在此补过. - ？
邸泉华佗： 答案贴出把// A∩B.cpp : 定义控制台应用程序的入口点.//#include ＂stdafx.h＂ int _tmain(int argc, _TCHAR* argv[]) { return 0; }#include<stdlib.h>#include<stdio.h>#define MAX_SIZE 20 struct SqList { int elemt[MAX_SIZE]; int length; }; typedef ...
马关县13794501133： 二叉树排序算法实现 急!急!急! - ？
邸泉华佗： 每次新来一个数,都根据其大小插入二叉树中1. root = null2. 首先,p = root, 将新来的数字A与节点p中的数字进行比较, 2.1 如果,节点p == null, p = new Node(); 且,该节点中的数字等于A 2.2 如果A比节点p中的数字大,p = p->rightChild 2.3 如果A比节点p中的数字小,p = p->leftChild
马关县13794501133： 二叉排序树的实现？
邸泉华佗： #include <stdio.h> #include <malloc.h> typedef struct BiTnode { int data; struct BiTnode *lchild,*rchild; }BiTnode,*BiTree; BiTree search_tree(BiTree T,int keyword,BiTree *father) { BiTree p; *father = NULL; p = T; while (p && p->data!=keyword) { *...
马关县13794501133： 二叉排序树的实现 数据结构？
邸泉华佗： Program p6_6(Input, Output); Type tree=^node; node=Record data:Integer; lchild,rchild:tree; End; Var bt:tree; n:Integer; Procedure creat_order_tree(Var btx:tree;nx:Integer); Var p,s,f:tree; flag:Boolean; Begin New(s); s^.data:=nx; s^.lchild:=Nil; s^....
马关县13794501133： 二叉排序树的操作？
邸泉华佗：实验目的】 由读入数据构造二叉排序树,并进行插入,查找,删除操作. 【设计原理】 二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树: 1. 若它的左子树不空,则右子树上所有结点的值均大于它的根结点的值 2. 若它的右子树不...
马关县13794501133： 二叉排序树的实现 - ？
邸泉华佗： /*以下是用c++ 实现的二叉排序树的源代码*/#include typedef struct TreeNode { int key; struct TreeNode *left; struct TreeNode *right; }treeNode; class BiSortTree { public: BiSortTree(void); void desplayTree(void);//显示这个树 void insertTree(int key)...
马关县13794501133： 二叉排序树的实现 用顺序和二叉链表作存储结构,完成学生成绩管理 - ？
邸泉华佗： void main() /*主函数*/ { for(;;) { switch(menu()) /* 选择判断*/ { case 1:Input(stud);/* 输入学生成绩*/ break; case 2:Statistic(stud); /*输出学生统计数据*/ break; case 3:Lookup(stud); /*查找学生成绩*/ cout<<＂\t\t\t＂; system(＂pause＂); break; ...
