Dynamic Array Based Stack ใน C

Question

ฉันเขียนสแต็กแบบไดนามิกใน C ที่ใช้อาร์เรย์เป็นโครงสร้าง ฉันพยายามรักษา O (1) เพื่อผลักดันและป๊อปและเชื่อว่าฉันได้ทำเช่นนั้น ฉันอยากรู้ว่าจะเขียนอะไรได้อย่างสะอาดตาและมีจุดบกพร่องที่ไม่สำคัญหรือไม่

#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

รีวิวโดย @G. Sliepen ฟังดูดีและฉันก็เห็นด้วยกับทุกสิ่งที่พูดในนั้น นอกจากนี้:

• อย่าซ่อนพอยน์เตอร์ไว้ข้างหลังtypedef! สิ่งนี้ทำให้โค้ดสับสนในการอ่านสำหรับโปรแกรมเมอร์ C รวมถึงตัวคุณเองด้วย คุณอาจคิดว่าคุณส่งผ่านข้อมูลด้วยค่าเมื่อคุณไม่ได้และสถานการณ์ที่สับสนคล้าย ๆ กัน

• ... = malloc(sizeof(int));มันเป็นความไม่มีประสิทธิภาพในการจัดสรรเพียง 1 reallocรายการและจากนั้นเกือบจะในทันทีต้อง โปรดทราบว่าทั้งหมดที่ตั้งหน่วยความจำแบบไดนามิกช้าเมื่อสร้างและเราควรขับรถเพื่อลดปริมาณของการโทรไป/malloc reallocการโทรหาพวกเขาบ่อยครั้งยังนำไปสู่การกระจายตัวของฮีปซึ่งอาจนำไปสู่การใช้หน่วยความจำที่สิ้นเปลืองและปัญหาอื่น

  ให้จัดสรรค่าประมาณ "มากพอ" ในครั้งแรกที่โทรmallocแทน อาจจะเป็น 100 รายการแทน และทุกครั้งที่หน่วยความจำของคุณหมดอย่าreallocเพิ่งเพิ่มอีก 1 รายการจัดสรรให้มากขึ้นและติดตามจำนวนห้องที่คุณจัดสรรไว้และจำนวนหน่วยความจำที่คุณใช้อยู่

  ในทำนองเดียวกันไม่จำเป็นต้องลดจำนวนหน่วยความจำที่จัดสรรทุกครั้งที่คุณเปิดบางสิ่ง การจัดสรรยังทำได้ช้า เพียงแค่ลดตัวนับที่ติดตามจำนวนหน่วยความจำที่จัดสรรที่คุณใช้อยู่

  สิ่งนี้คือสิ่งที่สำคัญจริงๆเมื่อพูดถึงประสิทธิภาพของโปรแกรม ทฤษฎี "บิ๊กโอ" น้อยกว่ามาก

• stack[(*c)-1] = NULL;ไม่ถูกต้องเป็นข้อบกพร่อง คุณไม่ควรกำหนดค่า NULL ให้กับตัวแปรทั่วไป แต่เฉพาะกับพอยน์เตอร์ NULL อาจถูกกำหนดเป็นประเภทตัวชี้จากนั้นรหัสนี้จะหยุดทำงาน

  ในความเป็นจริงคุณไม่จำเป็นต้องล้างหน่วยความจำที่ไม่ได้ใช้เลยนั่นไม่มีจุดหมาย

• ปัญหาเกี่ยวกับสไตล์ แต่ทำให้เป็นนิสัยที่จะใช้เสมอ{ }แม้ว่าจะมีเพียงบรรทัดเดียวในคำสั่งที่ตามหลังif/elseหรือคำสั่งวนซ้ำ และหลีกเลี่ยงการเลอะเทอะหนึ่งไลเนอร์เช่นif (!(*c)) return -1;

• iควรใช้ชื่อตัวแปรสำหรับตัววนซ้ำเท่านั้น ชื่อiในวงจริงยืนสำหรับiterator อย่าใช้เพื่อวัตถุประสงค์อื่นเช่นการป้อนข้อมูลของผู้ใช้

