[数据结构与算法]数据结构与算法-数组与字符串

一、数组与字符串

（一）数组

一组数据的集合

1.一维数组

（1）数组的创建

• 静态
• 动态

（2）数组名不是指针，数组名的地址是数组的首地址，它指代的是整个数组

（3）数组作为函数参数传入：数组名（作为数组的首地址传入，减少内存，通过指针访问）

#include <stdio.h>
#include <stdlib.h>

int Fuction(int *array,int size){

	return *(array+1);
}

void main(){
	int n = 100;
	//静态生成
	int array[n] = {11,22,33};
	//动态生成
	int *p = malloc(n*sizeof(int));
	printf("%d\n",sizeof(array));
	printf("%d\n",Fuction(array,100));
}

#include <iostream>
#include <vector>

//运算符重载，打印向量
ostream& operator << (ostream& o,vector<int>& array) {
	o << "[";
	for(auto x:array)
		o << x << ",";
	o << "]";
	return o;
}

int main(int argc,const char *argv[]) {
	
	int a[10];
	int *p = new int[10];

	//使用向量创建数组
	std::vector<int> array{1,2,3,4,5};
	cout << array <<endl;

	return 0;
}

import java.util.ArrayList;
public class Main(){
	public static void main(String[] args){
		//引用数组创建
		int [] array = new int[10];
		//数组列表模板创建数组
		ArrayList<Integer> al = new ArrayList<>();
		al.add(123);
		al.add(456);
		System.out.println(al);
	}
}

（4）数组元素查找

#include <stdio.h>

//返回值：数组下标（自带标志），找到为数组下标，找不到为-1
int findX(int *array,int size,int number) {
	int index = -1;
	for(int i =0;i < size;i++)
	{
		if(array[i] == number)
			index = i;
	}
	return index;
}

//返回值：标志，找到0，找不到-1
int getX(int *array,int size,int index,int *px) {
	int flag;
	if(index < 0 || index > size)
		flag = -1;
	else
		*px = array[index];
		
	return flag;
}

//返回值：最大值
int findMax(int *array,int size) {
	int max = array[0];
	for(int i = 0;i < size;i++)
	{
		if(max < array[i])
			max = array[i];
	}
	return max;
}

void main() {
	
	int array[5] = {1,2,3,4,5};
	int x = 2;
	int k = -1;
	k = findX(array,5,x);
	printf("%d\n",k);
	k = 2;
	int flag;
	flag = getX(array,5,k,&x);
	printf("%d\n",x);
	int max;
	max = findMax(array,5);
	printf("%d\n",max);
}

#include <iostream>
#include <vector>
#include <algorithm>
int main(int argc,const char *argv[]) {
	
	vector<int> array{1,2,3,4,5};
	vector<int>::iterator it;
	for(it = array.begin();it != array.end();it++)
	{
		printf("%d",*it);
	}
	int x;
	it = find(array.begin(),array.end(),x);
	cout << *it <<endl;
}

2.二维数组

在内存中还是一维存储的，只不过是逻辑上的二维

数组的数组（以数组为基本单位，一组数组的集合）

（1）array[][] 与 **p是否一样？

！不一样 array代表一个二维数组，p代表的是指向指针的指针变量

它们在内存上的存储方式是不一样的，数组是连续存储，指针并不一定是连续的

指针本身是指向某一个变量地址的，数组不是地址，所以不能用指针来代替数组

指针只能指向数组的首地址，可以用指针来对数组的元素进行访问，但是指针不是数组

所以 **P = array 是错误的，array不是指针，只能用(*p)[] = array，代表数组指针，指针指向的是整个数组（以数组为一个整体）

数组指针与指针数组？

数组指针 (*p)[]：本质是一个指针，指针指向的是一个数组（是整个数组，不是数组的首地址）

指针数组 *p[]：本质是一个数组，一组由指针变量组成的数组，数组里的每个元素都是指针

#include <stdio.h>

void main() {
	
	int array[2][3];
	int (*p)[3] = array;
	printf("%d",array);
	printf("%d",p);
}

public class Main() {
	public static void main(String[] args){
		
		int [][] array = new int[2][];
		array[0] = new int[3];
		array[1] = new int[4];
	}
}

字符串

一串字符

（1）字符串的创建

#include <stdio.h>

void main(){
	
	char *s = "hello world";
	//为什么输出的不是指针变量存储的字符串地址，因为输出类型为%s,也就是字符串类型
	printf("%s",s);
	char s1[] = "hello world";
	printf("%s",s1);
}

#include <iostream>
using namespace std;

int main(int argc,const char *argv[]) {
	
	string name = "hello world";
	cout << name <<endl;
	
	return 0;
}

public class Main(){
	public static void main(String[] args){
		String name = "hello world";
		System.out.println(name);
	}
}

（2）字符串常用操作

复制、拼接、比较等常用操作，各个语言都提供了相应的API，需要用到哪个就去查就行了

（3）字符串匹配

正则表达式

一种自动机，可以用来字符串匹配

#include <iostream>
#include <regex>

using namespace std;

int main(int argc,const char *argv[]){

	string email = "abc123@adg1.xyz";
	regex r("[a-z0-9]+@[a-z0-9]+\\.[a-z]+");
	cout << regex_match(email,r) <<endl;
	
	return 0;
}

import java.util.regex.Pattern;
public class Main{
	public static void main(String[] args){
		String email = "abc12@de.com";
		String r = "[a-z0-9]+@[a-z]+\\.[a-z]+";
		System.out.println(Pattern.matches(r,email));
	}
}