算法-在字符串中删除特定的字符或字符串
⾯试中经常会考到算法，下⾯分别讲如何删除⼀个字符串⾥的特定字符或特定字符串
⼀、
题⽬：输⼊两个字符串，从第⼀字符串中删除第⼆个字符串中所有的字符。
例如，输⼊”i want to be a excellent programmers”和”aem”，则删除之后的第⼀个字符串变成”i wnt to b  xcllnt progrrs"
分析：要编程完成这道题要求的功能可能并不难。毕竟，这道题的基本思路就是在第⼀个字符串中拿到⼀个字符，在第⼆个字符串中查⼀下，看它是不是在第⼆个字符串中。如果在的话，就从第⼀个字符串中删除。但如何能够把效率优化到让⼈满意的程度，却也不是⼀件容易的事情。也就是说，如何在第⼀个字符串中删除⼀个字符，以及如何在第⼆字符串中查⼀个字符，都是需要⼀些⼩技巧的。
⾸先我们考虑如何在字符串中删除⼀个字符。由于字符串的内存分配⽅式是连续分配的。我们从字符串当中删除⼀个字符，需要把后⾯所有的字符往前移动⼀个字节的位置。但如果每次删除都需要移动字符串后⾯的字符的话，对于⼀个长度为 n 的字符串⽽⾔，删除⼀个字符的时间复杂度为 O(n)。⽽对于本题⽽⾔，有可能要删除的字符的个数是 n，因此该⽅法就删除⽽⾔的时间复杂度为 O(n2)。
事实上，我们并不需要在每次删除⼀个字符的时候都去移动后⾯所有的字符。我们可以设想，当⼀个字符需要被删除的时候，我们把它所占的位置让它后⾯的字符来填补，也就相当于这个字符被删除了。在具体实现中，我们可以定义两个指针(psou和 pkey)，初始的时候都指向第⼀字符的起始位置。当 psou 指向的字符是需要删除的字符，则 psou 直接跳过，指向下⼀个字符。如果 psou 指向的字符是不需要删除的字符，那么把 psou 指向的字符赋值给 pkey 指向的字符，并且 psou 和 pkey同时向后移动指向下⼀个字符。这样，前⾯被psou 跳过的字符相当于被删除了。⽤这种⽅法，整个删除在 O(n)时间内就可以完成。
接下来我们考虑如何在⼀个字符串中查⼀个字符。当然，最简单的办法就是从头到尾扫描整个字符串。显然，这种⽅法需要⼀个循环，对于⼀个长度为 n 的字符串，时间复杂度是 O(n)。由于字符的总数是有限的。对于⼋位的 char 型字符⽽⾔，总共只有 28=256 个字符。我们可以新建⼀个⼤⼩为 256 的数组，把所有元素都初始化为 0。然后对于字符串中每⼀个字符，把它的 ASCII 码映射成索引，把数组中该索引对应的元素设为１。这个时候，要查⼀个字符就变得很快了：根据这个字符的 ASCII 码，在数组中对应的下标到该元素，如果为 0，表⽰字符串中没有该字符，否则字符串中包含该字符。此时，查⼀个字符的时间复杂度是 O(1)。其实，这个数组就是⼀个 hash 表。
基于上述分析，我们可以写出如下代码：
1#define _CRT_SECURE_NO_WARNINGS
2 #include <stdio.h>
3 #include <stdlib.h>
4
5char *  deleteStr(char *source, char *key)
6 {
7
8int hashTable[256];
9    memset(hashTable, 0, sizeof(hashTable));
10char *point_sou, *point_key;
11    point_sou = key;
12while (*point_sou != '\0')//待删除字符在哈希表⾥赋值为1
13    {
14        hashTable[*point_sou] = 1;
15        point_sou++;
16    }
17    point_sou = source;
18    point_key = source;
19while (*point_sou != '\0')
20    {
21if (!hashTable[*point_sou])//哈希表不为1时不是待删除字符，将sou指针指向的字符赋给key指针指向的字符，将两指针同时向后移
22        {
23            *point_key = *point_sou;
24            point_key++;
25        }
26        point_sou++;  //是待删除字符，sou指针继续向前移，key指针停留在待删除字符前
27//下⼀次循环判断是不是待删除字符，不是，将sou指针指向的字符赋给key指针指向的字符，souce也就相当于删除了前⾯的字符28
29    }
30    *point_key = '\0';
31return source;
32
33 }
34
35int main()
36 {
37char p[] = "i want to be a excellent programmers";
38char key[] = "aem";
39    printf("%s\n", deleteStr(p, key));
40 }
⼆、能够删除字符串中空格的函数是
问题描述：在给定字符串中查所有特定⼦串并删除，如果没有到相应⼦串，则不作任何操作。要求实现函数：int delete_sub_str(const char *str, const char *sub_str, char *result_str)
【输⼊】str：输⼊的被操作字符串  sub_str：需要查并删除的特定⼦字符串
【输出】result_str：在str字符串中删除所有sub_str⼦字符串后的结果
【返回】删除的⼦字符串的个数
1#define _CRT_SECURE_NO_WARNINGS
2 #include <stdio.h>
3 #include <stdlib.h>
4
5
6int Mysubstring(char* str_in, char* str_sub, char* str_out)
7 {
8int start = 0;    /* 记录开始⽐较下标 */
9int count = 0;    /* 记录⼦串个数 */
10int j = 0;        /* 记录⼦串的下标 */
11int k = 0;        /* 记录结果字符串的下标 */
12
13for (int i = 0; str_in[i] != '\0'; i++)
14    {
15        start = i;      /* 临时保存⽐较下标 */
16        j = 0;          /* 每次开始⽐较的时候，⼦串都从0开始，如果第⼀个字符相等，
17那么就接着⽐较下⼀个字符，否则进⼊下⼀轮循环 */
18
19while ((str_in[i] != '\0') && (str_sub[j] != '\0') && (str_in[i] == str_sub[j]))
20        {
21            i++;
22            j++;
23        }
24
25if (str_sub[j] != '\0')                /* 如果不是⼦串 */
26        {
27            str_out[k++] = str_in[start];  i = start;  /* 将当前⽐较的这个字符存⼊结果 */
28        }
29else/* 如果是⼦串 */
30        {
31            count++;
32            i--;          /* 因为返回for循环之后，进⾏下⼀次循环的时候还要进⾏i++的运算的 */
33        }
34    }
35
36return count;
37 }
38
39
40int main()
41 {
42char* str_in = "i want to be a excellent programmers ";
43char* str_sub = "want";
44char str_out[100] = { 0 };
45
46int  count = Mysubstring(str_in, str_sub, str_out);
47
48    printf("⼦串：%s\n", str_sub);
49    printf("个数：%d\n", count);
50    printf("原串：%s\n", str_in);
51    printf("结果：%s\n", str_out); 52
53return0;
54
55 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。