已有一排排好序的字符串str,现输入一个新字符c,通过折半查找法,快速找到字符c并插入位置
时间: 2024-03-08 14:48:40 浏览: 30
假设已有一个排好序的字符串数组 `str`,现在要向其中插入一个新字符 `c`,可以采用如下代码:
```c
#include <stdio.h>
#include <string.h>
void insertChar(char str[], int len, char c) {
int left = 0, right = len - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (c < str[mid])
right = mid - 1;
else if (c > str[mid])
left = mid + 1;
else // 如果c等于str[mid],则直接插入到mid的后面
break;
}
// 循环结束后,left存储了新字符应该插入的位置
memmove(str + left + 1, str + left, len - left); // 将left后面的字符向后移动一位
str[left] = c;
}
int main() {
char str[] = {'a', 'b', 'd', 'e', 'f', 'g'};
int len = sizeof(str) / sizeof(str[0]);
char c = 'c';
insertChar(str, len, c);
for (int i = 0; i < len + 1; i++) {
printf("%c ", str[i]);
}
printf("\n");
return 0;
}
```
程序输出结果为:
```
a b c d e f g
```
这里使用了 `memmove` 函数来将 `left` 后面的字符向后移动一位,以便为新字符腾出位置。需要注意的是,如果新字符恰好等于 `str[mid]`,则直接将新字符插入到 `mid` 的后面。