• อย่าใช้ "หมายเลขมายากล" else if(i == 3)ในรหัสเช่น ใช้ค่าคงที่ของข้อความแทน ตัวอย่างเช่น:

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

• ด้วย enum ด้านบนเราสามารถล้าง for loop และถ้างบค่อนข้างน้อยทำให้โค้ดยาวขึ้นเล็กน้อย แต่ดูแลรักษาได้ไกลกว่า:

  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)
  

  (โปรดทราบว่าฉันจงใจไม่สร้างuser_choiceenum ฉันทำสิ่งนี้เพียงเพราะscanf("%d", &user_choice);enum ไม่ปลอดภัยมิฉะนั้นtypedef enumจะดีกว่าint)

Answer 2

สร้างstructที่ห่อหุ้มรายละเอียดทั้งหมดของสแต็ก

ปัญหาคือสแต็กของคุณดูเหมือนตัวชี้ไปยังตัวชี้ที่intแยกไม่ออกจากพอยน์เตอร์อื่นถึงints และองค์ประกอบแรกที่ชี้ว่าได้รับการปฏิบัติแตกต่างจากองค์ประกอบอื่น ๆ ในกรณีนี้ควรสร้างโครงสร้างที่ติดตามหน่วยความจำที่จัดสรรและขนาดของหน่วยความจำที่จัดสรรไว้จะดีกว่า:

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

คุณเริ่มต้นดังต่อไปนี้:

struct Stack stack = {0, NULL};

ตอนนี้คุณควรเปลี่ยนpush()และpop()นำตัวชี้ไปที่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;
}

และคล้ายกันสำหรับpop(). โปรดสังเกตว่าเป็นเรื่องปกติที่จะมีฟังก์ชันที่ทำงานบนวัตถุนำตัวชี้ไปยังวัตถุนั้นเป็นพารามิเตอร์แรก นอกจากนี้ฉันได้ส่งคืนฟังก์ชันvoidโดยไม่จำเป็นต้องส่งคืนขนาดของขนาดสแต็กที่มีข้อมูลให้ผู้เรียกใช้แล้ว

หลีกเลี่ยงการใช้ตัวแปรส่วนกลาง

คุณควรหลีกเลี่ยงการใช้ตัวแปรส่วนกลางหากเป็นไปได้ โค้ดตัวอย่างของฉันด้านบนไม่จำเป็นต้องมี global stackอีกต่อไป การเปลี่ยนแปลงนี้ทำให้โค้ดสามารถจัดการหลายสแต็กโดยไม่มีข้อขัดแย้ง

เพิ่มฟังก์ชั่นในการสร้างและทำลายสแต็ก

แทนที่จะกำหนดให้ผู้โทรทราบวิธีการเริ่มต้นอย่างถูกต้องstruct Stackและเพื่อให้เป็นอิสระหลังจากใช้งานให้สร้างฟังก์ชันที่ทำเพื่อคุณ ซึ่งช่วยให้คุณสามารถเปลี่ยนภายในของstruct Stackภายหลังได้โดยไม่ต้องเปลี่ยนตำแหน่งทั้งหมดที่ใช้สแต็ก

ใช้คำนำหน้าทั่วไปเพื่อหลีกเลี่ยงความขัดแย้งของชื่อ

push()และpop()เป็นชื่อสามัญมาก มีสิ่งอื่น ๆ อีกมากมายที่สามารถผลักดันและดำเนินการได้เช่นคิว FIFO ฉันขอแนะนำให้คุณใช้คำนำหน้าทั่วไปสำหรับโครงสร้างข้อมูลและฟังก์ชันทั้งหมดสำหรับสแต็กของคุณ สิ่งนี้อาจเป็นได้Stackหรือstackถ้าคุณคิดว่าไม่น่าจะขัดแย้งกับสิ่งอื่น