算法与数据结构

异或

1.性质

0异或任何数等于任何数
任何数跟自己异或为0
满足交换律和结合律
所以两数交换
可以连用三个异或

2.使用

1.在一个数组中，只有一个出现奇数次的数，其余都是出现偶数次找出这个奇数次的数？

先int ji
数组为[a,b,c,d,e]
只需要
ji^a
ji^b
ji^c
ji^d
ji^e
就能找出这个出现奇数次的数

实例：

int main()
{
	int ji = 0;
	int c[] = { 1,2,2,3,3,4,4 };
	int sz = sizeof(c) / sizeof(c[0]);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		ji = ji ^ c[i];
	}
	printf("%d", ji);
}

2. 假如有两个奇数（a,b都是奇数）

那么答案就是这样算完结果就是ji=a^b
因为a!=b,所以a^b一定不全为0，它在某一位上一定为1
我们假设它在第一位为1
那么a和b在第一位一定不相等
我们设int ji’=0
让ji’去异或上数组中所有第一位为1的数
那么结果就是ji’=a or b
假如ji’=a,最后拿ji ^ ji’ 就能得到b

实例：

int main()
{
	int ji = 0;
	int c[] = { 1,2,2,3,3,4,4,6,6,5 };
	int sz = sizeof(c) / sizeof(c[0]);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		ji = ji ^ c[i];
	}

	int ji2 = 0;
	const int rightone = ji & ((~ji) + 1);//把自己最右侧的1弄出来了
	for (i = 0; i < sz; i++)
	{
		if (c[i] & rightone)
		{
			ji2 ^= c[i];
		}
	}
	int b = ji ^ ji2;

	printf("%d\n", ji);
	printf("%d\n", ji2);
	printf("%d\n", b);
}

插入法排序

作为排序,它比冒泡和选择有时更加的快捷,它的时间复杂度是从O[n]到O[n^2]，而冒泡和选择是严格的O[n^2];
他的原理是先从前两个比较，排序；前三个比较，排序以此类推
展示实例:

void swap(int c[], int j)
{
    c[j] = c[j] ^ c[j + 1];
    c[j+1] = c[j] ^ c[j + 1];
    c[j] = c[j] ^ c[j + 1];
}
void insertsort(int c[], int sz) {
    int i, j;
    for (i = 1; i < sz; i++)
    {
        for (j = i - 1; j >= 0 && c[j] > c[j + 1];j--)
        {
            swap(c, j);
        }
    }
    for (i = 0; i < sz; i++)
        printf("%d", c[i]);
}
int main()
{
	int a = 0;
	int c[] = { 3,2,4,6,4,2,1,3 };
	int sz = sizeof(c) / sizeof(c[0]);
	insertsort(c,sz);
}

归并排序

小知识：(a-b)/2=(a-b)>>1

时间复杂度:O(N*logN)

1.实现归并排序

void merge(int arr[],int l,int mid,int r)
{
   int* help=(int*)malloc((r-l+1)*sizeof(int));
   int i=0;
   int p1=l;
   int p2=mid+1;
   while(p1<=mid&&p2<=r)
   {
     help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
   }
   //有可能有一方先到达边界，进行查缺补漏
   while(p1<=mid)
   {
     help[i++]=arr[p1++];
   }
   while(p2<=r)
   {
     help[i++]=arr[p2++];
   }
   //最后放回arr中
   int j=0;
   for(j=0;j<i;j++)
   {
     arr[l++]=help[j];
   }
   free(help);
}
void mergesort(int arr[],int l,int r)
{
   if(l<r)
   {
   int mid=l+((r-l)>>1);
   //分治数组 很像树形的分治
   mergesort(arr,l,mid);
   mergesort(arr,mid+1,r);
   //合并数组，理解起来就是上面把左右部分分到最小利用merge将每两个小块合并
   merge(arr,l,mid,r);
   }
}
int main()
{
  int arr[]={1,4,6,3,6,8,8,5};
  int sz=sizeof(arr)/sizeof(arr[0]);
  mergesort(arr,0,sz-1);
  int i=0;
  for (i=0;i<sz;i++)
  {
    printf("%d",arr[i]);
  }
  return 0;
}

2.归并排序的利用

1.求小和

意思是求一个数列中每个数左边比他小的数的和。

我们可以反过来利用一个数右边有多少数比它大，小和就是所有数这样算的和

下面举实例代码：

int smallsum(int arr[], int sz)
{
	if (arr == NULL || sz < 2)
	{
		return 0;
	}
	return mergesort(arr, 0, sz - 1);
}

这是判断是否数列是否有两个数，有的话才进入求小和步骤

