【C语言】初阶数据结构相关习题（一）
今日语录：人的生命似洪水在奔流，不遇着岛屿、暗礁，难以激起美丽的浪花。——奥斯特洛夫斯基
文章目录
⭐一、判定是否互为字符重排
题目描述：判定是否互为字符重排
解题思路：
1.首先判断两个字符串长度是否相等，若不相等，那么他们不可能彼此排列，直接返回false。
2.若字符串长度相等，我们就可以使用qsort函数对两个字符串进行排序来判断它们是否排列。
qsort 是标准库中的快速排序函数，它需要以下参数：
• 要排序的数组（s1 和 s2）。
• 数组的长度（len1 和 len2）。
• 每个元素的大小（sizeof(char)）。
• 比较函数（cmp）。
3.排序完成后，如果两个字符串是彼此的排列，那么它们排序后的结果应该完全相同，因此我们就可以使用strncmp函数来比较排序后的字符串。
代码实现：
intcmp(constvoid* a,constvoid* 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.每次递归调用都会返回一个部分结果，最终将所有部分结果累加起来，得到最终的乘积。
代码实现：
intmultiply(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<stdio.h>intmain(){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<stdio.h>intmain(){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]);}return0;}🚆七、搜索插入位置
题目描述：搜索插入位置
解题思路：
1.定义两个指针 low 和 high，分别指向数组的起始位置和结束位置。定义一个变量 tmp，用于存储每次二分查找的中间索引。
2.使用 while 循环进行二分查找，计算中间索引 tmp。比较目标值 target 与中间值 nums[tmp]
3.如果循环结束仍未找到目标值，说明目标值不存在于数组中。如果目标值小于所有数组元素，low 会保持为0；如果目标值大于所有数组元素，low 会逐渐增加到 numsSize；如果目标值位于数组的某个位置之间，low 会停在目标值应该插入的位置。
代码实现：
intsearchInsert(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;}elseif(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。
代码实现：
intsearch(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;}elseif(nums[mid]< target){ left = mid +1;}else{ right = mid -1;}}return-1;}🏖️九、二进制链表转整数
题目描述：二进制链表转整数
解题思路：
1.使用一个指针 pcur 遍历链表，统计链表的节点个数。
2.再次从头节点开始遍历链表，计算二进制数的十进制值。
3.将每个节点的值乘以对应的权重 2 的(count−1)次方 ，权重从最高位开始计算，因此每次遍历时 count 减 1。将每个节点的值累加到结果 ret 中。
4.遍历完成后返回目标值ret即可。
代码实现：
typedefstructListNode ListNode;intgetDecimalValue(structListNode* 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;}今天的分享就到这里啦，如果感到不错，希望能给博主一键三连，感谢大家的支持！希望这篇文章可以帮到大家，我们下期再见！
