Помогите, надо заставить программу выводить в файл все слова, упорядоченные по частоте встречаемости. При этом нужно использовать древовидную сортировку
Я написал 1 половину программы - сортирует в алфавитном порядке, а заставить ее построить 2 дерево, на основе 1го не получается...
Вот текст программы, буду крайне признателен, если подскажите как это сделать или напишете этот кусок. Заранее спасибо.
| Код |
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
FILE *fp;
char text[240];
void wrds();
void opn();
char buf[240]; /* áóôåð ââîäà */
int lines; /* íîìåð ñòðîêè ôàéëà */
typedef struct node{
struct _data{ /* ÄÀÍÍÛÅ */
int counter; /* ñ÷åò÷èê*/
char *key; /* êëþ÷ - ñòðîêà */
int line; /* íîìåð ñòðîêè */
} data;
/* ÑËÓÆÅÁÍÀß ÈÍÔÎÐÌÀÖÈß */
struct node *l, /* ëåâîå ïîääåðåâî */
*r; /* ïðàâîå ïîääåðåâî */
} Node;
Node *root = NULL; /* êîðåíü äåðåâà (ññûëêà íà âåðõíèé óçåë) */
/* Îòâåäåíèå ïàìÿòè è èíèöèàëèçàöèÿ íîâîãî óçëà */
Node *newNode(s)
char *s; /* ñòðîêà */
{
Node *tmp;
// extern char *malloc(); /* âûäåëèòåëü ïàìÿòè */
tmp = (Node *) malloc(sizeof(Node));
if( tmp == NULL ){
fprintf( stderr, "Íåò ïàìÿòè.\n");
exit(1);
}
tmp -> l = tmp -> r = NULL; /* íåò ïîääåðåâüåâ */
tmp -> data.line = lines; /* íîìåð ñòðîêè ôàéëà */
tmp -> data.counter =1;
tmp -> data.key = malloc( strlen(s) + 1 );
/* +1 - ïîä áàéò '\0' â êîíöå ñòðîêè */
strcpy(tmp -> data.key, s); /* êîïèðóåì êëþ÷ â óçåë */
return tmp;
}
int z; /* Âûíåñåíî â ñòàòè÷åñêóþ ïàìÿòü, ÷òîáû ïðè êàæäîì
* ðåêóðñèâíîì âûçîâå íå ñîçäàâàëàñü íîâàÿ auto-ïåðåìåííàÿ,
* à èñïîëüçîâàëàñü îäíà è òà æå ñòàòè÷åñêàÿ */
/* Ðåêóðñèâíàÿ ïå÷àòü äåðåâà */
void printtree(root, tree, level, c)
Node *root; /* êîðåíü äåðåâà */
Node *tree; /* äåðåâî */
int level; /* óðîâåíü */
char c; /* èìÿ ïîääåðåâà */
{
if( root == NULL ){ printf("Äåðåâî ïóñòî.\n"); return; }
if( tree == NULL ) return;
/* åñëè åñòü - ðàñïå÷àòàòü ëåâîå ïîääåðåâî */
printtree (root, tree -> l, level + 1, '/'); /* 'L' */
/* ðàñïå÷àòàòü êëþ÷ óçëà */
for( z=0; z < level; z++ )
printf(" ");
printf("%c%3d--\"%s\" Words num %d""\n",
c, tree-> data.line, tree -> data.key, tree -> data.counter);
/* åñëè åñòü - ðàñïå÷àòàòü ïðàâîå ïîääåðåâî */
printtree(root, tree -> r, level + 1, '\\'); /* 'R' */
}
void prTree(tree) Node *tree;
{
printtree(tree, tree, 0, '*');
}
/* Äîáàâèòü óçåë ñ êëþ÷îì key â äåðåâî tree */
void addnode(tree, key)
Node **tree; /* â êàêîå äåðåâî äîáàâëÿòü: àäðåñ ïåðåìåííîé,
* ñîäåðæàùåé ññûëêó íà êîðíåâîé óçåë */
char *key; /* êëþ÷ óçëà */
{
#define TREE (*tree)
if( TREE == NULL ){ /* äåðåâî ïîêà ïóñòî */
TREE = newNode( key );
return;
}
/* èíà÷å åñòü õîòü îäèí óçåë */
if ( strcmp (key, TREE -> data.key) < 0 )
{
/* äîáàâèòü â ëåâîå ïîääåðåâî */
if ( TREE -> l == NULL ){
/* íåò ëåâîãî äåðåâà */
TREE -> l = newNode(key);
return;
}
else addnode( & TREE ->l , key);
}
else if (strcmp (key, TREE -> data.key) > 0)
{
/* äîáàâèòü â ïðàâîå äåðåâî */
if ( TREE -> r == NULL ){
/* íåò ïðàâîãî ïîääåðåâà */
TREE -> r = newNode(key);
return;
}
else addnode ( & TREE ->r, key);
}
else
{
TREE -> data.counter++;
}
}
void main(){
extern char *gets();
opn();
wrds();
prTree(root);
getch();
exit(0);
}
void wrds()
{
char *p;
char z[240]="";
int i=1;
char asd[]=(" !.,\n");
p = strtok (text, asd); // token => "words"
printf ("%s\n", p);
printf ("%d\n", i);
lines++;
addnode( & root, p );
i++;
do{
p = strtok(NULL, asd);
if (p==NULL)
break;
lines++;
addnode( & root, p );
printf ("%s\n", p);
printf ("%d\n", i);
i++;
}
while (p!=NULL);
}
void opn()
{
int n;
if ((fp=fopen("text.txt","r"))==NULL) //îòêðûëè ôàéë
{
perror ("Warning!");
getch();
exit (0);
}
n=fread (&text, sizeof text, 1, fp);
if (n==1)
exit(0);
fclose(fp);
}
|
|
)