int mergesort(int arr[],int l,int r)
{
   if(l==r)
   {
     return 0;
   }
   const int mid=l+((r-l)>>1);
   return mergesort(arr,l,mid)+mergesort(arr,mid+1,r)+merge(arr,l,mid,r);
}

int merge(int arr[],int l,int mid,int r)
{
  int* help=(int*)malloc((r-l+1)*sizeof(int));
  int i=0;
  int p1=l;
  int p2=mid+1;
  int res=0;
  while(p1<=mid&&p2<=r)
  {
    res+=c[p1]<c[p2]?((r-p2+1)*c[p1]):0;//计算左侧每一个数的小和
    help[i++]=c[p1]<c[p2]?c[p1]:c[p2];
  }
  while(p1<=mid)
  {
    help[i++]=c(p1++);
  }
  while(p1<=r)
  {
    help[i++]=c(p2++);
  }
  int j=0;
  for(j=0;j<i;j++)
  {
    c[l++]=help[j++];
  }
  return res;
}

以上是求小和的具体步骤

荷兰国旗问题

1.让数组左边为<=num的数,右边为>num的数

1.按照思路自写：

void swap(int arr[], int i,int p1)
{
	arr[i] = arr[i] ^ arr[p1];
	arr[p1] = arr[i] ^ arr[p1];
	arr[i] = arr[i] ^ arr[p1];

}
int main()
{
	int arr[] = { 2,4,2,1,4,6,3,5,6,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int num = 3;
	int p1 = 0;//给定一个小于区域
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		if (arr[i] <= num)//当arr[i]<=num时,i和p1都++，>时仅i++
		{
			if (i != p1)//等于了无法用异或交换
			{
				swap(arr,i,p1);
			}
			p1++;
		}
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d", arr[i]);
	}
	return 0;
}

2.让数组左边为<num的数,中间为=num的数,右边为>num的数

1.按照思路自写：

void swap(int arr[], int i,int p1)
{
	arr[i] = arr[i] ^ arr[p1];
	arr[p1] = arr[i] ^ arr[p1];
	arr[i] = arr[i] ^ arr[p1];

}
int main()
{
	int arr[] = { 2,4,2,1,4,6,3,5,6,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int num = 3;
	int p1 = 0;
	int p2 = sz - 1;
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		if (arr[i] < num)
		{
			if (i != p1)
			{
				swap(arr,i,p1);
			}
			p1++;
		}
		if (arr[i] > num)
		{
			if (i == p2)
			{
				break;
			}
			swap(arr, i, p2);
			i--;
			p2--;
		}
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d", arr[i]);
	}
	return 0;
}

3.由此我们可以得知快排的方法

//这是基于给出值在数组的最后

void swap(int arr[], int i, int p1) {
    int temp = arr[i];
    arr[i] = arr[p1];
    arr[p1] = temp;
}

void pai(int arr[], int p1, int p2) {
    if (p1 >= p2) {
        return;
    }
    int start = p1;
    int end = p2;
    int num = arr[p2];
    while (p1 < p2) 
    {
        while (p1 < p2 && arr[p1] <= num) 
        {
            p1++;
        }
        while (p1 < p2 && arr[p2] >= num) 
        {
            p2--;
        }
        swap(arr, p1, p2);
    }
    swap(arr, p1, end);
    pai(arr, start, p1 - 1);
    pai(arr, p1 + 1, end);
}

