一、本章内容常见的算法
- 线性表（数组）
- 队列
- 排序
- 查找
- 堆栈
- 二叉树
二、recaman问题(线性表—数组)
描述：
（题目要求0<k<50000,耗时：1000ms） eg:0,1,3,6,2,7,13,20,12,21,11,22,10……
for(i=1;i<=k;++i){
t=a[i-1]-i;
if(t<=0){
a[i]=a[i-1]+i;
continue;
}
for(j=1;j<i;++j){//上步没有continue，那么这步t>0
if(t==a[j])
break;
}
if(j==i){
a[i]=t;
}
else{
a[i]=a[i+1]+i;
}
}
- 规模：500000
- 基本操作：查找，比较(if(t==a[j]))
- 最坏的情况：总是t>0
- 复杂度：k*(k-1)/2∈O（n²）
- i=1，查找=0
- i=2，查找=1
- ……
- i=k,查找=k-1
所以基本上要运算:500000²。花费太长时间，必然超时。
解决办法：如果能只判断一次比较一次，那么复杂度就是一维线性：O(n)。 如何只要判断一次呢？定义两个线性表，一个线性表记录数据a[i]，另一个线性表used[t]（每计算一次a[i],就令used[a[i]]=1）,记录t当前这个数是否使用过。那么只需要判断if(used[t]==0)就可以避免查找多次
int a[500001],b[3020000];//b数组的大小是测试出来的，一开始可以开的很大.
//计算a=500000时候，值最大大约是3019000,所以开了一个3020000的数组
//b[i]=1,表示已经存在过，b[i]=0表示首次出现
int main(){
a[0]=0;
memset(b,0,sizeof(b));
for(int i=1;i<500001;i++){
a[i]=a[i-1]-1;
if(a[i]<=0||b[a[i]]==1)
a[i]=a[i-1]+i;
b[a[i]]=1;//标记是否使用
}
while(scanf("%d",&n),n+1)
printf("%d\n",a[n]);
return 0;
}
（PS：开的数组一般大小超过1万，2万,3万，4万，就不要开在函数内了。改在全局好。并且一般bool型的数组运算比int型的数组运算慢） 运用线性表–标记法！（牺牲了空间，换取时间）
三、队列，链表（类约瑟夫问题）
数据结构的循环队列(标记后继（指针）和数据)
定义队列为：
Struct queue{
Data password;
*queue next;
} 解决下列问题可以简化指针为：queue[0]=1,queue[i]=i+1,queue[n]=0;（标记后继的数组）
描述：人数是n，每个人的密码是m，n后数m达到的位置所在的人出列，最后未出列的人获胜（n,m<=100）
joseph(int m,int n,int a[]){//a数组记录密码值，也就是第i位置出列后，要报多少数
for(i=1;i<n;i++)//标记各个元素的后继结点
que[i]=i+1;
que[n]=1;//环形标记，尾部链接头部
i=n;//i表示当前位置，从n开始，因为到1号位置已经是报1了。
while(que[i]!=i){//如果自己的后继不是自己，也就是队列剩下不止一个人的时候循环继续
for(j=1;j<m;++j)//往后报数
i=que[i];//报数一次，当前位置就变成之前位置的后继，直到报到
printf("%d",que[i]);//输出出列序号
m=a[que[i]]; //取得新密码
que[i]=que[que[i]];//删除该元素---利用更改后继结点的方法
}
printf("%d\n",i);
} 更改后继，第i个出列，那么i-1的后继改成i的后继，也就是i-1原来的后继的后继(Q[i]=Q[Q[i]])。
复杂度：O（m* n）（出列n个人，每次出列一个要数m下，复杂度就是m *n）
四、堆栈(单栈)
处理需要反复从头开始进行的操作。对于前面的匹配后面的，这样的前后匹配的操作，适用于堆栈（eg:({[……]})这样的左右括号匹配，适用） 堆栈特点：先入后出，后入先出。
例题，找BUG 描述：输入一堆字符串,包含多个BUG字符。出现BUG的就删掉，留下其他字符输出 例如:BBUGUGBUBUGGG。最后余下空,输出。
if(栈顶的两个字符是U,B。当前需要push压入的就是G，那么就pop->B，U，G)
不需要一次循环找到bug就从头开始找bug，这样会超时的。
由于题目的时间限制，且不需要太多的栈功能可以考虑自己写栈，否则调stack头文件占用很大内存和时间。 如下：
#include<stdio.h>
char STACK[10000];
int SP,i;
void push(char c){//入栈
STACK[SP++]=c;
}
char pop(){//弹出栈顶
return STARK[--SP];//栈顶下降，返回弹出后的现栈顶元素
}
int main(void){
char c;
SP=0;
while((c=getchar())!=EOF){
if(c=='G'&&SP>1&&STARK[SP-2]=='B'&&STARK[SP-1]=='U'){
pop();
pop();
}
else
push(c);
}
for(i=0;i<SP;++i)
printf("%c",STARK[I]);
return 0;
}
堆栈使用类型应用
1.对于括号匹配（前后匹配）的问题适合堆栈来解决————匹配问题
例题：判断只由*和+组成的表达式中，去掉对运算结果没有影响的括号
思路：利用堆栈
- 去掉不含加号的括弧。‘(’入栈，之后遇到的第一个加号就入栈。如果在遇到)之前没有加号，那么就去掉这对括号。（如果没有加号有乘号，乘法已经是最高优先级了，这对括弧也可去掉）。总之‘(’之后，到‘)’之前没有+就弹栈
- 第一步之后，剩下的括号中必有+号。要使得这个这对括弧有保留下来的意义，需要括号前有字母或‘)’,或者括号后有‘(’或者字母.继续使用堆栈。只需要入栈‘(’.这个‘(’这个入栈的括弧肯定和栈顶的’)’（也就是表达式的最后一个右括号）匹配
代码如下：s栈记录‘(’位置，p栈记录加号位置
int main(){ while(gets(s)!=NULL){ for(i=0;s[i];++i) switch(s[i]){ case ‘)’:spush(i);break; case ‘)’:j=spop();if(!pp||pstack[pp-1]<j) s[i]=s[j]=’‘;else ppop();break;//j是前括弧的位置 case ‘+’:if(sp&&(!pp||sstack[sp-1]>))
} //上述消除了中间没有加号的括弧
for(i=j=0;s[i];++i)if(s[i]!='')t[j++]=s[i];t[j]=0;
for(i=0;t[i];++i)
switch(t[i]){
case ')':
case '(':
}
//j,i分别是一堆括号的前后标记.判断这对括弧的前后情况，看看要不要删除这对括号. }
2.Boolean Expressions
用堆栈来解决:这类表达式计算。(优先级低的放入堆栈，遇到更低的把之前的低的计算掉,再压入更低的那个操作符) 定义两个栈，oper栈是操作符栈，num是操作数栈
char oper[100],num[100],osp,nsp; void push(char c,short f){//f==0 操作符栈，f==1表示操作数栈
//从前往后进行入栈操作。规则如下：
}
int main(){ while(gets(s)!=NULL){ for(j=0;j<100;++j) oper[j]=num[j]=0; j=osp=nsp=0; }//清空栈,或者说初始化为空
}
操作如下： //遇到操作数V或者F，就入栈。 //遇到‘(’ 入栈， ‘（’不入栈[遇到‘)’后，在这对括弧之间的所有操作符都处理完] //（级别很高，)级别很小，‘）’比栈顶优先级小，所以遇到)必须要把前面运算符都操作掉 //遇到操作符，判断栈顶的操作符和接下来新的运算符的优先级。 //如果栈顶的优先级>=新来，那么进行栈顶操作符运算。弹出操作符栈顶，然后弹出操作数栈顶的两个操作数（如果原栈顶是一元操作符，就弹一个操作数），进行原栈顶操作运算，结果再压入操作数的栈顶。 //如果操作符栈顶(eg:|)比新来的运算符（eg:&），优先级低，那么新来的操作符入操作符栈 //’\0’的优先级最低，操作符栈中的操作符都运算完，操作数栈中的结果只剩下一个，也就是结果——输出
五、查找
二分法查找（转载）：C基础算法之二分法查找利用循环、递归实现
- 适用情况：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
- 基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
-
算法优势：二分法查找在针对大量有序排列的情况下发挥出很优越的效率，这里以最具规律性的数组为例，代码如下：
int binarysearch(int arr[],int len,int key);int binarysearch2(int array[],int key,int low,int high); int main(int argc, char * argv[]) { int array[] = {3,5,6,7,11,22,44,47 }; int i; printf("请参照下列数组，输入你要查找的目标：\n {"); int len = sizeof(array)/sizeof(int); for (i = 0; i < len; i++) { printf("%d,",array[i]); } printf("}:\n"); int dest; scanf("%d",&dest); int res = binarysearch(array,len,dest); printf("1. res = %d\n",res); int res2 = binarysearch2(array,dest,0,len - 1); printf("2. res = %d\n",res2); }
函数名称：用循环实现二分法查找过程,
返回值：返回目标值在数组中的下标
int binarysearch(int arr[],int len,int key)
{
int high,low;
high = len - 1;//假设数组是从小到大排列的
low = 0;
int midle = len/2;
while(high >= low)
{
midle = (high + low)/2;
if(arr[midle] == key)
return midle;
if(arr[midle] > key)
high = midle - 1; //前提是假设数组是从小到大排序，否则不确定是该加1还是减1
else if(arr[midle] < key )
low = midle + 1;
}
return (-1);
}
函数名称：用递归实现二分法查找
int binarysearch2(int array[],int key,int low,int high)
{
if (low >= high)
return (-1);
int midle = (low + high)/2;
if(array[midle] == key)
return midle;
if(midle == high || midle == low) //此时，只剩下了下标为high和low的两个数，
//确定另一个数不是key后，就确定查找完毕，并且未找到目标
{
if(array[high] == key)
return high;
else if(array[low] == key)
return low;
else
return (-1);
}
else if(array[midle] > key)
return binarysearch2(array,key,low,midle); //由于不确定排序方向，所以此处只能用midle值，而不能加1或减1
else if(array[midle] < key) //当中间值小于目标值时，在high的一侧继续查找，low变到midle位置上
return binarysearch2(array,key,midle,high);
}
