程序员数据结构笔记(三)

想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!
　　递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值)
　　　　　　　　　　　　　　2)二叉树(遍历等)
　　例2.判断数组元素是否递增
　　　　　int jidge(int a[],int n) {
　　　　　　if(n==1) return 1;
　　　　　　else
　　　　　　　if(a[0]>a[1]) return 0;
　　　　　　　else return jidge(a 1,n-1);
　　　　　}
　　例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树))
　　　　　int depth(nodetype *root) {
　　　　　　if(root==NULL)
　　　　　　　return 0;
　　　　　　else {
　　　　　　　h1=depth(root->lch);
　　　　　　　h2=depth(root->rch);
　　　　　　　return max(h1,h2) 1;
　　　　　　}
　　　　　 }
　　自己想想求二叉树结点个数(与上例类似)
　　例4.已知中序遍历和后序遍历,求二叉树.
　　　设一二叉树的:
　　　中序 S:E D F B A G J H C I
　　　　　　^start1 ^j ^end1
　　　后序 T:E F D B J H G I C A
　　　　　　^start2 ^end2
　　　　node *create(char *s,char *t, int start1,int start2,int end1,int end2)
　　　　{ if (start1>end1) return NULL; //回归条件
　　　　　root=(node *)malloc(sizeof(node));
　　　　　root->data=t[end2];
　　　　　找到S中T[end2]的位置为 j
　　　　　root->lch=create(S,T,s1,j-1,start1,j start2-start1-1);
　　　　　root->rch=create(S,T,j 1,end1,j start2-start1,end2-1);
　　　　　return root;
　　　　}
　　例5.组合问题
　　　n 个数: (1,2,3,4,…n)求从中取r个数的所有组合.
　　　设n=5,r=3;
　　　递归思想：先固定一位 5 (从另四个数当中选二个)
　　　　　　　　　　　　　 5,4 (从另三个数当中选一个)
　　　　　　　　　　　　　 5,4,3 (从另二个数当中选零个)
　　　即：n-2个数中取r-2个数的所有组合
　　　　　…
　　程序:
　　　void combire(int n,int r) {
　　　　for(k=n;k>=n r-1;k--) {
　　　　　a[r]=k;
　　　　　if(r==0) 打印a数组(表示找到一个解);
　　　　　else combire(n-1,r-1);
　　　　}
　　　}
回溯法:
　　回溯跟递归都是程序员考试里常出现的问题,大家必须掌握!
　　回溯法的有关概念:
　　1) 解答树:叶子结点可能是解,对结点进行后序遍历.
　　2) 搜索与回溯
　　五个数中任选三个的解答树(解肯定有三层,至叶子结点):
　　　　　　　　　　　　　　　ROOT 虚根
　　　　　　　　/　　　　　　/　　　 |　　\　　\
　　　　　　　 1　　　　　 2　　　　 3　　4　　 5
　　　　/ 　|　 |　 \　　/ | \ 　　 /\　　|
　　　 2　　3　 4　　5　3　4　5　　4　5　 5
　　　/|\ 　/\　|　 /\　|　|
　　 3 4 5 4　5 5　4　5 5　5
　　回溯算法实现中的技巧:栈
　　要搞清回溯算法，先举一个(中序遍历二叉树的非递归算法)来说明栈在非递归中所起的作用。
　　　　　 A 过程：push()->push()->push()->push()栈内结果:ABDE(E为叶子,结束进栈)
　　　　　/ \　　　pop()　　　ABD(E无右孩子,出栈)
　　　　 B　 C　　 pop()　　　AB(D无右孩子,出栈)
　　　　/\　　　　 pop()　　　A(B有右孩子,右孩子进栈)
　　　 D　F 　　　　.　　　　　 .
　　　/　/\　　　　 . 　　　　　.
　　 E　G　H　　　　. 　　　　　.
　　/　　　　　　　 .　　　　　 .
　 I　　　　　　　 最后结果： EDBGFIHAC
　　简单算法:
　　　　…
　　　if(r!=NULL) //树不空
　　　{ while(r!=NULL)
　　　　{ push(s,r);
　　　　　r=r->lch;　　　//一直向左孩子前进
　　　　}
　　　　while(!empty(s)) // 栈非空,出栈
　　　　{ p=pop(s);
　　　　　printf(p->data);
　　　　　p=p->rch;　　　//向右孩子前进
　　　　　while(p!=NULL)
　　　　　{ push(s,p);
　　　　　　p=p->lch; //右孩子进栈
　　　　　}
　　　　}
　　　}　//这就是传说中的回溯,嘻嘻……没吓着你吧
5选3问题算法:
　　思想: 进栈:搜索
　　出栈:回溯
　　边建树(进栈)边遍历(出栈)
　　基本流程:
　　太复杂了,再说我不太喜欢用WORD画图（有损形象），以后再整理!
　　程序: n=5;r=3
　　　　　……
　　　　　init(s)　　//初始化栈
　　　　　push(s,1)　//根进栈
　　　　　while(s.top<r-1)&&(s.data[s.top]!=n) //有孩子
　　　　　　push(s,s.data[s.top] 1); //孩子入栈
　　　　　while(!empty(s))
　　　　　{ if(s.top=r-1)
　　　　　　判断该"解"是否为解.
　　　　　　x=pop(s); //保留x,判断是否为最大值n,如果是n,则出栈
　　　　　　while(x==n)
　　　　　　x=pop(s);
　　　　　　push(s,x 1);
　　　　　　while(s.top<r-1)&&(s.data[s.top]!=n)
　　　　　　push(s,s.data[s.top] 1);
　　　　　}
　　背包问题: TW=20 , w[5]={6,10,7,5,8}
　　解的条件:1) 该解答树的叶子结点
　　2) 重量最大
　　解答树如下：　　　ROOT
　　　　　　　/ | | | \
　　　　　　　　　 6 10　　 7　　　5　 8
　　　　　　　　/ | | \　 / | \　 / \　|
　　　　　　　 10 7 5　8 7　5　8 5　 8 8
　　　　　　　　　| |　　　　　　|
　　　　　　　　　5 8　　　　　　8