int main() {
    int arr[] = { 2, 4, 2, 1, 4, 6, 3, 5, 6, 3 };
    int sz = sizeof(arr) / sizeof(arr[0]);

    pai(arr, 0, sz - 1);

    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

还可以通过产生随机数赋值num的方法降低时间复杂度，实在写不动了;

堆

优先级队列结构，就是堆结构

完全二叉树:

大根堆:每一棵子树的最大值就是头结点的值

小根堆:每一棵子树的最小值就是头结点的值

1.堆排序

给一个数通过跟父的比较交换可以保持大根堆此函数称为heapinsert(往上)

void heapinsert(int arr[],int index)
{
	while (arr[index] > arr[(index - 1) / 2])//跟父比较
	{
		swap(arr, index, (index - 1) / 2);//交换值
		index = (index - 1) / 2;//交换位置，再次跟父比较
	}
}

堆化的过程称为heapify(往下)

void heapify(int arr[], int index, int heapsize)
{
	int left = index * 2 + 1;//左孩子下标
	while (left < heapsize)//左孩子下标比右孩子下标小，因此只要比较左孩子就能判断是否有孩子
	{
		//先判断两个孩子中谁的值大，把小标赋值给largest
		int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
		//父和孩子之间，谁的值大，把小标给largest
		largest = arr[largest] > arr[index] ? largest : index;
		if (largest == index)
		{
			break;
		}
		swap(arr, largest, index);
		index = largest;
		left = index * 2 + 1;
	}
}

通过这两者可以构成所谓的堆排序heapsort

void heapsort(int arr[])
{
  int sz=sizeof(arr)/sizeof(arr[0]);
  if(arr==NULL||sz<2)
  {
    return;
  }
  int i=0;
  for(i=0;i<sz;i++)
  {
    heapinsert(arr,i);//构建大根堆，但时间复杂度有点大0(N*logN)
  }
  int heapsize=sz;
  swap(arr,0,--heapsize);//把最尾部的跟头交换，并把根堆减少
  while(heapsize>0)
  {
    heapify(arr,0,heapsize);//再次构建大根堆
    swap(arr,0,--heapsize);//再次交换，最后排序成功
  }
}

优化后

void heapsort(int arr[])
{
  int sz=sizeof(arr)/sizeof(arr[0]);
  if(arr==NULL||sz<2)
  {
    return;
  }
  int i=0;
  for(i=sz-1;i>=0;i--)
  {
     heapify(arr,i,sz);//此处的时间复杂度仅有O(N)，但后面依然是O(N*logN)
  }
  int heapsize=sz;
  swap(arr,0,--heapsize);//把最尾部的跟头交换，并把根堆减少
  while(heapsize>0)
  {
    heapify(arr,0,heapsize);//再次构建大根堆
    swap(arr,0,--heapsize);//再次交换，最后排序成功
  }
}

2.堆排序扩展题目

1.已知一个几乎有序的数组，数组元素移动的距离不可以超过k，k相对于数组来说较小，选择排序算法来针对这个数据排序

按照上面的思路，这题可以用小根堆排序并限制到k个进行小根堆的建立，先写出数组的小根堆化过程，与大根堆化类似

void minheapify(int arr[], int index, int heapsize)
{
	int left = index * 2 + 1;
	while (left < heapsize)
	{
		int minist = heapsize>left+1&&arr[left] > arr[left + 1] ? (left + 1) : left;
		minist = arr[minist] > arr[index] ? index : minist;
		if (minist == index)
		{
			break;
		}
		swap(arr, index, minist);
		index = minist;
		left = index * 2 + 1;
	}
}

之后进行限制在k个的排序即可得到

比较器

1.比较器概念

struct Student
{
	char name[10];
	int id;
	int age;
};
//想实现用id的升序排列
int Compare(Student o1, Student o2)
{
	//比较器统一规定:
	//返回负数的时候，第一个参数排在前面
	//返回正数的时候，第二个参数排在前面
	//返回0的时候，谁在前面无所谓
	//因此可以这么写
	if (o1.id < o2.id)
	{
		return -1;
	}
	if (o1.id > o2.id)
	{
		return 1;
	}
	//但我们有更精简的写法
	return o1.id - o2.id;
	//如果想要降序排列，只需要最后的减法反过来
	//return o2.id - o2.id;
}

2.比较器的利用

通过这个我们可以复习一下qsort的用法

//  qsort---排序
//1.void*
//1、此类型指针可以接受任意类型的地址
//2、此类型指针不能进行解引用
//3、此类型指针不能进行+-整数的操作
//qsort一般用法为：
//qsort(arr,sz,sizeof(arr[0]),cmp_void)
//其中cmp函数一般格式为
//int cmp (const void*e1,const void*e2)
//{
//在括号里需要是一种返回0，正数，负数的计算
//}
//展示例子
//1.首先是整形排序
int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);//由于void*类型不能解引用，因此使用强制类型转换
}
//2.接着是浮点数排序
int cmp_float(const void* e1, const void* e2)
{
	//此处需要利用float来返回int会警告，可利用比较大小的方式直接返回整数，但也可以不管警告
	return (*(float*)e1 - *(float*)e2);
}
//3.然后是结构体排序
	//定义一个结构体
	struct str
{
	char name[20];
	int age;
};

//(1)通过年龄排序
int cmp_str_age(const void* e1, const void* e2)
{
   return((struct str*)e1)->age - ((struct str*)e2)->age;
}
//(2)通过名字排序
int cmp_str_name(const void* e1, const void* e2)
{
	return strcmp(((struct str*)e1)->name, ((struct str*)e2)->name);
}

