LinkList

[luneshao]

合并有序链表 & 逆置

#include <stdio.h>

typedef struct LNode {
    int data;
    struct Node *next;
} Node, *List;

// 合并有序链表
List MergeList (List L1, List L2) {
    List p = L1->next;
    List q = L2->next;
    List c = L1;

    while(p != NULL) {
        if (p->data >= q->data) {
            c->next = q;
            c = q;
            q = q->next;
        } else {
            c->next = p;
            c = p;
            p = p->next;
        }
    }

    c->next = p == NULL ? q : p;

    return L1;
}

// 初始化
List initList1(int arr[]) {
    List p;
    List L = (List)malloc(sizeof(Node));
    L->next = NULL;
    p = L;

    for (int i = 0; i < 5; ++i) {
        Node *s = (Node *)malloc(sizeof(Node));
        s->data = arr[i];
        s->next = p->next;
        p->next = s;
        p = s;
    }
    return L;
}

// 逆置
List reverseList(int arr[]) {
    List L = (List)malloc(sizeof(Node));
    L->next = NULL;

    for (int i = 0; i < 5; ++i) {
        Node *s = (Node *)malloc(sizeof(Node));
        s->data = arr[i];
        s->next = L->next;
        L->next = s;
    }
    return L;
}

[luneshao]

最基本的顺序队列

初始化、入队、出队

#include <stdio.h>
#define MAX_LENGTH 5

typedef struct SQueue {
    int arr[MAX_LENGTH];
//    int len;
    int tail; // 队头指针
    int rear; // 队尾指针
} Queue;

void initQueue (Queue *queue);
void enQueue (Queue *queue, int data);
void deQueue (Queue *queue, int *data);

int main()
{
    Queue queue;
    initQueue(&queue);

    enQueue(&queue, 1);
    enQueue(&queue, 2);
    enQueue(&queue, 3);
    enQueue(&queue, 4);
    enQueue(&queue, 5);
//    enQueue(&queue, 6);
    int i;
    deQueue(&queue, &i);
//    deQueue(&queue, &i);
    printf("%d\n", i);
}

// 初始化
void initQueue (Queue *queue) {
//    queue->len = 0;
    queue->tail = 0;
    queue->rear = 0;
}

// 入队
void enQueue (Queue *queue, int data) {
    if (queue->rear == MAX_LENGTH) exit(0); // 队满
    queue->arr[queue->rear++] = data;
//    ++(queue->len);
}

// 出队
void deQueue (Queue *queue, int *data) {
    if (queue->tail == queue->rear) exit(0); // 队空
    *data = queue->arr[queue->tail++];
//    --queue->len;
}

[luneshao]

优化基本入队操作，队列未满的情况迁移数组

入队优化（迁移数组）

void enQueue (Queue *queue, int data) {
    if (queue->rear == MAX_LENGTH && queue->tail == 0) exit(0); // 队满

    if (queue->rear == MAX_LENGTH && queue->tail != 0) {
        for (int i = queue->tail; i < MAX_LENGTH; ++i) {
            queue->arr[i - queue->tail] = queue->arr[i];
        }

        queue->rear = queue->rear - queue->tail;
        queue->tail = 0;
    }

    queue->arr[queue->rear++] = data;
}

[luneshao]

链式队列

初始化、入队、出队

#include <stdio.h>
typedef struct SNode {
    int data;
    struct SNode *next;
} Node, *NodePtr;

typedef struct LQueue {
    NodePtr head;
    NodePtr rear;
} Queue;

void initLQueue (Queue *queue);
void enLQueue (Queue *queue, int data);
void deLQueue (Queue *queue, int *data);

int main()
{
    int i;
    Queue queue;
    initLQueue(&queue);

    enLQueue(&queue, 1);
    enLQueue(&queue, 2);
    enLQueue(&queue, 3);
    deLQueue(&queue, &i);
    deLQueue(&queue, &i);
    printf("%d\n", queue.head->next->data);
}

// 初始化
void initLQueue (Queue *queue) {
    NodePtr s = (NodePtr)malloc(sizeof(Node));
    queue->head = s;
    queue->rear = s;
    queue->rear->next = NULL;
}

// 入队
void enLQueue (Queue *queue, int data) {
    NodePtr s = (NodePtr)malloc(sizeof(Node));
    if (!s) exit(0); // 内存分配失败
    s->data = data;
    s->next = NULL;
    queue->rear->next = s;
    queue->rear = s;
}

// 出队
void deLQueue (Queue *queue, int *data) {
    if (queue->head == queue->rear) exit(0); // 队空
    *data = queue->head->next->data;
    queue->head->next = queue->head->next->next;
}

[luneshao]

循环队列

定义了 len 存储队列元素的长度。如果头指针、尾指针同时指向同一个位置时，依据长度是否等于 0 或 MAX_LENGTH 判断对空和队满状态。

入队时，用当前尾指针做下标存储数据，尾指针的下一个指向的下标为 (queue->rear+1) % MAX_LENGTH，实现循环。因为求模运算的结果始终小于 MAX_LENGTH。

出队时头指针的指向，同理。

#include <stdio.h>
#define MAX_LENGTH 5

typedef struct SQueue {
    int arr[MAX_LENGTH];
    int head; // 头指针
    int rear; // 尾指针
    int len;
} Queue;

void initSQueue (Queue *queue);
void enSQueue (Queue *queue, int data);
void deSQueue (Queue *queue, int *data);

int main()
{
    int i;
    Queue queue;
    initSQueue(&queue);

    enSQueue(&queue, 1);
    enSQueue(&queue, 2);
    enSQueue(&queue, 3);
    enSQueue(&queue, 4);
    enSQueue(&queue, 5);
    deSQueue(&queue, &i);
    enSQueue(&queue, 6);
//    deQueue(&queue, &i);
    printf("%d\n", queue.arr[--queue.rear]);
}

// 初始化
void initSQueue (Queue *queue) {
    queue->head = 0;
    queue->rear = 0;
    queue->len = 0;
}

// 入队
void enSQueue (Queue *queue, int data) {
    if (queue->rear == queue->head && queue->len == MAX_LENGTH) exit(0);

    queue->arr[queue->rear] = data;
    queue->rear = (queue->rear + 1) % MAX_LENGTH;
    ++queue->len;
}

// 出队
void deSQueue (Queue *queue, int *data) {
    if (queue->head == queue->rear && queue->len == 0) exit(0); // 队空
    *data = queue->arr[queue->head++];
    queue->head = (queue->head + 1) % MAX_LENGTH;
    --queue->len;
}