程序:
　　temp_w 表示栈中重量和
　　…
　　init(s); //初始化栈
　　i=0;
　　While(w[i]>TW)
　　　i ;
　　　If(i==n) Return -1; //无解
　　　Else {
　　　　Push(s,i);
　　　　Temp_w=w[i];
　　　　i ;
　　　　while(i<n)&&(temp_w w[i]<=TW)
　　　　　{ push(s,i);
　　　　　　temp_w =w[i];
　　　　　　i ;
　　　　}
　　　　max_w=0;
　　　　while(!empty(s))
　　　　　{ if(max_w<temp_w)
　　　　　　　max_w=temp_w;
　　　　　　　x=pop(s);
　　　　　　　temp_w-=w[x];
　　　　　　　x ;
　　　　　　　while(x<n)&&(temp_w w[x]>TW)
　　　　　　　　x ;
　　　　　　　while(x<n)
　　　　　　　{ push(s,x);
　　　　　　　　temp_w=temp_w w[x];
　　　　　　　　x ;
　　　　　　　　while(x<n)&&(temp_w w[x]>TW)
　　　　　　　　x ;
　　　　　　　}
　　　　　}
　　请大家思考:四色地图问题,比如给中国地图涂色,有四种颜色,每个省选一种颜色,相邻的省不能取同样的颜色.不许偷懒，不能选人口不多于xxxxＷ的"大国"哦!如果真的有一天台湾独立了，下场就是这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵呵。
贪婪法:
　　不求最优解,速度快(以精确度换速度)
　　例:哈夫曼树,最小生成树
　　装箱问题:
　　有n个物品,重量分别为w[n]，要把这n个物品装入载重为TW的集装箱内,需要几个集装箱?
　　思想1:对n个物品排序
　　拿出第1个集装箱，从大到小判断能不能放。
　　2 …
　　3 …
　　. …
　　. …
　　思想2: 对n个物品排序
　　用物品的重量去判断是否需要一只新箱子，如果物品重量小于本箱子所剩的载重量,则装进去,反之则取一只新箱子。
程序:
　　count=1;qw[0]=TW;
　　for(i=0;i<n;i )
　　{
　　　k=0;
　　　while(k<count)&&(w[i]>qw[k])
　　　　k ;
　　　　if(w[i]<=qw[k])
　　　　　qw[k]=qw[k]-w[i];
　　　　　code[i]=k; //第i个物品放在第k个箱子内
　　　　else
　　　　　{count ; //取一个新箱子
　　　　　　qw[count-1]=TW-w[i];
　　　　　　code[i]=count-1;
　　　　}
　　}
　　用贪婪法解背包问题:
　　n个物品，重量:w[n] 价值v[i]
　　背包限重TW，设计一个取法使得总价值最大.
　　方法:
　　　0　　1　　2　　3　…　n-1
　　　w0　 w1 　w2 　w3　…　wn-1
　　　v0　 v1 　v2 　v3　…　vn-1
　　　v0/w0　 …　　　　　v(n-1)/w(n-1) 求出各个物品的"性价比"
　　先按性价比从高到低进行排序
　　已知:w[n],v[n],TW
　　程序:
　　…
　　for(I=1;I<n;I )
　　　d[i]=v[i]/w[i]; //求性价比
　　　for(I=0;I<n;I )
　　　{ max=-1;
　　　　for(j=0;j<n;j )
　　　　{ if(d[j]>max)
　　　　　{ max=d[j];x=j; }
　　　　}　
　　　　e[i]=x;
　　　　d[x]=0;
　　　}
　　　temp_w=0;temp_v=0;
　　for(i=0;i<n;i )
　　　{ if(temp_w w[e[i]]<=TW)
　　　　　temp_v=temp_v v[e[v]];
　　}

分治法:
　　思想:把规模为n的问题进行分解,分解成几个小规模的问题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解.
　　例:数轴上有n个点x[n],求距离最小的两个点.
　　分:任取一点,可以把x[i]这n个点分成两个部分
　　小的部分 分点 大的部分
　　　　|_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._|
　　治:解=min{小的部分的距离最小值;
　　　大的部分的距离最小值;
　　　大的部分最小点和小的部分最大点这两点之差;}
程序员考试下午试题（模拟）
一、把一个字符串插入到另一个字符串的某个位置（指元素个数）之后
　　char *insert(char *s，char *t，int position)
　　{ int i;
　　　char *target;
　　　if（position>strlen(t)） printf("error");
　　　else
　　　{ for (i=0;i< （1） ;i )
　　　　{ if (i<position)
　　　　　target[i]=s[i];
　　　　　else
　　　　　{ if(i< （2） )
　　　　　　target[i]=t[i];
　　　　　　else （3） ;
　　　　　}
　　　　}
　　　}
　　　return garget;
　　}
二、辗转相除法求两个正整数的最大公约数
　　int f(int a,int b)
　　{ if (a==b) （4） ;
　　　else
　　　{ if (a>b) return f(a-b,b);
　　　　else （5） ;
　　　}
　　}
三、求一个链表的所有元素的平均值
　　typedef struct { int num;
　　　float ave;
　　}Back;
　　typedef struct node{ float data;
　　　struct node *next;
　　} Node;
　　Back *aveage（Node *head）
　　{ Back *p,*q;
　　　p=（Back *）malloc（sizeof（Back））;
　　　if （head==NULL）
　　　{ p->num=0;
　　　　p->ave=0; }
　　　else
　　　{ （6） ;
　　　　p->num=q->num 1;
　　　　（7） ; }
　　　retuen p;
　　}
　　main()
　　{ Node *h; Back *p;
　　　h=create(); /*建立以h为头指针的链表*/
　　　if (h==NULL) printf("没有元素");
　　　else { p=aveage(h);
　　　　printf("链表元素的均值为：o",p->ave);
　　　}
　　}
四、希尔排序
　　已知待排序序列data[n]；希尔排序的增量序列为d[m]，其中d[]序列降序排列，且d[m-1]=1。其方法是对序列进行m趟排序，在第i趟排序中，按增量d[i]把整个序列分成d[i]个子序列，并按直接插入排序的方法对每个子序列进行排序。
希尔排序的程序为：
　　void shellsort(int *data,int *d,int n,int m)
　　{ int i,j;
　　　for (i=0;i<m;i )
　　　for (j=0; （1） ;j )
　　　shell( （2） );
　　}
　　void shell(int *data,int d,int num,int n)
　　{ int i,j,k,temp;
　　　for (i=1; （3） ;i )
　　　{ j=0;
　　　　temp=data[j i*d];
　　　　while ((j<i)&&( （4） ))
　　　　j ;
　　　　for (k=j;k<i;k )
　　　　　data[k 1]=data[k];
　　　　（5） ;
　　　　（6） }
　　}
五、求树的宽度
　　所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
　　int Width(BinTree *T)
　　{ int front=-1,rear=-1; /* 队列初始化*／
　　　int flag=0,count=0,p;/*p用于指向树中层的最右边的结点，flag记录层中结点数的最大值。*／
　　　if(T!=Null)
　　　{ rear ; （1） ; flag=1; p=rear;
　　　}
　　　while( （2） )
　　　{ front ;
　　　　T=q[front];
　　　　if(T->lchild!=Null)
　　　　{ rear ; （3） ; count ; } //
　　　　　if(T->rchild!=Null)
　　　　　{ rear ; q[rear]=T->rchild; （4） ; }
　　　　　if(front==p) /* 当前层已遍历完毕*/
　　　　　{ if( （5） ) flag=count; count=0; //
　　　　　　p=rear; /* p指向下一层最右边的结点*/
　　　　　}
　　　}
　　　return(flag);
　　}
六、区间覆盖
　　设在实数轴上有n个点（x0，x1，……，xn-2，xn-1），现在要求用长度为1的单位闭区间去覆盖这n个点，则需要多少个单位闭区间。
　　int cover(float x[ ], int num)
　　{ float start[num],end[num];
　　　int i ,j ,flag, count=0;
　　　for (i=0;i<num;i )
　　　{ flag=1;
　　　　for (j=0;j< （1） ;j )
　　　　{ if ((start[j]>x[i])&&(end[j]-x[i]<=1)) （2） ;
　　　　　else if ( （3） ) end[j]=x[i];
　　　　　else if ((x[i]>start[j])&&(x[i]<end[j])) flag=0;
　　　　　if (flag) break;
　　　　}
　　　　if ( （4） )
　　　　　{ end[count]=x[i]; （5）; count ; }
　　　}
　　　return count-1;
　　}
　　start[count]=x[i]


七、围棋中的提子
　　在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W[i][j]=0表示在位置（i，j）上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。可以用回溯法实现提子算法。
　　下列程序是黑棋（tag=1）下在（i，j）位置后判断是否可以吃掉某些白子，这些确定可以提掉的白子以一个线性表表示。
　　问题相应的数据结构有：
　　#define length 19 /*棋盘大小*/
　　#define max_num 361 /*棋盘中点的数量*/
　　struct position { int row; int col;
　　}; /*棋子位置*/
　　struct killed { struct position data[max_num]; int num;
　　} *p; /*存储可以吃掉的棋子位置*/
　　struct stack { struct position node[max_num]; int top;
　　}; /*栈*/
　　int w[length][length]; /*棋盘中双方的棋子分布*/
　　int visited[length][length]; /*给已搜索到的棋子位置作标记，初值为0，搜索到后为1*/
　　struct killed *kill(int w[length][length],int r,int c,int tag)
　　{ struct killed *p;
　　　struct position *s;
　　　struct stack S;
　　　for (i=0;i<length;i )
　　　for (j=0;j<length;j )
　　　　（1） ;
　　　S.top=-1; p->num=-1;
　　　if (w[r-1][c]==tag*(-1)) s->row=r-1; s->col=c;

else if (w[r 1][c]==tag*(-1)) s->row=r 1; s->col=c;
　　　else if (w[r][c-1]==tag*(-1)) s->row=r; s->col=c-1;
　　　else if (w[r][c 1]==tag*(-1)) s->row=r; s->col=c 1;
　　　else p->len=0; return p;
　　　push(S,s); visited[s->row][s->col]=1;
　　　flag=search(s,tag);
　　　while ( （2）)
　　　{ push(S,s); visited[s->row][s->col]=1;
　　　　（3）;
　　　}
　　　while (S->top>=0)
　　　　{ pop(S);
　　　　　（4）;
　　　　　flag=search(s,tag);
　　　　　while (flag)
　　　　　{ push(S,s);
　　　　　　visit(s);
　　　　　　flag=search(s);
　　　　　}
　　　　}
　　}