int main()
{
	int i = 0;
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	float arr1[10] = { 9.0,8.0,7.0,6.0,5.0,4.0,3.0,2.0,1.0,0 };
	struct str s[3] = { {"张三",20},{"李四",10},{"王五",30}};

	int sz = sizeof(arr) / sizeof(arr[0]);
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	int sz2 = sizeof(s) / sizeof(s[0]);

	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	qsort(arr1, sz1, sizeof(arr1[0]), cmp_float);
	for (i = 0; i < sz1; i++)
	{
		printf("%f ", arr1[i]);
	}
	printf("\n");

	qsort(s, sz2, sizeof(s[0]), cmp_str_name);
	for (i = 0; i < sz2; i++)
	{
		printf("%s ", s[i].name);//！！加点进行访问，不要忘了
	}
	printf("\n");

	qsort(s, sz2, sizeof(s[0]), cmp_str_age);
	for (i = 0; i < sz2; i++)
	{
		printf("%d ", s[i].age);//！！加点进行访问，不要忘了
	}
	printf("\n");

}

计数排序，基数排序

void radixsort(int arr[], int l,int r,int digit)
{
	int radix = 10;
	int i = 0, j = 0;
	int* help = (int*)malloc((r - l + 1) * sizeof(int));
	for (int d = 0; d <= digit; d++)
	{
		//有多少位进几次
		//10个空间
		//count[0] 当前位(d位)是0的数字有多少个
		//count[1] 当前位(d位)是(0和1)的数字有多少个
		//以此类推
		int* count = (int*)malloc((radix) * sizeof(int));
		for (i = l; i < r; i++)
		{
			j = getDigit(arr[i], d);
			count[j]++;
		}
		for (i = 1; i < radix; i++)
		{
			count[i] = count[i] + count[i - 1];
		}
		for (i = r; i >= l; i--)
		{
			j = getDigit(arr[i], d);
			help[count[j] - 1] = arr[i];
			count[j]--;
		}
		for (i = l, j = 0; i < -r; i++, j++)
		{
			arr[i] = help[j];
		}
	}
}

稳定性

原来数组相等的数在左边的排序后依然在左边则认为其有稳定性

例如:归并排序,冒泡排序,桶排序

反转链表

反转主要步骤：

1. 首先需要三个元素，需要注意的是curr不能是头结点，头结点不需要参与反转
2. 其次使得temp为此时curr指向的下一个
3. 让curr指向prev，此时就已经反转了一个了，之后让curr=temp继续下去
4. 最后让头结点指向反转后最开始的值也就是prev

struct stu* reverseLink(struct stu* head) {
	struct stu* prev = NULL;
	struct stu* curr = head->next;
	struct stu* temp = NULL;
	while (curr != NULL)
	{
		temp = curr->next;
		curr->next = prev;
		prev = curr;
		curr = temp;
	}
	head->next = prev;
	return head;
}

具体步骤:

此处使用头插法的方式创建链表

由于头插法输出的数本来就是反的，因此反转后输出正常样子

struct stu
{
	int age;
	struct stu* next;
};
struct stu* createlink()
{
	struct stu* h = (struct stu*)malloc(sizeof(struct stu));
	h->next = NULL;
	int i = 0,n=0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		struct stu* p = (struct stu*)malloc(sizeof(struct stu));
		scanf("%d", &p->age);
		p->next = h->next;
		h->next = p;
	}
	return h;
}
struct stu* reverseLink(struct stu* head) {
	struct stu* prev = NULL;
	struct stu* curr = head->next;
	struct stu* temp = NULL;
	while (curr != NULL)
	{
		temp = curr->next;
		curr->next = prev;
		prev = curr;
		curr = temp;
	}
	head->next = prev;
	return head;
}

void printlink(struct stu*h)
{
	h = h->next;
	while (h != NULL)
	{
		printf("%d ",  h->age);
		h = h->next;
	}
}
int main()
{
	struct stu* h= createlink();
	h = reverseLink(h);
	printlink(h);
	free(h);
	h = NULL;
	return 0;
}

二叉树

1.递归序:

1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1

struct Treenode
{
	int data;
	struct Treenode* left;
	struct Treenode* right;
}Treenode;
void f(struct Treenode* head)//递归序实现
{
	if (head == NULL)
	{
		return;
	}
	f(head->left);
	f(head->right);
}

可分为

1. 先序遍历:先打印头结点，再打印左孩子，再打印右孩子

   ​ 按照递归序(只看第一次指到)打印顺序:1,2,4,5,3,6,7

2. 中序遍历:左 头 右

   ​ 按照递归序(只看第二次指到)打印顺序:4,2,5,1,6,3,7

