快速排序、strncpy、strncat、strncmp实现、回调函数以及指针+二维数组——C语言——day15

本文介绍: step1：选择一个基准值 // a[0]step2：从右边开始找，找比基准值小的值step3：从左边开始找，找比基准值大的值step4：交换找到的值step5：重复step2——step4步骤，直到begin与end相遇step6：此时将相遇位置上的值与基准值交换step7：针对小于、大于基准值的部分，分别继续进行快速排序递归调用。

今天主要的内容是利用指针实现快速排序、strncpy、strncat、strncmp实现、回调函数以及指针+二维数组

首先讲一下快速排序

快速排序的思想是：

在这里插入图片描述
step1：选择一个基准值 // a[0]
step2：从右边开始找，找比基准值小的值
step3：从左边开始找，找比基准值大的值
step4：交换找到的值
step5：重复step2——step4步骤，直到begin与end相遇
step6：此时将相遇位置上的值与基准值交换
step7：针对小于、大于基准值的部分，分别继续进行快速排序递归调用

eg：示例代码
#include<stdio.h>

void sort_print(int *begin,int *end)	//输出
{
	for(;begin <= end;++begin)
	{
		printf("%d  ",*begin);
	}
	putchar('n');
}

void swap(int *num1,int *num2)	//交换值
{
		int temp = *num1;
		*num1 = *num2;
		*num2 = temp;
}

void quick_sort(int *begin,int *end)	//快速排序
{
	int *p = begin;
	int *q = end;
	int *k = begin;

	if(begin > end)
	{
		return;
	}

	while(begin < end)
	{
		while(begin < end && *k > *end)
		{
			--end;
		}
		while(begin < end && *k < *begin)
		{
			++begin;
		}
		swap(begin,end);
	}
	swap(begin,k);

	quick_sort(p,end-1);
	quick_sort(begin+1,q);
}

int main(void)	//主函数
{
	int array[] = {5,6,8,1,4,3,2,9,0,7};
	int len = sizeof(array) / sizeof(array[0]);

	quick_sort(array,array+len-1);
	sort_print(array,array+len-1);

	return 0;
}

输出结果如下图所示：
在这里插入图片描述

接下来讲一下strncpy、strncat、strncmp实现过程

首先是strncpy

char *strncpy(char *dest, const char *src, size_t n)
{  
   正常拷贝，但是形参上多了一个n 
   当n < strlen(src)  
     只拷贝前n个字符，最终dest中不会有''
   当n == strlen(src)
     正常拷贝 
   当n > strlen(src)
   if (n) 拷贝够了次数 
   剩余拷贝 统统补0
   
   思路:
   // 结束条件 *src == ''
   // n次 拷贝完成没有
}
根据这个思路，我们可以写出以下函数：
char * str_n_cpy(char *s1,const char *s2,int n)
{				//const 简单可以理解为：s2为只读模式
	char *p = s1;
	while(n && (*s1 = *s2))
	{
		++s1;
		++s2;
		--n;
	}
	
	while(n)
	{
		*s1 == 0;
		s1++;
		--n;
	}

	return p;
}

strncat

char *strncat(char *dest, const char *src, size_t n)
 {
   在拼接的基础上，多了一个n控制条件 
   
   当n < strlen(src) 拼n下就结束,若n=3,只剪切前三个字符   n == 0
    
   当n >= strlen(src) src拼完就结束  src==''
   
 }
根据这个思路，我们可以写出以下函数：
char * str_n_cat(char *s1,const char *s2,int n)
{
	char *ret = s1;

	while(*s1 != '')
		s1++;

	while(n && *s2 != '')
	{
		*s1 = *s2;
		++s1;
		++s2;
		--n;
	}

	*s1 = '';

	return ret;
}

strncmp

int Strncmp(const char *s1, const char *s2, size_t n)
  {
   在比值的基础上，多了一个n控制条件 
   
   当n < 字符串大小时,比到两个字符串比到n就结束
    
   当n >= 字符串大小时,比到两个字符串比到''就结束
  }
根据这个思路，我们可以写出以下函数：
int str_n_cmp(const char *dest,const char *str,int n)
{
	n--;
	while(n && *dest == *str && *dest != '' && *str != '')
	{
		dest++;
		str++;
		n--;
	}

	return *dest - *str;
}

回调函数

回调函数: 通过函数指针调用的函数叫回调函数

技术上: 通过函数指针的实现

函数指针(指向基类型-为函数类型) 函数类型的指针

void qsort(void *base, size_t nmemb, size_t size,int (*compar)(const void *, const void *));
  
  @base    数组起始位置
  @nmemb   排序的元素个数 
  @size    单个元素的大小 
  @compar  比较函数  //确定进行比较的两个元素的大小规则


