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

  • 数组的内存分配:

    • 前边提到过,变量在内存中是从大到小寻址的(内存中以字节为单位),比如00000000
      00000000 00000000
      00001010在内存中,00001010的地方是纤维的;而数组则有点不一致,数组的要素自然的从上往下排列
      存储,整个数组的地点为首成分的地方。
      (然而结合成分的字节依然按从大到小)

      C语言 1

    • C语言 2

      C语言,注意:字符在内存中是以对应ASCII值的二进制方式储存的,而非上表的款式。
      在这些例子中,数组x的地点为它的首成分的地址0x08,数组ca的地点为0x03。

    • 注意数组越界难题,越界会造访到其余故事情节(比如有多少个数组在内存中挨着,第3个数组越界只怕会造访到第贰个数组的成分),甚至会让程序崩溃。

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

    • 在6二人编译器下,指针类型暗许为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;
      }
      
  • “填坑法”的思想:

    比如给出那样一题。须要从键盘输入六个0~9的数字,排序后输出。

    做法有多如牛毛,”填坑法”的情趣就是第叁定义1个十二个数的数组(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
            }
        }
    
  • 采纳排序

    • 重大考虑就是,基本上专断认同数组中首先个因素为最大(最小)值,之后将以此成分和前面的各类成分都开展相比,以由大到小排序为例,当第3个值遭逢比其大的,就进展置换。那样首轮过后,第②人就是最大的。接着举办第1轮,由第一个数开首每种相比,遇到比第①个数大的拓展置换,这样第3轮过后第四个数就是第一大的了,以此类推,不断拓展分选,最后已毕排序。

      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 –
      3遍,以此类推;上边写的是由大到小排序。

  • 冒泡排序

    • 重中之重思想是多个相邻的因素进行相比较,以增添排序为例,那么由第一个要素早先和第3个相比,如若第1个比第一个大,那么就展开置换;然后进行第1个和第多少个要素的可比,以此类推,第一批次过后,那么数组的终极二个因素就是最大的,以此类推。

      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。

  • 进制转换查表法