【C语言篇】☞ 10. 数组、常见算法、模拟栈操作

数组

1. 概念:

  一组具有相同数据类型的数码的稳步聚集。

数组名是二个地址(是常量),不可变更、不能够赋值、不可能做左值。

int a[3]; // 定义了二个称呼叫做a的数组, 数组中得以存放三个int类型的多少

2. 初始化

  1)int
a[5]={1,2,3,4,5};     //常用

  2)int
a[5]={1,2,3};         //部分起头化,剩余的要素开首化为0,即{1,2,3,0,0}

  3)int
a[5]={[0]=1,[1]=2,[3]=4,5}; //内定开首化,即{1,2,0,4,5}

  4)int
a[5]={0};             //常用,初阶化清零 {0,0,0,0,0}

  5)int
a[5]={};              //不推荐(可读性不佳) {0,0,0,0,0}

  6)int
a[]={1,2,3,4,5};      //不推荐
省略数组的尺寸,可读性不佳

3. 数CEO度

C语言,  数组的长短 = size(数组) / size(成分);

    // 动态总计数组的要素个数

    int a[5];

    int length = sizeof(a) /
sizeof(a[0]);

  数组名a是空间的首地址: a == &a[0] ==
&a

  C语言 1

  C语言 2

  • 题材一:为啥在函数情势参数的扬言中*a与a[]是一模一样的?

  上述二种格局都证实大家盼望的实际参数是指针。在那三种处境下,对a可进行的演算是一样的。而且,可在函数体内给a本人赋予新的值。C语言须求数组名只可以作为“常量指针”,但对于数组型方式参数的名字没有这一限量。

  • 问题二:请问i[a]与a[i]是千篇一律的呢?

  是的,它们是相同的。对于编写翻译器而言,i[a]等同于*(i+a),而*(i+a)也就是*(a+i),大家知晓,*(a+i)等效于a[i]。虽然,i[a]与a[i]是一律的,但一般大家在编程中只使用a[i],很少使用到i[a]。   

  • 题材三:数组下标越界的结果是哪些?

  C语言中数组下标越界,编写翻译器是不会检讨出荒谬的,可是事实上后果只怕会很严重,比如程序崩溃、程序的别的数据被更改等,所以在平凡的编制程序中,程序员应当养成特出的编制程序习惯,幸免那样的失实发生。

/**

 *  数组的拷贝

 */

#include <stdio.h>

int main() {

    int a[5] = {1, 2, 3, 4, 5};

    int b[5];

    for (int i = 0; i < 5; i++) {

        b[i] = a[i];

        printf("%d ", b[i]);

    }

    printf("\n");

    return 0;

}

二维数组

1. 概念

  二维数组其实是数组的数组,能够将二维数组领悟为一张几行几列的二维表。

二维数组:
数组中的每二个要素又是1个数组, 那么那几个数组就称为二维数组

要素类型
数组名称[一维数组的个数][种种一维数组的要素个数];

要素类型
数组名称[行数][列数];

 

//鲜明的报告二维数组: 有1个一维数组,各类一维数组有二个因素

// {{1, 2, 3}, {4, 5, 6}};

int a[2][3] = {1, 2, 3, 4, 5,
6};

数组的称谓正是数组的地方(首地址): &a == a == &a[0]

2. 初始化

int
a[3][2]={{1,2},{3,4},{5,6}}; //对应成分内容

int
b[3][2]={1,2,3,4,5,6}; //全体赋值

int
c[3][2]={1,2,3,4}; //依次赋值,自动补零

 

注意点: 各类一维数组的因素个数不可能省略!

char
name[][2] = {‘r’, ‘b’, ‘h’, ‘j’};//OK

// 搞不清楚应该分配多大的存款和储蓄空间, 以及搞不清楚应该把怎么样数据赋值给第③个数组, 以及哪些数据赋值给第三个数组

char
name1[2][] = {‘r’, ‘b’, ‘h’, ‘j’};//ERROR

char
name2[2][2] = {‘r’, ‘b’, ‘h’, ‘j’};//OK

 

   return;停止近来函数!

exit(0);退出整个程序。(包罗<stdlib.h>头文件)

C语言 3

  注:数组作为函数的参数字传送递(是地方传递), 在函数内部修改形参的值会影响到函数外部的实参值。

科学普及的部分算法

  选用排序、冒泡排序、折半询问(二分查找)、查表法(转进制)

两种排序算法能够总计为如下:

  • 都将数组分为已排序部分和未排序部分。
  • 挑选排序将已排序部分定义在左端,然后选拔未排序部分的微乎其微成分和未排序部分的第三个成分调换。
  • 冒泡排序将已排序部分概念在右端,在遍历未排序部分的经过进行调换,将最大要素调换来最右端。
  • 插入排序将已排序部分定义在左端,将未排序部分元的第二个成分插入到已排序部分合适的职位。

1. 接纳排序

  第三趟:在n个数中找到最小(大)数与首个数交流地点

  第三趟:在余下n-一个数中找到最小(大)数与第一个数沟通地点

      重复这么的操作…依次与第三个、第⑤个…数调换地方

  第n-1趟,最后可完成数据的升序(降序)排列。

  接纳排序的风味:最值出现在早先端

   C语言 4

