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

数组

1. 概念:

  一组有同样数据类型的数的雷打不动聚集。

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

int a[3]; // 定义了一个名号叫做a的往往组, 数组中得存放3个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. 屡组长度

  数组的尺寸 = 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. 概念

  二维数组其实是屡组的反复组,可以将二维数组了解为同张几乎行几排列的二维表。

二维数组:
数组中之各个一个因素而是一个反复组, 那么是数组就称二维数组

素类型
数组名称[一维数组的个数][每个一维数组的元素个数];

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

 

//明确的告知二维数组: 有2独一维数组,每个一维数组发3个元素

// {{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. 挑排序

  第1遍:在n个数中找到最好小(大)数与第一个数交换位置

  第2水:在剩余n-1单数吃找到最好小(大)数与亚独数交换位置

      重复这么的操作…依次与第三只、第四只…数交换位置

  第n-1和,最终只是实现数据的升序(降序)排列。

  选择排序的特色:最值出现于起始端

   C语言 4

2. 冒泡排序

  第1遍:依次比较相邻之片个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第n个要素位置(两星星比n-1破)

  第2遍:依次比较相邻的少数单数,不断交换(小数放前,大数放后)逐个推进,最值最后出现于第n-1个要素位置(两鲜比较n-2蹩脚)

      ……      ……

  第n-1趟:依次比较相邻的简单只数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第2单因素位置(两点滴比较1浅)

  C语言冒泡排序的特色:相邻元素两星星比,比较了一遍,最值出现在最终

  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