二进制原码、反码、补码

原码

反码

补码：反码+1

如何从补码到原数：（补码-1）->01对调（表示正负号的不对调）-> 二进制相加

ASCII编码

数字=字符时，其值是该字符对应的ASCII编码

字符串=数字时同理

条件表达式

expr1 ? exp2:expr3;

if expr1 is True then expr2 else expr3

时间复杂度

数组

1、正确的初始化

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

错误示例：

不要使用超过数组长度的序号：

int a[100]; a[100] = 40;

虽然长度是100，但序号是[0,99]

2、数组在函数的传递：名称且不带括号

int myArray[24];
void myFunctionRef(int[], int length)
myFunctionRef( myArray, 24 );

字符串数组

char string1[] = { 'f', 'i', 'r', 's', 't', '\0' }

数组的名字就是第一个元素的地址

char *s = "SPEIT"; *s = 'c';

在C语言中，字符串常量是不可更改的。s 是一个指向字符串常量 "SPEIT" 的指针，当你尝试修改这个字符串常量中的字符时，会导致错误。

修改的话应定义为字符串数组

char s[]= "SPEIT"; s[0] = 'c';

多维数组

二维数组在初始化时一般只确定列的个数

char vowels[][5] = {
{'A', 'E', 'I', 'O', 'U'},
{'a', 'e', 'i', 'o', 'u'}
};

类型强制转换

注意：把值从较高类型转换到较低类型，会引起数据的丢失

（最低类型）bool -> char -> unsigned char -> short -> unsigned short -> int -> unsigned int -> long int ->unsigned long -> float -> double -> long double ；

数值调用和实例调用(Call by Reference)

Call by Reference

void addone(int *n) {
(*n)++;
}

取地址：&

取值：*

a时=是数组名称，a[1]中的[]其实也是一种取值运算

指针

1、初始化：Initialize pointers to 0, NULL, or an address

2、错误示例：

int *c;
int k=5;
*c =5;

3、const

int *const myPtr = &x;
• Type int *const - constant pointer to an int
const int *myPtr = &x;
• Regular pointer to a const int, *myPtr can not be reassigned with a value
const int *const Ptr = &x;
•const pointer to a const int

4、b[n] = *(b + n)

5、对一个二维数组同理：

b[m][n] = *(*(b+m)+n);

6、指针的指针

int (*p)[n];

创建了行数不确定，列数为n的数组；指针p指向该数组的第一个值

int *p[n];

创建了n个内容为指针的数组；

排序算法

交换函数

void swap(int * A, int i , int j){
  int temp;
  temp = A[i];
  A[i] = A[j];
  A[j] = A[i];
}

插入排序 Insertion Sort

  1. 算法原理：从数列的第二个数开始到最后一个数进行循环，每一次都将它们与排在它们之前的所有数进行比较，并和所有比它大的数换位

  2. 算法代码：

void inssort(int *A, int N){
  int i,j,temp;
  for (i=1;i<N;i++){
    j = i-1
    temp = A[i]
    while (j>=0 && A[j]>temp){
      swap(A,j,j+1);
      j--;
    }
  }
}

选择排序 Selection Sort

  1. 算法原理：
    1. 从未排序部分中找到最小（或最大）元素。
    2. 将其与当前未排序部分的第一个元素交换。
    3. 重复上述过程，直到所有元素被排序。
  2. 算法代码：
void selsort(int *A , int N){
  int i,j,index;
  for (i=0;i<N-1;i++){
    index = i;
    for (j=i+1;j<N;j++)
      if (A[j]<A[index]) index = j;
  }
  if (index != i) swap(A,i,index);
}

冒泡排序 Bubble Sort

  1. 算法原理
    1. 从数组的第一个元素开始，逐一比较相邻的两个元素。
    2. 如果前一个元素比后一个元素大，则交换它们的位置。
    3. 一次完整的遍历会将当前未排序部分中最大的元素"冒泡"到数组的末端。
    4. 每次遍历后，末尾的元素已经是排序好的，因此下一次遍历时可以忽略末尾已排序的元素。
    5. 重复上述过程，直到没有更多的交换，数组已经排序完毕。
  2. 算法代码
void bubsort(int *A , int N){
  int i,j;
  for (i>0;i<N-1;i++){
    for (j>0;j<N-i-1;j++){
      if (A[j]>A[j+1])
        swap(A,j+1,j);
    }
  }
}

快速排序 Quick Sort

  1. 算法介绍：使用分治法（Divide and Conquer）策略，将问题分解为更小的子问题并逐步解决。快速排序的基本思想是通过一个“基准值”将数组分为两部分，使得一部分元素都小于基准值，另一部分元素都大于基准值。然后递归地对这两部分继续进行排序，最终实现整体的排序。
  2. 算法原理：
    1. 选择基准元素：从数组中选择一个基准元素，常见的选择方式有选择第一个元素、最后一个元素、随机选择一个元素或选择中间元素等。
    2. 分区操作（Partition）：将数组中的元素重新排列，使得基准元素的位置固定。所有比基准元素小的元素都移到基准元素的左侧，而所有比基准元素大的元素都移到基准元素的右侧。
    3. 递归排序：对基准元素左侧和右侧的两个子数组递归地进行快速排序。每次递归操作将数组分割成更小的子数组，直到子数组只有一个元素或为空，此时数组已经排序完毕。
  3. 算法代码
void quisort(int *A,int start,int end){
  int i;
  if (end>start){
    i = partition(A,start,end);
  	quisort(A,start,i-1);
  	quisort(A,i+1,end);
  }
}

int partition(int *A,int left,int right){
  int i=left,j=right,pivo;
  pivo = A[(left+right)/2];
  while (1){
    while (A[i]<pivo) i++;
    while (A[j]>pivo) i--;
    if (i<j)	
      swap(A,i,j);
    else	
      break;
  }
  return i;
}