　　void push( struct stack *S, struct position *s)
　　{ S->top ;
　　　S->node[S->top].row=s->row;
　　　S->node[S->top].col=s->col;
　　　p->num ;
　　　p->data[p->num].row=s->row;
　　　p->data[p->num].col=s->col;
　　}

　　void pop(struct stack *S)
　　{ S->top--;
　　}

　　struct position *gettop(struct stack *S)
　　{ struct position *s;
　　　s->row=S->data[S->top].row;
　　　s->row=S->data[S->top].row;
　　　return s;
　　}

　　int search(struct position *s,int tag)
　　{ int row,col;
　　　row=s->row; col=s->col;
　　　if (W[row 1][col]=(-1)*tag)&&(!visited[row 1][col])
　　　{ s->row=row 1;s->col=col; return 1;}
　　　if (W[row-1][col]=(-1)*tag)&&(!visited[row-1][col])
　　　{ s->row=row-1;s->col=col; return 1;}
　　　if (W[row][col 1]=(-1)*tag)&&(!visited[row][col 1])
　　　{ s->row=row;s->col=col 1; return 1;}
　　　if (W[row][col-1]=(-1)*tag)&&(!visited[row][col-1])
　　　{ s->row=row;s->col=col-1; return 1}
　　　（5）;
　　}

