链接列表 - C 中的堆栈排序

Question

我的代码如下：

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

struct stack {
    int data;
    struct stack* next;
};
struct Student
{
    unsigned long int rollnumber;
    char name[100];
    struct Student *next;
    
}* head;
// Utility function to initialize stack
void initStack(struct stack** s) { *s = NULL; }
 
// Utility function to check if stack is empty
int isEmpty(struct stack* s)
{
    if (s == NULL)
        return 1;
    return 0;
}
 
// Utility function to push an item to stack
void push(struct stack** s, int x, unsigned long int rollnumber, char *name)
{
    struct stack* p = (struct stack*)malloc(sizeof(*p));
 
    if (p == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        return;
    }
 
    p->data = x;
    p->next = *s;
    *s = p;
}
 
// Utility function to remove an item from stack
int pop(struct stack** s)
{
    int x;
    struct stack* temp;
 
    x = (*s)->data;
    temp = *s;
    (*s) = (*s)->next;
    free(temp);
 
    return x;
}

// Function to find top item
int top(struct stack* s) { return (s->data); }

// Recursive function to insert an item x in sorted way
void sortedInsert(struct stack** s, int x, unsigned long int rollnumber, char *name)
{
    // Base case: Either stack is empty or newly inserted
    // item is less than top (more than all existing)
    if (isEmpty(*s) || x < top(*s)) {
        push(s, x, rollnumber, name);
        return;
    }
    else{
    // If top is less, remove the top item and recur
    int temp = pop(s);
    sortedInsert(s, x, rollnumber, name);
 
    // Put back the top item removed earlier
    push(s, temp, rollnumber, name);}
}
 
// Function to sort stack
void sortStack(struct stack** s)
{
    // If stack is not empty
    char *name;
    unsigned long int rollnumber;
    if (!isEmpty(*s)) {
        // Remove the top item
        int x = pop(s);
 
        // Sort remaining stack
        sortStack(s);
 
        // Push the top item back in sorted stack
        sortedInsert(s, x, rollnumber, name);
    }
}
// Utility function to print contents of stack
void printStack(struct stack* s, unsigned long int rollnumber, char* name)
{
    struct Student* student = (struct Student *) malloc(sizeof(struct Student));
    struct Student* temp = head;
    while (s && temp!=NULL) {
        printf("%lu %s\n", temp->rollnumber, temp->name);
        s = s->next;
        temp = temp->next;
    }

    printf("\n");
}

void insert(unsigned long int rollnumber, char* name)
{
    
    struct Student * student = (struct Student *) malloc(sizeof(struct Student));
    student->rollnumber = rollnumber;
    strcpy(student->name, name);
    student->next = NULL;
    
    if(head==NULL){
        // if head is NULL
        // set student as the new head
        head = student;
    }
    else{
        // if list is not empty
        // insert student in beginning of head
        student->next = head;
        head = student;
    }
    
}

void Delete(unsigned long int rollnumber)
{
    struct Student * temp1 = head;
    struct Student * temp2 = head; 
    while(temp1!=NULL){
        
        if(temp1->rollnumber==rollnumber){
            
            printf("Record with roll number %lu Found\n", rollnumber);
            
            if(temp1==temp2){
                // this condition will run if
                // the record that we need to delete is the first node
                // of the linked list
                head = head->next;
                free(temp1);
            }
            else{
                // temp1 is the node we need to delete
                // temp2 is the node previous to temp1
                temp2->next = temp1->next;
                free(temp1); 
            }
            
            printf("Record successfully deleted\n");
            return;
            
        }
        temp2 = temp1;
        temp1 = temp1->next;
        
    }
printf("Student with roll number %lu is not found\n", rollnumber);
    
}
void display()
{
    struct Student * temp = head;
    while(temp!=NULL){
        
        printf("Roll Number: %lu\n", temp->rollnumber);
        printf("Name: %s\n", temp->name);
        temp = temp->next;
        
    }
}

int main(void)
{
    head = NULL;
    int choice;
    int fc_,id_,year_, fc_year;
    char name[100];
    struct student* s;
    unsigned long int rollnumber;
    struct stack* faculty;
    struct stack* year;
    struct stack* id;
    initStack(&faculty);
    initStack(&year);
    initStack(&id);
    printf("1 - Enter school number\n2 - Display school numbers by ID\n3 - Display school numbers sorted by year\n4 - Display school numbers sorted by the faculty codes\n5 - Delete a record by school number\n6 - Exit");
    do
    {
        printf("\nEnter Choice: ");
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:
                printf("Enter roll number: ");
                scanf("%lu", &rollnumber);
                fc_ = rollnumber/pow(10, 6);
                id_ = rollnumber%(10*10*10*10);
                fc_year = rollnumber/pow(10,4);
                year_ = fc_year%(100);
                printf("Enter name: ");
                scanf("%s", name);
                insert(rollnumber, name);
                push(&faculty, fc_, rollnumber, name);
                push(&year, year_, rollnumber, name);
                push(&id, id_, rollnumber, name);
                break;
            case 2:
                printf("Sorted by ID: \n");
                sortStack(&id);
                printStack(id, rollnumber, name);
                break;
            case 3:
                printf("Sorted by year: \n");
                sortStack(&year);
                printStack(year, rollnumber, name);
                break;
            case 4:
                printf("Sorted by faculty code: \n");
                sortStack(&faculty);
                printStack(faculty, rollnumber, name);
                break;
            case 5:
                printf("Enter roll number to delete: ");
                scanf("%lu", &rollnumber);
                Delete(rollnumber);
                break;
            case 6:
                break;
        }
        
    } while (choice != 6);
}

比如选择2时，我想按升序显示学生姓名和全学号。但是当我运行它就是我得到的（C，B，A 是我给的名字）：

