📄 prog3.c
字号:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
typedef struct Elementtype* Elementtypep;
typedef struct htinfo* hashtable;
int findht(hashtable ht,char * w,long int *i);
void insertht(hashtable ht,char *w,long int i);
long int hash(char *, hashtable ht );
struct Elementtype
{
int status;
char* key;
long int data;
};
struct htinfo
{long int tablesize;
long int size;
Elementtypep array;
};
hashtable Newht(int max );
void rehash(hashtable ht);
long int nextprime(void);
static int cmp(Elementtypep x,Elementtypep y,long int i);
void movearray(hashtable ht);
void quicksort(Elementtypep a,long int n);
static void q(Elementtypep a,long int left,long int right);
static int partition(Elementtypep x,long int left,long int right);
long int find=0;
main()
{
int max=509;
hashtable ht;
long int n,i,count=0;
char key[10];
char name[50];
long int j,flag=1;long int l;
char* w; char number[30];
char string[50];float SIZE;
long int k=0;long int x=0;
char ch;long int linenum=0;
FILE *fp;
ht=Newht(max);
printf("Enter the file name:");
scanf("%s",name);
if((fp=fopen(name,"r"))==NULL)
printf("file cannot be open");
while((ch=getc(fp))!=EOF)
{
if((isalpha(ch)||ch=='_'))
{
flag=1;
string[k]=tolower(ch);
k++;
}
else if(isalnum(ch))
{
if(flag==1)
{
string[k]=ch;
k++;
flag++;
}
}
else if (ch=='\n')
{
string[k]='\0';
w=malloc(sizeof(k+1));
strncpy(w,string,k+1);
k=0;
i=0;
if(findht(ht,w,&i)==0)
{
insertht(ht,w,i);
SIZE = ht->size/ht->tablesize;
if(SIZE>.50)
{find=0;
rehash(ht);
printf("The table size of rehash table is=");
printf("%ld\n",ht->tablesize);
}
i=0;
}
else if (findht(ht,w,&i)!=0)
{
ht->array[i].data++;
i=0;
}
}
else if (!(isalpha(ch)||isalnum(ch)||ch=='_'))
{
string[k]='\0';
w=malloc(sizeof(k+1));
strncpy(w,string,k+1);
k=0;
i=0;
if(findht(ht,w,&i)==0)
{
insertht(ht,w,i);
SIZE=ht->size/ht->tablesize;
if(SIZE>.50)
{find=0;
rehash(ht);
printf("The tablesize of rehash table is=");
printf("%ld\n",ht->tablesize);
}
i=0;
}
else if(findht(ht,w,&i)!=0)
{
ht->array[i].data++;
}
i=0;
}
}
movearray(ht);
printf("The tablesize of this table is=%ld\n",ht->tablesize);
printf("The max number of probes for this table is=%ld\n",find);
printf("\n");
fclose(fp);
return 0;
}
/*********************************************************************
This funtion bulds new hashtable.
***********************************************************************/
hashtable Newht( int max )
{
hashtable ht;int i;
ht=malloc(sizeof(struct htinfo));
ht->tablesize=max;
ht->size=0;
ht->array=malloc(sizeof(struct Elementtype )*509);
for(i=0;i<509;i++)
{
ht->array[i].data=0;
ht->array[i].status=0;
}
return ht;
}
/*******************************************************************
This function try to find the element in the table ,and sets
the value where it find it.it return 0 for false and 1 for (TRUE).
*************************************************************************/
int findht(hashtable ht,char *w,long int *ip)
{
int *time=0;
long int value =0; long int i=0;
static long int probes;
value = hash(w,ht);
while((ht->array[value].status)!=0)
{
if((strcmp(ht->array[value].key,w))==0)
{find++;
*ip=value;
return 1;
}
i=(i+1)%ht->tablesize;
find++;
}
* ip=value;
find++;
return 0;
}
/*********************************************************************
This function Insert the new element into the hashtable.
*****************************************************************/
void insertht(hashtable ht,char *word,long int i)
{ht->size++;
ht->array[i].key=word;
ht->array[i].status=1;
ht->array[i].data=1;
}
/***********************************************************************
This function computes the hash of the Element.
**********************************************************************/
long int hash(char* w, hashtable ht)
{
int i;unsigned long int sum=0;
if(w[0]=='\0')
return 0;
for(i=0;w[i]!='\0';i++)
sum=(sum+w[i])<<2;
sum=sum+w[0];
return sum%ht->tablesize;
}
/******************************************************************
This function moves the first n elements of hashtable into
the array.
****************************************************************/
void movearray(hashtable ht)
{Elementtypep a;
long int k ;
long int n =0;long int count=0;
long int i=0;
long int j =0;
a=malloc(sizeof(struct Elementtype)*(ht->tablesize));
for(j=0;j<(ht->tablesize);j++)
{if((ht->array[j].key)!=0)
{a[i].key=ht->array[j].key;
a[i].data=ht->array[j].data;
a[i].status=ht->array[j].status;
++i;
n++;
count++;
}
}
quicksort(a,n);
printf("The total number of words=%d\n",--n);
for(i=0;i<n;i++)
{ printf("%s\n ",a[i].key);
printf(" %ld\n",a[i].data);
}
}
/*************************************************************
This function is recursive it uses partition to sort the array
*********************************************************************/
void quicksort(Elementtypep a,long int n)
{
q(a,0,n-1);
}
/***************************************************************
This function is static and use different parameters which
are hidden from user.
****************************************************************/
static void q(Elementtypep a , long int left,long int right)
{
long int i=0; long int pivotposition=0;
if(right<=left)
;
else{
pivotposition=partition(a,left,right);
q(a,left,pivotposition-1);
q(a,pivotposition+1,right);
}
}
/************************************************************
This function Partition divides sort the array.
************************************************************/
static int partition(Elementtypep a,long int left,long int right)
{static long int count=0;long int * countp=0;
long int mid=0;long int i=0,j=0;
Elementtypep pivot;
Elementtypep hold;
hold=(Elementtypep)malloc(sizeof(struct Elementtype));
pivot=malloc(sizeof(struct Elementtype));
mid=(left+right)/2;
pivot->key=a[mid].key;
pivot->data=a[mid].data;
a[mid].key=a[right].key;
a[mid].data=a[right].data;
a[right].key=pivot->key;
a[right].data=pivot->data;
i=left;
j=right-1;
for(;;)
{
while(cmp(a,pivot,i)>0)
{count++;
i++;
}
while(i<j&&(cmp(a,pivot,i)==0))
{count++;
j--;
}
if(i<j)
{
hold->key=a[i].key;
hold->data=a[i].data;
a[i].key=a[j].key;
a[i].data=a[j].data;
a[j].key=hold->key;
a[j].data=hold->data;
i++;
j--;
}
else break;
}
a[right].key=a[i].key;
a[right].data=a[i].data;
a[i].key=pivot->key;
a[i].data=pivot->data;
return i;
}
/**********************************************************************
The function CMP compares the Element with the Pivot, and return
the value depending on their frequncey order and if they are equal
then they are compared by alphabetical order.
********************************************************************/
static int cmp(Elementtypep a,Elementtypep pivot,long int i)
{
if((a[i].data)>(pivot->data))
return 1;
else if((a[i].data)==(pivot->data))
{if(strcmp((a[i].key),(pivot->key))>0)
return 1;
}
else if(strcmp((a[i].key),(pivot->key))<0)
return 0;
else
return 0;
}
/****************************************************************
This function REHASH makes a new hashtable of double the size of
last one .It also transfer the Elements of oldhashtable.
********************************************************************/
void rehash(hashtable ht)
{
long int value=0;
long int n=0;
long int maxsize=0;
long int i=0;
char * temkey;
hashtable oldarray;
long int oldsize=ht->tablesize;
oldarray=ht;
maxsize=nextprime();
ht=malloc(sizeof(struct htinfo));
ht->tablesize=maxsize;
ht->array=malloc(sizeof(struct Elementtype)*maxsize);
while(i<oldsize)
{
if((oldarray->array[i].status)!=0)
{
temkey=oldarray->array[i].key;
value=hash(temkey,oldarray);
ht->array[value].key=temkey;
ht->array[value].data=oldarray->array[i].data;
ht->array[value].status=oldarray->array[i].status;
i++;
n++;
}
else
i++;
}
printf("The size of rehash table=");
printf("%ld",ht->tablesize);
ht->size=n;
free(oldarray->array);
free(oldarray);
}
/************************************************************************
The function nextprime returns the next size for hash table which is
almost the double of last one.
*************************************************************************/
long int nextprime(void)
{
static int i=0;
static long int p[14]={1021,2039,4093,8191,16381,32749,65521,
131071,262139,524287,1048573,2097143,4194301};
if(i==15)
printf("No next prime");
return p[i++];
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -