1.课程安排表：

1. 线性表

2. 字符串

3. 栈和队列

4.树

5.查找

6.排序

7.暴力枚举法

8.广度优先搜索

9.深度优先搜索

10.分治

11.贪心

12.动态规划

13.图

14.数学方法与常见模型

15.大整数运算

16. 基础功能

2.   编程技巧：

1.把较大的数组放在main 函数（全局变量）外，作为全局变量，这样可以防止栈溢出，因为栈的大小是有限制的。GCC (C编译器) 段错误

2.如果能够预估栈，队列的上限，则不要用stack,queue，使用数组来模拟，这样速度最快。

3.输入数据一般放在全局变量，且在运行过程中不要修改这些变量。

4.在判断两个浮点数a 和b 是否相等时，不要用a==b，应该判断二者之差的绝对值fabs(a-b) 是否小于某个阈值，例如1e-9。

5.判断一个整数是否是为奇数，用x % 2 !=0，不要用x % 2 ==1，因为x 可能是负数。

6.用char 的值作为数组下标（例如，统计字符串中每个字符出现的次数），要考虑到char 可能是负数。有的人考虑到了，先强制转型为unsignedint 再用作下标，这仍然是错的。正确的做法是，先强制转型为unsignedchar，再用作下标。这涉及C++ 整型

3.线性表小结：

题目：快速找到未知长度单链表的中间节点。

设置2个指针，一开始同时指向头，第一个指针比第二个指针快2倍

4. 字符串函数的内部实现

1.strlen

描述：实现strlen，获取字符串的长度。函数原型如下：

int strlen(const char *str)

代码：

int strlen(const char *str)
{
	const char *s;
	for(s=str; *s; ++s)
		;
	return (s-str);
}

2.strcpy

   实现strcpy，字符串拷贝函数，函数原型如下：

char*strcpy(char *to, const char *from);

代码：

char *strcpy(char *to, const char *from)
{
	assert(to != NULL  && from != NULL);//断言错误
	char *p = to;
	while((*p++ = *from++) != '\0')
	;
	return to;
}

例如：数字1，2,3

1 2 3       ；    当前序号1

1 3 2       ；    当前序号2

2 1 3       ；    当前序号3

2 3 1       ；    当前序号4

3 1 2       ；    当前序号5

3 2 1       ；    当前序号6

三个数字1,2,3,有6种可能的排序情况，上述分别将序号都列举了出来。

那么现在需要解决的问题就是：已知当前排列中的序号 N, 求下一个序列 N+1。

求解过程：

为了便于操作，我们假设5个数字，分别是1,2,3,4,5

测试序列：以当前序列：1,4,3,5,2求出它的下一次排列。

现在将问题分解为4步骤：

1. 从后向前找出第一个不符合降序排列的数的下标，记为 i_pos，在本例子中那么就是数字3，下标i_pos 就是2。这里解释下何为第一个“不符合降序排列的数”，以例子来解释，从后向前找数的过程中，5,2,  是一个降序的排列，而3,5,2, 则破坏了这个降序的排列结构。

2. 在第一步找到的降序队列中，从其中找出大于下标为i_pos 的数，并且这个数在所有大于下标为i_pos 的数列中是最小的。那么以例子来说，这一步找到的数就是5，记录下标为j_pos;

3. 交换i_pos, 和 j_pos 下标的值。  执行完之后： 1,4,5,3,2

4. 从下标i_pos+1 开始知道末尾，对数列进行升序。例子中就应该是对 3,2 进行升序，最后的结果就是: 1,4,5,2,3

5. 最后输出结果。

代码实现：

#include <iostream>
#define swapData(x,y) {int tmp=x; x = y; y = tmp;}

using namespace std;

int next_permutation(int *num, int n)
{
	int length = n-1;
	int i_pos=-1;
	
	for(int i=length; i > 0; i --)
	{
		if(num[i]>num[i-1])
		{
			i_pos = i-1;
			break;
		}
	}
	// 判断是否到了末尾，即全部序列是降序的 
	if(i_pos==-1) return 0;
	
	int j_pos;
	for(int i=length; i > i_pos; i--)
	{
		if(num[i] > num[i_pos])
		{
			j_pos = i;
			break;
		}
	}
	
	swapData(num[i_pos], num[j_pos]);
	
	
	//冒泡排序 
	for(int i=i_pos+1; i < n; i++)
	{
		for(int j=length;  j > i; j--)
		{
			if(num[j] < num[j-1])
				swapData(num[j], num[j-1]);
		}
	}
		
	return 1;
}

main()
{
	int num[5]={1,2,3,4,5};
	do
	{
		for(int i=0; i <= 4; i++)
			cout << num[i] << " ";
		cout << endl;
	}while(next_permutation(num, 5));
	return 0;
}