Enter Choice: 2
705102020 C
705102010 B
705102005 A

我确信我排序正确，但可能是我的 printStack 函数工作不正常。我该如何扭转它？

Answer 1

主要问题是您的堆栈和学生列表之间没有联系，但代码假定存在联系。您可以根据需要对堆栈重新排序，但这不会对列表重新排序。当你打印的时候，学生们只是按照他们插入顺序的倒序出来（因为你在列表的前面插入，然后从前到后遍历列表）。

您有两个主要选择：

将链表和所有栈合并为一个链表。如果您愿意，可以同时使用 list-style 和 stack-style。或者
将堆栈节点指针指向相应的列表元素，并在打印堆栈时遍历这些节点以按照堆栈隐含的顺序获取学生。

Answer 2

最好独立于代码的其余部分定义堆栈结构：

struct stack {
    void *data;
    struct stack *next;
};

void stack_init(struct stack **ss)
{
    *ss = NULL;
}

bool stack_push(struct stack **ss, void *data)
{
    struct stack *node = malloc(sizeof *node);
    if (!node) return false;
    
    node->data = data; // Copy address, not data
    node->next = *ss;
    *ss = node;
    
    return true;
}

bool stack_pop(struct stack **ss, void **data)
{
    if (!*ss) return false;
    
    struct stack *rm = *ss;
    *ss = (*ss)->next;
    if (data) *data = rm->data; // If nothing is provided (i.e. NULL), data will leak if it was allocated dynamically.
    free(rm);
    
    return true;
}

bool stack_top(const struct stack *ss, void **data)
{
    if (!ss) return false;
    
    *data = ss->data;
    return true;
}

void stack_print(const struct stack *ss, void print(const struct stack*))
{
    for (const struct stack *sp = ss; sp; sp = sp->next)
        print(sp);
}

您可以像这样实现堆栈排序功能：

struct stack *stack_find_min(struct stack *ss, int (*cmp)(const void*, const void*))
{
    struct stack *min = ss;
    for (struct stack *sp = ss; sp; sp = sp->next)
        if (cmp(sp->data, min->data) < 0)
            min = sp;
    
    return min;
}

void stack_sort(struct stack *ss, int (*cmp)(const void*, const void*))
{
    if (!ss) return;
    
    for (struct stack *sp = ss; sp; sp = sp->next) {
        struct stack *min = stack_find_min(sp, cmp);
        swap(&sp->data, &min->data);
    }
}

swap() 交换两个指针：

void swap(void **p1, void **p2)
{
    void *tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

之后，定义你的学生数据结构：

struct student {
    unsigned long rollnumber;
    char name[100];
    struct student *next;
};

struct student *student_insert(struct student **head, unsigned long rollnumber, const char *name)
{
    struct student *st = malloc(sizeof(*st));
    if (!st) return NULL;
    
    st->rollnumber = rollnumber;
    strncpy(st->name, name, 99);
    st->next = *head;
    *head = st;
    
    return st;
}

void student_print(const struct stack *ss)
{
    struct student *st = ss->data;
    printf("%ld\t%s\n", st->rollnumber, st->name);
}

int student_compare_id(const void *s1, const void *s2)
{
    // MUST cast void* into (struct student*) first.
    const struct student *student1 = s1;
    const struct student *student2 = s2;
    
    unsigned long rollnumber1 = student1->rollnumber;
    unsigned long rollnumber2 = student2->rollnumber;
    
    unsigned long id1 = rollnumber1 % 10000;
    unsigned long id2 = rollnumber2 % 10000;
    
    return id1 == id2 ? 0 : (id1 < id2 ? -1 : 1);
}

如果你想测试上面的内容：

int main(void)
{
    struct stack *ss;
    stack_init(&ss);

    struct student *st = NULL;
    student_insert(&st, 100181234, "James");
    student_insert(&st, 200195678, "John");
    student_insert(&st, 300200324, "Goku");
    student_insert(&st, 400214321, "Taylor");
    
    for (struct student *p = st; p; p = p->next)
        stack_push(&ss, p);

    puts("Unsorted stack:");    
    stack_print(ss, student_print);
    
    stack_sort(ss, student_compare_id);
    
    puts("\nSorted by ID:");
    stack_print(ss, student_print);

    // Don't forget to free the memory allocated for students
    // and pop all nodes of the stack (ommited here).
}

输出：

Unsorted stack:
100181234   James
200195678   John
300200324   Goku
400214321   Taylor

Sorted by ID:
300200324   Goku
100181234   James
400214321   Taylor
200195678   John

还有一些事情：

不要使用 scanf() 读取用户输入。 fgets() 更安全。
可以直接用10000代替pow(10, 4)。为什么要浪费 CPU 个周期来计算常量？
在您的 insert() 函数中，不需要测试 *head == NULL。 else 语句中的代码处理这种情况。

编辑： 在 student_compare_id() 中，必须先将 const void* 指针转换为 const struct student*，然后再取消引用。以前的版本似乎可以工作，因为 rollnumber 恰好是结构中的第一个字段。那是一种未定义的行为。现在修复了。

这是任何人都不应该使用的以前的版本：

int student_compare_id(const void *s1, const void *s2)
{
    unsigned long rollnumber1 = *(unsigned long*)s1; // WRONG!
    unsigned long rollnumber2 = *(unsigned long*)s2; // WRONG!
    
    unsigned long id1 = rollnumber1 % 10000;
    unsigned long id2 = rollnumber2 % 10000;
    
    return id1 == id2 ? 0 : (id1 < id2 ? -1 : 1);
}

链接列表 - C 中的堆栈排序

Linked List - Stack Sorting in C

c

stack

linked-list