3. 后序遍历:左 右 头

   ​ 按照递归序(只看第三次指到)打印顺序:4,5,2,6,7,3,1

   先序:
   void preorderrecur(struct Treenode* head)
   {
   	if (head == NULL)
   	{
   		return;
   	}
   	printf("%d ", head->data);
   	preorderrecur(head->left);
   	preorderrecur(head->right);
   }

   中序:
   void inorderrecur(struct Treenode* head)
   {
   	if (head == NULL)
   	{
   		return;
   	}
   	preorderrecur( head->left);
   	printf("%d ", head->data);
   	preorderrecur(head->right);
   }

   后序:
   void posorderrecur(struct Treenode* head)
   {
   	if (head == NULL)
   	{
   		return;
   	}
   	preorderrecur(head->left);
   	preorderrecur(head->right);
   	printf("%d ", head->data);
   }

2.栈

由于先序递归的实现可以用栈来辅助,这里我们先学一下栈的创建压入与弹出

#define MaxSize 50   //定义栈中的元素的最大个数
typedef struct stack
{
	int data[MaxSize];
	int top;  //栈顶指针
}stack;

void Initstack(stack* s)
{
	s->top = -1;      //初始化栈顶指针<判空条件s->top=-1
}

int isempty(stack *s)
{
	return (s->top == -1);
}
int isfull(stack* s)
{
	return s->top == MaxSize - 1;
}
//进栈
void push(stack* s, int value)
{
	if (isfull(s)) return ;//栈满了，报错
	s->data[++s->top] = value;
	return ;
}
//出栈
int pop(stack*s)
{
	if (isempty(s)) //判空
	{
		return -1;
	}
	return s->data[s->top--];
}
//读栈顶元素
int peek(stack*s)
{
	if (isempty(s)) return -1;//判空
	return s->data[s->top];
}
int main()
{
	stack s;
	Initstack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	push(&s, 4);
	push(&s, 5);
	push(&s, 6);
	printf("Top element: %d\n", peek(&s));
	printf("Pop element: %d\n", pop(&s));
	printf("Top element: %d\n", peek(&s));
	printf("Pop element: %d\n", pop(&s));
	return 0;
}

动态开辟

typedef struct sqstack
{
	int* bottom;
	int* top;
	int stacksize;
}sqstack;
struct sqstack* initstack(sqstack*s,int n)
{
	s->bottom = (int*)malloc(sizeof(int) * n);
	if (!s->bottom)
	{
		return ERROR;
	}
	s->top = s->bottom;
	s->stacksize = n;
	return s;
}
void push(sqstack* s, int e)
{
	if ((s->top - s->bottom) == s->stacksize - 1)
	{
		s->bottom = (int*)realloc(s->bottom,sizeof(int) * (s->stacksize + 20));
		if (!s->bottom)
		{
			return ;
		}
		s->top = s->bottom + s->stacksize;
		s->stacksize += 20;
	  }
	*++s->top = e;
	return;
}
int pop(sqstack* s)
{
	if (s->top <= s->bottom)
	{
		return 0;
	}
	return *(s->top--);
}
int main()
{
	int n = 100;
	struct sqstack* s = (struct sqstack*)malloc(sizeof(sqstack));
	s=initstack(s, n);
	push(s, 1);
	push(s, 2);
	printf("%d",pop(s));
}

3.用栈辅助非递归写出遍历

先序遍历程序:

void preorderunrecur(struct treenode* head)//先序遍历
{
	if (head != NULL)
	{
		stack s;
		Initstack(&s);
		push(&s, head);
		while (!isempty(&s))
		{
			head = pop(&s);
			printf("%d", head->data);
			if (head->right != NULL)
			{
				push(&s,head->right);
			}
			if (head->left != NULL)
			{
				push(&s, head->left);
			}
		}
	}
}

整体程序:

#define MaxSize 50   //定义栈中的元素的最大个数
typedef struct stack
{
	struct treenode* data[MaxSize];
	int top;  //栈顶指针
}stack;
struct treenode
{
	int data;
	struct treenode* left;
	struct treenode* right;
}Node;
struct treenode* createnode(int data)
{
	struct treenode* node = (struct treenode*)malloc(sizeof(struct treenode));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}
void Initstack(stack* s)
{
	s->top = -1;      //初始化栈顶指针<判空条件s->top=-1
}

