1

Objective: 使用插入排序对指针数组进行降序排序。同时，当指针数组被排序时，指针指向的数组也会随之排序。

void insert(int **table, int row)

{

//  Local Declaration

    int temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = *table[current];
        walker = current - 1;
        while(walker >= 0 && temp > *table[walker])
        {
            *table[walker + 1] = *table[walker];
            walker--;
        }
        *table[walker + 1] = temp;
    }

return;

}

样本输出：

Before insertion sort:

1 -66

2 51 0

3 68 61 37

4 91 80 31 -9

5 59 42 -15 -19 -75

After insertion sort:

5 -66 -59 134218571 4132481 0

4 51 0 31 131357707

3 68 61 37

2 91 80

1 59

我应该创建每个数组的副本，并且当我使用插入排序交换数组时，还是有更有效的方法来完成任务？

完整的程序：

/*********************************************************************************
** CIS 15BG                                                           Winter, 2013
***************
**
** Homework 3:
**        Pointers, Dynamic Allocation of Memory, Ragged Arrays, and Sorting
**
**********************************************************************************

  This program creates a dynamic table that can store a ragged 2D array
  of integers, sorts each row then rearranges them by length

***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifdef _MSC_VER
#include <crtdbg.h>  // needed to check for memory leaks (Windows only!)
#endif

#define MEM_ERROR printf("Not enough memory\n")

int** getRow(int *row);
void valiRow(int *row);
void getSize(int **table, int row);
int  valiSize(int size);
void fillTable(int **table, int row);
void bubble(int **table, int row);
void insert(int **table, int row);
void save(int **table, int row);

int main (void)
{
    //  Local Declaration
    int **table;
    int row;

    //  Statement
    table = getRow(&row);
    getSize(table, row);
    fillTable(table, row);
    bubble(table, row);
    insert(table, row);

    #ifdef _MSC_VER
    printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Memory Leak\n");
    #endif
    return 0;

}// main

/* getRow */
int** getRow(int *row)
{
    //  Local Declaration
    int **table;

    //  Statement
    printf("Please enter the number of rows (1-10): ");
    scanf("%d", &*row);

    valiRow(&*row);

    table =(int**)calloc(*row+1, sizeof(int));
    if(table == NULL)
        MEM_ERROR, exit(100);

    return table;
}

/* valiRow */
void valiRow(int *row)
{
    //  Statement
    while(*row > 10 || *row < 1)
    {
        while(getchar() != '\n')
        ;
        printf("Please enter a number between (1-10): ");
        scanf("%d", &*row);
    }

    return;
}
/* getSize */
void getSize(int **table, int row)
{
    //  Local Declaration
    int i, size;

    //  Statement
    for(i = 0; i < row; i++)
    {
        printf("<ROW %2d> Please enter a size (1-15): ", i + 1);
        scanf("%d", &size);

        size = valiSize(size);

        table[i] = (int*)calloc(size + 1, sizeof(int));
        table[i][0] = size;
    }

    if(table == NULL)
        MEM_ERROR, exit(101);

    return;
}

/* valiSize */
int valiSize(int size)
{
    //  Statement
    while(size > 15 || size < 1)
    {
        while(getchar() != '\n')
        ;
        printf("Please enter a valid size (1-15): ");
        scanf("%d", &size);
    }

    return size;
}

/* fillTable */
void fillTable(int **table, int row)
{
    //  Local Declaration
    int random, i, j;

    //  Statement
    srand(time(NULL));
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < (table[i][0]) + 1; j++)
        {
            random = -99 + rand() % 199;
            table[i][j + 1] = random;
        }
    }

    return;
}

/* bubble */
void bubble(int **table, int row)
{
    //  Local Declaration
    int current, last, walker, temp;
    int i, j;
    //  Statment

    for(i = 0; i < row; i++)
    {
        last = table[i][0];
        for(current = 1; current < last; current++)
        {
            for(walker = last; walker > current; walker--)
            {
                if(table[i][walker] > table[i][walker - 1])
                {
                    temp = table[i][walker];
                    table[i][walker] = table[i][walker - 1];
                    table[i][walker - 1] = temp;
                }
            }
        }
    }

    return;
}

/* insert */
void insert(int **table, int row)
{
    //  Local Declaration
    int temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = *table[current];
        walker = current - 1;
        while(walker >= 0 && temp > *table[walker])
        {
            *table[walker + 1] = *table[walker];
            walker--;
        }
        *table[walker + 1] = temp;
    }

    return;
}
4

2 回答 2

1

您应该在插入函数中交换指针交换第一个元素（大小）的值并不意味着交换数组的剩余元素。

void insert(int **table, int row)
{
    //  Local Declaration
    int *temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = table[current];
        walker = current - 1;
        while(walker >= 0 && *temp > *table[walker])
        {
            table[walker + 1] = table[walker];
            walker--;
        }
        table[walker + 1] = temp;
    }

    return;
}
于 2013-02-02T11:19:58.017 回答
0

memmove() 是你的朋友：

#include <stdio.h>
#include <string.h> /* for memmove() */


void insertion_sort(int **table, size_t cnt);
void insertion_sort(int **table, size_t cnt)
{
    int *tmp;
    size_t src,dst;

    for(src = 1; src < cnt; src++)
    {
        tmp = table[src];
        for(dst=src; dst-- > 0 && *tmp < *table[dst]; ) {;}
                /* when we get out of the loop, 
                ** table[dst] is the element BEFORE our insertion point,
                ** so re-increment it to point at the insertion point */
        if (++dst == src) continue;

        memmove(table+dst+1,table+dst, (src-dst) * sizeof  table[0] );
        table[dst] = tmp;
    }

return 0;
}

int array[5] = { 11,12,13,14,15};
int *ptrs[5] = { array+3, array+0, array+4, array+2, array+1 };
int main (void)
{
size_t idx;
insertion_sort(ptrs, 5);

for (idx=0; idx < 5; idx++) {
        printf  ("[%zu] : %p: %d\n"
                , idx, (void*) ptrs[idx], *ptrs[idx]
                );

        }
return 0;
}
于 2013-02-02T12:28:58.920 回答