【C语言】初阶数据结构相关习题（一）

🎆个人主页：夜晚中的人海

今日语录：人的生命似洪水在奔流，不遇着岛屿、暗礁，难以激起美丽的浪花。——奥斯特洛夫斯基

文章目录

• ⭐一、判定是否互为字符重排
• 🎉二、 回文排列
• 🚀三、字符串压缩
• 🎡四、递归乘法
• 🏠五、取近似值
• 🏝️六、数列
• 🚆七、搜索插入位置
• 🚘八、搜索旋转排序数组
• 🏖️九、二进制链表转整数

⭐一、判定是否互为字符重排

题目描述：判定是否互为字符重排

解题思路：
1.首先判断两个字符串长度是否相等，若不相等，那么他们不可能彼此排列，直接返回false。

2.若字符串长度相等，我们就可以使用qsort函数对两个字符串进行排序来判断它们是否排列。

qsort 是标准库中的快速排序函数，它需要以下参数：
• 要排序的数组（s1 和 s2）。
• 数组的长度（len1 和 len2）。
• 每个元素的大小（sizeof(char)）。
• 比较函数（cmp）。

3.排序完成后，如果两个字符串是彼此的排列，那么它们排序后的结果应该完全相同，因此我们就可以使用strncmp函数来比较排序后的字符串。

代码实现：

int cmp(const void* a,const void* b){ return *(char*)a - *(char*)b;}bool CheckPermutation(char* s1, char* s2) { int len1 = strlen(s1); int len2 = strlen(s2); if(len1 != len2) { return false; } qsort(s1,len1,sizeof(char),cmp); qsort(s2,len2,sizeof(char),cmp); if(strncmp(s1,s2,len1) == 0) { return true; } return false;}

🎉二、 回文排列

题目描述：回文排列

解题思路：
1.我们首先要理解回文字符串的特性，一个字符串可以通过重新排列形成回文字符串的条件是：如果字符串长度为偶数，那么每个字符必须出现偶数次；如果字符串长度为奇数，那么最多只能有一个字符出现奇数次，其余字符必须出现偶数次。

2.我们使用一个大小为 128 的数组 a 来统计每个字符的出现次数（假设字符集为 ASCII，其范围为 0-127）。

3.遍历字符串 s，将每个字符的 ASCII 码值对应的数组位置加一。

4.遍历数组 a，统计出现次数为奇数的字符个数，如果某个字符的出现次数是奇数，则count 加一。

5.如果 count 大于等于 2，说明有多个字符的出现次数为奇数，这种情况下无法形成回文字符串，直接返回 false。

6.遍历完数组后，如果count的值小于2，说明最多只有一个字符的出现次数为奇数，这种情况下可以构成回文字符串，则返回 true。

代码实现：

