习题课：数组、指针、字符串

《计算机程序设计》

苏醒

计算机学院计算机研究所编译系统研究室

逻辑或运算

编程实现

已知a、b是两个01串，则规定a和b进行“逻辑或”运算的过程为：

  • 若a、b位数不相同，需在位数较少者的前面补0，使其位数相同；
  • 将a、b按位对齐，逐位运算，某位运算规则为：若两位全为0则在结果中该位为0，否则为1。

例如，a为”0100111”、b为”10010101”时，a先在高位补0，变为”00100111”，然后两者计算得”10110111”。

补全函数void OR(char *a, char *b, char *c)代码，其中，参数a、b长度不超过20，将a、b逻辑或结果存在c中。

注意：若计算结果c的高位是’0’，注意保留，不要省去。

逻辑或运算
#include <iostream>
#include <cstring>
using namespace std;
#define LEN 21
void OR(char* a, char* b, char* c) {
  /********Program********/


  /********  End  ********/
}
逻辑或运算
int main() {
  char a[LEN] = "";
  char b[LEN] = "";
  char c[LEN] = "";
  cin >> a;
  cin >> b;
  OR(a, b, c);
  cout << c << endl;
  return 0;
}

逻辑或运算

提示

本题可能用到的字符串函数如下：

  • int strlen(char *s);返回字符串s的长度
  • char *strcpy(char *s1, char *s2);把字符串s2复制到s1，返回s1
  • char *strcat(char *s1, char *s2);把字符串s2拼接到s1后面，返回s1
  • int strcmp(char *s1, char *s2);比较字符串s1和s2的大小，相等时返回0
逻辑或运算
void OR(char* a, char* b, char* c) {








}

逻辑或运算

提示

本题可能用到的字符串函数如下：

  • int strlen(char *s);返回字符串s的长度
  • char *strcpy(char *s1, char *s2);把字符串s2复制到s1，返回s1
  • char *strcat(char *s1, char *s2);把字符串s2拼接到s1后面，返回s1
  • int strcmp(char *s1, char *s2);比较字符串s1和s2的大小，相等时返回0
逻辑或运算：解法1
void OR(char* a, char* b, char* c) {
  int al = strlen(a), bl = strlen(b);
  int len = al > bl ? al : bl;
  char acopy[len+1] = {0}, bcopy[len+1] = {0};
  strcpy(acopy + len - al, a);
  strcpy(bcopy + len - bl, b);
  for (int i = 0; i < len; i++)
    c[i] = (acopy[i] == '0' and bcopy[i] == '0' ? '0' : '1');
  c[len] = '\0';
}

逻辑或运算

提示

本题可能用到的字符串函数如下：

  • int strlen(char *s);返回字符串s的长度
  • char *strcpy(char *s1, char *s2);把字符串s2复制到s1，返回s1
  • char *strcat(char *s1, char *s2);把字符串s2拼接到s1后面，返回s1
  • int strcmp(char *s1, char *s2);比较字符串s1和s2的大小，相等时返回0
逻辑或运算：解法2
void OR(char* a, char* b, char* c) {
  int al = strlen(a), bl = strlen(b);
  int len = al > bl ? al : bl;
  char *atail = a + al - 1;
  char *btail = b + bl - 1;
  char *ctail = c + len - 1;
  while (ctail >= c) {
    char ac = (atail >= a) ? *atail : '0';
    char bc = (btail >= b) ? *btail : '0';
    *ctail = (ac == '0' && bc == '0') ? '0' : '1';
    atail--;
    btail--;
    ctail--;
  }
}

字符串比较

编程实现

完成函数int compareString(char a[], char b[])，参数a和b是2个长度相等的仅由大小写字母组成的字符串，该函数比较字符串a和b并返回比较结果，它们之间的关系是以下3种情况之一：

  • 1：两个字符串相应位置上的字符完全一致(区分大小写)，比如Beijing 和Beijing；
  • 2：两个字符串相应位置上的字符仅在不区分大小写的前提下完全一致（即并不满足情况1），比如beijing 和BEIjing；
  • 3：两个字符串即使是不区分大小写也不能一致。比如Beijing 和Nanjing。

