精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

strlen函数
strlen的功能

strlen函数的功能是计算字符串的长度

    char* p ="abcdef";
    int ret = strlen(p);
strlen的作用机理

字符串在存储的时候会默认将最后一位放为0

char* p = "abcdef";

在内存中存储的是 abcdef\0
我们strlen函数在工作时就是从我传入的地址开始,一直到\0的出现

strlen的返回值

strlen的返回值时 size_t即无符号的整型
无符号整型减无符号整型时,所得结果一定是一个无符号整型,即一个大于0的数

if(strlen("abc")- strlen("abcdef")>0)
{
    printf("666");
}
else
{
    printf("777");
}

在这个案例中,strlen"abc“返回3 strlen(“abcdef”)返回7,如果按照int类型理解的话,应为-4
但是无符号数的运算规则使他不可能得到一个负数,所以-4被修正为整数,打印666

strlen的自我实现
int myStrlen(char* p) //循环计数器
{
    int sum=0;
    while(*(p++)!='\0')
    {
        sum++;
    }
    return sum;
}

int myStrlen2(char* p) //指针减指针写法
{
    char* p1 = p;
    while(*p!='\0')
    {
        p++;
    }
    return p - p1;
}

int myStrlen3( char* p) //递归实现
{
    if(*p!='\0')
    	return 1 + myStrlen3(p++);
    return 0;
}
strcpy函数
strcpy函数的功能

将一个字符串拷贝到另一个字符串里面,从头开始放,并且\0也顺便拷贝进去
strcpy函数判断字符串的标准是\0,即我找到\0后就不找了
目标的空间必须足够大,不然会报错
strcpy函数的返回值是目的数组的地址

	char* p = "ab\0cde";
    char arr[] = "xxxxxxxxxxxxxxxx";

arr里面放的就是ab\0xxxxxxxxxxxxx

strcpy函数的模拟实现
char* myStrcpy(char* p1, char* p2)
{
    char* des = p1;
    while (*(p1++) = *(p2++))
    {
        ;
    }
}
return des;
strcat函数
strcat函数的功能
char* strcat(char* dest, const char* src);

将源函数src连接到目标字符串dest的后面,并返回目标空间的首地址。
注意:目标字符串必须有足够的空间
并且源字符串和目标字符串都必须有可见的\0

strcat函数的模拟实现
char* mystrcat(char* dest, char* src)
{
    char* ret = dest;
    while(*dest!='\0')
    {
        dest++;
    }
    /*找到第一个字符串的\0*/
    while(*dest++ = *src++)
    {
        ;
    }
    /*完成连接*/
    return ret;	
}
strcnp
strcmp的功能
int strcmp(char*p1, char*p2);

比较两个字符串的大小,如果p1小于p2返回小于0的数
p1大于p2返回大于0的数
p1等于p2返回0

strcmp的作用原理

比较两个字符串的第一个元素,若不同结束比较,返回一个整数
若相同再比较下一个元素,重复上述过程
直到两个元素相同且都为\0是结束判断反回0

char* p1 ="abc\0adc";
char* p2="abc\0sdasdads";
printf("%d", strcmp(p1,p2));// 0

根据上面的原理可知当两者相同且都为0时就结束了判断,所以这两个字符串判断为相同·

strcmp的模拟实现
int strcmp(char*s1, char*s2)
{
    while(*s1 == *s2)
    {
        if(*s1=='\0')
        	return 0;
        	s1++;
        	s2++;
    }
    return *s1 - *s2;
}
strncpy
strncpy的功能
char* strncpy(char* dest, char*src, int n)

表示把src的前n为元素拷贝到dest中,并且在第n+1位填上\0
如果src小于n位,则会默认填上\0
strcnpy有效的解决了srcnpy盲拷贝的问题

strnpy的模拟实现
char* strnpt(char* dest, char* src, int n)
{
	char* ret = dest;
	for(int i = 0; i < n; i++)
	{
		if (drc[i] == '\0')
		{
			dest[i] = src[i];
			return ret;
		}
			dest[i] = src[i];
	}
	dest[n] = '\0';
	return ret;
}
strncat
strncat 的工作原理
char* strncat(char* dest, char*src, int n)

strncat工作分为两个步骤
1,找到dest字符串的\0位
2,从\0位开始将src的前n个元素放进去
3,放进去后在n+1的位置补0
注意,如果src的元素不足n个,则会在填充完毕所有的元素后补0

strncat的模拟实现
char* mystrncat(char* dest, char* src, int n)
{
	char* ret = dest;
	while (*dest)
	{
		dest++;
	}
	//拿到目的字符串的\0位
	for (int i = 0; i < n; i++)
	{
		if (src[i] == '\0')
			break;
		*dest = src[i];
		dest++;
	}
	*dest = '\0';
	return ret;
}
strncmp
strncmp的工作原理
int strncmp(char* s1, char* s2, int n);

从第一个元素开始比较,如果相同则比较第二个,若不同则返回对应的值。值的大小同strcmp。
与strcmp不同的是,strncmp只比较n次。

