假设以单链表结构表示串,每个结点数据域存放一个字符,且附设头结点。试编写算法,实现串的下列 基本操作: StrAsign(S,chars);StrCopy(S.T) ;StrCompare(S.T) :StrLength(S); StrCat(S.T);SubString( Sub,S,pos,len)。
时间: 2023-06-08 17:04:49 浏览: 129
好的,我可以帮你回答这个问题。
以下是每个操作的具体实现:
1. StrAsign(S, chars): 将字符串 chars 赋给 S,即把 chars 中的字符逐个赋给 S 的单链表结构,且最后一个结点的 next 指针为 NULL。
2. StrCopy(S.T): 将字符串 T 复制到串 S 中,即先清空 S 中原有内容,然后把 T 的字符逐个赋给 S 中的结点。
3. StrCompare(S.T): 比较串 S 和串 T 的大小。从两个串的第一个字符开始比较,如果相同,继续比较下一个字符,直到有不同的字符出现,或一个串已经比较完。如果两个串完全相同,则返回 0,如果 S>T,则返回 1,如果 S<T,则返回 -1。
4. StrLength(S): 返回串 S 的长度,即单链表结构中结点的个数(不包括头结点)。
5. StrCat(S.T): 将串 T 拼接到串 S 的末尾,即找到 S 中最后一个结点,然后把 T 的字符逐个赋给新的结点。
6. SubString(Sub, S, pos, len): 截取 S 中从 pos 开始的 len 个字符,并把结果存储在 Sub 中。需要遍历 S 中的结点,找到第 pos 个结点,然后把后面的 len 个字符逐个赋给 Sub 中的结点。注意,pos 和 len 都是从 1 开始计数的。
希望这些操作能够帮助到你。如果还有其他问题,可以继续问我。
相关问题
4假设以单链表结构表示串,每个结点数据域存放一个字符,且附设头结点。试编写算法,实现串的下列 StrAsign(S,chars) ;StrCopy(S,T) ;StrCompare( s, T) ;StrLength(S); StrCat(S, T) ;SubString( Sub ,S,pos,len)。
1. 实现 StrAssign(S, chars) 函数,将一个字符数组 chars 赋值给链式串 S。
```
void StrAssign(LinkList &S, char *chars) {
LinkList p = S->next;
int i = 0;
while (p != NULL) {
LinkList q = p;
p = p->next;
free(q);
}
S->next = NULL;
while (chars[i] != '\0') {
LinkList node = (LinkList)malloc(sizeof(LNode));
node->data = chars[i];
node->next = S->next;
S->next = node;
i++;
}
}
```
2. 实现 StrCopy(S, T) 函数,将链式串 T 复制到链式串 S。
```
void StrCopy(LinkList &S, LinkList &T) {
LinkList p = T->next, q = S;
while (p != NULL) {
LinkList node = (LinkList)malloc(sizeof(LNode));
node->data = p->data;
node->next = NULL;
q->next = node;
q = q->next;
p = p->next;
}
}
```
3. 实现 StrCompare(S, T) 函数,比较链式串 S 和 T 的大小关系。
```
int StrCompare(LinkList S, LinkList T) {
LinkList p = S->next, q = T->next;
while (p != NULL && q != NULL) {
if (p->data > q->data) {
return 1;
} else if (p->data < q->data) {
return -1;
}
p = p->next;
q = q->next;
}
if (p == NULL && q == NULL) {
return 0;
} else if (p == NULL) {
return -1;
} else {
return 1;
}
}
```
4. 实现 StrLength(S) 函数,返回链式串 S 的长度。
```
int StrLength(LinkList S) {
int len = 0;
LinkList p = S->next;
while (p != NULL) {
len++;
p = p->next;
}
return len;
}
```
5. 实现 StrCat(S, T) 函数,将链式串 T 连接到链式串 S 的末尾。
```
void StrCat(LinkList &S, LinkList &T) {
LinkList p = S;
while (p->next != NULL) {
p = p->next;
}
LinkList q = T->next;
while (q != NULL) {
LinkList node = (LinkList)malloc(sizeof(LNode));
node->data = q->data;
node->next = NULL;
p->next = node;
p = p->next;
q = q->next;
}
}
```
6. 实现 SubString(Sub, S, pos, len) 函数,将链式串 S 中从 pos 位置开始的 len 个字符复制到链式串 Sub 中。
```
void SubString(LinkList &Sub, LinkList S, int pos, int len) {
LinkList p = S->next;
int i = 1;
while (p != NULL && i < pos) {
p = p->next;
i++;
}
LinkList q = Sub;
for (int j = 0; j < len && p != NULL; j++) {
LinkList node = (LinkList)malloc(sizeof(LNode));
node->data = p->data;
node->next = NULL;
q->next = node;
q = q->next;
p = p->next;
}
}
```
注意,在这些函数的实现中,我们都使用了链表的基本操作,如链表的遍历、插入、删除等。同时,需要注意对链表的头结点进行特殊处理。
假设以单链表结构表示串,每个结点数据域存放一个字符,且附设头结点。编写算法,实现串的下列操作:StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);StrCat(S,T);SubString(Sun,S,pos,len)。C语言
下面是基于单链表结构实现串操作的算法,注意代码中的注释。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义链表结点
typedef struct ListNode {
char data;
struct ListNode *next;
} ListNode;
// 定义头结点
typedef struct {
ListNode *head;
int length;
} LString;
// 初始化串
void StrAssign(LString *S, char *chars) {
// 新建头结点
S->head = (ListNode *)malloc(sizeof(ListNode));
S->head->next = NULL;
S->length = 0;
// 如果 chars 不为空,则将每个字符插入到链表中
if (chars != NULL) {
ListNode *p = S->head;
while (*chars != '\0') {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = *chars;
node->next = NULL;
p->next = node;
p = node;
chars++;
S->length++;
}
}
}
// 复制串 T 到 S 中
void StrCopy(LString *S, LString *T) {
ListNode *p = T->head->next;
// 如果 T 不为空,则将其每个字符插入到 S 中
while (p != NULL) {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = p->data;
node->next = NULL;
S->head->next = node;
S->length++;
p = p->next;
}
}
// 比较串 S 和 T 的大小关系
int StrCompare(LString *S, LString *T) {
ListNode *p = S->head->next;
ListNode *q = T->head->next;
// 逐个比较 S 和 T 的每个字符,直到出现不相等或其中一个串遍历结束
while (p != NULL && q != NULL) {
if (p->data < q->data) {
return -1;
} else if (p->data > q->data) {
return 1;
}
p = p->next;
q = q->next;
}
if (p == NULL && q == NULL) {
return 0;
} else if (p == NULL) {
return -1;
} else {
return 1;
}
}
// 返回串 S 的长度
int StrLength(LString *S) {
return S->length;
}
// 将 T 串连接到 S 的末尾
void StrCat(LString *S, LString *T) {
ListNode *p = S->head;
// 找到 S 的最后一个结点
while (p->next != NULL) {
p = p->next;
}
ListNode *q = T->head->next;
// 将 T 的每个字符插入到 S 的末尾
while (q != NULL) {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = q->data;
node->next = NULL;
p->next = node;
p = node;
S->length++;
q = q->next;
}
}
// 返回从字符串 S 的 pos 位置开始的 len 个字符组成的子串
void SubString(LString *Sub, LString *S, int pos, int len) {
// 如果 pos 不合法,则返回空串
if (pos < 1 || pos > S->length || len < 0 || pos + len - 1 > S->length) {
Sub->head = (ListNode *)malloc(sizeof(ListNode));
Sub->head->next = NULL;
Sub->length = 0;
return;
}
// 找到从 pos 开始的结点
ListNode *p = S->head->next;
for (int i = 1; i < pos; i++) {
p = p->next;
}
// 将 pos 开始的 len 个字符插入到 Sub 中
ListNode *q = p;
Sub->head = (ListNode *)malloc(sizeof(ListNode));
Sub->head->next = NULL;
Sub->length = 0;
for (int i = 0; i < len; i++) {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = q->data;
node->next = NULL;
Sub->head->next = node;
Sub->length++;
q = q->next;
}
}
int main() {
LString S, T, Sub;
char *s = "hello";
char *t = "world";
char *sub = "llo";
StrAssign(&S, s);
StrAssign(&T, t);
StrAssign(&Sub, sub);
printf("S: ");
ListNode *p = S.head->next;
while (p != NULL) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
printf("T: ");
p = T.head->next;
while (p != NULL) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
printf("Sub: ");
p = Sub.head->next;
while (p != NULL) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
printf("StrCompare(S, T): %d\n", StrCompare(&S, &T));
printf("StrLength(S): %d\n", StrLength(&S));
StrCat(&S, &T);
printf("StrCat(S, T): ");
p = S.head->next;
while (p != NULL) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
SubString(&Sub, &S, 3, 5);
printf("SubString(S, 3, 5): ");
p = Sub.head->next;
while (p != NULL) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)