int isempty(stack *s)
{
	return (s->top == -1);
}
int isfull(stack* s)
{
	return s->top == MaxSize - 1;
}
//进栈
void push(stack* s, struct treenode* value)
{
	if (isfull(s)) return ;//栈满了，报错
	s->data[++s->top] = value;
	return ;
}
//出栈
struct treenode* pop(stack*s)
{
	if (isempty(s)) //判空
	{
		return NULL;
	}
	return (struct treenode*)s->data[s->top--];
}
//读栈顶元素
struct treenode* peek(stack*s)
{
	if (isempty(s)) return NULL;//判空
	return s->data[s->top];
}
void preorderunrecur(struct treenode* head)//先序遍历
{
	if (head != NULL)
	{
		stack s;
		Initstack(&s);
		push(&s, head);
		while (!isempty(&s))
		{
			head = pop(&s);
			printf("%d", head->data);
			if (head->right != NULL)
			{
				push(&s,head->right);
			}
			if (head->left != NULL)
			{
				push(&s, head->left);
			}
		}
	}
}
int main()
{
	struct treenode* root = createnode(1);
	root->left = createnode(2);
	root->right = createnode(3);
	root->left->left = createnode(4);
	root->left->right = createnode(5);
	root->right->left = createnode(6);
	root->right->right = createnode(7);
	preorderunrecur(root);
	return 0;
}

中序遍历程序:

跟先序遍历的差别:1.每次从根节点取出来,直到左子树为空时,2.之后进入右子树,再重复操作第一步

4.二叉树的分类

搜索二叉树:每一棵子树左孩子比父小，右孩子比父大

完全二叉树:一个二叉树要么最后一行是满的,要么最后一层从左到右依次变满

满二叉树:字面意思，全满，可以通过节点数=2的深度次方-1来判断

平衡二叉树:对于任何一个子树来说，左树的高度和他右树的高度差不超过1

5.队列

学了栈顺便学一下队列,其实就是先进先出的栈,比栈多了一个栈底的指针,通过比较栈底指针与栈顶指针来初始化栈;具体代码如下

#define MaxSize 50
struct Queue
{
	int items[MaxSize];
	int front;
	int rear;
};
struct Queue* createqueue()
{
	struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
	queue->front = -1;
	queue->rear = -1;
	return queue;
}
int isempty(struct Queue* queue)
{
	return queue->rear == -1 ? 1 : 0;
}
int isfull(struct Queue* queue)
{
	return queue->rear == MaxSize - 1 ? 1 : 0;
}
void enqueue(struct Queue* queue, int value)
{
	if (isfull(queue))
		return;
		queue->items[++queue->rear] = value;
		return;
	
}
int dequeue(struct Queue* queue)
{
	int item = 0;
	if (isempty(queue))
	{
		return -1;
	}
	item = queue->items[++queue->front];
	if (queue->front > queue->rear) 
		queue->front = queue->rear = -1;
	return item;
}
int main()
	{
	struct Queue* queue = createqueue();
	enqueue(queue, 1);
	enqueue(queue, 2);
	enqueue(queue, 3);
	printf("%d", dequeue(queue));
	printf("%d", dequeue(queue));
	printf("%d", dequeue(queue));
	return 0;
	}

接下来是循环队列

• 这里实际上有两个重点:

• 1. rear的下一个要为front时,就是

     (q->rear + 1) % maxsize == q->front时 队为满

  2. front==rear时为空

#define maxsize 100
typedef struct queue
{
	int array[maxsize];
	int front;
	int rear;
}squeue;
squeue initcirqueue()
{
	squeue q;
	q.front = q.rear = 0;
	return q;
}
void insertqueue(squeue* q, int e)
{
	if ((q->rear + 1) % maxsize == q->front)
	{
		return;
	}
	q->array[q->rear] = e;
	q->rear = (q->rear + 1) % maxsize;
	return;
}

void deletequeue(squeue* q, int* x)
{
	if (q->front == q->rear)
	{
		return;
	}
	*x = q->array[q->front];
	q->front = (q->front + 1) % maxsize;
	return;
}

然后是链式队列

typedef struct qnode
{
	int data;
	struct qnode* next;
}qnode;
typedef struct linkqueue
{
	qnode* front, * rear;
}linkqueue;
linkqueue* initlinkqueue()
{
	linkqueue* q;
	qnode* p;
	p = (qnode*)malloc(sizeof(qnode));
	p->next = NULL;
	q = (linkqueue*)malloc(sizeof(linkqueue));
	q->front = q->rear = p;
	return q;
}
void insertlinkqueue(linkqueue* q, int e)
{
	qnode* p;
	p = (qnode*)malloc(sizeof(qnode));
	if (!p)
	{
		return;
	}
	p->data = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
	return;
}
void outqueue(linkqueue* q, int* x)
{
	if (q->front == q->rear)
	{
		return;
	}
	qnode* p = q->front->next;
	*x = p->data;
	q->front->next = p->next;
	if (p == q->rear)
		q->rear = q->front;
	delete(p);
	return;
}

void destroylinkqueue(linkqueue* q)
{
	while (q->front != NULL)
	{
		q->rear = q->front->next;
		delete(q->front);
		q->front = q->rear;
	}
	return;
}