2. 冒泡排序

  第二趟:依次比较相邻的八个数,不断绝外交关系流(小数放前,大数放后)各种推进,最值最终现身在第n个因素地点(两两比较n-3次)

  第①趟:依次相比较相邻的五个数,不断沟通(小数放前,大数放后)每种推进,最值最终出现在第n-二个因素地方(两两比较n-二回)

      ……      ……

  第n-1趟:依次比较相邻的四个数,不断绝外交关系换(小数放前,大数放后)每个推进,最值最终出现在第②个因素地点(两两相比较三遍)

  冒泡排序的性状:相邻成分两两对比,相比完一趟,最值出现在最终

  C语言 5

3. 折半找寻

  优化查找时间(不用遍历整体数额)

折半搜寻的原理:

    1> 数组必须是照猫画虎的

    2> 必须已知min和max(知道限制)

    3> 动态总计mid的值,取出mid对应的值实行相比

    4> 倘诺mid对应的值大于要物色的值,那么max要变小为mid-1

    5> 假诺mid对应的值小于要寻找的值,那么min要变大为mid+1

/**

 *  已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置

 */

#include <stdio.h>

#include <time.h>

//法1:遍历数组逐个查找

int findKey(int *arr, int length, int key) {

    for (int i = 0; i < length; i++) {

        if (arr[i] == key) {

            return i;

        }

    }

    return -1;

}

//法2:折半查找

int findKey1(int *arr, int length,int key) {

    int min = 0, max = length – 1, mid;

    while (min <= max) {

        mid = (min + max) / 2; //计算中间值

        if (key > arr[mid]) {

            min = mid + 1;

        } else if (key < arr[mid]) {

            max = mid – 1;

        } else {

            return mid;

        }

    }

    return -1;

}

int main() {

    int arr[10000] = {0, [9995] = 1, 3, 6, 10, 12};

    int key = 3;

    int length = sizeof(arr) / sizeof(arr[0]);

    clock_t startTime = clock();

//    int index = findKey(arr, length, key);//共消耗了27毫秒!

    int index = findKey1(arr, length, key); //共消耗了1毫秒!

    clock_t endTime = clock();

    printf("共消耗了%lu毫秒!\n", endTime – startTime);

    printf("key对应的下标位置: %d\n", index); // 9996

    return 0;

}

  

/**

 *  已知一个有序的数组, 要求给定一个数字, 将该数字插入到数组中, 使数组还是有序的

 *  分析:其实就是找到需要插入数字的位置(min的位置)

 */

#include <stdio.h>

 

int insertValue(int *arr, int length,int key) {

    int min = 0, max = length – 1, mid;

    while (min <= max) {

        mid = (min + max) / 2; //计算中间值

        if (key > arr[mid]) {

            min = mid + 1;

        }

        if (key < arr[mid]) {

            max = mid – 1;

        }

    }

    return min;

}

int main() {

    int a[5] = {1, 3, 5, 7, 9};

    int key = 4;

    int length = sizeof(a) / sizeof(a[0]);

    int insertIndex = insertValue(a, length, key);

    printf("需要插入的位置是: %i\n", insertIndex);

    return 0;

}

4. 进制查表法

  能够打字与印刷输出任意进制

  C语言 6

  C语言 7

  C语言 8

打包优化 进制查表法:

/**

 * 查表法(封装优化)

 */

#include <stdio.h>

/**

 *  转换所有的进制

 *  value:  就是需要转换的数值

 *  base:   就是需要&上的数

 *  offset: 就是需要右移的位数

 */

void total(int value, int base, int offset)

{

    // 1.定义一个数组, 用于保存十六进制中所有的取值

    char charValue[] = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’};

    // 2.定义一个数组, 用于保存查询后的结果

    char result[32] = {‘0’};

    // 3.定义一个变量, 用于记录当前需要存储到查询结果数组的索引

    int index = sizeof(result) / sizeof(result[0]);

    // 4.循环取值

    while (value != 0) {

        // 1) 取出1位的值

        int res = value & base;// base: 1 7 15

        // 2) 利用取出来得值到表中查询对应的结果

        char ch = charValue[res];

        // 3) 存储查询的结果

        result[–index] = ch;

        // 4) 移除二进制被取过的1位

        value = value >> offset;// offset: 1 3 4

    }

    // 5.打印结果

    for (int i = index; i < 32; i++) {

        printf("%c", result[i]);

    }

    printf("\n"); 

}

/** 转二进制 */

void printBinary(int num) {

    total(num, 1, 1);

}

/** 转八进制 */

void printOct(int num) {

    total(num, 7, 3);

}

/** 转十六进制 */

void printHex(int num) {

    total(num, 15, 4);

}

int main() {

    printBinary(10); //1010

    printOct(23);    //27

    printHex(1004);  //3ec

    return 0;

}

 

  C语言 9

   C语言 10

模拟栈的操作

  C语言 11

  C语言 12