数据结构实验：next数组

在字符串匹配算法中，next数组是一个非常重要的数据结构。它是用来表示模式串中每个位置之前的子串中前缀和后缀的最长公共部分的长度。具体来说，设模式串为p，p的长度为m。则next数组的长度为m，第i个位置的值表示p中以第i个字符结尾的子串的前缀和后缀的最长公共部分的长度。

next数组的计算方法是基于动态规划的思想。具体来说，我们可以先将next[0]和next[1]设置为0，然后从第二个位置开始，依次计算每个位置的值。计算方法如下：

1. 如果i=0，则直接令next[0]=-1。
2. 如果i=1，则直接令next[1]=0。
3. 如果i>1，则令j=next[i-1]，然后不断往前找next[j]，直到找到一个位置k，使得p[i-1]=p[k]。此时，next[i]=j+1。如果一直找到了p[0]仍然没有找到符合条件的k，则令next[i]=0。

计算完next数组之后，我们就可以利用它来进行字符串匹配了。具体来说，我们可以将模式串p和文本串t从左到右依次比较，如果p和t的某个位置不匹配，就根据next数组中的值将模式串p向右移动一定的距离，然后再和文本串t的当前位置比较。这样，我们就可以用O(m+n)的时间复杂度完成字符串匹配的过程。

相关问题

数据结构实验约瑟夫环

约瑟夫环是一个经典的问题，它的基本形式是：n个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，直到所有人出圈为止。在数据结构中，可以使用链表或数组来实现约瑟夫环。

以下是使用链表实现约瑟夫环的示例代码：

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

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

void createList(LinkList *L, int n) {
    *L = (LinkList) malloc(sizeof(Node));
    (*L)->next = *L;
    Node *p = *L;
    for (int i = 1; i <= n; i++) {
        Node *newNode = (Node *) malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = p->next;
        p->next = newNode;
        p = p->next;
    }
}

void josephus(LinkList L, int m) {
    Node *p = L;
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            p = p->next;
        }
        Node *q = p->next;
        printf("%d ", q->data);
        p->next = q->next;
        free(q);
    }
    printf("%d\n", p->data);
}

int main() {
    int n = 7, m = 3;
    LinkList L;
    createList(&L, n);
    josephus(L, m);
    return 0;
}

数据结构舞伴问题实验

舞伴问题是一个经典的队列应用问题，主要涉及到队列的操作和模拟。根据引用和引用提供的信息，我们可以进行如下的实验演示：

1. 首先，我们需要创建两个队列，分别表示男士队和女士队。可以使用数组或链表来实现队列。

2. 接下来，我们需要将男士和女士依次加入到各自的队列中。可以通过循环读取输入的方式来实现。

3. 然后，我们需要模拟舞伴配对的过程。可以使用一个循环来模拟，每次从男士队和女士队的队头各取出一个人作为舞伴。

4. 如果两个队列的长度不相等，说明有人未配对，需要将未配对的人重新放回队列中，等待下一轮舞曲。

5. 最后，我们可以输出每一轮舞伴配对的结果，以及最终未配对的人数。

以下是一个简单的C语言实现的舞伴问题的代码示例：

#include <stdio.h>

#define MAX_SIZE 100

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

void initQueue(Queue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

int isEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

void enqueue(Queue *queue, int value) {
    if ((queue->rear + 1) % MAX_SIZE == queue->front) {
        printf("Queue is full.\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
}

int dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE;
    return value;
}

void dancePartner(Queue *maleQueue, Queue *femaleQueue) {
    int round = 1;
    while (!isEmpty(maleQueue) && !isEmpty(femaleQueue)) {
        int male = dequeue(maleQueue);
        int female = dequeue(femaleQueue);
        printf("Round %d: Male %d and Female %d are partners.\n", round, male, female);
        round++;
    }
    if (!isEmpty(maleQueue)) {
        printf("There are %d males waiting for the next round.\n", maleQueue->rear - maleQueue->front);
    }
    if (!isEmpty(femaleQueue)) {
        printf("There are %d females waiting for the next round.\n", femaleQueue->rear - femaleQueue->front);
    }
}

int main() {
    Queue maleQueue, femaleQueue;
    initQueue(&maleQueue);
    initQueue(&femaleQueue);

    // 依次将男士和女士加入队列
    enqueue(&maleQueue, 1);
    enqueue(&maleQueue, 2);
    enqueue(&maleQueue, 3);
    enqueue(&femaleQueue, 4);
    enqueue(&femaleQueue, 5);
    enqueue(&femaleQueue, 6);

    dancePartner(&maleQueue, &femaleQueue);

    return 0;
}