您当前的位置：首页 > 计算机 > 编程开发 > 数据结构与算法

数组和常用算法

时间：12-14来源：作者：点击数：4

理解 C 语言中的数组

数组是一个变量，由数组类型相同的一组元素组成

数组的结构和基本要素

标识符：数组的名称，用于区分不同的数组
数组元素：向数组中存放的数据
元素下标：对数组元素进行编号
元素类型：数组元素的数据类型

数组只有一个名称，及即标识符（用来表示数组的变量名）

元素下标标明了元素在数组中的位置，从0开始

数组重的每个元素都可以通过下标来访问

数组长度固定不变，避免数组越界

一维数组

语法

datatype arrayName[size];

初始化一维数组

//正确，后面的元素个数与声明的一致
int years[6] = {2012,2013,2014,2015,2016,2017};

//正确，后面的5个元素未初始化，默认值为0
int months[12] = {1,3,5,7,8,10,12};

//正确：元素个数为2
int days[] = {1,15};

//错误：未知元素个数
int array[] = {};

示例

#include <stdio.h>

/**
#数组的定义：类型 数组名[元素个数]
#eg: int a[5];//一个int 占用4个字符内存
#eg: char b[24];//一个char 占用1个字符内存
#eg: double c[3];//一个double 占用8个字符内存
#上面几个类型，都占用多少个字符的内存？(24)
#数组不能动态定义
*/
int main(){
  int s[10];
  int i,sum = 0;
  for(i=0;i<10;i++){
    printf("请输入第%d位同学的成绩：",i+1);
    scanf("%d",&s[i]);
    sum += s[i];
  }
  printf("成绩录入完毕，该次考试的平均分是:%.2f\n",(double)sum/10);
  return 0;
}

/*
#访问数组中的元素:数组名[下标]
#注意：数组的越界
*/

/*
# 数组的初始化
# 将数组中所有元素初始化为0-->int a[10] = {0};//事实上这里只是将第一个元素赋值为0
# 如果是赋予不同的值，那么用逗号分隔开即可-->int a[10] = {1,2,3,4,5,6,7,8,9,0}
# 你还可以只给一部分元素赋值，未被赋值的元素自动初始化为0-->int a[10] = {1,2,3,4,5,6}
# 有时候还可以偷懒，可以只给出各个元素的值，而不指定数组的长度(因为编译器会根据值的个数自动判断数组的长度)
# c99增加了一种新特性：指定初始化的元素。这样就可以只对数组中的某些指定元素进行初始化赋值，而未被赋值的原书自动初始化为0-->int a[10] = {[3]=1,[5]=3}
*/
int main(){
  int a[10] = {0};
  int b[10] = {1,2,3,4,5};
  int i;
  int j;

  for(i=0;i<10;i++){
    printf("第%d个元素的值为:%d\n",(i+1),a[i]);
  }

  for(j=0;j<10;j++){
    printf("第%d个元素的值为:%d\n",(j+1),b[j]);
  }
}

字符数组和字符串常量

# include <stdio.h>
# include <string.h>
//字符数组

/*
# 字符串常量："FishC","小甲鱼","鱼C工作室"（一旦确认就不能改变）
# 字符数组：char a[] = {'',''}
*/
int main(){
  //初始化字符数组的每个元素
  char str1[] = {'F','i','s','h','C','\0'};

  //使用字符串常量初始化
  char str2[] = "FishC";

  //字符串处理函数(避免重新造轮子)
  //1、获取字符串的长度：strlen
  printf("sizeof str2 = %d\n",sizeof(str2));//包含'\0'
  printf("strlen str2 = %u\n",strlen(str2));
  //2、拷贝字符串：strcpy/strncpy

  //3、连接字符串：strcat/strncat

  //4、比较字符串：strcmp/strncmp

  return 0;
}

数组排序

1.冒泡排序

将相邻的两个数两两比较，每次外循环都将最大（最小）的数移到最后，如果后一个数小于（大于）前一个数，两个数交换。