6. 层次遍历

需要运用队列,跟3.差不多,

7.二叉排序树

做到了一个问题关于二叉排序树的

这里复习一下二叉排序树,左子树比头结点小,右子树比头结点大

• 二叉排序树的创建:

  struct Treenode
  {
  	int val;
  	struct Treenode*left;
  	struct Treenode*right;
  }treenode;
  
  Treenode*createnode(int key)//这里是创建以key为头结点的树
  {
  	Treenode*newnode=(Treenode*)malloc(sizeof(Treenode));
  	newnode->val=key;
  	newnode->left=NULL;
  	newnode->right=NULL;
  	return newnode;
  }
  
  Treenode* insert(Treenode* node,int key)//这里就是关键了,插入形成二叉排序树
  {
  	if(node==NULL)
  	{
  		return createnode(key);//这里不能node=createnode(key)否则会报错
  	}
  	if(key<node->val)
  	{
  		node->left=insert(node->left,key);
  	}
  	else
  	{	
  		node->right=insert(node->right,key);
  	}
  	return node;
  }

• 查找

  int findlevel(struct Treenode* root,int target,int level)
  {
  	if (root==NULL)
  	{
  		return -1;
  	}
  	if (root->val==target)
  	{
  		return level;
  	}
  	int leftlevel=findlevel(root->left,target,level+1);
  	if(leftlevel!=-1)
  	{
  		return leftlevel;
  	}
  	return findlevel(root->right,target,level+1);
  }

• 到这里就结束了,最后是主函数

  int main()
  {
  	Treenode* root = NULL;
  	int values[1000] = {};
  	int N,K;
  	scanf("%d %d", &N,&K);
  	for (int i = 0; i < N; i++)
  	{
  		scanf("%d", &values[i]);
  	}
  	int n = sizeof(values) / sizeof(values[0]);
  	for (int i = 0; i < n; i++)
  	{
  		root = insert(root, values[i]);
  	}
  	printf("%d", findlevel(root, K, 1));
  	return 0;
  }

图

• 定义为一个偶对(V,E),G=(V,E),

• V是顶点的非空有限集

• E是无序集V&V的一个子集

• 路径,简单路径,回路,简单回路

• 思路:由n个顶点至少需要n-1条边使得其连通

  ​ 对无向图 至少需要n-1顶点的完全图的边+1确保它连通

1. 图的储存方式

1. 邻接表:

   

2. 邻接矩阵

   没有相邻的路即为无穷大


图的表达方法还有许许多多;

2.图的内容

1. 点

struct node
{
   int value;
   int in;//入度,一个点有多少个箭头指向它
   int out;//出度
   struct node*nexts;//箭头指向谁就包括谁
   struct node*edges;//有多少箭头从点发出
};

2. 有向边

struct edge
{
   int weight;
   struct node from;
   struct node to;
};

图有点集有边集，把东西都放着里面

贪心算法

分配会议时间

要求能举行最多的会议,思路是以结束时间谁早来进行安排

struct program
{
	int start;
	int end;
};
int cmp_str (const void *e1, const void*e2)
{
	return ((struct program*)e1)->end - ((struct program*)e2)->end;
}
int bestarrange(struct program program[], int timepoint,int n)
{
	qsort(program, n, sizeof(program[0]), cmp_str);
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		if (timepoint <= program[i].start)
		{
			result++;
			timepoint = program[i].end;
		}
	}
	return result;
}
int main()
{
	struct program program[10000];
	int n=0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &program[i].start, &program[i].end);
	}
	int result = bestarrange(program, 0,n);
	printf("%d", result);
	return 0;
}

动态规划

最长递增子序列

通过暴力搜索可以知道

int L(int nums[],int i,int sz)
{
	if(i== sz-1)
		return 1;
	int max_len = 1;
	for (int j = i + 1; j < sz; j++)
	{
		if (nums[j] > nums[i])
		{
			max_len=max(max_len,L(nums, j,sz)+1);
		}
	}
	return max_len;
}
int main()
{
	int nums[] = { 1, 5, 2, 4, 3 };
	int i = 0;
	int max = 1;
	int sz = sizeof(nums) / sizeof(nums[0]);
	while (i < sz)
	{
		max=max(max,L(nums, i,sz));
		i++;
	}
	printf("%d", max);
	return 0;
}

但有一个重要的问题就是时间复杂度太大了

我们可以利用一个哈希表来缩短所用时间，减少过程中的重复，当再次计算一个数的时候直接把他的结果返回，能大大减少时间

