约瑟夫环——一枪一个小moca
#include<stdio.h>
int main(){
int n,m=3;
scanf("%d",&n);
int ans=0,i=0;
for(i=1;i<=n;i++){
ans=(ans+m)%i;
}
printf("%d",ans+1);
return 0;
}
二分查找/二分法
-
查找a中是否存在key
int find(int a[], int n, int key){ int l = 0, r = n - 1, mid; while (l <= r){ mid = l + (r - l) / 2; //左右边界中间点的值 if (a[mid] < key) l = mid + 1; //如果当前的mid比目标小，则左边界右移到mid右边 else if (a[mid] > key) r = mid - 1; //如果当前的mid比目标大，则右边界左移到mid左边 else return mid; //如果当前的mid等于目标，返回mid } return -1; //没找到key } -
查a中第一个大于等于 key 的
int find_first(int a[], int n, int key){ int l = 0, r = n - 1, mid; while (l <= r){ mid = l + (r - l) / 2; if (a[mid] < key) l = mid + 1; //如果当前的mid<目标，则左边界右移到mid右边 else r = mid - 1; //如果当前的mid>=目标，则右边界左移到mid左边 } if (l < 0 || l >= n) return -1; //key<a[0] || key>a[n-1] return a[l] == key ? l : -1; //如果key不存在，返回-1 } -
查a中第一个大于key的
int find_last(int a[], int n, int key){ int l = 0, r = n - 1, mid; while (l <= r){ mid = l + (r - l) / 2; if (a[mid] <= key) l = mid + 1; //如果当前的mid<=目标，则左边界右移到mid右边 else r = mid - 1; //如果当前的mid>目标，则右边界左移到mid左边 } if (l < 0 || l >= n) return -1; //key<a[0] || key>a[n-1] return a[l] == key ? l : -1; //如果key不存在，返回-1 } -
二分法求单调（递增）函数func(x)的解
double solve(double left, double right, double y){ double mid; while (right - left > eps){ mid = (right + left) / 2; if (func(mid) > y) // 递减则 func(mid) < y right = mid; else left = mid; } return mid; }
排序
-
冒泡排序-升序
void bubble_sort(int a[], int n){ for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++){ if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } -
选择排序-升序
void select_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min_idx]) { min_idx = j; } } if (min_idx != i) { int temp = a[i]; a[i] = a[min_idx]; a[min_idx] = temp; } } } -
qsort快排
qsort(a, n, sizeof(double), cmp); //a 需要排序的数组名称 n 需要排序的个数 sizeof(double) 一个元素的大小 //升序排序，最基础的写法 int cmp(const void*p1, const void*p2){ double *d1=(double *)p1; //转换为目标类型 double *d2=(double *)p2; //转换为目标类型 if((*d1 - *d2) < -eps) return -1; //返回负数=p1在p2前面 else if((*d1 - *d2) > eps) return 1; //返回正数=p1在p2后面 else return 0; }// 结构体的指针数组的cmp int cmp(const void *p1, const void *p2){ struct tnode **d1 = (struct tnode **)p1; struct tnode **d2 = (struct tnode **)p2; if((*d1)->weight < (*d2)->weight){ return -1; }else if((*d1)->weight > (*d2)->weight){ return 1; }else{ if((*d1)->c < (*d2)->c){ return -1; }else{ return 1; } } } -
归并排序
void msort(int left, int right){ //归并排序 if(left == right){ // 只剩一个元素，已经有序，无需排序 return; } int mid = (left+right)/2; // 排序左侧 msort(left, mid); // 排序右侧 msort(mid+1, right); // 合并 int left_i = left, right_i = mid+1, i=left; while(left_i<=mid && right_i<=right){ if(a[right_i] < a[left_i]){ temp[i++] = a[right_i]; right_i++; }else if(a[right_i] > a[left_i]){ temp[i++] = a[left_i]; left_i++; }else{ temp[i++] = a[right_i]; temp[i++] = a[left_i]; left_i++; right_i++; } } while(left_i<=mid){ temp[i++] = a[left_i++]; } while(right_i<=right){ temp[i++] = a[right_i++]; } for(int j=left; j<=right; j++){ // printf("%d ", temp[j]); a[j] = temp[j]; } // puts(""); }
高精度
-
高精度加法
#include <stdio.h> #include <string.h> #define MAX 1000005 char s1[MAX], s2[MAX]; int a1[MAX], a2[MAX]; int main() { int len, len1, len2, i, j; scanf("%s", s1); //s1读入第一个数字 scanf("%s", s2); //s2读入第二个数字 len1 = strlen(s1); len2 = strlen(s2); for (i = 0; i < len1; i++) //字符串倒序导入数组，方便从低位开始运算 a1[i] = s1[len1 - 1 - i] - '0'; for (i = 0; i < len2; i++) //字符串中的是字符，要转换成数字 a2[i] = s2[len2 - 1 - i] - '0'; len = (len1 > len2) ? len1 : len2; for (i = 0; i < len; i++) { a1[i + 1] += (j = (a1[i] + a2[i]) / 10);//进位 a1[i] = (a1[i] + a2[i]) % 10;//保留 } if (j) len++;//最后一位是否进位 for (i = 0; i < len; i++) printf("%d", a1[len - 1 - i]); return 0; } -
高精度减法
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 1000005 char s1[MAX], s2[MAX]; int a[MAX], b[MAX]; int main() { int len, i; scanf("%s %s", s1, s2); int l1 = strlen(s1); int l2 = strlen(s2); int flag = 0; if (l1 < l2 || (strcmp(s1, s2) < 0 && l1 == l2)) { //s2代表的数更大 len = l2; flag = 1; for (i = l2 - 1; i >= 0; i--) a[l2 - i - 1] = s2[i] - '0'; for (i = l1 - 1; i >= 0; i--) b[l1 - i - 1] = s1[i] - '0'; } else { len = l1; for (i = l1 - 1; i >= 0; i--) a[l1 - i - 1] = s1[i] - '0'; for (i = l2 - 1; i >= 0; i--) b[l2 - i - 1] = s2[i] - '0'; } for (i = 0; i < len; i++) { a[i] -= b[i]; if (a[i] < 0) { a[i + 1] -= 1; a[i] += 10; } } while (a[len - 1] == 0 && len > 1) len--; if (flag == 1) printf("-"); for (i = len - 1; i >= 0; i--) printf("%d", a[i]); printf("\n"); return 0; } -
高精度乘法
#include <stdio.h> #include <string.h> #define MAX 1000005 char s1[MAX], s2[MAX]; int a1[MAX], a2[MAX], ans[MAX]; int main() { int i, j, len1, len2; scanf("%s%s", s1, s2); len1 = strlen(s1); len2 = strlen(s2); for (i = 0; i < len1; i++) { a1[i] = s1[len1 - 1 - i] - '0'; } for (i = 0; i < len2; i++) { a2[i] = s2[len2 - 1 - i] - '0'; } for (i = 0; i < len1; i++) { for (j = 0; j < len2; j++) { ans[i + j] += a1[i] * a2[j]; } } for (i = 0, j = 0; i < len1 + len2; i++) { ans[i] += j; j = ans[i] / 10; ans[i] %= 10; } for (; ans[i] == 0; i--){ if(i<0){ printf("0"); break; } } //跳过前面的0 for (; i >= 0; i--) { printf("%d", ans[i]); } return 0; }
最大公约数
int gcd(int a, int b) {
while (b != 0) {
int tmp = a;
a = b;
b = tmp % b;
}
return a;
}
输出全排列
#include <stdio.h>
int n;
int stack[10];
void print_stack();
void dfs(int len);
int find_in_stack(int key, int len);
int main() {
scanf("%d", &n);
dfs(0);
return 0;
}
void dfs(int len) {
if (len == n) {
print_stack();
return;
}
for (int i = 1; i <= n; i++)
if (!find_in_stack(i, len)) {
stack[len] = i;
dfs(len + 1);
}
}
void print_stack() {
for (int i = 0; i < n; i++)
printf("%d ", stack[i]);
puts("");
}
int find_in_stack(int key, int len) {
for(int i = 0; i < len; i++)
if (key == stack[i])
return 1;
return 0;
}
计算组合数
long long comb(long long n, long long m) { //n >= m
if (m == n || m == 0) return 1;
else return comb(n - 1, m) + comb(n - 1, m - 1);
}
快速幂取模-a的b次方%p
long long fast_pow(long long a, long long b, long long p) {
long long ans = 1;
a = a % p;
while (b) {
if (b & 1) //b二进制的最后一位是1时
ans = (ans * a) % p;
b >>= 1; // b按位右移
a = a * a % p;
}
return ans;
}
-
假设我们拿到了a，并且b=11。想求 a11，但是又不想乘11次，有点慢。以电脑视角稍稍观察一下 b=(11)10，二进制下是 b=(1011)2。制作一个base。现在base = a，表示的是，a1 = a。待会base会变的。制作一个ans，初值 11，准备用来做答案。
while(b > 0) { -
循环一。看，b（二进制）的最后一位是11吗？是的。这代表a11=a8×a2×a1中的“ ×a1 ”存在。所以 ans*=base。
if(b & 1) ans *= base; /*关于 b & 1： “&”美名曰“按位与”。 x & y 是二进制 x 和 y 的每一位分别进行“与运算”的结果。 与运算，即两者都为 1 时才会返回 1，否则返回 0。 那么 b & 1 二进制 b = 1011 1 = 0001 b&1 = 0001 因为 1（二进制）的前面几位全部都是 0， 所以只有 b 二进制最后一位是 1 时，b & 1 才会返回 1。 挺巧妙的，并且很快。)*/然后base努力上升，他通过自乘一次，使自己变成a2。
base *= base;同时
b >>= 1;它把（二进制的）自己每一位都往右移动了。原来的最后第二位，变成了最后第一位。b=(101)2。
} -
循环二，再看看b，最后一位还是11。这说明有“ ×a2 ”，ans∗=base。base继续努力，通过base∗=base让自己变成了a4。然后b也右移一位。b=(10)2。
-
循环三，可是b的最后一位不再是1了，说明不存在“×a4”。base自我升华，达到了a8。且 b>>=1。这一步中，答案没有增加，可是毕竟 b>0，还有希望。
-
循环四，b的最后一位是1，这说明“×a8”的存在。ans∗=base。由于b再右移一位就是0了，循环结束。
总的来说，如果b在二进制上的某一位是1，我们就把答案乘上对应的a2^n。
一些相关笔记补充
-
直接求幂可以用循环解决，但是会出现溢出的问题
long long normal(long long base,long long power){ long long result=1; for(int i=1;i<=power;i++){ result*=base; } return result; } -
取模运算的法则：
(a+b)%p=(a%p+b%p)%p
(ab)%p=(a%pb%p)%p，利用这一法则可以在循环乘积每一步前先取模来防止溢出 -
快速幂算法：每一步将指数分成两半，相应底数做平方运算，最后求出的结果实际是指数为奇数时的底数相乘
while(power>0){ if(power&1==1){ result=result *base; } power>>=1; base=base*base; }
汉诺塔
#include <stdio.h>
void move(int n, char from, char to) {
printf("Move %d from %c to %c!\n", n, from, to);
}
void hanoi(int n, char from, char via, char to) {
if (n == 1){ //只剩一个盘子，递归结束
move(n, from, to);
}else{
hanoi(n - 1, from, to, via); //先把n-1个盘子拿走
move(n, from, to); //再移动最底下的
hanoi(n - 1, via, from, to); //再把n-1个搬到目标棍子上
}
}
int main(){
int n;
scanf("%d", &n);
char a = 'A', b = 'B', c = 'C';
hanoi(n, a, b, c);
return 0;
}
判断质数
-
法一：直接判断
int is_prime(int x){ if (x < 2) return 0; for (int i = 2; i * i <= x; i++){ if (x % i == 0) return 0; } return 1; } -
生成质数表再查找
//利用已有的质数表primes，判断n是否为质数 int isPrime(int primes[], int n){ int i; for(i=0; primes[i]*primes[i] <= n; i++){ if(n % primes[i]== 0) return 0; } return 1; } //构造≤Q的质数表（Q>=5） void init_primes(int primes[], int Q){ int count=3, num, step; primes[0] = 2; primes[1] = 3; primes[2] = 5;//头3个质数 num = 7; step = 2;//初始为2 while(count < Q){ step = 6-step;// 构造4-2-4-2-...序列，减少遍历 if(isPrime(primes, num)) primes[count++] = num; num += step;// 下一个可能的质数 } }
判断闰年
if((y%4==0 && y%100!=0) || y%400==0){
printf("闰喵29\n");
}else{
printf("不闰喵28\n");
}
计算逆序数
// 利用归并排序计算一串数字a中的逆序数
int a[500010], temp[500010];
long long nixu;
void msort(int left, int right);
int main() {
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
}
msort(0, n-1);
printf("%lld", nixu);
return 0;
}
void msort(int left, int right){
if(left == right){ // 只剩一个元素，已经有序，无需排序
return;
}
int mid = (left+right)/2;
// 排序左侧
msort(left, mid);
// 排序右侧
msort(mid+1, right);
// 合并
int left_i = left, right_i = mid+1, i=left;
while(left_i<=mid && right_i<=right){
if(a[right_i] < a[left_i]){
nixu += (mid-left_i+1);
temp[i++] = a[right_i++];
}else{
temp[i++] = a[left_i++];
}
}
while(left_i<=mid){
temp[i++] = a[left_i++];
}
while(right_i<=right){
temp[i++] = a[right_i++];
}
for(int j=left; j<=right; j++){
a[j] = temp[j];
}
}
斐波那契数列
-
斐波那契数列
int fb(int n){ if(n<=3) return 1; return fb(n-3)+fb(n-1); } -
广义斐波那契数列
#include <stdio.h> long long gfb(long long n,long long p,long long q,long long a,long long b,long long c ); int main(){ long long n,t,p,q,a,b,c; scanf("%lld%lld%lld%lld%lld%lld",&n,&p,&q,&a,&b,&c); t=gfb(n,p,q,a,b,c); printf("%lld",t); return 0; } long long gfb(long long n,long long p,long long q,long long a,long long b,long long c ){ if(1==n) return p; if(2==n) return q; if(n>=3) return (a*gfb(n-1,p,q,a,b,c)+b*gfb(n-2,p,q,a,b,c)+c); }
大数乘法取模-(a*b)%mod
#include <stdio.h>
long long quickMulMod(long long a, long long b, long long mod){
long long ans = 0;
while (b){
if (b & 1ll){
ans = (ans + a) % mod;
}
a = (a + a) % mod;
b >>= 1;
}
return ans;
}
计算三角形周长面积
#include <stdio.h>
#include <math.h>
double S(double a,double b,double c);
double C(double a,double b,double c);
int main(){
int t;
double x1,y1,x2,y2,x3,y3;
double a,b,c;
scanf("%d",&t);
for(int i=0;i<t;i++){
scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
a=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
c=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
printf("%.3f %.3f\n",C(a,b,c),S(a,b,c));
}
return 0;
}
double C(double a,double b,double c){
return a+b+c;
}
//海伦公式
double S(double a,double b,double c){
double co,si;
co=(a*a+b*b-c*c)/(2*a*b);
si=sqrt(1-co*co);
return a*b*si/2;
}
进制转化
-
十进制转二进制小数
#include <stdio.h> #include <string.h> int main() { double xiao,x; int zheng,a[50],b[11],i=0,cnt=0,len=0,tmp; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); scanf("%lf",&x); tmp=zheng=(int)x; //整数部分 if(!zheng){ //整数是0 printf("0"); }else{ //整数不是0 while(zheng){ a[len++]=zheng%2; zheng /= 2; } } for(i=len-1;i>=0;i--){ //输出整数部分 printf("%d",a[i]); } printf("."); //输出小数点 xiao=x-tmp; //小数部分 while(xiao){ tmp=(int)(xiao*2); b[cnt++]=tmp; xiao=2*xiao-tmp; } for(i=0;i<10;i++){ //输出小数部分 printf("%d",b[i]); } return 0; } -
二进制转十进制
int bin2Dec(int arr[]){ /* * 将2进制转为10进制 * 设1个int的32位bit由低到高存在arr[0]...arr[31] * 函数命名是binary to decimal的缩写 */ int ret = 0; for (int i = 0; i < 32; i++){ ret += arr[i] * (1 << i); //相当于ret += arr[i] * (int)pow(2, i); } return ret; //ret是得到的十进制数 } -
任意进制转换为2-36进制的long long
#include <stdio.h> #include <ctype.h> typedef long long ll; /** * Convert string to long long int * * @param s source string * @param base 2 <= base <= 36 * @return long long int value */ ll str2ll(char s[], int base) { ll sum = 0; int x, i; for (i = 0; s[i]; i++) { if (isdigit(s[i])) x = s[i] - '0'; else if (islower(s[i])) x = s[i] - 'a' + 10; else if (isupper(s[i])) x = s[i] - 'A' + 10; else { printf("Unexpected Character!"); return -1; } if (x >= base) { printf("Unexpected Character!"); return -1; } sum *= base; sum += x; } return sum; } int main() { char s[32]; int x; scanf("%s%d", s, &x); //s需要转换的字符串 //x进制 printf("%lld", str2ll(s, x)); return 0; }
首个出现三次的字母
#include <stdio.h>
#include <string.h>
int w1[27]={0};
int w2[27]={0};
int main()
{
int i=0;
char str[105]={};
scanf("%s",str);
int len=strlen(str);
int flag=0;
for(i=0;i<len;i++){
if(w1[str[i]-'a']==0){
w1[str[i]-'a']=i+1;
}else{ //出现过一次
if(w2[str[i]-'a']==0) w2[str[i]-'a']=i+1;
else{
printf("%c %d %d %d",str[i],w1[str[i]-'a'],w2[str[i]-'a'],i+1); //哪个字符 第一出现 第二次出现 第三次出现
flag=1;
}
}
if(flag) break;
}
return 0;
}
子串逆置
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#define ll long long
#define ull unsigned long long
char s[205];
char t[205];
void swap(char a,char b);
int main(){
scanf("%s %s",s,t);
int ls=strlen(s),lt=strlen(t);
int i=0,j=0;
int head,tail;
char tmp;
int flag=1;
for(i=0;i<=(ls-lt);i++){
j=0;
flag=1;
if(s[i]==t[j]){
for(j=1;j<lt;j++){
if(s[i+j]!=t[j]){
flag=0;
break;
}
}
}
if(flag&&j==lt){
for(head=i,tail=i+lt-1;head<tail;head++,tail--){
tmp=s[head];
s[head]=s[tail];
s[tail]=tmp;
}
i+=lt-1;
}
}
for(i=0;i<ls;i++){
printf("%c",s[i]);
}
return 0;
}
字符串归零（by onlyar）
typedef unsigned long long ull
void fill_zero_to_string(char *address){
ull zero =0;
for (int i=0;i*sizeof(zero)< MAX_KEEPWORD_LEN; i++){
*((ull *) address + i) = zero;
}
}
字符串查找（或许你想写个strstr吗）
#include <stdio.h>
#include <string.h>
#define MN 50005
char hastack[MN];
char needle[MN];
int strStr(char a[],char b[]);
int main(){
gets(hastack);
gets(needle);
printf("%d",strStr(hastack,needle));
return 0;
}
int strStr(char a[],char b[]){
if(b==NULL){
return 0;
}else{
int flag=1;
int la=strlen(a),lb=strlen(b),i=0,j=0;
for(i=0;i<=(la-lb);i++){
flag=1;
for(j=0;j<lb;j++){
if(a[i+j]!=b[j]){
flag=0;
break;
}
}
if(flag) return i+1;
}
if(!flag) return -1;
}
}
多关键字排序-所以说这位不知名的学长你为什么要三目运算符套三目运算符啊（害怕）
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#define ll long long
#define ull unsigned long long
int n, k;
struct node{
int id;
int w[11];
};
struct node arr[1010];
int cmp(const void *a, const void *b){
struct node c = *(struct node *)a;
struct node d = *(struct node *)b;
int i;
for(i = 0; i < k; ++i)
if(c.w[i] == d.w[i]) continue;
else return i % 2 ? (d.w[i] > c.w[i] ? 1 : -1) : (c.w[i] > d.w[i] ? 1 : -1);
return c.id - d.id;
}
int main(){
scanf("%d%d", &n, &k);
int i, j;
for(i = 0; i < n; ++i){
arr[i].id = i + 1;
for(j = 0; j < k; ++j)
scanf("%d", &arr[i].w[j]);
}
qsort(arr, n, sizeof(arr[0]), cmp);
for(i = 0; i < n; ++i)
printf("%d ", arr[i].id);
return 0;
}
你绝对不会用到的-二的幂次方-才不是因为看不懂不敢用呢
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#define ll long long
#define ull unsigned long long
void re(int n);
int main(){
ll n;
scanf("%lld",&n);
re(n);
return 0;
}
void re(int n){
int flag=0;
if(n==0){
printf("0");
}else if(n==1){
printf("2(0)");
}else{
for(int i=31;i>=0;i--){
if(n&(1<<i)){
printf(flag++?"+2(":"2(");
re(i);
printf(")");
}
}
}
}
我觉得不会再考一遍吧-双阶乘-但还是存一下吧
- 版本1
#include <stdio.h>
int a[2500000];//定义数组同时将数组全部初始化
int main(){
long long n,t,k=0;
scanf("%lld", &t);
int i,m,s,c,temp;//i用来乘阶乘；m为数组位数; s为位数; c是进位
while(k<t){
scanf("%lld", &n);
if(n == 0){
printf("1\n");
}else{
if(n%2 == 0&&n!=0){ //偶数情况
a[0]=1;
s=1;
//利用数组来存储结果
for(i=2;i<=n;i+=2){
for(m=0,c=0;m<s;m++){
temp=a[m]*i+c;
a[m]=temp%10;
c=temp/10; //进位
}
while(c!= 0){
++s;
a[s-1]=c%10;
c=c/10;
}
}
//倒序输出结果
for(i=s-1;i>=0;i--){
printf("%d",a[i]);
}
printf("\n");
}else{ //奇数情况
a[0]=1;
s=1;
//利用数组来存储结果
for(i=1;i<=n;i+=2){
for(m=0,c=0;m<s;m++){
temp=a[m]*i+c;
a[m]=temp%10;
c=temp/10;
}
while(c!=0){
++s;
a[s-1]=c%10;
c=c/10;
}
}
//倒序输出结果
for(i=s-1;i>=0;i--){
printf("%d",a[i]);
}
printf("\n");
}
}
k++;
}
return 0;
}
- 版本2
#include<stdio.h>
int main(){
int a[10001];
int b,sum;
int x=0;
int y,z=0;
int i=0,k=1;
scanf("%d",&y);
for(k=1;k<=y;k++){
z=0;
i=0;
while(i<=10000){
a[i]=0;
i++;
}
a[10000]=1;
scanf("%d",&b);
for(;b>=2;b-=2){
for(i=10000;i>=0;i--){
a[i]*=b;
}
for(i=10000;i>=0;i--){
if(a[i]>=10000){
a[i-1]+=(a[i]/10000);
a[i]%=10000;
}
}
}
while(a[z]==0){
z++;
}
printf("%d",a[z]);
for(i=z+1;i<=10000;i++){
printf("%04d",a[i]);
}
printf("\n");
}
return 0;
}
只能伸长不能缩短的变长数组
/*
* 定义结构体 struct Vector，其指针重命名为 VecPtr
* length : 数组已使用的长度
* capacity : 数组的容量
* array ：用于存放数据的区域
*/
typedef struct Vector {
int length;
int capacity;
int *array;
} *VecPtr;
/*
* 创建一个空的变长数组，初始容量为 5，返回变长数组的指针
*/
VecPtr create_vector() {
VecPtr vec = (VecPtr) malloc(sizeof(struct Vector));
vec->array = (int *) malloc(5 * sizeof(int));
vec->capacity = 5;
vec->length = 0;
return vec;
}
/*
* 这个函数可以在数组的尾部插入元素，当数组满了自动扩大一倍
* vec : 变长数组的指针
* item : 要插入的元素
*/
void push_back(VecPtr vec, int item) {
vec->array[vec->length] = item;
vec->length++;
if (vec->length == vec->capacity) // 满了
vec->array = (int *) realloc(vec->array, 2 * vec->capacity * sizeof(int)); // 翻倍
}
