C语言关于链表数组和队列的笔试题

1. 请编写一个函数，将一个数组转化成链表，并返回链表的头指针。

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* array_to_linkedlist(int arr[], int size) {
    Node *head = NULL, *tail = NULL;

    for (int i = 0; i < size; i++) {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = arr[i];
        node->next = NULL;

        if (head == NULL) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }

    return head;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    Node *head = array_to_linkedlist(arr, size);

    // 遍历链表
    Node *p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }

    return 0;
}

2. 请编写一个函数，判断一个链表是否是循环链表，如果是循环链表，返回 1，否则返回 0。

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

int is_circular_linkedlist(Node *head) {
    if (head == NULL) {
        return 0;
    }

    Node *p = head, *q = head;
    while (q != NULL && q->next != NULL) {
        p = p->next;
        q = q->next->next;

        if (p == q) {
            return 1;
        }
    }

    return 0;
}

int main() {
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 1;

    Node *p1 = (Node*)malloc(sizeof(Node));
    p1->data = 2;
    head->next = p1;

    Node *p2 = (Node*)malloc(sizeof(Node));
    p2->data = 3;
    p1->next = p2;

    Node *p3 = (Node*)malloc(sizeof(Node));
    p3->data = 4;
    p2->next = p3;

    // 将链表变成循环链表
    p3->next = head;

    printf("%d\n", is_circular_linkedlist(head));

    return 0;
}

3. 请编写一个函数，实现队列的入队和出队操作。

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

#define MAX_SIZE 100

typedef struct Queue {
    int data[MAX_SIZE];
    int front, rear;
} Queue;

Queue* create_queue() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = 0;
    return q;
}

int is_full(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

int is_empty(Queue *q) {
    return q->front == q->rear;
}

void enqueue(Queue *q, int x) {
    if (is_full(q)) {
        printf("Queue is full.\n");
        return;
    }

    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

int dequeue(Queue *q) {
    if (is_empty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }

    int x = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;

    return x;
}

int main() {
    Queue *q = create_queue();

    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    printf("%d\n", dequeue(q));
    printf("%d\n", dequeue(q));
    printf("%d\n", dequeue(q));
    printf("%d\n", dequeue(q));

    return 0;
}