经典C++面试题程序

根据提供的文件信息，我们可以归纳出以下几个关键的C++知识点及相关代码示例： ### 1. 求最大公约数（GCD） ```cpp int commax(int m, int n) { int m_cup = m; int n_cup = n; int res = m_cup % n_cup; while (res != 0) { m_cup = n_cup; n_cup = res; res = m_cup % n_cup; } return n_cup; } ``` **知识点解析：** - **功能**: 该函数用于求解两个整数的最大公约数。 - **算法**: 使用辗转相除法，即欧几里得算法，这是一种非常高效的方法来计算两个正整数的最大公约数。 - **参数解释**: `m` 和 `n` 分别是输入的两个整数。 - **返回值**: 返回 `m` 和 `n` 的最大公约数。 ### 2. 字符串匹配查找子串 ```cpp char* comstr(char* lstr, char* sstr) { char* substr = (char*)malloc(256); if (strstr(lstr, sstr) != NULL) return sstr; for (int i = strlen(sstr) - 1; i > 0; i--) { for (int j = 0; j <= strlen(sstr) - i; j++) { memcpy(substr, &sstr[j], i); substr[i] = '\0'; if (strstr(lstr, substr) != NULL) return substr; } } return NULL; } ``` **知识点解析：** - **功能**: 查找字符串 `lstr` 中是否包含字符串 `sstr` 的子串，并返回最短的匹配子串。 - **实现**: 通过遍历所有可能的子串组合进行匹配。 - **参数解释**: `lstr` 是长字符串，`sstr` 是短字符串。 - **返回值**: 如果找到子串则返回匹配的子串指针，否则返回 `NULL`。 ### 3. 循环排序数组 ```cpp int main() { int a[] = {10, 6, 9, 5, 2, 8, 4, 7, 1, 3}; int len = sizeof(a) / sizeof(int); int temp; for (int i = 0; i < len;) { temp = a[a[i] - 1]; a[a[i] - 1] = a[i]; a[i] = temp; if (a[i] == i + 1) i++; } for (int j = 0; j < len; j++) cout << a[j]; return 0; } ``` **知识点解析：** - **功能**: 对数组进行循环排序。 - **算法**: 这种排序方法称为循环置换排序，其核心思想是将每个元素移动到它应该在的位置上。 - **参数解释**: 数组 `a` 包含待排序的整数。 - **返回值**: 输出排序后的数组。 ### 4. 字符串拼接 ```cpp char* strcat(char* des, char* rsc) { assert((*des != NULL) && (*rsc != NULL)); char* p = des; while (*des != '\0') des++; while (*rsc != '\0') { *des++ = *rsc++; } *des = '\0'; return p; } ``` **知识点解析：** - **功能**: 将字符串 `rsc` 拼接到字符串 `des` 的末尾。 - **实现**: 逐个字符复制直到遇到空字符 `\0`。 - **参数解释**: `des` 和 `rsc` 分别是要拼接的目标字符串和源字符串。 - **返回值**: 返回原始目标字符串 `des` 的起始地址。 ### 5. 链表操作 ```cpp Lnode* create(Lnode* head) { int n = 5; head->next = NULL; for (int i = n; i > 0; i--) { Lnode* p = new Lnode; scanf("%c", &p->data); p->next = head->next; head->next = p; } return head; } void reserve(Lnode* head) { Lnode* q = head->next; head->next = NULL; while (q) { Lnode* p = q->next; q->next = head->next; head->next = q; q = p; } } ``` **知识点解析：** - **功能**: 创建链表并反转链表。 - **创建**: 通过逐个添加节点到链表头部来构建链表。 - **反转**: 遍历原链表，将每个节点链接到新的头结点之前。 - **参数解释**: `head` 是链表的头结点。 - **返回值**: `create` 函数返回新创建的链表的头结点。 ### 6. 二叉树操作 ```cpp typedef struct node { char data; struct node* lchild, * rchild; } treenode; treenode* creat_tree(); int leafnumber = 0; int depth = 0; treenode* creat_tree() { treenode* t; char c; c = getchar(); if ('#' == c) return NULL; else { t = (treenode*)malloc(sizeof(treenode)); t->data = c; t->lchild = creat_tree(); t->rchild = creat_tree(); } return t; } void preorder(treenode* p) { if (p != NULL) { printf("%c", p->data); preorder(p->lchild); preorder(p->rchild); } } void inorder(treenode* p) { if (p != NULL) { inorder(p->lchild); printf("%c", p->data); inorder(p->rchild); } } void postorder(treenode* p) { if (p != NULL) { postorder(p->lchild); postorder(p->rchild); printf("%c", p->data); } } void countleaf(treenode* t) { if (t != NULL) { c // 此处代码缺失 } } ``` **知识点解析：** - **功能**: 构建二叉树、前序遍历、中序遍历、后序遍历以及计数叶子节点数量。 - **构建**: 通过递归的方式构建二叉树。 - **遍历**: 前序、中序和后序遍历分别按照“根左右”、“左根右”和“左右根”的顺序访问树的节点。 - **计数叶子节点**: 通过递归方式统计二叉树中叶子节点的数量。 - **参数解释**: `treenode` 定义了二叉树节点的结构；`p` 是指向树节点的指针。 - **返回值**: `creat_tree` 返回创建好的二叉树的根节点。