如何在基数排序时将字符串粘在一起？

我必须通过使用基数排序来制作一个程序来对字符串进行排序（确切长度为7个字符）。我已经创建了一个函数来分别对每列进行排序。我的问题是如何使整个字符串移动，而不仅仅是一个字符。我真的很难看到它应该如何在C中工作。我做了一个数组“char strings [3] [8]”和“char output [3] [8]”以获得排序的3个字符串每个7个字符。例如排序这些字符串：如何在基数排序时将字符串粘在一起？

strcpy(strings[0], "kupbars"); 
strcpy(strings[1], "daparba"); 
strcpy(strings[2], "jykaxaw");

在输出我得到：

dakaaaa 
juparbs 
kypbxrw

每一列正确排序，但字符不会粘在一起。我尝试了很多方法3小时，但没有任何工作。

我的代码如下所示：

void countingSort(char a[][8], char b[][8]) { 
    int c[123]; 
    for (int pos = 6; pos >= 0; pos--) { 
    for (int i = 0; i < 123; i++) 
     c[i] = 0; 
    for (int i = 0; i < 3; i++) 
     c[(int)a[i][pos]]++; 
    for (int i = 1; i < 123; i++) 
     c[i] += c[i - 1]; 
    for (int i = 2; i >= 0; i--) { 
     b[--c[(int)a[i][pos]]][pos] = a[i][pos]; 
    } 
    } 
}

（有常数限制字符串的长度等，因为它很容易将其更改为变量 - 我只是专注于正确得到这个工作方案）

来源

2016-12-07 lemka8

我相信这是通常用链表每个数字的桶，这将有一个指针到整个字符串执行。（您需要更复杂的数据结构;难以在原地完成） – qxz

尝试改变回路移动整个字符串：

for (int i = 2; i >= 0; i--) { 
     int k = --c[(int)a[i][pos]]; 
     for(int j = 0; j < 8; j++) { 
      b[k][j] = a[i][j]; 
     } 
    }

来源

2016-12-07 05:16:21 rcgldr

非常感谢，它的工作原理！ :)也许来自其他用户的提议也会起作用，但是你对我来说最容易理解 – lemka8

inner for loop可以用memcpy（）或memmove（）替换，但是我试图用一个基本的例子。 – rcgldr

@ lemka8别担心，这个答案很好。我♥回答像rcgldr那样，但我的极限是两个'for'循环的功能。所以我不会拿你的代码，并建议你一个“更清洁”的解决方案。不要犹豫，稍后再试。如果你想在C中写入，你需要一个理解指针。顺便说一句，欢迎来到堆栈溢出，这是一个很好的问题。 – Stargateur

你可以做一个循环列表，但是它有点花销。我建议你使用memmove()。

#include <string.h> 

void array_move_forward(char array[3][8]) { 
    for (int i = 0; i < 3; i++) { 
    char tmp = array[i][6]; 
    memmove(array[i] + 1, array[i], 6); 
    array[i][0] = tmp; 
    } 
} 

void array_move_rewind(char array[3][8]) { 
    for (int i = 0; i < 3; i++) { 
    char tmp = array[i][0]; 
    memmove(array[i], array[i] + 1, 6); 
    array[i][6] = tmp; 
    } 
}

另一种解决方案是自己操纵字符串，并使用索引来指示字符串的第一个字母。

{ 
    char str[7]; 
    int i = 0; 
    ... 
    int j = i; 
    for (int k = 0; k < 7; k++) { 
    char tmp = str[j++ % 7]; 
    } 
}

有了，你可以只是i++或i--旋转你的字符串。

struct my_string_radix { 
    char str[7]; 
    int begin; 
}

来源

2016-12-07 02:18:19 Stargateur

如何在基数排序时将字符串粘在一起？

回答

相关问题