VPF::Помогите, древовидная сортировка...

mpjoke

Дата 23.12.2006, 20:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 23.12.2006

Репутация: нет
Всего: нет

Помогите, надо заставить программу выводить в файл все слова, упорядоченные по частоте встречаемости. При этом нужно использовать древовидную сортировку
Я написал 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);
    }

Pete

Дата 23.12.2006, 23:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

Дерево должно быть одно.
Строй дерево (двоичное, раземеется) по мере прочтения каждого слова. Изначально дерево пусть. Прочел слово --- добавил узел, след. слово --- след. узел и т.д. При добавлении надо будет сравнивать элементы (a, b --- слова):
(a < b) <=> strcmp(a, b) < 0
(a = b) <=> strcmp(a, b) = 0
(a > b) <=> strcmp(a, b) > 0.

Потом, пока дерево непусто, удаляешь очередное слово и пишешь его в файл.

--------------------

Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу)
Не откладывай на завтра то, что можешь сделать сегодня. (Пословица)
А теперь выпишем точное значение числа пи... (Препод)
Жахни, Пендальф! © Гоблин

mpjoke

Дата 24.12.2006, 11:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 23.12.2006

Репутация: нет
Всего: нет

Я так и делал при сортировке по алфавиту, а теперь надо отсортировать по частоте встречаемости...
А мне как то не взять инфу из отсортированного по алфавиту дерева...

Pete

Дата 24.12.2006, 15:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

Зачем сортировать по алфавиту?

Цитата(Pete @ 24.12.2006, 00:01

)

Прочел слово --- добавил узел, след. слово --- след. узел и т.д.

Так ты сразу построишь двоичное дерево (алгоритм добавления спиши откуда-нибудь). А двоичное дерево обладает интересным свойством: для любого узла x дерева все элементы левого (правого) поддерева не больше (не меньше) x. Таким образом минимальный элемент --- самый левый лист. В соответствии с этим, удаляем минимум и печатаем его; удаляем след. мин и печатаем его; ... удаляем послед элемент и печатаем его.

--------------------

Kuvaldis

Дата 24.12.2006, 16:21 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 11
Всего: 61

Идея достаточно проста:
нужно обойти построенное тобой дерево любым из известных способов - симметричным, preorder, postorder. Т.е. так, чтобы ты заходил в каждый узел ровно один раз

Исходное дерево отсортированно в лексиграфическом порядке.
Т.е.

Цитата

для любого узла x дерева все элементы левого (правого) поддерева не больше (не меньше) x

Теперь строишь новое дерево по такому же принципу, только теперь сравнение делаешь не по strcmp, а по уже имеющейся инфе о количестве встречаемости

Т.е. придется строить НОВОЕ дерево
упорядочение на месте старого - это ОЧЕНЬ неприятное и долгое занятие. Его лучше не рассматривать.

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Pete

Дата 24.12.2006, 18:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

Цитата(Kuvaldis @ 24.12.2006, 17:21

)

Теперь строишь новое дерево по такому же принципу, только теперь сравнение делаешь не по strcmp, а по уже имеющейся инфе о количестве встречаемости

Точно, ошибся.. user posted image

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »