Stack Berbasis Array Dinamis di C

Question

Saya menulis tumpukan dinamis dalam C yang menggunakan array sebagai struktur. Saya mencoba mempertahankan O (1) untuk push dan pop dan yakin saya telah melakukannya. Saya ingin tahu apa yang bisa ditulis dengan cara yang lebih bersih dan apakah ada bug yang tidak sepele.

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

int push(int val, int *c);
int pop(int *c);

int *stack;

int main(){
    int *c = malloc(sizeof(int));
    stack = malloc(sizeof(int));
    *c = 0;
    int i;
    for(;;){
       printf("1. Push\n2. Pop\n3. Stack\n4. Quit\n>>> ");
       scanf("%d", &i);
       if(i == 1){
           printf("Value: ");
           scanf("%d", &i);
           push(i, c);
       }
       else if(i == 2)
           printf("Value popped: %d\n", pop(c));
       else if(i == 3)
           for(int i = 0; i < *c; i++)
               printf("%d\n", stack[i]);
       else
           break;
    }
    free(stack);
    return 0;
}

int push(int val, int *c){
    int *r;
    r = realloc(stack, ((*c)+1)*sizeof(int));
    if (r == NULL){
        free(stack);
        exit(0);
    }
    stack = r;
    stack[*c] = val;
    ++(*c);
    return *c;
}

int pop(int *c){
    if (!(*c)) return -1;
    int x = stack[(*c)-1];
    stack[(*c)-1] = NULL;
    int *r;
    printf("%d\n", *c);
    r = realloc(stack, ((*c)-1)*sizeof(int));
    if(r == NULL){
        free(stack);
        exit(0);
    }
    --(*c);
    stack = r;
    return x;
}

```

Answer 1

Review oleh @G. Sliepen bagus dan saya setuju dengan semua yang dikatakan di sana. Tambahan:

• Jangan pernah menyembunyikan petunjuk di balik a typedef! Ini membuat kode sangat membingungkan untuk dibaca oleh pemrogram C termasuk Anda. Anda mungkin berpikir Anda melewatkan data dengan nilai padahal sebenarnya tidak, dan situasi membingungkan serupa.

• ... = malloc(sizeof(int));Tidak efisien untuk hanya mengalokasikan 1 item dan kemudian harus segera realloc. Perhatikan bahwa semua lokasi memori dinamis lambat saat dibuat, dan kita harus mengemudi untuk meminimalkan jumlah panggilan ke malloc/ realloc. Memanggilnya secara sering juga menyebabkan fragmentasi heap , yang dapat menyebabkan penggunaan memori yang sia-sia dan masalah lainnya.

  Sebaliknya, alokasikan perkiraan yang "cukup besar" saat pertama kali Anda menelepon malloc. Mungkin 100 item. Dan setiap kali Anda kehabisan memori, jangan reallochanya 1 item lagi, alokasikan lebih banyak dan catat berapa banyak ruang yang telah Anda alokasikan, dan berapa banyak dari memori yang Anda gunakan.

  Demikian pula, tidak perlu mengecilkan jumlah memori yang dialokasikan setiap kali Anda mengeluarkan sesuatu. Dealokasi juga lambat. Kurangi saja penghitung yang melacak berapa banyak memori yang dialokasikan yang Anda gunakan.

  Hal-hal seperti inilah yang sebenarnya penting dalam hal kinerja program. Teori "Big O", jauh lebih sedikit.

• stack[(*c)-1] = NULL;salah, bug. Anda tidak boleh menetapkan NULL ke variabel umum, hanya untuk pointer. NULL mungkin juga didefinisikan sebagai tipe pointer dan kemudian kode ini akan rusak.

  Sebenarnya Anda tidak perlu menghapus memori yang tidak digunakan sama sekali, itu tidak ada gunanya.

• Masalah gaya, tetapi biasakan untuk selalu menggunakan { }meskipun hanya ada satu baris di dalam pernyataan berikut if/elseatau pernyataan perulangan. Dan hindari kalimat satu baris yang ceroboh sepertiif (!(*c)) return -1;

• Nama variabel ihanya boleh digunakan untuk pengulangan iterator. Nama idalam lingkaran sebenarnya adalah singkatan dari iterator . Jangan gunakan untuk tujuan lain seperti mengambil masukan pengguna.

• Jangan gunakan "angka ajaib" dalam kode, seperti else if(i == 3). Gunakan konstanta tekstual sebagai gantinya. Sebagai contoh:

    enum
    {
      PUSH  = 1,
      POP   = 2,
      PRINT = 3,
      QUIT  = 4,
    };
  

• Dengan enum di atas, kita dapat membersihkan loop for dan if cukup banyak pernyataan, membuat kode sedikit lebih panjang tetapi jauh lebih mudah dipelihara:

  int user_choice = 0;
  while(user_choice != QUIT)
  {
    printf("1. Push\n2. Pop\n3. Stack\n4. Quit\n>>> ");
    scanf("%d", &user_choice);
  
    switch(user_choice) 
    {
      case PUSH: 
      {
        printf("Value: ");
        scanf("%d", &i);
        push(i, c);
        break;
      }
  
      case POP:
      {
        printf("Value popped: %d\n", pop(c));
        break;
      }
  
      case PRINT:
      {
        for(int i = 0; i < *c; i++)
        {
          printf("%d\n", stack[i]);
        }
        break;
      }
  
      default:
        user_choice = QUIT; // defensive programming, quit upon all invalid choises
    } // switch(user_choice) 
  } // while(user_choice != QUIT)
  

  (Perhatikan bahwa saya sengaja tidak membuat user_choicejenis enum. Saya melakukan ini hanya karena scanf("%d", &user_choice);pada enum tidak aman. Jika tidak, a typedef enumakan lebih disukai int.)

Answer 2

Buat structyang merangkum semua detail tumpukan

Masalahnya adalah bahwa tumpukan Anda hanya terlihat seperti penunjuk ke int, tidak bisa dibedakan dari penunjuk lain ke ints. Dan elemen pertama yang ditunjuk diperlakukan berbeda dari elemen lainnya. Dalam hal ini, lebih baik membuat struct yang melacak memori yang dialokasikan dan ukurannya, seperti:

struct Stack {
    size_t size;
    int *data;
};

Anda memulainya sebagai berikut:

struct Stack stack = {0, NULL};

Sekarang Anda harus mengubah push()dan pop()mengarahkan penunjuk ke struct stack:

void push(struct Stack *stack, int val) {
    stack->size++;
    int *new_data = realloc(stack->data, stack->size * sizeof *stack->data);

    if (!new_data) {
        // error handling here, or just
        abort();
    }
    
    stack->data = stack->new_data;
    stack->data[stack->size - 1] = val;
}

Dan serupa untuk pop(). Perhatikan bahwa biasanya fungsi yang beroperasi pada suatu objek mengarahkan penunjuk ke objek itu sebagai parameter pertama. Juga, saya membuat fungsi kembali void, tidak perlu mengembalikan ukuran ukuran tumpukan informasi yang sudah tersedia untuk pemanggil.

Hindari menggunakan variabel global

Anda harus menghindari penggunaan variabel global jika memungkinkan. Contoh kode saya di atas tidak lagi harus ada yang global stack. Perubahan ini memungkinkan kode untuk mengelola banyak tumpukan tanpa konflik.

Tambahkan fungsi untuk membuat dan menghancurkan tumpukan

Daripada meminta pemanggil mengetahui cara menginisialisasi a dengan benar struct Stackdan membebaskannya setelah digunakan, buat fungsi yang melakukan ini untuk Anda. Itu memungkinkan Anda untuk mengubah internal struct Stacknanti, tanpa harus mengubah semua tempat di mana tumpukan digunakan.

Gunakan awalan umum untuk menghindari konflik nama

push()dan pop()merupakan nama yang sangat umum. Ada lebih banyak hal yang dapat memiliki operasi push dan pop, seperti antrian FIFO. Saya sarankan Anda menggunakan awalan umum untuk semua struktur dan fungsi data untuk tumpukan Anda. Ini bisa saja Stackatau stackjika Anda pikir itu tidak mungkin bertentangan dengan hal lain.