VPF::сортировка символов в строке по частоте их встреча

lenarano

Дата 17.4.2014, 12:03 (ссылка)

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

Загрузка ...

Шустрый

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

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

Язык си. Бьюсь над задачей несколько дней. На этапе сортировки ничего не делает. Видно, что код указан неверно((( Помогите исправить исходный код, чтобы получилась сортировка.

Код


#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <conio.h>



int main(void)
{ 
setlocale(LC_ALL,"rus");
int symbols[256]; 
memset( symbols, 0, sizeof(int) * 256 ); 
int i,l,j,tmp,d,  nmin;
char tmpc;
char string[21];
int max = 0, maxi = 0; 
printf( "Ââåäèòå ñòðîêó: \n" ); 
gets (string); 
l = strlen( string ); 
for(i=0;i<l;i++)
if( (symbols[string[i]]+=1) > max ) 
{max=symbols[string[i]];
maxi=i;
}
for( i = 0; i < 256; i++ ) 
{if(symbols[i])
printf( "Символ '%c'. Он встречался %d раз\n", i, symbols[i] );
}
printf( "Наиболее васто встречается '%c'. Он встречается %d раз\n", string [maxi], symbols[string[maxi]] );
printf( "Отсортируем символы в порядке убывания их встречаемости\n");
for( i = 0; i < 255; i++ ) 
  {nmin=i;
   for( j = i+1; i < 256;i++ )
if(symbols[string[j]]<symbols[string[nmin]])
    nmin=j;
   if(nmin!=i)
      {tmp=symbols[string[i]];
       symbols[string[i]]=symbols[string[nmin]];
       symbols[string[nmin]]=tmp;
      }
  }
 for( i = 0; i < 256; i++ ) 
{if(symbols[i])
printf( "Символ '%c'. Он встречался %d раз\n", i, symbols[i] );
}
getch(); 
return 0; 
}

Это сообщение отредактировал(а) lenarano - 17.4.2014, 12:04

borisbn

Дата 17.4.2014, 12:48 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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

Везде, где встречается

Код

symbols[string[j]]

замени на

Код

symbols[ (unsigned char) string[ j ] ]

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

xvr

Дата 17.4.2014, 12:48 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

У вас не сортировка, а какие то танцы с бубном. smile

При чем вообще массив с исходной строкой (string) при сортировке массива частот символов?

lenarano

Дата 17.4.2014, 13:03 (ссылка)

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

Загрузка ...

Шустрый

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

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

программирование не мой конек.Но я стараюсь))) У меня всё красиво получилось на этапе подсчета символов и нахождения максимального по частоте. Далее нужно отсортировать их. Вот как тут использовать "пузырек" дальше. Может символы загнать под один массив, а их колличество под другой, а потом пустить вот это

Код


void bubbleSort(char *a, int *b,  int size )
{
    int tmp, i, j;
    char tmpc;
    for(i = 0; i < size - 1; ++i) // i - номер прохода
    {            
        for(j = 0; j < size - 1; ++j) // внутренний цикл прохода
        {     
            if (b[j + 1] < b[j]) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
                tmpc = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = tmpc;
            }
        }
    }

Но вы правы-изначально когда я беру сортировку я беру не те значения. Вот как тут выкрутится. Поверьте уже исчерпала свои внутренние ресурсы. Практики работы с кодами мне не хватает. Заочка я((( Помогите)))) Спасите)))

Это сообщение отредактировал(а) lenarano - 17.4.2014, 13:04

xvr

Дата 17.4.2014, 13:15 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Вам в любом случае нужны и сами символы и их частоты в явном виде, т.к. после сортировки простого соотвествия 'код символа' <-> 'индекс в массиве' уже не будет. Сделайте массив структур - <символ,частота> (вместо int symbols[256]) и его заполняйте и сортируйте.

lenarano

Дата 17.4.2014, 14:46 (ссылка)

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

Загрузка ...

Шустрый

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

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

Идею поняла и подхватила её smile

