指针练习（一）

下列程序的结果

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>

int main()
{
	int a[5] = { 1,2,3,4,5 };
	int* ptr = (int*)(&a + 1);
	printf("%d,%d", *(a + 1), *(ptr - 1));
	return 0;
}

结果是 2，5

首元素地址+1指第二个元素的地址，即2。&a + 1 指向的是5后面一个的地址，-1又回去了

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
struct Test
{
	int Num;
	char* pcName;
	short sDate;
	char cha[2];
	short sBa[4];
};
//假设p的值为0x100000，如下表达式的值分别为多少
//Test的大小是20字节
int main()
{
	printf("%p\n", p + 0x1);//0x100014
	printf("%p\n", (unsigned long)p + 0x1);//0x100001 p被强制转换成整型了
	printf("%p\n", (unsigned int*)p + 0x1);//0x100001无符号整型指针+1跳过一个无符号整型即+4
	return 0;
}

前提是32位编译

答：p+0x1指针+1就是指跳过一个Test结构体所以+20

0x100001 p被强制转换成整型了

0x100004无符号整型指针+1跳过一个无符号整型即+4

64位的时候一个指针是8byte你结构体就是32字节了所以+1就是0x20

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int main()
{
	int a[4] = { 1,2,3,4 };
	int* ptr1 = (int*)(&a + 1);
	int* ptr2 = (int*)((int)a + 1);
	printf("%x,%x", ptr1[-1], *ptr2);
	return 0;
}

4,20000

4：&a + 1刚好在4后面一个，-1又回到4

而对于ptr2，小端存储

01 00 00 00 | 02 00 00 00 | 03 00 00 00 | 04 00 00 00 |

ptr2指向的地址被转换成int后+1 相当于从->01变为01->00然后再输出向后数4个byte，即使0x 02 00 00 00

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int main()
{
	int a[3][2] = { (0,1),(2,3),(4,5) };// -->{1,3,5}
	int* p;
	p = a[0];//p -> *(p + 0)
	printf("%d", p[0]);
	return 0;
}

结果 1

1 | 3
5 | 0
0 | 0

括号表达式，算最后一个逗号右边的结果,所以p->1

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int main()
{
	int a[5][5];
	int(*p)[4];
	p = a;
	printf("%p,%d\n", &p[4][2] - &a[4][2], &p[4][2] - &a[4][2]);
	return 0;
}

地址无正负之分，补码的-4是FFFFFFFC,-4

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int main()
{
	int aa[2][5] = { 1,2,3,4,5,6,7,8,9,10 };
	int* ptr1 = (int*)(&aa + 1);
	int* ptr2 = (int*)(*(aa + 1));
	printf("%d,%d", *(ptr1 - 1), *(ptr2 - 1));
	return 0;
}

结果是10，5.10是因为&aa+1指的是跳过整个二维数组，再-1回到最后一个元素。
5是因为*（aa + 1）指的是跳过一行，再-1回到第一行最后一个元素5

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int main()
{
	char* a[] = { "work", "at", "alibaba" };
	char** pa = a;
	pa++;
	printf("%s\n", *pa);
	return 0;
}

结果at,char* p = “abc”,所以char* a[],里面又三个char*,pa++就是指向at

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int main()
{
	char* c[] = { "ENTER", "NEW", "POINT", "FIRST" };
	char** cp[] = {c + 3, c + 2, c + 1, c};
	char*** cpp = cp;
	printf("%s\n", **++cpp);
	printf("%s\n", *-- * ++cpp + 3);
	printf("%s\n", *cpp[-2] + 3);
	printf("%s\n", cpp[-1][-1] + 1);
	return 0;
}

注意++cpp，做完运算在第二个表达式中结果保留

第一个cpp先++指的是c+2，再解引用两次刚好到”POINT”
第二个cpp先++指的是c+1,解引用完再–变成c,再解引用指的是”ENTER”,+3刚好从E开始输出ER。
第三个cpp[]->* cpp,然后再解引用即** （cpp-2）+3，cpp-2回到开始的位置，即c+3，解2次引用就是FIRST，+3就是从S开始输出ST
第四个是指* (* (cpp - 1) - 1)+1,即先* (cpp - 1) 得到c + 2，再 - 1 得到c + 1,接引用完是”NEW”,再+1指的是从E开始输出EW

杨氏矩阵
有一个数字矩阵，矩阵的每行从左到右递增，矩阵从上到下是递增的
请编写程序在这样的矩阵中查找某个数字是否存在
要求时间复杂度小于O（N）

思路：因为每一行右边最大，所以比较最右边，小了就去掉这一行，直接看下一行，每一列的最下面都是最大的，比较后，小了就去掉这一列，这样就能保住时间复杂度了.

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int find_num(int arr[3][3], int r, int c, int k)
{
	int x = 0;
	int y = c - 1;
	while (x < c && y >= 0) {
		if (arr[x][y] < k)
			x++;//加一行
		else if (arr[x][y] > k)
			y--;//去一列
		else
			return 1;
	}
	return 0;
}
int main()
{
	int a[3][3] = { 1,2,3,
					4,5,6,
					7,8,9 };
	//查找一个数字，比如7
	//可以遍历但时间复杂度就变为O（N^2）
	//O(1):不管几个元素都是遍历常数次
	int k = 7;
	//如果找到返回1，否则返回0
	int ret = find_num(a, 3, 3, k);
	if (ret == 1)
		printf("找到了\n");
	else
		printf("找不到\n");

	return 0;
}