答案：

（1）strlen(s) strlen(t) （2）position strlen(t) （3）target[i]=s[i-strlen(t)]
（4）return a （5）return f(a,b-a)
（6）q=aveage(head->next)　　（7）p->ave=(head->data q->ave*q->num)/p->num
（1）j<d[i] （2）data,d[i],j,n　（3）num i*d<n　　（4）data[j i*d]<temp　　（5）data[j]=temp
（1）q[rear]=T （2）front<p （3）q[rear]=T->lchild （4）count （5）flag<count
（1）count （2）(x[i]>end[j])&&(x[i]-start[j]<=1) （3）start[j]=x[i] （4）!flag （5）
（1）visited[i][j]=0 （2）flag　　（3）flag=search(s,tag) （4）s=gettop(S)　（5）return 0

想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!
　　递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值)
　　　　　　　　　　　　　　2)二叉树(遍历等)
　　例2.判断数组元素是否递增
　　　　　int jidge(int a[],int n) {
　　　　　　if(n==1) return 1;
　　　　　　else
　　　　　　　if(a[0]>a[1]) return 0;
　　　　　　　else return jidge(a 1,n-1);
　　　　　}
　　例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树))
　　　　　int depth(nodetype *root) {
　　　　　　if(root==NULL)
　　　　　　　return 0;
　　　　　　else {
　　　　　　　h1=depth(root->lch);
　　　　　　　h2=depth(root->rch);
　　　　　　　return max(h1,h2) 1;
　　　　　　}
　　　　　 }
　　自己想想求二叉树结点个数(与上例类似)
　　例4.已知中序遍历和后序遍历,求二叉树.
　　　设一二叉树的:
　　　中序 S:E D F B A G J H C I
　　　　　　^start1 ^j ^end1
　　　后序 T:E F D B J H G I C A
　　　　　　^start2 ^end2
　　　　node *create(char *s,char *t, int start1,int start2,int end1,int end2)
　　　　{ if (start1>end1) return NULL; //回归条件
　　　　　root=(node *)malloc(sizeof(node));
　　　　　root->data=t[end2];
　　　　　找到S中T[end2]的位置为 j
　　　　　root->lch=create(S,T,s1,j-1,start1,j start2-start1-1);
　　　　　root->rch=create(S,T,j 1,end1,j start2-start1,end2-1);
　　　　　return root;
　　　　}
　　例5.组合问题
　　　n 个数: (1,2,3,4,…n)求从中取r个数的所有组合.
　　　设n=5,r=3;
　　　递归思想：先固定一位 5 (从另四个数当中选二个)
　　　　　　　　　　　　　 5,4 (从另三个数当中选一个)
　　　　　　　　　　　　　 5,4,3 (从另二个数当中选零个)
　　　即：n-2个数中取r-2个数的所有组合
　　　　　…
　　程序:
　　　void combire(int n,int r) {
　　　　for(k=n;k>=n r-1;k--) {
　　　　　a[r]=k;
　　　　　if(r==0) 打印a数组(表示找到一个解);
　　　　　else combire(n-1,r-1);
　　　　}
　　　}
回溯法:
　　回溯跟递归都是程序员考试里常出现的问题,大家必须掌握!
　　回溯法的有关概念:
　　1) 解答树:叶子结点可能是解,对结点进行后序遍历.
　　2) 搜索与回溯
　　五个数中任选三个的解答树(解肯定有三层,至叶子结点):
　　　　　　　　　　　　　　　ROOT 虚根
　　　　　　　　/　　　　　　/　　　 |　　\　　\
　　　　　　　 1　　　　　 2　　　　 3　　4　　 5
　　　　/ 　|　 |　 \　　/ | \ 　　 /\　　|
　　　 2　　3　 4　　5　3　4　5　　4　5　 5
　　　/|\ 　/\　|　 /\　|　|
　　 3 4 5 4　5 5　4　5 5　5
　　回溯算法实现中的技巧:栈
　　要搞清回溯算法，先举一个(中序遍历二叉树的非递归算法)来说明栈在非递归中所起的作用。
　　　　　 A 过程：push()->push()->push()->push()栈内结果:ABDE(E为叶子,结束进栈)
　　　　　/ \　　　pop()　　　ABD(E无右孩子,出栈)
　　　　 B　 C　　 pop()　　　AB(D无右孩子,出栈)
　　　　/\　　　　 pop()　　　A(B有右孩子,右孩子进栈)
　　　 D　F 　　　　.　　　　　 .
　　　/　/\　　　　 . 　　　　　.
　　 E　G　H　　　　. 　　　　　.
　　/　　　　　　　 .　　　　　 .
　 I　　　　　　　 最后结果： EDBGFIHAC
　　简单算法:
　　　　…
　　　if(r!=NULL) //树不空
　　　{ while(r!=NULL)
　　　　{ push(s,r);
　　　　　r=r->lch;　　　//一直向左孩子前进
　　　　}
　　　　while(!empty(s)) // 栈非空,出栈
　　　　{ p=pop(s);
　　　　　printf(p->data);
　　　　　p=p->rch;　　　//向右孩子前进
　　　　　while(p!=NULL)
　　　　　{ push(s,p);
　　　　　　p=p->lch; //右孩子进栈
　　　　　}
　　　　}
　　　}　//这就是传说中的回溯,嘻嘻……没吓着你吧
5选3问题算法:
　　思想: 进栈:搜索
　　出栈:回溯
　　边建树(进栈)边遍历(出栈)
　　基本流程:
　　太复杂了,再说我不太喜欢用WORD画图（有损形象），以后再整理!
　　程序: n=5;r=3
　　　　　……
　　　　　init(s)　　//初始化栈
　　　　　push(s,1)　//根进栈
　　　　　while(s.top<r-1)&&(s.data[s.top]!=n) //有孩子
　　　　　　push(s,s.data[s.top] 1); //孩子入栈
　　　　　while(!empty(s))
　　　　　{ if(s.top=r-1)
　　　　　　判断该"解"是否为解.
　　　　　　x=pop(s); //保留x,判断是否为最大值n,如果是n,则出栈
　　　　　　while(x==n)
　　　　　　x=pop(s);
　　　　　　push(s,x 1);
　　　　　　while(s.top<r-1)&&(s.data[s.top]!=n)
　　　　　　push(s,s.data[s.top] 1);
　　　　　}
　　背包问题: TW=20 , w[5]={6,10,7,5,8}
　　解的条件:1) 该解答树的叶子结点
　　2) 重量最大
　　解答树如下：　　　ROOT
　　　　　　　/ | | | \
　　　　　　　　　 6 10　　 7　　　5　 8
　　　　　　　　/ | | \　 / | \　 / \　|
　　　　　　　 10 7 5　8 7　5　8 5　 8 8
　　　　　　　　　| |　　　　　　|
　　　　　　　　　5 8　　　　　　8