第六章 数组
要存储大量的数据,就必须定义存储空间很大的变量,可以用数组和结构体。这里我们将数组。
6.1 数组与存储分配
6.1.1 定义数组
数组是用来存放各个数据元素的一组相互间有关联的变量,这一组变量有共同的名称,用名称及在数组内的序号标识各个变量。
定义数组的基本格式:
- “类型”可以是任何一个系统固有的类型标识符:char、int、float、double等,也可以是自定义类型标识符;“数组名”必须符合标识符的命名规则;“元素个数”用来确定数组元素的数量,必须是常量或者由常量组成的计算式,其计算结果必须是正整数。
补充:自定义类型标识符 typedef : 用 typedef 定义“新类型”的格式(说是“新类型”其实就是原来的类型换了一个叫法):
固定大小的数组:
如果你在编译时就已经知道数组的大小,你可以直接定义一个固定大小的数组:
int a[10]; // 定义一个包含10个整数的数组
变量长度数组 (VLA):
如果你需要在运行时确定数组的大小,并且你确信你的编译器支持C99标准,你可以使用变量长度数组 (VLA):
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int a[n]; // 根据用户输入定义数组大小
// 接下来可以对数组进行操作
return 0;
}
注意:VLA 是在 C99 中引入的,并非所有编译器都支持。而且,VLA 会分配在栈上,可能受限于栈大小。
动态内存分配:
如果你需要在运行时确定数组的大小,并且希望在堆上分配内存以避免栈溢出,可以使用 malloc 和 free 进行动态内存分配和释放:
malloc是C语言系统关于动态内存管理的一个库函数,使用该函数时必须在程序前面用 #include <stdlib.h> 预处理命令。
函数原型:void*malloc(unsigned int);
- 函数malloc的入口参数是一个无符号整数,这是向系统申请空间的字节数。在使用时可以用 数据个数*sizeof(数据类型) 来求出不同数据类型所占据的字节数,同时sizeof 也解决了在不同编译系统中的同样的数据类型可能占据不同的字节数的问题。
- 出口参数是一个基类型为void的指针。我们知道void * 是一种通用指针类型,它可以指向任何类型的对象。所以我们在使用时需要将返回值强制转换成目标类型指针。
- 函数的功能是在系统管理的内存中按参数指定的大小找一段连续的内存区域。申请内存空间后应立即判断是否申请成功,如果系统可以分配出这样一段内存,则函数返回值是这一段内存的起始地址,如果存储区已不能满足内存分配的要求,则函数返回值是NULL。
- 如果申请成功则需要立刻把函数返回值用对应的指针类型数据把返回值存起来。存放变量后可以用访问指针的方法访问该变量。
- 使用malloc动态申请到的内存空间在使用完后要交还给系统,让系统可以再把这一段存储空间分配作其他的用途。“交还”是用库函数free实现。
库函数free:
函数原型:void free(void*);
用于释放由malloc函数申请的内存。使用时需要#include <stdlib.h>的预处理命令。
注意事项:
- 只释放一次:确保不要多次释放同一个指针,因为这会导致未定义行为(Undefined Behavior)。
free(ptr); // 正确
free(ptr); // 错误,不要重复释放同一个指针
- 检查指针是否为 NULL:在释放内存之前,最好检查指针是否为 NULL,以避免释放 NULL 指针。
if (ptr != NULL)
{
free(ptr);
ptr = NULL; // 将指针重新设置为 NULL,避免悬挂指针
}
- 释放后设置指针为 NULL:释放内存后,通常将指针设置为 NULL,以避免悬挂指针(dangling pointer)的问题。
free(ptr);
ptr = NULL; // 避免悬挂指针
完整malloc和free使用过程
#include <stdlib.h>
//其他预处理命令
int main()
{
int p*=NULL;//对指针变量初始化
int n;
scanf("%d",&n); //输出想要的数据个数
p=(int*)malloc(n*sizeof(int));//申请n个大小为sizeof(int)的存储空间并返回int类型的地址
//立即判断是否申请成功
if(p==NULL)
printf("内存不足");
else
{
//申请成功的相关操作
}
free(p);//使用完后释放该内存
p=NULL;//避免悬挂指针
return 0;
}
如果使用了多个 malloc 调用来动态分配内存,那么需要为每个 malloc 调用对应一个 free 调用来释放相应的内存。这是因为每个 malloc 调用分配的内存块都是独立的,每个块都需要单独释放。
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *ptr1 = NULL;
int *ptr2 = NULL;
int *ptr3 = NULL;
// 分配内存
ptr1 = (int *)malloc(10 * sizeof(int));
if (ptr1 == NULL)
{
fprintf(stderr, "Memory allocation for ptr1 failed!\n");
return 1;
}
ptr2 = (int *)malloc(20 * sizeof(int));
if (ptr2 == NULL)
{
fprintf(stderr, "Memory allocation for ptr2 failed!\n");
return 1;
}
ptr3 = (int *)malloc(30 * sizeof(int));
if (ptr3 == NULL)
{
fprintf(stderr, "Memory allocation for ptr3 failed!\n");
return 1;
}
// 使用内存
for (int i = 0; i < 10; i++)
{
ptr1[i] = i;
}
for (int i = 0; i < 20; i++)
{
ptr2[i] = i + 10;
}
for (int i = 0; i < 30; i++)
{
ptr3[i] = i + 30;
}
// 打印数组内容
for (int i = 0; i < 10; i++)
{
printf("%d ", ptr1[i]);
}
printf("\n");
for (int i = 0; i < 20; i++)
{
printf("%d ", ptr2[i]);
}
printf("\n");
for (int i = 0; i < 30; i++)
{
printf("%d ", ptr3[i]);
}
printf("\n");
// 释放内存
free(ptr1);
ptr1 = NULL;
free(ptr2);
ptr2 = NULL;
free(ptr3);
ptr3 = NULL;
return 0;
}
在这里我们看到一个新内容“NULL”,我们在补充一下。
定义:NULL 是一个预处理器宏定义,用于表示一个空指针常量。它是一个特殊的值,用来表示一个指针不指向任何有效的对象或内存位置。
在 C 语言中,NULL 的定义通常有两种形式:
传统定义:
#define NULL ((void *)0)
C99标准定义:
#define NULL (void *)0
NULL的应用:
(1)初始化指针:在定义指针时,将其初始化为 NULL 表示该指针暂时不指向任何对象。
int *ptr = NULL; // 指针 ptr 被初始化为 NULL
(2)检查指针是否为空:在使用指针之前,通常需要检查指针是否为 NULL,以避免未定义行为。遵守“先定义后使用”原则。
if (ptr == NULL)
printf("Pointer is NULL\n");
else
{
// 使用指针 ptr
}
(3)表示函数返回值:某些函数(例如:malloc)可能返回一个指向动态分配内存的指针,如果没有成功分配内存,通常返回 NULL。
int *ptr = NULL; // 初始化指针为 NULL
ptr = (int *)malloc(sizeof(int));// 分配内存
if (ptr == NULL)
printf("Memory allocation failed!\n");
else
{
//内存分配成功后的操作
}
注意:
NULL: 通常叫做“空指针”或“空指针常量”。
void*: 通常叫做“通用类型指针”或者“空类型指针”。
NULL 和 void* 的区别:
NULL:是一个特定的空指针常量。
void*:是一个通用指针类型,可以指向任何类型的对象。
ok,到目前为止我们补充的内容已经写完了,如果想知道更加详细的内容请看后续章节,现在我们回归数组这里。
- 数组元素原指数组中的数据,引入数组的概念之后,数组元素被用来指称数组中的一个存储单元,而把存放在这个单元中的数据称为数组元素的值,在不引起混淆的情况下也可以简称数组元素。
- 访问数组元素一般用“数组名[下标]”的形式指出访问数组的哪一个元素,“下标”从0开始,最大值为“元素个数”减1。
- 不允许访问整个数组,数组名不代表整个数组,而是代表数组的0号下标元素在内存中的地址。但为了叙述方便,在文字描述中指称整个数组时仍然称“数组变量+数组名”。
6.1.2 数组的存储分配
定义一个数组则是命令计算机安排一组存储单元,每一个存储单元占据的内存字节数及存储数据形式相同,由定义数组时的“类型”确定,各个存储单元在内存中连续安排。
6.1.3 数组元素的初值
给数组初始化的格式:
- “常量表”是用逗号分隔的若干常量,常量的个数不得超过“元素个数”。
- 定义char 或 unsigned char 型数组时,“常量表”可以是字符串常量,格式如下:
eg:
写法一:
char s[10]={'a','b','c','d','f','\0'}; //显式地加入了字符串终止符
或
char s[10]={'a','b','c','d','f'}; //需要手动添加终止符
写法二:
char s[10]={"abcdf"}; //隐式地加入了字符串终止符
写法三:
char s[10]="abcdf"; //隐式地加入了字符串终止符
由于字符串都是以“ \0 ”作为结束符的符号串,结束符需要占据一个字符型存储单元,所以在定义用与存放字符串的字符数组时需要考虑把数组元素+1,为存放结束符准备1字节的存储空间(如果字符串刚好占满了整个字符数组,而没有额外的空间来存放\“0“,则会导致三个问题:字符串无法正确解析,溢出风险,内存安全问题)。
- 如果声明了一个整型数组但没有显式地初始化所有元素,那么未初始化的元素将具有不确定的值(Undefined Value)。这意味着它们可以包含任何值,具体取决于编译器和运行时环境。
同理,如果声明了一个字符数组但没有显式地初始化所有元素,那么未初始化的元素将具有不确定的值(Undefined Value)。这意味着它们可以包含任何值,具体取决于编译器和运行时环境。
如果一个整型数组,并且只提供了一部分初始值,那么未提供的部分将被初始化为0(数字0)
如果声明了一个字符串并且仅部分初始化,那么未初始化的字符之后会被自动填充为“ \0 ”(空字符),这是因为在C语言中字符串是以“ \0 ”结尾的。
6.2 访问数组元素
典型应用:
- 数据统计
(均匀分布的)随机数的生成三个要点:
(1)在main前面用#include 包含文件windows.h,写成如下形式:
#include "windows.h"
(2)在main中先用“srand(GetCurrentTime());”把随机数系统初始化;
srand(GetCurrentTime());
(3)生成a~b范围的公式为:
a + rand()%(b-a+1)
eg:用随机数工具模拟掷色子的现象:掷100次色子,显示每次是哪个面朝上,并统计6个面朝上各出现了多少次。
#include <stdio.h>
#include "windows.h"
int main()
{
int a[6]={0},i,n;
srand(GetCurrentTime());//把随机数系统初始化
for(i=0;i<100;i++)
{
n=rand()%6;
printf("%4d ",n+1);
a[n]++;
}
printf("\n统计结果:\n");
for(i=0;i<6;i++)
{
printf("%d号面朝上的次数%d\n",i+1,a[i]);
}
return 0;
}
- 查找
“判断一批数据中是否存在指定的值”是一种最基本的查找。存储数据的组织形式不同,查找的形式及方法也很多。最简单的查找方法就是顺序查找,即逐个检查每一个数据,直到发现目标值为止,或者找完了所有数据也没有发现目标。无论哪一种情况,都可以作出“是否存在”的判断。另一种常用的查找方法是在一批数据中求最大值或最下值。
“存在型”查找:
eg:产生100个1000以内的随机非负数,存放到某整型数组中。对于键盘输入的一个整数值,判断数组中是否存在这个数,反复查找直到输入-1为止。
#include <stdio.h>
#include "windows.h"
#define N 100
int main()
{
int i,n,a[N],k;
srand(GetCurrentTime());
for(i=0;i<N;i++)
a[i]=rand()%1000; //产生100个数据
while(1)
{
scanf("%d",&n); //输入要查找的目标值
if(n==-1) //-1结束进程
break;
k=0;
while(k<N&&a[k]!=n)
k++; //未找完且未找到则准备查看下一个
if(k<N)
printf("找到\n");
else
printf("未找到\n");
}
return 0;
}
扩展成“完全性问题”:如果输入的数存在,则输出存在多少次;不存在则输出0次。
#include <stdio.h>
#include "windows.h"
#define N 100
int main()
{
int i,n,a[N],k,count=0;//增添count变量用来统计次数
srand(GetCurrentTime());
for(i=0;i<N;i++)
a[i]=rand()%1000; //产生100个数据
while(1)
{
scanf("%d",&n); //输入要查找的目标值
if(n==-1) //-1结束进程
break;
k=0;
while(k<N)
{
if(n==a[k])
count++;
k++;
}
if(count==0)
printf("%d不存在\n",n);
else
printf("%d存在,出现次数为%d\n",n,count);
}
return 0;
}
“极值型”查找:
产生10个100以内的随机非负整数,存放到某整型数组中。找出数组中的最大值,并指出最大值在数组中的位置。(也有完全性问题的思想)
#include <stdio.h>
#include "windows.h"
#define N 10
int main()
{
int a[N],i,max;
//产生10个100以内的随机非负整数,存放到某整型数组中
srand(GetCurrentTime());
for(i=0;i<N;i++)
{
a[i]=rand()%100;
}
for(i=0;i<N;i++)
printf("%d ",a[i]);
max=0;
for(i=1;i<N;i++)
{
if(a[max]<a[i])
max=i;
}
printf("最大值在数组中的位置第%d个,值为%d",max+1,a[max]);
return 0;
}
- 排序
常见的排序方法:选择排序,冒泡排序,快速排序,归并排序。
题目:
76,63,13,4,34,90,97,77,78,49 按升序排列
选择排序:
原理:通过遍历数组,选择出数组的最小或最大值,与指定位置交换数据,遍历完整个数组的所有位置就完成排序。
#include <stdio.h>
int main()
{
int i,j,t,n,min,k,a[10]={76,63,13,4,34,90,97,77,78,49};
//方法一:
for(i=0;i<10;i++)
{
min=i;
for(j=i+1;j<10;j++)
{
if(a[j]<a[min])
min=j;
}
t=a[min];
a[min]=a[i];
a[i]=t;
}
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
//方法二:
for(i=1;i<10;i++)
{
for(k=0,j=1;j<=10-i;j++)
if(a[k]<a[j])
k=j;
t=a[k];
a[k]=a[10-i];
a[10-i]=t;
}
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
return 0;
}
冒泡排序:
原理:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。
#include <stdio.h>
int main()
{
int a[10]={76,63,13,4,34,90,97,77,78,49},i,j,t;
for(i=0;i<9;i++)//外层循环次数:元素个数-1(因为最后一个数不用排)
{
//内层循环比较数据
for(j=0;j<10-1-i;j++)//每次排完序后对最后一个都不用在比较 :元素个数-1表示下标,在 -i 表示已经排序好的不用在参与运算
{
if(a[j]>a[j+1]) //按升序排列
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<10;i++)
printf("%d ",a[i]);
return 0;
}
快速排序:
#include <iostream>
using namespace std;
const int N = 100010;//定义了一个全局常量
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;//直接结束
int i = l - 1, j = r + 1, x = q[l+r>>1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
归并排序:
#include <iostream>
using namespace std;
int num[1000000];
int tmp[1000000];
void merge_sort(int* num, int l, int r) {
if (l >= r)
return;
int mid = l + r >> 1;
merge_sort(num, l, mid), merge_sort(num, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (num[i] <= num[j])
tmp[k++] = num[i++];
else
tmp[k++] = num[j++];
while (i <= mid)
tmp[k++] = num[i++];
while (j <= r)
tmp[k++] = num[j++];
for (i = l, j = 0; i <= r; i++, j++)
num[i] = tmp[j];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
merge_sort(num, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", num[i]);
return 0;
}
判断排序的方法还有很多,到底哪个好取决于时间复杂度和空间复杂度······
6.3二维数组
6.3.1 二维数组的基本概念
- 定义二维数组,格式如下:
- “类型”和“数组名”的规定与一维数组相同。
- “行数”和“列数”都必须是常量或由常量构成的计算式,计算结果必须是正整数。
- 二维数组的内存分配:
计算机按照“行优先”的原则分配内存,把同一行的各个元素在内存中连续存储。 - 二维数组的初值:
初始化的格式如下:
写法一:
int a[3][4]={1,1,1,1,1,1,1,1,1,1,1,1};
写法二:可以省略“行数”
int a[][4]={1,1,1,1,1,1,1,1,1,1,1,1};
写法三:
int a[3][4]={{1,1,1,1},
{1,1,1,1},
{1,1,1,1}};
注意:和一维数组的6.1.3 数组元素的初值的说明的第三点同理。
6.3.2 二维数组的应用
6.3.3 多维数组
6.4 字符串数组与字符串
存储一个汉字需要一个两个字符型存储单元(2字节)。
6.4.1 字符串的相关操作
- 字符串的输入:
第一种:
scanf("%s",内存地址);
计算机会从键盘上逐个读取字符,依次存入由“内存地址”开始的存储单元,直到遇到空格或者回车符为止。空格符和回车符不作为有效输入,但会在最后一个有效输入字符后面添加一个结束符‘\0’。
说明:
- “内存地址”可以表示为“&数组名[下标]”意思是从某一个元素开始存放字符出直到遇到空格或者换行符,并在输入的有效字符后面一个元素中存放‘\0’
- 取数组元素在内存中的地址还有一种更简单的方法,C语言规定数组名本身就代表了该数组首元素在内存中的地址。因此“&str[0]”等效于“str”,“&str[2]”等效于“str+2”。
第二种:
因为scanf不能读取含有空格的字符串,所以有另一个库函数“gets”
gets(内存地址);
在读入字符串时,把空格当作有效输入,回车键不作为有效输入,存储了最后一个有效字符之后会在后面添加一个结束符‘\0’。
2. 字符串的输出:
第一种:
printf("%s",内存地址)
第二种:
gets(内存地址);
等效于 printf(“%s\n”,内存地址);
注意:
有的时候给字符串初始化的时候,计算机并不会隐式的添加结束符,就会导致输出函数在输出目标字符串之后在内存中继续查找有效字符并显示,直到找到串结束符。
3. 处理字符串的库函数
常用的字符串操作有“strlen(求串长)”,“strcmp(串比较)”,“strcpy(串复制)”,“strcat(串拼接)”等。
用上面的操作需要在main前面写预处理命令:#include “string.h”,这些函数等我有空在详情展开吧!