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

06-02 1259阅读

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

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

文章目录

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

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

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

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

解题思路：

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 = 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 
        return S;
    }
    for(int i = 1;i  
🎡四、递归乘法 
题目描述：递归乘法 
 
解题思路：
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
        arr[i] = (arr[i-1] * 2 + arr[i-2]) % 32767;
    }
    long n;
    scanf("%ld",&n);
    for(int i = 0;i
        int num;
        scanf("%d",&num);
        printf("%ld\n",arr[num-1]);
    }
    return 0;
}

    int low = 0;
    int high = numsSize - 1;
    int tmp = 0;
    while(low 
        tmp = (low + high)/2;
        if(nums[tmp] == target)
        {
            return tmp;
        }
        else if(nums[tmp] target)
        {
            high = tmp - 1;
        }
        else
        {
            low = tmp + 1;
        }
    }
    return low;
}
h2🚘八、搜索旋转排序数组/h2 
p题目描述：搜索旋转排序数组/p 
pimg src="https://i-blog.csdnimg.cn/direct/9de5ed2cb12b4e768dcf4726cdad18c1.png" alt="在这里插入图片描述" //p 
p解题思路：/pp1.首先要找到旋转点，使用二分查找的方法。如果 nums[0]  nums[numsSize - 1]，说明数组确实被旋转了。/p 
p2.每次比较 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 nums[left])
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }
    //前半部分查找
    if(nums[0] 
        left = 0,right = mid;
    }
    //后半部分查找
    else
    {
        left = mid + 1,right = numsSize - 1;
    }
    while(left 
        mid = (left + right) / 2;
        if(nums[mid] == target)
        {
            return mid;
        }
        else if(nums[mid] next;
    }
    return ret;
}
 
今天的分享就到这里啦，如果感到不错，希望能给博主一键三连，感谢大家的支持！希望这篇文章可以帮到大家，我们下期再见！

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

高速稳定云服务器9.9元起