strcmp的模拟实现
int mystrncmp(char* s1, char* s2, int n)
{
	for(int i = 0; i < n; i++)
	{
		if (s1[i] != s2[i])
			return s1[i] - s2[i];
	}
	return 0;
}
strstr
strstr的工作原理
char* strstr(char* s1, char* s2);

功能在于寻找s1中s2第一次出现的位置,如果找到了返回s2第一次出现的地址,如果没找到返回NULL

strstr的模拟实现 --滑动窗口模式

######何为滑动窗口?
滑动窗口用于比较一个定长范围内的数量关系,常常和动态规划结合在一起。

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

在这个函数中,我们要从字符串s1中寻找s2,就把s2当作窗口,s1就相当于窗台,我们把窗口一次一次往后移动,如果正好匹配上了就代表我们找到了。

代码实现
char* strstr(char* s1, char* s2) //滑动窗口匹配机制
{
	if (*s2 == '\0')
		return s1;
	char* cp = s1;//控制窗口的指针
	char* p1 = NULL;
	char* p2 = s2;
	//p1 和 p2是两个在具体比较时的指针
	while (*cp)
	{
		p1 = cp;
		while (*p1 == *p2 && p1 != NULL && p2 != NULL)
		{
			p1++;
			p2++;
		}//判断窗口内容是否匹配
		if (*p2=='\0')
			return cp;//判断是否匹配到底
		cp++;//若为匹配到底就把窗口后移一位
		p2 = s2;
	}
	return NULL;
}
strstr的模拟实现 --kmp算法

下一章细讲

memcpy
mencpy的工作原理
void* memcpy(void* dest, void* src, size_t count);

将src内存区域中的 前count个字节拷贝到desr中
memcpy操作的是直接的内存,这相比strcpy以\0作为拷贝的终结点是不同的,直接以count 作为拷贝的终结点

memcpy的模拟实现

在模拟实现前,我们有一个关键的问题等待大家确认,即我们在实现内存拷贝时是以一个字节一个字节的去拷贝,还是四个四个字节去拷贝。
这个问题其实也很哈解决,如果以非一的字节去拷贝的话,总有一些情况无法满足,因此我们采取一个字节一个字节的拷贝

void* memcpy(void* dest, void* src, size_t count)
{
    void* ret = dest;
    while(count != 0)
    {
        *(char*)dest = *(char*)src
        dest = (char*)dest + 1;
        src = (char*) src + 1;
    } 
    return ret;
}
memcpy的弊端

memcpy不支持重叠拷贝,即不支持我把自己的一部分拷贝到自己身上。
因为我们在看他的模拟实现的时候,memcpy是事实演算的,即直接在自己身上动手,之后继续进行。
所以我们在采用memcpy的时候,只连接两个不同的字符串,不连接自己

memmove

memcpy的弊端

memmove是对memcpy的升级,相较于memcpy固定化的从右向左拷贝所可能出现的覆盖问题,memmove对其拷贝前进行了升级探究,具体过程如下图所示

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

当我们想将src开始的16个字节移动到dest时,如果按照memecpy从左到右的形式拷贝,则会出现如下情况

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

(先拷贝前两个到dest,然后两个指针都后移)

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

(再顺次同方法拷贝后两个)

这时问题就显而易见了,由于固定化的从左向右拷贝,使得重叠区域拷贝失败,因此memmove对此进行了升级

memcpy的升级

前面我们分析过,当src小于dest时(如下图所示),我们不能采取从左向右拷贝,而是要从右向左拷贝。

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

那么当src大于dest时(如下图所示),我们要如何拷贝他呢?

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

这时候我们就发现从左向右拷贝正好可以完美实现它

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

精读大话数据结构,陪你拿下45分 EP5 串的应用与实现

这就是我们分析出来的memmove工作原理

如果src大于dest,我们就从左向右拷贝;如果src小于dest我们就从右向左拷贝;

memmove的模拟实现

根据前面我们所分析的工作原理,我们首先要对其进行分类,之后再具体进行实现。

void* mymemmove(void* dest, void* src, size_t count)
{
	void* ret = dest;
	if (dest < src)
	{
		while (count--)  /*循环count次*/
		{
			*(char*)dest = *(char*)src;
			/*指针的类型决定了解引用操作引用的空间的大小,这里我们一个字节一个字节拷贝,所以要转化为char*类型的指针*/
			dest = (char*)dest + 1;
			/*由于void*类型的指针不明确解引用类型大小,所以我们要想后移1个字节,需要把他们先转化成char*类型*/
			src = (char*)src + 1;
		}
	}
	else
	{
		while (count--)
		{
			*((char*)dest + count) = *((char*)src + count);
			/*由于c语言中,计数从0开始,所以从dest 到 dest+count这么多个字节,最后一个字节的地址是dest + count - 1; 第一个字节的地址是 dest + 0;*/
		}
	}
	return ret;
}
上一篇:【第3版emWin教程】第45章 emWin6.x窗口管理器之定时器使用


下一篇:C语言选择排序算法