bool canPermutePalindrome(char* s) { int len = strlen(s); int a[128] = {0}; int count = 0; for(int i = 0;i < len;i++) { //将字符所对应的ASCII码值位置++ a[s[i]]++; } for(int i = 0;i < 128 ;i++) { if(a[i] % 2 == 1) { count++; } if(count >= 2) { return false; } } return true;}

🚀三、字符串压缩

题目描述：字符串压缩

解题思路：
1.首先判断特殊情况，如果字符串的长度小于等于2，则压缩后的字符串长度并不会小于原始字符串，因此直接返回源字符串。

2.分配一个足够大的内存空间用于存储压缩后的字符串。初始化计数器count 为 1，用于记录当前字符的连续出现次数；初始化指针 p 为 0，用于记录压缩后字符串的当前位置。

3.使用一个循环从第 1 个字符开始遍历字符串，直到字符串末尾。如果当前字符与前一个字符相同，则计数器 count 加一；如果当前字符与前一个字符不同，则将前一个字符及其出现次数写入压缩后的字符串。（将字符写入 ret[p]，并将指针 p 向后移动一位；使用sprintf函数将计数器 count 转换为字符串并写入 ret[p]，同时更新指针 p 的位置。重置计数器 count 为 1，开始统计下一个字符的连续出现次数。）

4.遍历完成后，比较压缩后的字符串长度与原始字符串长度，如果压缩后的字符串长度大于原始字符串长度，则返回原始字符串，否则返回压缩后的字符串。

代码实现：

char* compressString(char* S) { int len = strlen(S); char* ret = (char*)malloc(sizeof(char)*len*2); int count = 1; int p = 0; int n = 0; if(len <= 2) { return S; } for(int i = 1;i < len + 1;i++) { if(S[i] == S[i - 1]) { count++; } else { ret[p] = S[i - 1]; p++; n = sprintf(&ret[p],\"%d\",count); p = p + n; count = 1; } } if(strlen(ret) > len) { return S; } else { return ret; }}

🎡四、递归乘法

题目描述：递归乘法

解题思路：
1.我们可以理解乘法其实就是重复的加法。如：A×B 可以表示为将 A 加上自身 B 次。

2.如果B>1时，则该问题就可以被分解为A×B=A+(A×(B−1))；当 B=1 时，乘积直接等于 A，因为任何数乘以 1 都等于它本身。

3.每次递归调用都会返回一个部分结果，最终将所有部分结果累加起来，得到最终的乘积。

代码实现：

int multiply(int A, int B) { int ret = 0; if(B > 1) { ret += multiply(A,B-1) + A; } else { ret = A; } return ret;}

🏠五、取近似值

题目描述：取近似值

解题思路：
1.我们要理解当浮点数强制类型转化为整型时，它是只向上调整的，并不会进行四舍五入的操作。

2.因此我们可以先将浮点数加上0.5，然后在进行强制类型转换。如果小数部分大于或等于 0.5，则加上 0.5 后会触发向上取整；若小数部分小于0.5，则加上 0.5 后不会触发向上取整。（这一方法只适用于浮点数为正数时）

代码实现：

#include int main() { int ret = 0; float n; scanf(\"%f\",&n); printf(\"%d\\n\",(int)(n + 0.5));}

🏝️六、数列

题目描述：数列

解题思路：
1.定义一个足够大的数组 arr，用于存储生成的伪随机数序列，将数组的前两个元素初始化为 1 和 2。

2.使用循环从第 3 个元素开始，根据递推公式生成后续的序列值，每个元素的值由前两个元素计算得出，并对 32767 取模，以确保值不会超出 long 类型的范围。

3.由于数组索引从 0 开始，而用户输入的索引从 1 开始，因此需要将用户输入的索引值减 1，以获取对应的数组元素。

代码实现：

#include int main() { long arr[1000000] = {1,2}; for(int i= 2;i<1000000;i++) { arr[i] = (arr[i-1] * 2 + arr[i-2]) % 32767; } long n; scanf(\"%ld\",&n); for(int i = 0;i<n;i++) { int num; scanf(\"%d\",&num); printf(\"%ld\\n\",arr[num-1]); } return 0;}

🚆七、搜索插入位置

题目描述：搜索插入位置

解题思路：
1.定义两个指针 low 和 high，分别指向数组的起始位置和结束位置。定义一个变量 tmp，用于存储每次二分查找的中间索引。

2.使用 while 循环进行二分查找，计算中间索引 tmp。比较目标值 target 与中间值 nums[tmp]

3.如果循环结束仍未找到目标值，说明目标值不存在于数组中。如果目标值小于所有数组元素，low 会保持为0；如果目标值大于所有数组元素，low 会逐渐增加到 numsSize；如果目标值位于数组的某个位置之间，low 会停在目标值应该插入的位置。

代码实现：

int searchInsert(int* nums, int numsSize, int target) { int low = 0; int high = numsSize - 1; int tmp = 0; while(low <= high) { tmp = (low + high)/2; if(nums[tmp] == target) { return tmp; } else if(nums[tmp] >target) { high = tmp - 1; } else { low = tmp + 1; } } return low;}

🚘八、搜索旋转排序数组

题目描述：搜索旋转排序数组

解题思路：
1.首先要找到旋转点，使用二分查找的方法。如果 nums[0] > nums[numsSize - 1]，说明数组确实被旋转了。

2.每次比较 nums[mid] 和 nums[left]，如果 nums[mid] > nums[left]，说明 mid 在前半部分的升序子数组中，旋转点在右半部分。否则，旋转点在左半部分。最终，left 和 right 会收敛到旋转点的位置。

3.确定查找范围。找到旋转点后，根据目标值 target 的大小，确定在哪个子数组中进行查找。如果 target 在前半部分的范围内，则在前半部分进行查找；否则，在后半部分进行查找。

4.使用标准的二分查找算法在选定的子数组中查找目标值。如果循环结束仍未找到目标值，则返回 -1。

代码实现：

int search(int* nums, int numsSize, int target) { int left = 0,right = numsSize - 1; int mid = numsSize - 1; while(nums[0] > nums[numsSize - 1] && left < right) { mid = (left + right) / 2; if(nums[mid] >nums[left]) { left = mid; } else { right = mid; } } //前半部分查找 if(nums[0] <= target) { left = 0,right = mid; } //后半部分查找 else { left = mid + 1,right = numsSize - 1; } while(left <= right) { mid = (left + right) / 2; if(nums[mid] == target) { return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;}

🏖️九、二进制链表转整数

题目描述：二进制链表转整数

解题思路：
1.使用一个指针 pcur 遍历链表，统计链表的节点个数。

2.再次从头节点开始遍历链表，计算二进制数的十进制值。

3.将每个节点的值乘以对应的权重 2 的(count−1)次方 ，权重从最高位开始计算，因此每次遍历时 count 减 1。将每个节点的值累加到结果 ret 中。

4.遍历完成后返回目标值ret即可。

代码实现：

typedef struct ListNode ListNode;int getDecimalValue(struct ListNode* head) { ListNode* pcur = head; int count = 0; int ret = 0; //记录链表的结点个数 while(pcur) { count++; pcur = pcur->next; } pcur = head; //再次从头开始遍历链表，计算结果 while(pcur) {  ret += (pcur->val) * pow(2,count - 1); count--; pcur = pcur->next; } return ret;}

今天的分享就到这里啦，如果感到不错，希望能给博主一键三连，感谢大家的支持！希望这篇文章可以帮到大家，我们下期再见！