字符串采用带头结点的链表存储,编写函数LinkString Index(LinkString s,LinkString t),查找子串t在主串s中第一次出现的位置,若匹配不成功,则返回NULL。 C语言
时间: 2024-10-13 10:14:02 浏览: 30
在C语言中,你可以使用链表结构来表示字符串,并设计一个`Index`函数来查找子串`t`在主串`s`中的首次出现位置。这里首先需要定义链表节点结构,然后遍历主串,对每个可能的子串起始位置进行匹配。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
char data;
struct Node* next;
} ListNode;
// 链表初始化
ListNode* createNode(char c) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = c;
newNode->next = NULL;
return newNode;
}
// 将字符串转换为链表
ListNode* stringToLinkedList(char* str) {
ListNode* head = NULL, *current = NULL;
for (int i = 0; str[i] != '\0'; ++i) {
head = current = createNode(str[i]);
current->next = head;
}
return head;
}
// 搜索子串,找到匹配并返回索引
int indexOfSubstring(ListNode* s, ListNode* t) {
int lenT = 0, lenS = 0;
while (t && t->next) { // 计算子串长度
lenT++;
t = t->next;
}
ListNode* sTemp = s, *tTemp = t;
for (lenS = 0; sTemp && lenS < lenT; ++lenS) {
if (sTemp->data == tTemp->data) {
tTemp = tTemp->next;
} else {
sTemp = sTemp->next;
}
}
if (tTemp == NULL) { // 匹配失败,返回NULL
return NULL;
} else {
return lenS; // 匹配成功,返回子串起始位置
}
}
// 测试函数
void test() {
char s[] = "Hello, World!";
char t[] = "World";
ListNode* sList = stringToLinkedList(s);
ListNode* tList = stringToLinkedList(t);
int result = indexOfSubstring(sList, tList);
if (result == NULL) {
printf("Substring not found.\n");
} else {
printf("Substring found at position %d.\n", result);
}
}
int main() {
test();
return 0;
}
```
在这个示例中,`indexOfSubstring`函数通过比较两个链表中的字符来查找子串。如果找到匹配,它会返回子串的起始位置;如果没有找到,函数将返回`NULL`。
阅读全文