请帮我用c语言写一段链表匹配的代码,以下是背景和要求。 已知两个由正整数组成的无序序列A、B,每个序列的元素个数未知,但至少有一个元素。你的任务是判断序列B是否是序列A的连续子序列。假设B是“1 9 2 4 18”,A是“33 64 1 9 2 4 18 7”,B是A的连续子序列;假设B是“1 9 2 4 18”,A是“33 1 9 64 2 4 18 7”,B不是A的连续子序列。 要求:建立两个单链表A、B用于存储两个正整数序列,然后按照题目的要求,判断链表B是否是链表A的连续子序列。正整数的输入用-1作为结束标志,注意-1不算这个正整数序列中的元素(不要统计-1)。在程序结束前要释放链表A、B中的所有节点。
时间: 2024-01-22 22:21:07 浏览: 71
下面是链表匹配的C语言代码,注释已经详细解释了每一步的操作:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct node {
int data;
struct node *next;
} Node;
// 定义链表结构体
typedef struct list {
Node *head;
Node *tail;
} List;
// 初始化链表
void initList(List *lst) {
lst->head = NULL;
lst->tail = NULL;
}
// 添加节点到链表尾部
void addNode(List *lst, int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (lst->head == NULL) {
lst->head = newNode;
lst->tail = newNode;
} else {
lst->tail->next = newNode;
lst->tail = newNode;
}
}
// 释放链表中所有节点
void freeList(List *lst) {
Node *cur = lst->head;
Node *next;
while (cur != NULL) {
next = cur->next;
free(cur);
cur = next;
}
}
// 判断链表B是否是链表A的连续子序列
int match(List *lstA, List *lstB) {
Node *curA = lstA->head;
Node *curB = lstB->head;
int flag = 0;
while (curA != NULL) {
// 如果链表A当前节点的值和链表B当前节点的值相等
if (curA->data == curB->data) {
flag = 1;
// 判断链表B是否已经匹配完毕
if (curB->next == NULL) {
return 1;
}
curB = curB->next;
} else {
// 如果链表B已经匹配了一部分,但是当前节点的值不相等
// 则重置curA和curB,并将flag设为0
if (flag == 1) {
curA = curA - (lstB->head - curB);
curB = lstB->head;
flag = 0;
}
}
curA = curA->next;
}
return 0;
}
int main() {
List lstA, lstB;
int num;
// 初始化链表A和链表B
initList(&lstA);
initList(&lstB);
// 输入链表A中的元素,以-1结束
printf("Input elements of list A (end with -1): ");
scanf("%d", &num);
while (num != -1) {
addNode(&lstA, num);
scanf("%d", &num);
}
// 输入链表B中的元素,以-1结束
printf("Input elements of list B (end with -1): ");
scanf("%d", &num);
while (num != -1) {
addNode(&lstB, num);
scanf("%d", &num);
}
// 判断链表B是否是链表A的连续子序列
if (match(&lstA, &lstB)) {
printf("List B is a continuous subsequence of list A.\n");
} else {
printf("List B is not a continuous subsequence of list A.\n");
}
// 释放链表A和链表B中的所有节点
freeList(&lstA);
freeList(&lstB);
return 0;
}
```
阅读全文