. Вот я немного навояла. Что дальше делать пока не знаю(((Не получается подсчитать и заполнить количество каждого символа smile

Код


#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <conio.h>
void bubbleSort(char *a, int *b,  int size );

struct str
{char sim;
 int skl;};
 

int main(void)
{setlocale(LC_ALL,"rus");
struct str s [256], *str1[256];
int i,j,len;
char tmpc;
char string[21];
memset( s, 0, sizeof(s)); 
len = strlen( string ); 
printf( "Введите строку: \n" ); 
gets (string);
i=0;
  while(string[i]!='\0')
    {s[i].sim=string[i];
    printf( "%dсимвол %c\n",i+1, s[i].sim );
    i++;
    }
  
   for(i=0;i<256;i++)
    {if(s[i].sim)
    s[i].skl+=1;
    }  
    printf( "Символ '%c'. Он встречался %d раз\n", s[1].sim, s[1].skl );
}
   void bubbleSort(char *a, int *b,  int size )
{
    int tmp, i, j;
    char tmpc;
    for(i = 0; i < size - 1; ++i) // i - номер прохода
    {            
        for(j = 0; j < size - 1; ++j) // внутренний цикл прохода
        {     
            if (b[j + 1] < b[j]) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
                tmpc = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = tmpc;
            }
        }
    }
}

Это сообщение отредактировал(а) lenarano - 17.4.2014, 17:28

borisbn

Дата 17.4.2014, 16:56 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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

А где обнуление i перед вторым while'ом ? А также её инрементация ?
Функция bubbleSort должна выглядеть как-то так:

Код

void bubbleSort(struct str *a, struct str *b,  int size )
{
    struct str tmp;
    int i, j;
    struct str tmpc;
    for(i = 0; i < size - 1; ++i)
    {            
        for(j = 0; j < size - 1; ++j)
        {     
            if (b[j + 1].skl < b[j].skl) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
                tmpc = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = tmpc;
            }
        }
    }
}

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

lenarano

Дата 17.4.2014, 17:04 (ссылка)

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

Загрузка ...

Шустрый

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

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

Спасибо, я ещё до этого не дошла. Бьюсь над формированием количества символов. Сверху ещё один вариант. Что то все равно не так(((Что -то не так уже в самой структуре. Вед в итоге нам надо из
addfffxxxx получить хххxfffdda

Код



i#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <conio.h>
void bubbleSort(char *a, int *b,  int size );
struct str
{char sim;
 int skl;};
 
int main(void)
{setlocale(LC_ALL,"rus");
struct str s [256], *str1[256];
int i,j,len;
char tmpc;
char string[21];
memset( s, 0, sizeof(s)); 
len = strlen( string ); 
printf( "Ââåäèòå ñòðîêó: \n" ); 
gets (string);
i=0;
  while(string[i]!='\0')
    {tmpc=s[i].sim=string[i];
    s[i].skl+=1;
    printf( "%d Ñòðîêà %c\n",i+1, s[i].sim );
    i++;
    if(tmpc==string[i])s[i].skl+=1;
    }
  printf( "Ñèìâîë'%c'. Âñòðå÷àëñÿ%d ðàç\n", s[3].sim, s[3].skl );
   for(i=0;i<256;i++)
    {if(s[i].sim)
    s[i].skl+=1;
    }  
    printf( "Ñèìâîë'%c'. Âñòðå÷àëñÿ%d ðàç\n", s[1].sim, s[1].skl );
}
   


/*  void bubbleSort(struct str *a, struct str *b,  int size )
{
    struct str tmp;
    int i, j;
    struct str tmpc;
    for(i = 0; i < size - 1; ++i)
    {            
        for(j = 0; j < size - 1; ++j)
        {     
            if (b[j + 1].skl < b[j].skl) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
                tmpc = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = tmpc;
            }
        }
    }
}*/*/

Это сообщение отредактировал(а) lenarano - 17.4.2014, 19:30

xvr

Дата 17.4.2014, 20:02 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Цитата(lenarano @ 17.4.2014, 17:04

)

Бьюсь над формированием количества символов.

Да уж

Код


struct str
{
 char sim;
 int count;
};

struct str freq_tabls[256];

void parse_string(const char* str)
{
 int i;
 for(i=0;i<256;++i)
  {
    freq_tabls[i].sim=i;
    freq_table[i].count=0;
  }
 while(*str) 
  freq_tabls[(unsigned char)*str++].count++;
}

int main(void)
{
 setlocale(LC_ALL,"rus");
 char string[1024];
 printf( "Ââåäèòå ñòðîêó: \n" ); 
 gets (string);
 parse_string(string);
 ....
}

Дальше сами

lenarano

Дата 17.4.2014, 20:49 (ссылка)

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

Загрузка ...

Шустрый

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

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

Теперь не получается пузырек((Пробовала и через qsort. Все равно нет. Опять лажаю. smile

Помогите(((
И как сделать, чтобы выводились не все символы, а только те которые нам надо?

Код


#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>

struct str
{char sim;
 int count;};
struct str freq_tabls[256];

void bubbleSort(struct str *a, struct str *b,  int size )
{
    struct str tmp;
    int i, j;
    struct str tmpc;
    for(i = 0; i < size - 1; ++i)
    {            
        for(j = 0; j < size - 1; ++j)
        {     
            if (b[j + 1].count < b[j].count) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
                tmpc = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = tmpc;
            }
        }
    }
}
int cmp(const void *a, const void *b) {
     return *(int*)a - *(int*)b;
 }

 void parse_string(const char* str)
{
 int i;
 for(i=0;i<256;++i)
  {
  freq_tabls[i].sim=i;
  freq_tabls[i].count=0;
  }
 while(*str) 
  freq_tabls[(unsigned char)*str++].count++;
}

int main(void)
{setlocale(LC_ALL,"rus");
char string[1024];
 int i;
 printf( "Введите строчку: \n" ); 
 gets (string);
 parse_string(string);
  for( i = 0; i < 256; i++ )
  printf( "Cимвол '%c'. Он встречался %d раз\n", freq_tabls[i].sim, freq_tabls[i].count );
  bubbleSort(freq_tabls[0].sim, freq_tabls[0].count,  256 );
 // qsort(freq_tabls, 256, sizeof(struct str), cmp );
  for( i = 0; i < 256; i++ ) 
  printf( "Cимвол '%c'. Он встречался %d раз\n", freq_tabls[i].sim, freq_tabls[i].count );
}

Это сообщение отредактировал(а) lenarano - 17.4.2014, 22:15

borisbn

Дата 18.4.2014, 08:34 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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

Код

void bubbleSort( struct str *b,  int size )
{
    struct str tmp;
    int i, j;
    for(i = 0; i < size - 1; ++i)
    {            
        for(j = 0; j < size - 1; ++j)
        {     
            if (b[j + 1].count < b[j].count) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
            }
        }
    }
}

и далее:

Код

...
  bubbleSort( freq_tabls, 256 );

Если хочешь с помощью qsort, то ф-ция сравнения д.б. примерно такая

Код

int cmp(const void *a, const void *b) {
    struct str * left = (struct str*) a;
    struct str * right = (struct str*) b;
    return left->count < right->count;
}

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

lenarano

Дата 18.4.2014, 09:04 (ссылка)

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

Загрузка ...

Шустрый

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

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

Нам нужно сравнение производить по ключу: ключ count. Но!!! при сравнении перекидывать и sim. Пробую сортировать с помощью указателей. Но ничего не получается(((
Вот видоизмененный кот

Код


#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>

struct str
{char sim;
 int count;};
struct str freq_tabls[256];
typedef struct str *psim;//новый тип данных ,указатель на структуры
typedef struct str *pcount;
 //функции
 void parse_string(const char* str)//подсчет количества символов
{
 int i;
 for(i=0;i<256;++i)
  {
  freq_tabls[i].sim=i;
  freq_tabls[i].count=0;
  }
 while(*str) 
  freq_tabls[(unsigned char)*str++].count++;
}

void Del(char *s)//удаление повторяющихся символов
{
   int flag[256] = {0};
   char *ps = s;
   while(*ps)
      if (!flag[*ps])
      {
         flag[*ps] = 1;
         ps++;
      }
      else strcpy(ps, ps + 1);
}

void bubbleSort(struct str *a, struct str *b,  int size )
{
    struct str tmp;
    int i, j;
    struct str tmpc;
    for(i = 0; i < size - 1; ++i)
    {            
        for(j = 0; j < size - 1; ++j)
        {     
            if (b[j + 1].count < b[j].count) 
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j]; 
                b[j] = tmp;
                tmpc = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = tmpc;
            }
        }
    }
}
/*int cmp(const void *a, const void *b) {
     return *(int*)a - *(int*)b;
 }*/


int main(void)
{setlocale(LC_ALL,"rus");
char string[1024];
int i;
psim p1[256];
pcount p2[256];
printf( "\n\nВведите строчку: \n" ); 
gets (string);
//printf( "\nЗадание 1.\nСтроку вывести на экран, причем если в ней дублируется символ - выводить его только в месте первого включения.\n\n" );
 //Del(string);
// puts(string);
 printf( "\nЗадание 2.\n Отсортировать символы в строке в порядке убывания частоты их встречаемости\n\n" ); 
 parse_string(string);
for( i = 0; i < 256; i++ ) 
 printf( "Cимвол '%c'. Он встречался %d раз\n", freq_tabls[i].sim, freq_tabls[i].count );
    for( i = 0; i < 256; i++ )
      {p1[i]=&freq_tabls[i].sim;
       p2[i]=&freq_tabls[i].count;
      }
 bubbleSort(p1, p2,  256);
for( i = 0; i < 256; i++ ) 
     printf( "Cимвол '%c'. Он встречался %d раз\n", freq_tabls[i].sim, freq_tabls[i].count );
}|

Вот что здесь не так?

Это сообщение отредактировал(а) lenarano - 18.4.2014, 09:21

borisbn

Дата 18.4.2014, 09:25 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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

Цитата(lenarano @ 18.4.2014, 09:04

)

Вот что здесь не так?

Всё.
Лови

Код


#include <stdio.h>
struct str
{
    char sim;
    int count;
};
struct str freq_tabls[ 256 ];
void parse_string(const char* str)//подсчет количества символов
{
 int i;
 for(i=0;i<256;++i)
  {
  freq_tabls[i].sim=i;
  freq_tabls[i].count=0;
  }
 while(*str) 
  freq_tabls[(unsigned char)*str++].count++;
}
void bubbleSort( struct str *b,  int size )
{
    struct str tmp;
    int i, j;
    for(i = 0; i < size - 1; ++i)
    {            
        for(j = 0; j < size - 1; ++j)
        {     
            if (b[j + 1].count > b[j].count)  // обрати внимание, что знак д.б. "больше", т.к. тебе надо сортировать по убыванию
            {
                tmp = b[j + 1]; 
                b[j + 1] = b[j];   // вот тут копируется как ключ (count), так и символ (sim)
                b[j] = tmp;
            }
        }
    }
}

int main()
{
    setlocale(LC_ALL,"rus");
    char string[1024];
    int i;
    printf( "\n\nВведите строчку: \n" ); 
    gets(string);
    printf( "\nЗадание 2.\n Отсортировать символы в строке в порядке убывания частоты их встречаемости\n\n" ); 
    parse_string( string );
    bubbleSort( freq_tabls,  256);
    for ( i = 0; i < 256; i++ )
    {
        if ( freq_tabls[ i ].count == 0 ) {
            break; // т.к. массив отсортирован, то после первого нуля все остальные д.б. тоже нули
        }
        printf( "Cимвол '%c'. Он встречался %d раз\n", freq_tabls[i].sim, freq_tabls[i].count );
    }
}

Играйся - http://ideone.com/D7K9oF

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

lenarano

Дата 18.4.2014, 10:33 (ссылка)

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

Загрузка ...

Шустрый

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

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

Пытаюсь адаптировать две функции(удаление повторяющихся символов и сортировка) к друг другу, что бы они не влияли на результаты друг друга. Для этого создаю новый массив символов идентичный string. При выводе результата в строке stringdubler появляется лишний символ. Почему он там появляется и как его убрать. Спасибо.

Код


#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <conio.h>


struct str
{char sim;
 int count;};
struct str freq_tabls[256];

 //функции
 void parse_string(const char* str)//подсчет количества символов
{
 int i;
 for(i=0;i<256;++i)
  {
  freq_tabls[i].sim=i;
  freq_tabls[i].count=0;
  }
 while(*str) 
  freq_tabls[(unsigned char)*str++].count++;
}

void Del(char *s)//удаление повторяющихся символов
{
   int flag[256] = {0};
   char *ps = s;
   while(*ps)
      if (!flag[*ps])
      {
         flag[*ps] = 1;
         ps++;
      }
      else strcpy(ps, ps + 1);
}

void bubbleSort(struct str *b,  int size )//сортировка 
{
    struct str tmp;
    int i, j;
    for(i = 0; i < size - 1; ++i)
    {            
     for(j = 0; j < size - 1; ++j)
        {     
         if (b[j + 1].count > b[j].count) 
          {
            tmp = b[j + 1]; 
            b[j + 1] = b[j]; 
            b[j] = tmp;
          }
        }
    }
}

int main(void)
{setlocale(LC_ALL,"rus");
char string[1024];
char stringdybler[1024];
int i,len;
printf( "\n\nВведите строчку: \n" ); 
gets (string);
len=strlen(string);
for(i=0;i<len;i++)
stringdybler[i] = string[i];
puts (stringdybler);
printf( "\nЗадание 1.\nСтроку вывести на экран, причем если в ней дублируется символ - выводить его только в месте первого включения.\n\n" );
Del(stringdybler);
puts(stringdybler);
 printf( "\nЗадание 2.\n Отсортировать символы в строке в порядке убывания частоты их встречаемости\n\n" ); 
 parse_string(string);
  bubbleSort( freq_tabls,  256);
     for( i = 0; i < 256; i++ )
      {
        if ( freq_tabls[ i ].count == 0 ) {
            break; // т.к. массив отсортирован, то после первого нуля все остальные д.б. тоже нули
        }
        printf( "Cимвол '%c'. Он встречался %d раз\n", freq_tabls[i].sim, freq_tabls[i].count );
       }
 
}

lenarano

Дата 18.4.2014, 10:59 (ссылка)

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

Загрузка ...

Шустрый

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

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

Как приятно находить свои ошибки самой

Код


len=strlen(string);
for(i=0;i<len+1;i++)
stringdybler[i] = string[i];
puts (stringdybler);

Ребят всем спасибо, кто помог. smile

Это сообщение отредактировал(а) lenarano - 18.4.2014, 11:00

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