Digital Sort строки

@ulyxa117 · Регистрация: 30.04.2013

Студворк — интернет-сервис помощи студентам

Небходимо реализовать цифровую сортировку строк. У меня крашится непонятно почему

C++

spis *DigitalSort(spis *&S, int L)
{
 int j,i,d;
 spis *p;
 tle Q[4000];
 for (j=L;j>=0;j--)
  {
   for (i=0;i<256;i++)
    Q[i].tail=(spis *)&Q[i].head;
   p=S;
   while (p) 
     {
      d=p->digit[j];
      Q[d].tail->next=p; // здесь краш
      Q[d].tail=p; 
      p=p->next; 
     }
   p=(spis*)&S;
   for (i=0;i<256;i++)
    {
     if (Q[i].tail!=(spis *)&Q[i].head) 
      {
       p->next=Q[i].head;
       p=Q[i].tail;
      }
    }
   p->next=NULL; 
  }
}

Добавлено через 9 часов 48 минут
Дело в том, что код этой сортировки не мой... и я не могу точно понять смысл этих строк.

C++

1 2	Q[i].tail=(spis )&Q[i].head; p=(spis)&S;

Добавлено через 2 часа 1 минуту

C++

spis *DigitalSort(spis *&S, int L)
{
 int j,i;
 int d;
 spis *p;
 tle Q[4000];
 for (j=L-1;j>=0;j--) {
     for (i=0;i<4000;i++)
         Q[i].tail=(spis *)&Q[i].head;
     p=S;
     while (p) {
           d=int(p->key[j])+128;         
           Q[d].tail->next=p;
           Q[d].tail=p; 
           p=p->next; 
     }
     p=(spis*)&S;
     for (i=0;i<4000;i++) {
         if (Q[i].tail!=(spis *)&Q[i].head) {
            p->next=Q[i].head;
            p=Q[i].tail;
         }
     }
     p->next=NULL;
 }
}

почему то после кажого пробега по разряду уменьшается длинна очереди, остаются только элементы с одинаковым ключом сортировки.. и так на каждом шагу

Добавлено через 11 часов 59 минут
причем первым.. то есть если к примеру сортирую последовательность
Прпа
Крта
Капа
Норм
Пост
то сначала останется
Прпа
Крта
Капа
потом
Прпа
Капа
Потом
Капа
и на последнем шаге останется только
Капа

@ulyxa117 · 11.05.2013, 18:20 **[ТС]**

ЗАРАБОТАЛО! оооочень долго парился по этому поводу, заработало таким образом, может кому поможет!)

C++

spis *DigitalSort(spis *S, int L){
 int j,i;
 int d;
 spis *p,*t;
 tle Q[256];
 bool b;
 for (j=L-1;j>=0;j--) {
     for (i=0;i<256;i++) Q[i].b=false;
     p=S;         
     while (p!=NULL) {
           d=int(p->key[j])+128;         
           if (!Q[d].b) {
              Q[d].head=Q[d].tail=p;
              Q[d].b=true;
           } else {
             Q[d].tail->next=p;
             Q[d].tail=p;
           }
           p=p->next; 
     }
     b=false;
     for (i=0;i<256;i++) {
         if (Q[i].b) {
            if (!b) {
               t=Q[i].head;
               b=true;
            } else p->next=Q[i].head;
            p=Q[i].tail;            
         }
     }
     p->next=NULL;
     S=t;
 }
 return S;
}

27.11.2013, 12:39

ulyxa117, не мог ты написать, как у тебя происходит инициализация и заполнение списка с последующим выводом.

Hellraiser BCH
	27.11.2013, 12:39	3
	ulyxa117, не мог ты написать, как у тебя происходит инициализация и заполнение списка с последующим выводом.

Опции темы