数据结构：字符串操作

浅浅的花香味﹌ 2022-02-14 06:49 281阅读 0赞

### 文章目录 ###

*   *  字符串操作
     *   *  大小写转换
         *  字符串比较函数
         *  字符串分割
     *  查找算法
     *   *  折半查找
         *   *  猜商品价格

## 字符串操作 ##

字符串大小写转换  
A-Z 65-90  
a-z 97-122  
n+32 = N

**简便方法：使用位运算**  
A 100 0001  
a 110 0001  
大写字母二进制第六位始终为0，小写字母为1  
按位与&：有0得0 小写转大写使用 &101 1111  
按位或|：有1得1 大写转小写使用 |010 0000

demo.cpp

#include <stdio.h>
    #include <stdlib.h>
    
    /*
    字符串拷贝
    */  
    bool diyStrCpy(char *source, char *target,int len)
    {
    	//计算字符串总大小
    	int i = 0;
    	while (source[i] != '\0')
    	{
    		i++;
    	}
    	if (i > len)
    	{
    		return false;
    	}
    
    	//直接拷贝，无法判断字符串大小
    	i = 0;
    	while (source[i] != '\0')
    	{
    		target[i] = source[i];
    		i++;
    	}  
    	target[i] = '\0';
    	return true;
    }  
    
    /*
    字符串连接
    */  
    bool diyStrCat2(char *str1,int len, char *str2) //len代表str1内存总长度
    {
    	int i = 0;
    	int k = 0;
    	while (str2[k] != '/0')
    	{
    		k++;
    	}
    	while (str1[i] != '\0')
    	{
    		i++;
    	}
    	if (i + k -1 > len)
    	{
    		return false;
    	}
    	k = 0;
    	while (str2[k] != '\0')
    	{
    		str1[i++] = str2[k++];
    	}  
    	str1[i] = '\0';  
    	return true;
    
    }  
    
    /*
    字符串连接
    */
    bool diyStrCat3(char *str1, char *str2,char *target)
    {
    	int i = 0;
    	int k = 0;
    	
    	//没有检验传入过来target是否有容纳两个字符串的空间
    	while (str1[i] != '\0')
    	{
    		target[i] = str1[i];
    		i++;
    	}  
    	while (str2[k] != '\0')
    	{
    		target[i++] = str2[k++];
    	} 
    	target[i] = '\0';
    	return true;
    }

### 大小写转换 ###

常规方法

//大写字母转换为小写字母
    bool diyStr2Low(char *str, char *target, int len)
    {
    	int strLen = 0; //字符串的长度，不带\0
    	while (str[strLen] != '\0')
    	{
    		strLen++;
    	}
    	if (strLen >= len)
    	{
    		return false;
    	}
    	int k = 0;
    	while (str[k] != '\0')
    	{
    		if (str[k] >= 'A'&& str[k] <= 'Z' )
    		{
    			target[k] = str[k] + 32;
    			
    		}
    		else 
    		{
    			target[k] = str[k];
    		}
    		k++;
    	}
    	target[k] = '\0';
    	return true;
    }
    //小写转大写
    bool diyStr2High(char *str, char *target, int len)
    {
    	int strLen = 0; //字符串的长度，不带\0
    	while (str[strLen] != '\0')
    	{
    		strLen++;
    	}
    	if (strLen >= len)
    	{
    		return false;
    	}
    	int k = 0;
    	while (str[k] != '\0')
    	{
    		if (str[k] >= 'a'&& str[k] <= 'z')
    		{
    			target[k] = str[k] - 32;
    
    		}
    		else
    		{
    			target[k] = str[k];
    		}
    		k++;
    	}
    	target[k] = '\0';
    	return true;
    }

位运算