#define Max_Size 100
int Table[Max_Size] = { 0 };
void create_memo(int i,int length,int table[])
{
		table[i]=length;
}
int find_key(int table[], int key)
{
	return (table[key] != 0);
}
int L(int nums[],int i,int sz)
{
	if (find_key(Table, i))
	{
		return Table[i];
	}
	if(i== sz-1)
		return 1;
	int max_len = 1;
	int j = 0;
	for ( j = i + 1; j < sz; j++)
	{
		if (nums[j] > nums[i])
		{
			max_len=max(max_len,L(nums, j,sz)+1);
		}
	}
	create_memo(i,max_len ,Table);
	return max_len;
}
int main()
{
	int nums[] = { 1, 5, 2, 4, 3 };
	int i = 0;
	int max = 1;
	int sz = sizeof(nums) / sizeof(nums[0]);
	while (i < sz)
	{
		max=max(max,L(nums, i,sz));
		i++;
	}
	printf("%d", max);
	return 0;
}

DFS

斐波那契递归

先从最简单的学起

int n;
int f(int x)
{
	if (x == 1)return 1;
	if (x == 2)return 2;
	return f(x - 1) + f(x - 2);
}
int main()
{
	scanf("%d", &n);
	int res = f(n);
	printf("%d\n", res);
	return 0;
}

主要是返回前一项和后一项的和

递归搜索树

可得f(6)=13

递归实现指数问题

从1-n这n个整数中随机选取任意多个，输出所有可能的选择方案

1到n有两种选择，选或不选，也就是2^n个

递归/DFS最重要的是顺序

1. 顺序:从1~n一次考虑每一个数选或不选

递归搜索树

代码

const int N = 20;
int n;
int st[N];//记录每个数的状态，0表示还没考虑,1表示选这个数,2表示不选这个数
void dfs(int x)//x表示枚举到了哪个位置
{
	if (x > n)
	{
		for (int i = 1; i <= n; i++)
		{
			if (st[i] == 1)
			{
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}

	//选
	st[x] = 1;
	dfs(x + 1);
	st[x] = 0;//恢复现场

	//不选
	st[x] = 2;
	dfs (x + 1);
	st[x] = 0;//恢复现场
}
int main()
{
	scanf("%d", &n);
	dfs(1);
	return 0;
}

全排列问题

顺序:

1. 依次枚举每个位置应该放那个数

   假如是123,第一个位置可以放三个数

2. 依次枚举每个数应该放哪个位置

   假如是123,第一个数1可以放三个位置

这里写第一种方法

eg:当n=3时,一共有三个位置

递归搜索树

代码

const int N = 10;
bool st[N]; //true表示已经选过,false表示没有选过这个数
int n;
int arr[N];//存的是答案,也就是123或者312这样的
void dfs(int x)
{
	if (x > n)
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d ", arr[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])
		{
			st[i] = true;
			arr[x] = i;
			dfs(x + 1);
			st[i] = false;
			arr[x] = 0;
		}
	}
}
int main()
{
	scanf("%d", &n);
	dfs(1);
	return 0;
}

组合数问题

顺序:

1. 依次枚举每个数放哪个位置
2. 依次枚举每个位置放那个数

这里选第二种

递归搜索树

代码

int arr[21];
int n,r;
void dfs(int x,int start)
{
	if (x > r)
	{
		for (int i = 1; i <= r; i++)
		{
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}
	for(int i=start;i<=n;i++)
	{
		arr[x] = i;
		dfs(x + 1,i+1);
		arr[x] = 0;
	}
}
int main()
{
	scanf("%d%d", &n,&r);
	dfs(1,1);
	return 0;
}

选数

跟组合数问题一样的递归树

int n, k;
int q[30];
int arr[30];
int res = 0;
bool is_prime(int sum)
{
	if (sum < 2)return false;
	for (int i = 2; i <= sqrt(sum); i++)
	{
		if (sum % i == 0)return false;
	}
	return true;
}
void dfs(int x, int start)
{
	if ((x - 1) + (n - start + 1) < k)
	{
		return;
	}  //剪枝过程,x-1是已经选了几个,n-start+1是可选择数,两者加起来要大于等于k才能有解,否则直接return
	if (x > k)
	{
		int sum = 0;
		for (int i = 1; i <=k; i++)
		{
			sum += arr[i];
		}
		if (is_prime(sum))
		{
			res++;
		}
		return;
	}
	for (int i = start;i <= n; i++)
	{
		arr[x] = q[i];
		dfs(x + 1, i + 1);
		arr[x] = 0;
	}
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <=n; i++)
	{
		scanf("%d", &q[i]);
	}
	dfs(1, 1);
	printf("%d\n", res);
	return 0;
}