提示：大写字母的ASCII码比相应的小写字母的ASCII码小32

字符串比较
#include <iostream>
using namespace std;
#define STR_LEN 81
int compareString(char a[], char b[]) {
    /********Program********/
    /********  End  ********/
}
int main() {
    char a[STR_LEN], b[STR_LEN];
    cin >> a >> b;
    cout << compareString(a, b) << endl;
    return 0;
}

字符串比较

字符串比较
int compareString(char a[], char b[]) {
  char *pa = a, *pb = b;
  int result = 1;
  while (*pa) {








  }
  return result;
}

字符串比较

字符串比较
int compareString(char a[], char b[]) {
  char *pa = a, *pb = b;
  int result = 1;
  while (*pa) {
    if (*pa != *pb) {
      if (*pa - *pb == 32 || *pb - *pa == 32)
        result = 2;
      else
        return 3;
    }
    pa++;
    pb++;
  }
  return result;
}

考考你

更改题目要求，要求支持比较长度不同的字符串，若字符串长度不同则返回4，应该如何更改程序？

行程编码

编程实现

行程编码是一种简单有效的压缩算法，它可将连续的重复字符压缩成“重复次数+字符”的形式，从而减少存储开销。例如，“AAAABBCDEE”压缩后为“4A2B1C1D2E”，“aaaBCCeFF”压缩后为“3a1B2C1e2F”。 完成函数run_length_coding(char *src, char *dst)，功能是按行程编码算法压缩字符串，其中参数src是待压缩的字符串（仅包含字母），压缩后的结果保存在参数dst中。

行程编码
#include <iostream>
#include <string>
using namespace std;
void run_length_coding(char* src, char* dst) {
  /**********Program**********/
  /********** End **********/
}
int main() {
  char s[1000], t[1000];
  cout << "请输入一个字符串:";
  cin >> s;
  run_length_coding(s, t);
  cout << "压缩结果为:" << t << endl;
  return 0;
}

行程编码

提示

提示：可能用到的字符串函数说明如下

  • sprintf(char *str, const char *format, …);发送格式化输出到str所指向的字符串，并返回打印的字符数。
行程编码
void run_length_coding(char* src, char* dst) {










}

行程编码

提示

提示：可能用到的字符串函数说明如下

  • sprintf(char *str, const char *format, …);发送格式化输出到str所指向的字符串，并返回打印的字符数。
行程编码
void run_length_coding(char* src, char* dst) {
  char *pdst = dst;
  int count = 1;
  for (char *psrc = src; *psrc; psrc++) {
    if (*psrc == *(psrc + 1)) {
      count++;
    } else {
      pdst += sprintf(pdst, "%d%c", count, *psrc);
      count = 1;
    }
  }
}

考考你

如果你不会使用sprintf函数，怎么办？

抽取整数

编程实现

完成函数digit(char str[])，其功能是抽取字符串str中的数字，用抽取到的数字组成整数，并返回该整数。 字符串str中可能包含小写英文字母和数字字符0-9，函数digit只抽取其中的数字字符组成整数。

如str为”asd123fgh34sxc1”，则抽取到的数字组成的整数为123341，请完成该函数的编写。

说明：测试用例保证不会发生整数越界。

抽取整数
#include <iostream>
using namespace std;
int digit(char str[]) {
  /**********Program**********/
  /********** End **********/
}
int main() {
  char s[1000];
  cin >> s;
  cout << digit(s) << endl;
  return 0;
}
asd123fgh34sxc1  # 输入
123341           # 输出

抽取整数

抽取整数
int digit(char str[]) {
  int result = 0;
  for (char *p = str; *p; p++) {
    if (*p >= '0' && *p <= '9') {
      result = result * 10 + *p - '0';
    }
  }
  return result;
}

计算机程序设计