/*按位操作 大小写转换
    前提条件：
    1.target容量够存储转换后的内容
    2.只有大小写字符，无其他字符  
    */
    //大写转小写  按位或 0100 0000
    bool diyStr2LowerEx(char *source, char *target)
    {
    	int k = 0;
    	while (source[k] != '\0')
    	{
    		target[k] = source[k] | 32;
    		k++;
    	}
    	target[k] = '\0';
    	return true;
    }
    //小写转大写  按位与&  1011 1111
    bool diyStr2UpperEx(char *source, char *target)
    {
    	int k = 0;
    	while (source[k] != '\0')
    	{
    		target[k] = source[k] & 95;
    		k++;
    	}
    	target[k] = '\0';
    	return true;
    }

### 字符串比较函数 ###

bool diyStrCmp(char *str1, char *str2)
    {
    	//如果想不区分大小写，调用转换大小写函数后，再比较
    	int k = 0;
    	while (str1[k] != '\0')  //只要判断一个条件就可以了，因为另一个字符串到\0肯定会匹配失败退出
    	{
    		if (str1[k] != str2[k])
    		{
    			return false;
    		}
    		k++;
    	}
    	if (str1[k] == str2[k]) //都相等代表都到了结束位置
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }

### 字符串分割 ###

demo.cpp

int diySeparateStr(char *source, char separator,char target[][20])
    {
    	int k = 0; //遍历用的索引
    	int n = 0;  //要写入第几个字符串
    	int i = 0;  //写入字符在当前字符串中的位置索引
    	while (source[k] != '\0')
    	{
    		if (source[k] != separator)
    		{
    			target[n][i++] = source[k];
    		}
    		else
    		{
    			target[n][i] = '\0';
    			n++;
    			i = 0;
    		}
    		k++;
    	}
    	target[n][i] = '\0';
    	return n+1;//返回子字符串的个数
    }

## 查找算法 ##

顺序查找，折半查找  
折半查找：必须是有序集合

### 折半查找 ###

//递归折半查找算法
    int SearchAlg1(int *pArr, int target, int low, int high)
    {
    	int mid = 0;
    	if (low > high)
    	{
    		return -1;
    	}
    	mid = (low + high) / 2;
    	if (pArr[mid] == target)
    	{
    		return mid;
    	}
    	else if (pArr[mid] > target)
    	{
    		return SearchAlg1(pArr, target, low, mid - 1);
    	}
    	else if (pArr[mid] < target)
    	{
    		return SearchAlg1(pArr, target, mid + 1, high);
    	}
    }
    //非递归折半查找算法
    int SearchAlg2(int *pArr, int len,int target)
    {
    	int low = 0;
    	int high = len - 1;
    	int mid = (low + high) / 2;
    
    	while (low < high && pArr[mid] != target)
    	{
    		if (pArr[mid] < target) //中间值小于目标值
    		{
    			low = mid + 1;
    			mid = (low + high) / 2;
    		}
    		else if (pArr[mid] > target)
    		{
    			high = mid - 1;
    			mid = (low + high) / 2;
    		}
    	}
    	if (pArr[mid] == target)
    	{
    		return mid;
    	}
    	return -1;
    }

#### 猜商品价格 ####

int GuessNum(int firstNum, int rightNum)
    {
    	//每次猜的价格都是上次价格的两倍
    	int count = 1;
    	int standardNum = firstNum;
    	printf("standardNum = %d\n", standardNum);
    	while (standardNum < rightNum)
    	{
    		count++;
    		standardNum *= 2;
    		printf("standardNum = %d\n", standardNum);
    	}
    	//找到比目标价格大的数（最靠近的）用折半查找
    	int lowNum = 0;
    	int highNum = standardNum;
    	int midNum = highNum;
    	while (midNum != rightNum)
    	{
    		if (midNum < rightNum)
    		{
    			lowNum = midNum;
    			midNum = (lowNum + highNum) / 2;
    		}
    		else if(midNum > rightNum)
    		{
    			highNum = midNum;
    			midNum = (lowNum + highNum) / 2;
    		}
    		printf("I guess %d\n", midNum);
    		count++;
    	}
    	printf("ok\n");
    	return count;
    }