eg：写了一个简单的+-*/运算
#include<stdio.h>

int add(int a,int b)
{
	return a + b;
}

int sub(int a,int b)
{
	return a - b;
}

int mul(int a,int b)
{
	return a * b;
}

int div(int a,int b)
{
	return a / b;
}

void processData(int a,int b,int (*pfunc)(int ,int ))
{
	printf("result = %dn",pfunc(a,b));
}

int main(void)
{
	int a,b;
	char c;

	scanf("%d %c %d",&a,&c,&b);

	switch(c)
	{
	case '+':
		processData(a,b,add);
		break;
	case '-':
		processData(a,b,sub);
		break;
	case '*':
		processData(a,b,mul);
		break;
	case '/':
		processData(a,b,div);
		break;
	}

	return 0;
}

万能指针

void *  //万能指针  --可以接收任意类型的指针 
        //void类型 
		//
		
		注意: 
		 如果通过该类型的地址进行数据访问
		 一定要转换为 明确类型

指针+二维数组

int a[3][4]; //本质还是一维数组 
int[4] a[3]; //理解角度 
             //a --数组名 --代表类型 int [3][4]
			 //a --代表的值 -- 首元素的地址 -- a[0] 
			 //a[0] 的数据类型 int[4]
			 //&a[0]--对应的数据类型 int(*)[4] //数组类型 (一维整型数组类型)
             //数组类型的指针 --- 数组指针                   
			 int *

举一个详细的例子：
int (*p)[4] = a;

*p   //三步运算完成后
     *p 相当于 是 int[4]这种类型 //数组
	 *p 就相当于 int[4]这个数组的 数组名

int a = 10;
int *p = &a;

*p <=> a	 

*(*(p+i) + j)<=>a[i][j]

p+1 //偏移到了 下一个 int[4]
    //类型为int(*)[4]
*(p+1) //偏移到下一个int 
       //*(p+1) 代表的类型int[4] 此时相当于是 int[4]的数组名 
	   //*(*(p+1) + 1)<=>a[1][1]

这些举例可能还不够让人理解，可以看一看示例。


eg1：将二维整型数组打印，并输出最大值。
#include<stdio.h>

void printfArray(int (*p)[4],int row)
{
	int i = 0;
	int j = 0;
	for(i = 0;i < row;++i)
	{
		for(j = 0;j < 4;++j)
		{
			printf("%2d ",*(*(p+i)+j));
		}
		putchar('n');
	}
}

int max_of_array(int (*p)[4],int row)
{
	int i = 0;
	int j = 0;
	int	max = **p;
	for(i = 0;i < row;++i)
	{
		for(j = 0;j< 4;++j)
		{
			if(*(*(p+i)+j) > max) 
			{
				max = *(*(p+i)+j);
			}
		}
	}
	return max;
}

int main(void)
{
	int a[3][4] = {1,5,3,2,6,7,9,10,14,19,50,2};
	
	printfArray(a,3);
	int i = max_of_array(a,3);
	printf("max = %dn",i);

	return 0;
}

可以得到输出结果：
在这里插入图片描述

上面列了一个整型数组的例子，接下来将一个二维字符型数组的例子。

eg2：实现:
	 char *s[ ] = {"help","word","hello","world","china"};
	1.实现排序
	2.查找

#include<stdio.h>
#include<string.h>

void print_str(char **p,int len)
{
	int i = 0;
	for(i = 0;i < len;++i)
	{
		printf("%sn",*(p+i));
	}
}

void bull_sort(char **p,int len)
{
	for(int i = 0;i < len - 1; ++ i)
	{
		for(int j = 0;j < len - i - 1;++j)
		{
			if(strcmp(*(p+j),*(p+j+1)) > 0)
			{
				char *s = *(p+j);
				*(p+j) = *(p+j+1);
				*(p+j+1) = s;
			}
		}
	}
}

int bin_search(char **p,int len,char *s2)
{
	int begin = 0;
	int end = len - 1;

	while(begin <= end)
	{
		int mid = begin + (end - begin) / 2;
		if(strcmp(*(p+mid),s2) == 0)
		{
			return 1;
		}else if(strcmp(*(p+mid),s2) > 0)
		{
			end = mid - 1;
		}else
		{
			begin = mid + 1;
		}
	}
	return 0;
}

int main(void)
{
	char *s[5] = {"help","word","hello","world","china"};
	char s2[10];
	print_str(s,5);
	putchar('n');
	bull_sort(s,5);
	print_str(s,5);
	printf("input you find word:");
	scanf("%s",s2);
	int ret = bin_search(s,5,s2);
	if(ret == 1)
	{
		printf("find!n");
	}else
	{
		printf("not find!n");
	}

	return 0;
}