単連結リストの整列 #89 補数にしない

C

負数から10進数での各桁の数字を取り出すときに9からその数字を減じた値でもって比較した。
つまり、10進法での9の補数で順位を定義したことになる。
しかし、わざわざ補数表現にせずに、
負数の場合はその桁の数字に負符号を付けたものを値とすることでも問題ないと思われ。
つまり、負数の各桁の数字が1の時は-1、2の時は-2、……というように。

...snip
static int issup(cintelem_t p, cintelem_t q, void *base)
{
    if (base == 0) {
        return intelem_get_val(p) >= 0 && intelem_get_val(q) < 0;
    } else {
        int ip = intelem_get_val(p), iq = intelem_get_val(q);
        ip = ip >= 0 ? ip / (int)base % 10 : - (-ip) / (int)base % 10;
        iq = iq >= 0 ? iq / (int)base % 10 : - (-iq) / (int)base % 10;
        return ip > iq;
    }
}
...snip

この順位定義関数で実行すると、

-521  357 -937 -770 -205 -296    8  195  983  454 -656  416 -896  507 -313  495   20 -669 -925 -977
-669 -937 -977 -296 -656 -896 -205 -925 -313 -521 -770   20  983  454  195  495  416  357  507    8
-296 -896 -977 -770 -669 -656 -937 -925 -521 -313 -205  507    8  416   20  454  357  983  195  495
-977 -937 -925 -896 -770 -669 -656 -521 -313 -296 -205    8   20  195  357  416  454  495  507  983
-977 -937 -925 -896 -770 -669 -656 -521 -313 -296 -205    8   20  195  357  416  454  495  507  983

百の位が0の場合、負数でも非負数でも順位決めに使う値は0となり、その区別がつかなくなる。
が、これは9の補数表現を利用していた時の負数の0と正数の9の区別がつかないのと同じであり問題ない。
たとえば、

...snip
int main(void)
{
    int i;
    intlist_t list = intlist_new();
    for (i = 0; i <= 20; i++) intlist_add_first(list, i * 10 - 100);
    print(list);
...snip

のようなコードなら、

 100   90   80   70   60   50   40   30   20   10    0  -10  -20  -30  -40  -50  -60  -70  -80  -90 -100
 100   90   80   70   60   50   40   30   20   10    0  -10  -20  -30  -40  -50  -60  -70  -80  -90 -100
 -90  -80  -70  -60  -50  -40  -30  -20  -10  100    0 -100   10   20   30   40   50   60   70   80   90
-100  -90  -80  -70  -60  -50  -40  -30  -20  -10    0   10   20   30   40   50   60   70   80   90  100
-100  -90  -80  -70  -60  -50  -40  -30  -20  -10    0   10   20   30   40   50   60   70   80   90  100