用C语言写一个next数组的代码

以下是一个简单的用C语言实现next数组的代码：

void getNext(char* pattern, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (pattern[i]) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

其中，`pattern`为要匹配的模式串，`next`为存储next数组的数组。运行该函数后，`next`数组中存储的就是`pattern`的next数组。

相关问题

用C语言写一段用数组的链表代码

由于“数组的链表”一词理解起来有些困难，这里我提供两个数组相关的链表代码。

1. 数组实现的链表

这种链表的实现方式是使用一个指针数组和一个可用位置的指针来表示链表。节点的数据存放在数组中，通过数组下标来访问。链表的头节点指针指向第一个可用位置的指针，链表的尾节点指针指向最后一个非可用位置的指针。

#define MAX_NODE 100

int data[MAX_NODE];
int next[MAX_NODE];
int head;
int tail;
int free_pos;

void init() {
    for (int i = 0; i < MAX_NODE; i++) {
        next[i] = i + 1;
    }
    next[MAX_NODE - 1] = -1;
    free_pos = 0;
    head = -1;
    tail = -1;
}

int allocate_node() {
    if (free_pos == -1) {
        return -1;  // 标记无可用节点
    }
    int pos = free_pos;
    free_pos = next[pos];
    return pos;
}

void free_node(int pos) {
    next[pos] = free_pos;
    free_pos = pos;
}

void insert(int val) {
    int pos = allocate_node();
    if (pos == -1) {
        return;  // 链表已满
    }
    data[pos] = val;
    next[pos] = -1;
    if (head == -1) {
        head = pos;
    } else {
        next[tail] = pos;
    }
    tail = pos;
}

void remove(int val) {
    int curr = head;
    int prev = -1;
    while (curr != -1 && data[curr] != val) {
        prev = curr;
        curr = next[curr];
    }
    if (curr == -1) {
        return;  // 没有找到值为val的节点
    }
    if (prev == -1) {
        head = next[curr];
    } else {
        next[prev] = next[curr];
    }
    free_node(curr);
}

void show() {
    int curr = head;
    while (curr != -1) {
        printf("%d ", data[curr]);
        curr = next[curr];
    }
    printf("\n");
}

2. 动态数组实现的链表

这种链表的实现方式是使用动态数组，数组中的元素是节点指针，每个节点指针指向一个节点。链表的头节点指针指向第一个节点，链表的尾节点指针指向最后一个节点。当链表需要扩容时，动态数组会重新分配更大的内存，并将原有元素复制到新的内存中。

#include <stdlib.h>

typedef struct node_t {
    int val;
    struct node_t* next;
} node_t;

int size;
int capacity;
node_t** nodes;

void init() {
    size = 0;
    capacity = 1;
    nodes = (node_t**)malloc(capacity * sizeof(node_t*));
    nodes[0] = NULL;
}

void insert(int val) {
    node_t* node = (node_t*)malloc(sizeof(node_t));
    node->val = val;
    node->next = NULL;
    nodes[size] = node;
    size++;
    if (size == capacity) {
        capacity *= 2;
        nodes = (node_t**)realloc(nodes, capacity * sizeof(node_t*));
    }
    if (size == 1) {
        nodes[0] = node;
    } else {
        nodes[size - 2]->next = node;
    }
}

void remove(int val) {
    node_t* curr = nodes[0];
    node_t* prev = NULL;
    while (curr != NULL && curr->val != val) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL) {
        return;  // 没有找到值为val的节点
    }
    if (prev == NULL) {
        nodes[0] = curr->next;
    } else {
        prev->next = curr->next;
    }
    free(curr);
    size--;
    if (size <= capacity / 2) {
        capacity /= 2;
        nodes = (node_t**)realloc(nodes, capacity * sizeof(node_t*));
    }
}

void show() {
    node_t* curr = nodes[0];
    while (curr != NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

用c语言实现next数组

好的，关于用C语言实现next数组，我可以提供一些基本的思路。next数组是用来描述一个字符串的最长相同前缀和后缀的长度，通常用于字符串匹配算法中，比如KMP算法。具体实现时，可以通过两个指针i和j从头开始遍历字符串，同时维护一个next数组。如果当前字符匹配成功，则i和j同时向后移动，如果匹配失败，则i不变，j移动到next[j]的位置，这里的next[j]表示j的前缀字符串的最长相同前缀和后缀的长度。

具体代码实现如下：

void getNext(char* p, int* next) {
    int len = strlen(p);
    int j = 0, k = -1;
    next[0] = -1;
    while (j < len - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++j;
            ++k;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

这段代码实现了getNext函数，用来生成next数组。其中p表示给定的字符串，next表示生成的next数组。