如果要返回坐标怎么办（return只能返回一个值）怎么改

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
int find_num(int arr[3][3], int *px, int *py, int k)
{
	int x = 0;
	int y = *py - 1;
	while (x < *px && y >= 0) {
		if (arr[x][y] < k)
			x++;//加一行
		else if (arr[x][y] > k)
			y--;//去一列
		else {
			*px = x;
			*py = y;
			return 1;
		}
			
	}
	return 0;
}
int main()
{
	int a[3][3] = { 1,2,3,
					4,5,6,
					7,8,9 };
	int k = 7;
	int x = 3;//行
	int y = 3;//列
	/*
	&x，&y
	1.传入参数
	2.带回值
	*/
	int ret = find_num(a, &x, &y, k);
	if (ret == 1) {
		printf("找到了\n");
		printf("下标是:%d %d", x, y);
	}
		
	else
		printf("找不到\n");

	return 0;
}

字符串左旋

题目内容：

实现一个函数，可以左旋字符串中的k个字符

例：

ABCD左旋第一个字符得到BCDA

ABCD左旋两个字符得到CDAB

#include <stdio.h>
#include <string.h>
void string_rotate(char* str, int k)
{
	int i = 0;
	int len = strlen(str);
	for (i = 0; i < k; i++) {
		//每次左旋一个字符
		char tmp = *str;//首地址 
		// 把后面的n-1个字符往前挪 
		int j = 0;
		for (j = 0; j < len - 1; j++) {
			*(str + j) = *(str + j + 1);
		}
		//tmp再放到最后
		*(str + len - 1) = tmp;
	}
	
}
int main()
{
	char arr[10] = "ABCDEF"; 
	int k;
	scanf("%d", &k);
	string_rotate(arr, k);
	puts(arr);
	return 0;
 }

神奇的方法

比如A B C D E F k = 2
先逆序 A B 再逆序D E F
得到 B A F E D
再整体逆序得到
D E F A B
神奇
代码实现加个之前写过的逆序即可

#include <stdio.h>
#include <string.h>
#include <assert.h>
void reverse(char* left, char* right)
{ 
	assert(left);
	assert(right); 
	while (left < right) {
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
void string_rotate(char* str, int k)
{
	assert(str);
	int n = strlen(str);
	reverse(str, str + k - 1);//左 
	reverse(str + k, str + n - 1);//右 
	reverse(str, str + n - 1);//整体 
	
}

int main()
{
	char arr[10] = "ABCDEF"; 
	int k;
	scanf("%d", &k);
	string_rotate(arr, k);
	puts(arr);
	return 0;
 }

进一步深入

写一个函数，判断一个字符串是否是另外一个字符串旋转之后的字符串。

例：

给定s1=AABCD和s2=BCDAA,返回1
给定s1=abcd和s2=ACBD,返回0

分析

每转一次都比较以下

#include <stdio.h>
#include <string.h>
#include <assert.h>
int is_string_rotate(char* str1, char* str2)
{
	int i = 0;
	int n = strlen(str1);//5
	for (i = 0; i < n; i++) {
		//每次左旋一个字符
		char tmp = *str1;
		// 把后面的n-1个字符往前挪 
		int j = 0;
		for (j = 0; j < n - 1; j++) {
			*(str1 + j) = *(str1 + j + 1);
		}
		//tmp再放到最后
		*(str1 + n - 1) = tmp;
		if (strcmp(str1, str2) == 0) {
			return 1;
		}
	}
	return 0;
}
int main()
{
	char arr1[] = "AABCD"; 
	char arr2[] = "BCDAA";  
	int ret = is_string_rotate(arr1, arr2);
	if (ret == 1){
		printf("Yes");
	}
	else {
		printf("No");
	}
	return 0;
 }

神奇的方法

将AABCD重复俩遍可以得到所有的反转
AABCDAABCD
A ABCDA ABCD
AA BCDAA BCD
………

改版后的代码

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

int is_string_rotate(char* str1, char* str2)
{
	assert(str1);
	assert(str2);
	//长度不相等，肯定不是 
	if (strlen(str1) != strlen(str2)){
		return 0;
	}
	//1.str1字符串的后边追加一个str1
	//AABCDAABCD
	int n = strlen(str1); 
	strncat(str1, str1, n);//追加后面的字符串前n个在前面的字符串 
	//2.判断str2是否为str1的子串 
	strstr(str1, str2);//判断一个字符串是否是另一个字符串的子串 
	//返回找到的str2在str1第一次匹配的地址 
	char* ret = strstr(str1, str2);
	return ret != NULL;
}
int main()
{
	char arr1[20] = "AABCD"; 
	char arr2[] = "BCDAA";  
	int ret = is_string_rotate(arr1, arr2);
	if (ret == 1){
		printf("Yes");
	}
	else {
		printf("No");
	}
	return 0;
 }