#include <stdio.h>
int main(){
  int arr[8] = {9,5,6,12,1,3,18,11};
  int array_length = sizeof(arr)/sizeof(arr[0]);
  int i = 0,j = 0,tmp;
  for(int i = 0;i<(array_length-1);i++){
    for(int j = 0;j<(array_length-1-i);j++){
      if(arr[j]<arr[j+1]){
        tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }

  //打印排序过后的数组
  for(int k = 0;k<array_length;k++){
    printf("%d,",arr[k]);
  }
}

性能测试

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

unsigned long long a[50000000];
double maopao(unsigned long long a[],int n){
  int i,j,temp;
  clock_t beg,end;//起始时间和结束时间
  double time;
  beg = clock();
  for(i=0;i<n-1;i++){
    for(j=0;j<n-1-i;j++){
      if(a[j]<a[j-1]){
        temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
      }
    }
  }
  end = clock();
  time = (double)(end-beg);//CLOCKS_PER_SEC
  return time;//运行时间
}

int main(){
  int n,i;
  printf("请输入一个数：");
  scanf("%d",&n);
  srand(time(NULL));
  for(i=0;i<n;i++){//随机生成带牌数组
    a[i] = rand();
  }
  printf("冒泡排序运行时间%f\n",maopao(a,n));

  for(i=0;i<n;i++){
    a[i] = i;
  }
  printf("最好情况下，冒泡排序法表现如下：%f秒\n",maopao(a,n));

  for(i=0;i<n;i++){
    a[n-i-1] = i;
  }
  printf("最坏情况下，冒泡排序法表现如下：%f秒\n",maopao(a,n));
  return 0;
}

请输入一个数：100000\ 冒泡排序运行时间31747605.000000\ 最好情况下，冒泡排序法表现如下：23207438.000000秒\ 最坏情况下，冒泡排序法表现如下：34457264.000000秒

冒泡排序法是最慢的排序算法，实际运用中效率最低。

2.选择排序

每进行一次外循环都找到最大（最小）的数移到后面，每次内循环将最大的数与数组重的某个数比较，如果最大值小于（大于）那个数，将那个数的下标记录到max中。

#include <stdio.h>
int main(){
  int arr[8] = {9,5,6,12,1,3,18,11};
  int array_length = sizeof(arr)/sizeof(arr[0]);
  int temp,max;
  for(int i = 0;i<(array_length-1);i++){
    max = 0;//每次外循环都认为第一个元素为最大的
    for(int j = 1;j<(array_length-i);j++){
      if(arr[max]<arr[j]){
        max = j;
      }
    }
    temp = arr[max];
    arr[max] = arr[array_length-1-i];
    arr[array_length-1-i] = temp;
  }

  //打印排序过后的数组
  for(int k = 0;k<array_length;k++){
    printf("%d,",arr[k]);
  }
  printf("\n");
}

选择排序和冒泡排序差不多，使用较少

3.插入排序法

从第二个数开始，与已拍好的序列的周后哟个数比较，如果其值小雨最后一个数，则与前一个数比较，找到小于它的数，将其插入到这个数后面

#include <stdio.h>
int main(){
  int arr[8] = {9,5,6,12,1,3,18,11};
  int array_length = sizeof(arr)/sizeof(arr[0]);
  int temp;
  for(int i = 1;i<array_length;i++){
    temp = arr[i];
    for(int j = i-1 ;j>=0;j--){
      if(temp > arr[j]){
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  //打印排序过后的数组
  for(int k = 0;k<array_length;k++){
    printf("%d,",arr[k]);
  }
  printf("\n");
}

二维数组

语法

datatype name[rowSize][colSize];

#include <stdio.h>

//二维数组
/*
# 二维数组也叫做矩阵
# 二维数组的定义：类型 数组名[常量表达式][常量表达式]
#eg: int a[6][6];
#eg: char b[4][5];
#eg: double c[6][3]

# 二维数组的访问：数组名[下标][下标]
# 注意数组的越界

# 二维数组的初始化：由于二位数组在内存中是线性存放的，因此可以将所有的数据写在一个花括号内
#eg: int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12}

# 为了更直观地表示元素的分布，可以用大括号将每一行的元素括起来
#eg: int a[3][4] = { {1,2,3,4},{5,6,7,8},{9,10,11,12} }

# 二维数组也可以仅对一部分元素赋值

# 二维数组的初始化也可以偷懒，让编译器根据元素的数量计算数组的长度。但只有第1维的元素可以不写，其他维度必须写上
*/

int main(){
  int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
  int b[3][4] = {
    {1,2,3,4},
    {5,6,7,8},
    {9,10,11,12}
  };
  int i,j;
  for(i=0;i<3;i++){
    for(j=0;j<4;j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
  return 0;
}