(为了区分队空和队满)
6、进队：队是否满？满则不进，否则 rear=(rear+1)%n, 放新元素在rear位置
（先调整指针，后处理元素） 7、出队：队是否空？空则不出，否则 front=(front+1)%n, 取front位置元素
（先调整指针，后处理元素） f
0 1 2 3 4 5 n=6 c d e a b r
循环队列方案2:带'的与方案1相反 1、maxsize=n,数组长度是n 2'、队头整型指针front, 指向非空位置， 除非队空 3'、队尾整型指针rear， 指向空位置
4、队空：rear==front,初始化f=r=0 5、队满：(rear+1)%n==front, 牺牲一个单元
6'、进队：放新元素在rear位置 rear=(rear+1)%n, 7'、出队：取front位置元素 front=(front+1)%n, f
0 1 2 3 4 5 n=6 A r
涉及题目： 08年 7,16
06年 一(10,20)
05年 一(3,5)，二(2)
第五章 递归
写递归程序：有时很容易（数学公式存在）。 有时很难(没有现成数学公式)
运行原理：堆栈，编程时看不见。
递归程序一定可以写成非递归。对应的非 递归一般使用堆栈。
递归变成非递归有时候很难， 对问题的理解不够。
比如Ackerman函数，写成递归很容易， 变成非递归很难。
递归算法复杂度分析有时候很难 （生成函数）。
同样一个问题有时候用递归很容易 解决，用非递归不容易解决
同样一个问题有时候用非递归很容 易解决，用递归不容易解决
同样一个问题有时候用非递归，用 递归都不容易解决
=========================================== 如果没有数学公式，简单递归程序写法 1、写出递归函数的定义:
函数名，参数，结果(返回值类型和意义) 2、处理边界情况
3、按照递归函数的定义
（利用低一级结果，得到本级的结果）， 自己调用自己,自圆其说
========================================= 写非递归 写递归 |- 1(无定义), n<0 n!=n*...*2*1= |- 1, 0<=n<=1 |- n*(n-1)!,n>1
//非递归:O(n)
int f(int n){//f(n)计算n! int i,j;
if(n<=1)return 1; j=1;
for(i=1;i<=n;i++) j=j*i; return j; } //递归
int F(int n){
//写出函数定义：F(n)算出n!
if(n<=1)return 1; //处理边界情况 return n*F(n-1); //自己调用自己， } //同时满足结果
void main(){ int x,y; x=F(5); y=f(5);
printf(\ }
设F(n)的时间复杂度是T(n) 则F(n-1)的时间复杂度是T(n-1) T(1)=1
T(n)=1+T(n-1) T(n-1)=1+T(n-2)
T(n)=1+T(n-1) =1+1+T(n-2) =2+T(n-2) =3+T(n-3)
=1+1+...+T(1)=n-1+T(1) =1+1+...+1=n=O(n)
T(n)=k+T(n-1) =k+k+T(n-2) =2k+T(n-2) =3k+T(n-3) =nk=O(n)
=============================== Ackerman(n,m)函数
A(1,0)=2, n=1,m=0 A(0,m)=1 n=0,m>=0 A(n,0)=n+2 n>=2,m=0 A(n,m)=A(A(n-1,m),m-1) n,m>=1
int A(int n, int m){ if(n==1&&m==0)return 2; if(n==0&&m>=0)return 1; if(n>=2&&m==0)return n+2; if(n>=1&&m>=1)
return A(A(n-1,m),m-1); }
void main(){ int x;
x=A(9,4);
printf(\ }
假定A(n,m)的时间复杂度T(n,m) T(n,m)=1+T(A(n-1,m),m-1)+T(n-1,m) ================================ 斐氏数列
1 1 2 3 5 8 13 21 34 55 89 ..... |- 1 n=0 F(n)=|- 1 n=1 |- F(n-1)+F(n-2) n>1
//递归: F(n)算出F(n), //时间复杂度是T(n) int F(int n){
if(n<=1)return 1; return F(n-1)+F(n-2); }
T(n)=1+T(n-1)+T(n-2)
= 1 + 1+T(n-2)+T(n-3) + 1+T(n-3)+T(n-4)
生成函数来算。
//非递归: H(n)算出F(n),O(n) int H(int n){ int i,x,y,z ; if(n<=1)return 1; x=1; y=1;
for(i=2;i<=n;i++){ z=x+y; x=y; y=z; } }
main(){ int x,y x=F(13000); y=H(4);
printf(\ }
涉及题目： 08年 25 07年 27 06年 四(25) 05年 四(1)
第六章 排序
线性序：数字<，字符串字典序，姓氏笔画
整数数字排序，从小到大排序，数字放在数组里头
稳定：对于key相同者ai和aj，如果原
来ai在aj之前，排序后，保证ai还在aj之前， 则称为稳定，
否则叫做不稳定（不保证ai还在aj之前）。 （!=保证ai不在aj之前）。
最好 最坏 平均 稳定 =========================================== 冒泡：O(n) O(n*n) O(n*n) Yes
插入：O(n) O(n*n) O(n*n) Yes 折半
插入：O(n*logn) O(n*logn) O(n*logn) Yes 选择：O(n*n) O(n*n) O(n*n) Yes 归并：O(n+m) O(n+m) O(n+m) Yes 归并：O(nlogn) O(nlogn) O(nlogn) Yes 快速：O(n*logn) O(n*n) O(n*logn) NO 堆： O(n*logn) O(n*logn) O(n*logn) NO ===========================================
一、冒泡：Bubble Sort 0、执行多遍 每一遍： 1、指定一个方向： 从前到后（大数下沉），或
从后到前（小数上升）均可 但是只能选择一个方向。 2、相邻数据比较 3、次序不对就交换 4、每遍之后，数组变短
1、一旦没有交换就不要下一遍（停止）。 否则进行下一遍
1 2 3 4 5 6
选定：从前到后， n-1遍 2 6 3 7 5 4
第一遍： n-1次比较 2 3 6 7 5 4 2 3 6 7 5 4 2 3 6 5 7 4 2 3 6 5 4 | 7
第2遍： n-2次比较 2 3 6 5 4 | 7 2 3 5 6 4 | 7 2 3 5 4 | 6 7
第3遍： n-3次比较 2 3 5 4 | 6 7 2 3 4 | 5 6 7
第4遍： n-4次比较 2 3 4 | 5 6 7
第一遍： n-1次比较 2 3 6 5 4 | 7 一遍后最大的数字在最后
第二遍： n-2次比较 2 3 5 4 6 7
两遍后次大的数字在次后
第三遍： n-3次 2 3 4 | 5 6 7
三遍后第三大的数字在第三后
第四遍：没有交换 2 3 4 | 5 6 7 不需要第五遍
最后一遍,n-1遍 1次
最好时间复杂度=O(n)，只有一遍
最坏时间复杂度，n-1遍
=n-1+n-2+n-3+...+2+1= n*(n-1)/2=O(n*n)
平均时间复杂度=O(n*n) (n-1
+n-1+n-2 +n-1+n-2+n-3 +....
+n-1+n-2+...+1 )/n=O(n*n)
最坏：最多n-1遍
第1遍： n-1次比较 第2遍： n-2次比较 .........
+ 第n-1遍：1次比较 ---------------------- n*(n-1)
-------=O(n*n) 2
最好：1遍 O(n)
第1遍： n-1次比较
代码：
void bubble(int a[],int n){ int i,j;
for(i=1;i<=n;i++) for(j=i;j>0;j--)
比较交换(a[j-1],a[j]); }
运行情况如下： i=1;
j=1 比较交换(a[0],a[1]); ----------------------------------- i=2
j=2 比较交换(a[1],a[2]); j=1 比较交换(a[0],a[1]); --------------------------- i=3
j=3 比较交换(a[2],a[3]); j=2 比较交换(a[1],a[2]); j=1 比较交换(a[0],a[1]); --------------------------- i=4
j=4 比较交换(a[3],a[4]); j=3 比较交换(a[2],a[3]); j=2 比较交换(a[1],a[2]); j=1 比较交换(a[0],a[1]);
二、插入排序：直接插入
1、插入方向：2种，一般选择从后向前 2、利用原来的数组，排好序的部分放 在数组前面。
最开始的时候，只有第一个元素是 排好序的。
3、移动数据可以逐个
(临时单元记忆待查入元素， 书本上用)
也可以成批。
4、复杂度：n-1遍
最坏 最好 第1遍：1次 1 第2遍：2次 1 第3遍：3次 1 ....
+ 第n-1遍：n-1次 1 ------------------------------ O(n*n) O(n)
选定：从后向前 最坏 3 3.5 4 5 | 6 v=3.5 ========
最好