【C语言】7.数组内存分析,冒泡,选择,二分叉查找

  • 屡次组的内存分配:

    • 面前提到了,变量在内存中是从十分至有些寻址的(内存中盖字节为单位),比如00000000
      00000000 00000000
      00001010当内存中,00001010之地方是极致小之;而数组则有些不同,数组的元素自然之于达向下排列
      存储,整个数组的地址也首元素的地方。
      (但是做元素的字节还是以自十分至有些)

      图片 1

    • 图片 2

      留意:字符在内存中是为对应ASCII值的二进制形式储存的,而未上表的款型。
      在是例子中,数组x的地点也她的首元素的地址0x08,数组ca的地方为0x03。

    • 在意数组越界问题,越界会访问到另外情节(比如来半点单数组在内存中挨在,第一独数组越界可能会见看到第二个数组的因素),甚至会于程序崩溃。

  • 当数组名作为函数参数时,
    因为电动转换为借助针类型,所以在函数中无法动态计算除数组的因素个数

    • 于64各类编译器下,指针类型默认为8个字节

    • 有时候我们也许想要于一个函数里面动态计算数组的个数,所以可能会见这么做:

      void printMyArray(int myArray[]) {
          int length = sizeof(myArray) / sizeof(myArray[0]);
          for(int i = 0; i < length; i++) {
              printf("%i", myArray[i]);
          }
      }
      
      int main() {
          int myArray[5] = {1,2,3,4,5};
          printMyArray(myArray);
          return 0;
      }
      

      可以视于printMyArray函数中我们动态计算传进来的数组的个数,但是结果是错误的,因为它们不得不输出前少单数。

      即时是坐,在管数组当成函数的参数的时候,数组会被当成指针,所以是8个字节,所以计算产生之length是2,所以不得不输出前少只数字。

      化解:我们得为有一个新的参数来博length,在main()里面计算好length然后传播printMyArray。

      void printMyArray(int myArray[], int length) {
          for(int i = 0; i < length; i++) {
              printf("%i ", myArray[i]);
          }
      }
      
      int main(int argc, const char * argv[]) {
          int myArray[5] = {1,2,3,4,5};
          int length = sizeof(myArray) / sizeof(myArray[0]);
          printMyArray(myArray, length);
          return 0;
      }
      
  • “填坑法”的思想:

    随为有这样同样写。要求自键盘输入6个0~9的数字,排序后输出。

    做法时有发生为数不少,”填坑法”的意思就是是率先定义一个10个数的数组(0~9),初始化都为0。

    继而接受用户的输入(可以据此for循环),关键的同等步是,将用户输入的值作为数组的下标,将之下标所对应之值改也1(填坑),再接着for循环输出数组中值是1之目。

    // 空间换时间, 适合数据比较少
    //    1.定义数组,保存用户输入的整数
    //    一定要给数组初始化, 否则有可能是一些随机值
        int numbers[10] = {0};
    //    2.接收用户输入的整数
    //    2.1定义变量接收用户输入的整数
        int index = -1;
        for (int i = 0; i  < 6; i++) {
            printf("请输入第%d个整数\n", i + 1);
            scanf("%d", &index);
    //        将用户输入的值作为索引取修改数组中对应的元素的值为1
    //        指针的时候回来演示刚才的问题
            numbers[index] =  1 ;
        }
    
        int length = sizeof(numbers) / sizeof(numbers[0]);
        for (int i = 0; i < length; i++) {
            if (1 == numbers[i]) {
                // 输出索引
                printf("%d", i);
            }
        }
    

    这做法的中心思想是数组中的初始值都也0,而往往组的目录和用户输入的数字是逐一对应的,所以特待将用户输入的数字相对应之目的要素改成为1,然后再度for循环输出的口舌相当给有序输出,最后抱结果。

    只是这种做法是发生问题之,比如用户输入了更的数字,但是地方的做法只能够用同样之数字输出一差。我们的做法是将平索引的因素的数字增长,之后再搭一层循环来展开输出。

    //    1.定义数组,保存用户输入的整数
        int numbers[10] = {0};
    //    2.接收用户输入的整数
    //    2.1定义变量接收用户输入的整数
        int index = -1;
        for (int i = 0; i  < 6; i++) {
            printf("请输入第%d个整数\n", i + 1);
            scanf("%d", &index);
    //        将用户输入的值作为索引取修改数组中对应的元素的值为1
    //        假设 用户输入的是 1,1,1,2,2,2
            numbers[index] =  numbers[index] + 1 ;
        }
    
        int length = sizeof(numbers) / sizeof(numbers[0]);
        for (int i = 0; i < length; i++) {
    //        j = 1 因为如果数组元素中存储的值是0不用输出
    //        将i对应存储空间中的元素取出,判断需要输出几次
            for (int j = 1; j <= numbers[i]; j++) {
                printf("%d", i);// 1 1 1 2 2 2
            }
        }
    
  • 选排序

    • 关键考虑就,基本上默认数组中首先单因素呢极端要命(最小)值,之后将此元素和后面的每个元素还进展较,以出于特别到多少排序为条例,当第一个价值遇到比那非常之,就进展置换。这样第一轮过后,第一员就是是极其可怜的。接着进行次轮子,由第二独数开逐个比较,遇到比第二单数好之展开置换,这样第二轮后第二个数便是第二深的了,以此类推,不断拓展分选,最后做到排序。

      void selectSort(int numbers[], int length) {
          for (int i = 0; i < length; i++) {
              for (int j = i + 1; j < length; j++) {
                  if (numbers[i] < numbers[j]) {
                      int temp = numbers[i];
                      numbers[i] = numbers[j];
                      numbers[j] = temp;
                  }
              }
          }
      }
      
      int main(int argc, const char * argv[]) {
          int myArray[] = {42, 7, 1, -3, 88};
          int length = sizeof(myArray) / sizeof(myArray[0]);
          selectSort(myArray, length);
          for (int i = 0; i < length; i++) {
              printf("%i ", myArray[i]);
          }
          return 0;
      }
      

      以写的时段可这么想:当第一个数来比较的时节,i =
      0,那么j应该等于i +
      1,因为第一个数要和第二单数开于,并且于length – 1不行;当i =
      1时时,j = 2,并且于length –
      2糟糕,以此类推;上面写的是出于好到多少排序。

  • 冒泡排序

    • 要想是少单相邻之要素进行比较,以追加排序也条例,那么由第一个因素开始跟次单比,如果第一只比较第二只好,那么即使开展置换;然后开展次单及老三单元素的比,以此类推,第一轮后,那么累组的末段一个因素就是是太酷之,以此类推。

      void bubbleSort(int numbers[], int length) {
          for (int i = 0; i < length - 1; i++) {
              for (int j = 0; j < length - i - 1; j++) {
                  if (numbers[j] > numbers[j + 1]) {
                      int temp = numbers[j];
                      numbers[j] = numbers[j + 1];
                      numbers[j + 1] = temp;
                  }
              }
          }
      }
      
      int main(int argc, const char * argv[]) {
          int myArray[] = {42, 7, 1, -3, 88};
          int length = sizeof(myArray) / sizeof(myArray[0]);
          bubbleSort(myArray, length);
          for (int i = 0; i < length; i++) {
              printf("%i ", myArray[i]);
          }
          return 0;
      }
      

      瞩目这里和甄选排序不同的凡,比较的不要numbers[i]和numbers[j],而是比较的numbers[j]和numbers[j+1],而外层循环的i代表比较的轮数,内层循环才是确实的各级一样轱辘展开的比。这里是多排序。

  • 赔本半查找

    • 赔本半寻找顾名思义,我们找到数组的不过要命值max,最小值min求来中值mid,然后据此mid作为数组下标得到相应的元素,用者元素以及目标价key进行比:

      1. 如果numbers[mid] >
        key,那么证明key在min和mid之间,那么尽管装max为mid –
        1,min不更换,然后再计算mid,重复上述手续,最后找有key。

      2. 如果numbers[mid] <
        key,那么证明key在mid和max之间,那么即使安装min为mid +
        1,max不转换,然后还计算mid,重复上述手续,最后找有key。

      3. 注意这里的了断条件,有或数组中发出这key,也产生或没有,那么当min >
        max时,说明数组中连没有这个key,要小心这种情形。

    • 亏本半追寻要求数组必须是有序的。(有序表)

      int binSearch(int myArray[], int length, int key) {
          int index = -1;
      
          int max = length - 1;
          int min = 0;
          int mid = (max + min) / 2;
      
          while (min <= max) {
              if (myArray[mid] > key) {
                  max = mid - 1;
              } else if (myArray[mid] < key){
                  min = mid + 1;
              } else if (myArray[mid] == key) {
                  index = mid;
                  break;
              }
              mid = (max + min) / 2;
          }
      
          return index;
      }
      
      int main(int argc, const char * argv[]) {
          int myArray[] = {-3, 1, 7, 42, 88};
          int length = sizeof(myArray) / sizeof(myArray[0]);
          int index = binSearch(myArray, length, 88);
          printf("index: %i ", index);
          return 0;
      }
      

      率先自己借要index =
      -1,表示尚未对应的值。接着获取max,min,mid的价值,注意while循环的准,在此处我为此底是当min
      <= max的下循环,当min >

      max时候跳出循环,说明并未找到key的价。在循环体里面,像刚刚分析的那样判断,当myArray[mid]

      key的上证实我们找到了是价值,那么将index设置成找到价值的下标,然后跳出循环。如果无找到价值则index
      = -1。

  • 进制转换查表法