Cで最小ヒープソートの配列へのポインタを使用する方法は?

0xC0d3

私は最小ヒープを使用してヒープソートを作成しようとしていましたが、それも配列ポインターを指す構造体を使用していました。今ではどちらかのいくつかの論理的な誤りがあるcreateHeapの機能や中heapify関数が。注:プログラムの残りの部分をチェックまたは編集する必要はありません。HeapifyおよびcreateHeapは、プログラムの残りの部分に従って変更する必要があります。

   #include <stdio.h>
#include <stdlib.h>

// Max heap of length len and values stored in array
struct MinHeap{
    int size;
    int* array;
};

// Function declarations
void createHeap(struct MinHeap*);
void heapify(struct MinHeap* , int );
void heapSort(struct MinHeap*);
void swap(int*,int*);
void printArray(int*, int);

int main(){

    int numelems;
    scanf("%d",&numelems);
    int * arr = (int*) malloc(sizeof(int) * numelems);
    int i;

    for(i=0;i<numelems;i++)
    scanf("%d",&arr[i]);

    struct MinHeap* minHeap =  (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->size                   = numelems;   // initialize size of heap
    minHeap->array                 = arr;     // Assign address of first element of array

    createHeap(minHeap);
    heapSort(minHeap);

    printArray(minHeap->array,numelems);
    return 0;
}

// heapSort function
void heapSort(struct MinHeap* minHeap){


    // Repeat following steps while heap size is greater than 1. 
    while (minHeap->size > 1){
        // The smallest item in Heap is stored at the root. Replace it with the last item of the heap followed by reducing the size of heap by 1.
        swap(&minHeap->array[0], &minHeap->array[minHeap->size - 1]);
        --minHeap->size;  // Reduce heap size

        // heapify the root of tree.
        heapify(minHeap, 0);
    }
} 

// function swap 2 integers
void swap(int* num1, int* num2){ 
    int temp = *num1;
    *num1    = *num2;  
    *num2    = temp; 
}

// prints an array of given size
void printArray(int* a, int len){
    int i;
    for (i = len-1; i >=0 ; i--)
        printf("%d ", a[i]);
}

void createHeap(struct MinHeap *heap)
{

    int len=heap->size-1,i;
    for(i=len;i>=0;i--)
    heapify(heap,i);
}
void heapify(struct MinHeap *heap,int i)
{
    int min;
    int right=2*i+2,left=i*2+1;
    if(right<heap->size-1 && heap->array+i>heap->array+right)
    min=right;
    else min =i;
    if(left<heap->size-1 && heap->array+i>heap->array+left)
    min=left;
    if(min!=i)
    {
        swap(heap->array+i,heap->array+min);
        heapify(heap,min);
    }   
}
rafix07

ではheapify機能あなたは変更せた値ではないポインタを比較する必要があります

heap->array+i>heap->array+right

heap->array[i]>heap->array[right]

注:array[i]は別の記述方法である*(array+i)ため、コードをに変更するとコードは機能します*(heap->array + i) > *(heap->array + right)が、一般的に、角かっこを使用すると状況がはるかに明確になります。

かどうかを確認条件ではleftrightインデックスが配列の範囲内であなたが交換する必要がありますleft < heap->size-1によってleft <= heap->size-1(と同じことを行うためにrightインデックスを)。

これらの行が実行された後

if(right<=heap->size-1 && heap->array[i]>heap->array[right])
    min=right;
else 
    min =i;

min次の比較で使用する値を取る必要があります

if(left<=heap->size-1 && heap->array[min]>heap->array[left])

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集
0

コメントを追加

0

関連記事

分類Dev

cの配列をポインターでソートする

分類Dev

Cでポインタの配列へのポインタの配列を定義する方法は?

分類Dev

C ++で動的2D配列を宣言するときに、ポインターへのポインターを使用するのはなぜですか?

分類Dev

ポインタの配列で選択ソートを使用する

分類Dev

ポインターメンバーを使用してポインターの配列をソートできる関数を構成する方法

分類Dev

Javaで配列タイプのリストをソートする方法は?

分類Dev

cの未知の型配列で最大要素を見つける方法(関数へのポインターを使用)

分類Dev

C ++:ループ内の関数ポインターへの配列を生成する方法

分類Dev

Rust forCで配列へのポインターを表す方法

分類Dev

ポインタのみを使用して整数の配列をソートするときの「for」ループ

分類Dev

ループを使用して関数へのポインタの配列を初期化する方法

分類Dev

C#foreachループでポイントのオフセットメソッドを使用してポイントの配列を変更する

分類Dev

配列ブラケットを使用するこのループとCのポインター表記の違いは何ですか?

分類Dev

引数に応じてポインタの配列をソートする方法

分類Dev

ポインタの配列にソートを実装する

分類Dev

ポインタの配列を整数にソートする

分類Dev

各列のタイプが異なる C の 2D 配列をソートする方法は?

分類Dev

タイプスクリプトの配列を値でソートする方法

分類Dev

C言語で多次元配列へのポインタを使用する方法は?

分類Dev

C / C ++で配列へのポインタを使用する必要があるのはなぜですか?

分類Dev

ポインタ配列へのポインタを使用してマージソートが機能しない

分類Dev

Cでは、不完全な型の配列へのポインターの使用を許可する必要がありますか?

分類Dev

cの文字の配列へのポインタポイントを作成する

分類Dev

最小ヒープの削除の最悪の場合のランタイムが配列O(N)として実装されているのはなぜですか?

分類Dev

C ++で動的2D配列へのポインタを初期化する方法

分類Dev

固定サイズの配列へのポインターのアドレスを、Cのポインターへのポインターを期待する関数に渡せないのはなぜですか?

分類Dev

Cで配列へのポインタを初期化する

分類Dev

配列からポインタへの変換。C ++で配列のサイズを見つける方法は?

分類Dev

効率的なC ++ 11の方法で配列へのポインタを構造体にキャストする

Related 関連記事

  1. 1

    cの配列をポインターでソートする

  2. 2

    Cでポインタの配列へのポインタの配列を定義する方法は?

  3. 3

    C ++で動的2D配列を宣言するときに、ポインターへのポインターを使用するのはなぜですか?

  4. 4

    ポインタの配列で選択ソートを使用する

  5. 5

    ポインターメンバーを使用してポインターの配列をソートできる関数を構成する方法

  6. 6

    Javaで配列タイプのリストをソートする方法は?

  7. 7

    cの未知の型配列で最大要素を見つける方法(関数へのポインターを使用)

  8. 8

    C ++:ループ内の関数ポインターへの配列を生成する方法

  9. 9

    Rust forCで配列へのポインターを表す方法

  10. 10

    ポインタのみを使用して整数の配列をソートするときの「for」ループ

  11. 11

    ループを使用して関数へのポインタの配列を初期化する方法

  12. 12

    C#foreachループでポイントのオフセットメソッドを使用してポイントの配列を変更する

  13. 13

    配列ブラケットを使用するこのループとCのポインター表記の違いは何ですか?

  14. 14

    引数に応じてポインタの配列をソートする方法

  15. 15

    ポインタの配列にソートを実装する

  16. 16

    ポインタの配列を整数にソートする

  17. 17

    各列のタイプが異なる C の 2D 配列をソートする方法は?

  18. 18

    タイプスクリプトの配列を値でソートする方法

  19. 19

    C言語で多次元配列へのポインタを使用する方法は?

  20. 20

    C / C ++で配列へのポインタを使用する必要があるのはなぜですか?

  21. 21

    ポインタ配列へのポインタを使用してマージソートが機能しない

  22. 22

    Cでは、不完全な型の配列へのポインターの使用を許可する必要がありますか?

  23. 23

    cの文字の配列へのポインタポイントを作成する

  24. 24

    最小ヒープの削除の最悪の場合のランタイムが配列O(N)として実装されているのはなぜですか?

  25. 25

    C ++で動的2D配列へのポインタを初期化する方法

  26. 26

    固定サイズの配列へのポインターのアドレスを、Cのポインターへのポインターを期待する関数に渡せないのはなぜですか?

  27. 27

    Cで配列へのポインタを初期化する

  28. 28

    配列からポインタへの変換。C ++で配列のサイズを見つける方法は?

  29. 29

    効率的なC ++ 11の方法で配列へのポインタを構造体にキャストする

ホットタグ

アーカイブ