数据结构总复习（2）

二叉树基本操作

  1 //亲爱的，我又来写代码了，希望做到自己心中有思路，提纲，下笔如有神。。
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 typedef  char IelemType;
  7 typedef struct BiTNode{
  8   IelemType data;
  9   struct BiTNode *lchild;
 10   struct BiTNode *rchild;
 11  
 12 }BiTNode,*BiTree;
 13 typedef struct {
 14    BiTNode *base;//栈底
 15    BiTNode *top;//栈顶
 16    int stacksize;
 17    int length;
 18    int visited;
 19 }SqStack;
 20 #define stack_init_size 100
 21 #define stackAdd 10
 22 void InitStack(SqStack &s)
 23 {
 24     s.base=(BiTNode *)malloc(stack_init_size*sizeof(BiTNode));
 25     if(!s.base)
 26     {
 27         printf("内存分配失败！
");
 28         exit(0);
 29     }
 30     s.top=s.base;
 31     s.stacksize=stack_init_size;
 32     s.length=0;
 33     s.visited=0;
 34 }
 35 
 36 void Push(SqStack &s,BiTree t)
 37 {
 38    if(s.top-s.base>=s.stacksize)
 39    {
 40        s.base=(BiTNode *)realloc(s.base,(s.stacksize+stackAdd)*sizeof(BiTNode));
 41        if(!s.base)
 42        {
 43            printf("重新分配内存失败!
");
 44            exit(0);
 45        }
 46        s.top=s.base+s.stacksize;
 47        s.stacksize+=stackAdd;
 48    }
 49    *s.top++=*t;
 50    s.visited=0;
 51    s.length++;
 52    
 53 }
 54 void Pop(SqStack &s,BiTree &t)
 55 {
 56   if(s.top==s.base)
 57   {
 58       printf("栈中无元素进来
");
 59       exit(0);
 60   }
 61   t=(BiTNode *)malloc(stack_init_size*sizeof(BiTNode));
 62   *t=* --s.top;
 63   s.length--;
 64 }
 65 void GetTop(SqStack s,BiTree &t)
 66 {
 67   if(s.top==s.base)
 68   {
 69       printf("栈中无元素进来
");
 70       exit(0);
 71   }
 72   t=(BiTNode *)malloc(stack_init_size*sizeof(BiTNode));
 73   *t=*(s.top-1);
 74 }
 75 void CreateBiTree(BiTree &t,int i,int j,char ch)
 76 {
 77     if(i==0)
 78         printf("请输入根结点:
");
 79     if(i!=0&&i>=j)
 80         printf("请输入%c的左结点:
",ch);
 81     if(j!=0&&j>i)
 82         printf("请输入%c的右结点:
",ch);
 83     char e;
 84     char str[20];
 85     while(1)
 86     {
 87         fflush(stdin);//清除缓存，这个用法要记住。
 88         for(int k=0;k<20;k++)
 89         {
 90             str[k]=getchar();
 91             if(str[k]=='
')
 92                 break;//跳出for循环，注意和continue的区别
 93         }
 94         if(k==0) printf("请输入字符再按Enter键
");
 95         if(k==1)
 96             break;
 97         if(k>1)
 98             printf("只能输入一个字符，请重新输入");
 99     }
100     e=str[0];
101     if(e==' ') t=NULL;
102     else
103     {
104         if(!(t=(BiTree)malloc(sizeof(BiTNode))))
105             exit(0);
106         t->data=e;
107         ch=t->data;
108         i++;
109         CreateBiTree(t->lchild,i,j,ch);
110         j=i;j++;
111         CreateBiTree(t->rchild,i,j,ch);
112     }
113 }
114 int TreeDepth(BiTree t,int i,int &h)
115 {
116   if(t)
117   {
118     i=i+1;
119     if(h<i)
120         h=i;
121     TreeDepth(t->lchild,i,h);
122     TreeDepth(t->rchild,i,h);
123   }
124   return h;
125 }
126 void SaveElem(BiTree t,BiTree *Q,int i)
127 {
128     if(t)
129     {
130         Q[i]=t;
131         SaveElem(t->lchild,Q,2*i);
132         SaveElem(t->rchild,Q,2*i+1);
133     }
134 }
135 void Lev_Traverse(BiTree t,int h)
136 {
137     if(t==NULL)
138         printf("sorry!目前树为空.
");
139     int k=h,i,j;
140     BiTree *Q;
141     if(!(Q=(BiTree *)malloc(int(pow(2,h)-1)*sizeof(BiTNode))))
142         exit(0);
143 for(i=1;i<=int(pow(2,h)-1);i++){
144         Q[i]=NULL;}//初始化的问题
145 
146     SaveElem(t,Q,1);
147     for(i=1;i<=(pow(2,h)-1);i++)
148     {
149         if(int(pow(2,h))%i==0)
150         {
151             printf("
");
152           for(j=0;j<pow(2,k-1)-1;j++){
153                 printf(" ");
154             }
155             k--;
156         }
157        //for(j=0;i<k;i++)
158         //   printf("*");
159        if(Q[i])
160            printf("%c",Q[i]->data);
161        if(!Q[i])
162            printf(" ");
163      for(j=0;j<pow(2,k+1)-1;j++){
164                 printf(" ");}
165     }
166 }
167 void FirstPrint(BiTree T,int i){
168     //按先序次序(递归)访问二叉树
169     if(i==0)//现在知道为什么i需要这样传递进来了吧
170         printf("
先序(递归)遍历结果如下:
");
171     if(T){
172         i++;
173         printf("%-5c",T->data);      //访问T
174         FirstPrint(T->lchild,i);   //递归遍历左子树
175         FirstPrint(T->rchild,i);   //递归遍历右子树
176     }
177     i=0;
178 }//FirstPrintBiTree
179 void MiddlePrint(BiTree T,int i){
180     //按中序次序(递归)访问二叉树
181     if(i==0)
182         printf("
中序(递归)遍历结果如下:
");
183     if(T){
184         i++;
185         MiddlePrint(T->lchild,i);    //递归遍历左子树
186         printf("%-5c",T->data);      //访问T
187         MiddlePrint(T->rchild,i);   //递归遍历右子树
188     }
189     i=0;
190 }//MiddlePrint
191 void LastPrint(BiTree T,int i){
192     //按后序次序(递归)访问二叉树
193     if(i==0)printf("
后序(递归)遍历结果如下:
");
194     if(T){
195         i++;
196         LastPrint(T->lchild,i);   //递归遍历左子树
197         LastPrint(T->rchild,i);   //递归遍历右子树
198         printf("%-5c",T->data);   //访问T
199     }
200     i=0;
201 }//LastPrint
202 
203 //非递归先序遍历
204 void PreOrder(BiTree T,int i)
205 {
206     if(i==0)
207         printf("先序(非递归)遍历结果如下:
");
208     BiTree p=T,q;
209     SqStack s;
210     InitStack(s);
211     if(T)
212     {
213         while(1)
214         {
215           printf("%c",p->data);
216           Push(s,p);
217          if(p->lchild)
218          {
219              p=p->lchild;
220          }
221          else
222              break;
223         }
224         while(1)
225         {
226            Pop(s,q);
227            if(q->rchild)
228            {
229                q=q->rchild;
230                 printf("%c",q->data);
231            }
232            if(s.length==0)
233                break;
234         }
235     }
236 }
237 
238 //非递归中序遍历
239 void InOrder(BiTree T,int i)
240 {
241     if(i==0)
242         printf("中序(非递归)遍历结果如下:
");
243     BiTree p=T;
244     SqStack s;
245     InitStack(s);
246     while(p||(s.length!=0))
247     {
248         if(p)
249         {
250           Push(s,p);
251           p=p->lchild;
252         }
253         else
254         {
255              Pop(s,p);
256              printf("%c",p->data);//OK,完全正确。
257              p=p->rchild;
258         }
259     }
260 }
261 
262 //非递归后序遍历
263 void LastOrder(BiTree T,int i)
264 {
265     if(i==0)
266         printf("后序(非递归)遍历结果如下:
");
267     BiTree p=T,q=NULL;
268     SqStack s;
269     InitStack(s);
270     if(T)
271     {
272       while(1)
273       {
274          Push(s,p);
275          if(p->lchild)
276             p=p->lchild;
277          else
278          {
279            if(p->rchild)
280                p=p->rchild;
281             else
282             {
283                 break;
284             }
285          }
286       }//while
287      while(1)
288      {
289          GetTop(s,p);//先获得栈顶指针，然后去判断
290 
291          //若其右孩子已经被访问过，或是该元素没有右孩子，则由后序遍历的定义，此时可以visit这个结点了。
292          if(!p->rchild||s.visited)
293          {
294            Pop(s,q);
295            printf("%c",q->data);
296          }
297          else//右孩子存在，且未被访问
298          {
299            p=p->rchild;
300            while(p)
301            {
302                Push(s,p);
303                p=p->lchild;
304            }
305            s.visited=1;
306          }
307           if(s.length==0)
308                break;
309      }//while
310     }
311 }
312 
313 int mainMenu()
314 {
315     system("cls");
316     int choose;
317     char str[20];
318     printf("
			    [1]构造二叉树
");
319     printf("
			    [2]显示树状二叉树
");
320     printf("
			    [3]遍历二叉树 ->>进入子菜单
");
321     printf("
			    [4]查看二叉树信息 ->>进入子菜单
");
322     printf("
			    [5]对二叉树进行操作 ->>进入子菜单
");
323     printf("
			    [0]退出程序");
324     printf("
			*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*");
325     printf("
			请输入你的选择: ");
326     while(1){
327     scanf("%s",str);//接受输入
328     if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0
329         ||strcmp(str,"4")==0||strcmp(str,"5")==0){
330         choose=atoi(str);//转化为整型
331         break;
332     }
333     else{printf("			选择错误请重新输入: ");}
334     }
335     if(choose==0){printf("

	…~~~…~~~谢谢使用本程序~~~…~~~…

");}
336     return choose;
337 }
338 int TraverseMenu()
339 {
340     system("cls");
341     int choose;
342     char str[20];
343     printf("
			*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*");
344     printf("
			  请选择对应的选项按对应的方式遍历二叉树");
345     printf("
			*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*");
346     printf("
				[1]按先序(递归)遍历二叉树
");
347     printf("
				[2]按中序(递归)遍历二叉树
");
348     printf("
				[3]按后序(递归)遍历二叉树
");
349     printf("
				[4]按先序(非递归)遍历二叉树
");
350     printf("
				[5]按中序(非递归)遍历二叉树
");
351     printf("
				[6]按后序(非递归)遍历二叉树
");
352     printf("
				[7]按层次(非递归)遍历二叉树
");
353     printf("
				[0]返回主菜单");
354     printf("
			*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*
");
355     printf("			请输入你的选择: ");
356     while(1){
357     scanf("%s",str);//接受输入
358     if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0
359         ||strcmp(str,"4")==0||strcmp(str,"5")==0||strcmp(str,"6")==0||strcmp(str,"7")==0){
360         choose=atoi(str);//转化为整型
361         break;
362     }
363     else{printf("			选择错误请重新输入: ");}
364     }
365     if(choose==0){printf("

	…~~~…~~~谢谢使用本程序~~~…~~~…

");}
366     return choose;
367 }
368 int main()
369 {
370    system("color e0");
371    BiTree t;
372    int choose;
373    int flag=0;
374    while((choose=mainMenu())!=0)
375    {
376        switch(choose)
377        {
378        case 1:
379             if(flag==1)
380                    printf("你已经创建树，请先销毁！
");
381             else
382             {
383                 system("cls");
384                 CreateBiTree(t,0,0,'e');
385                 flag=1;
386             }
387         system("pause");
388         break;
389        case 2:
390            if(flag!=1)
391                printf("你还没建树!
");
392            else
393            {
394               system("cls");
395               int h;
396               h=TreeDepth(t,0,h);
397               printf("树的高度为:%d
",h);
398               printf("二叉树层序遍历结果为:
");
399               Lev_Traverse(t,h);
400            }
401            system("pause");
402            break;
403        case 3:
404            if(!t)
405                printf("你还没建树!
");
406            else
407            {
408                while((choose=TraverseMenu())!=0)
409                {
410                    switch(choose)
411                    {
412                    case 1:FirstPrint(t,0);printf("

");
413                           system("pause");break;
414                    case 2:MiddlePrint(t,0);printf("

");
415                           system("pause");break;
416                    case 3:LastPrint(t,0);printf("

");
417                           system("pause");break;
418                    case 4:PreOrder(t,0);printf("

");
419                           system("pause");break;
420                    case 5:InOrder(t,0);printf("

");
421                           system("pause");break;
422                    case 6:LastOrder(t,0);printf("

");
423                           system("pause");break;
424                    }
425                }
426            }
427 
428        }
429    }
430 
431     return 0;
432 }

View Code

线索二叉树（算法有点被绕到了）

#include<stdio.h>
typedef enum PointerTag {Link,Thread};//Link=0，指针(指其左右孩子)；Thread=1，线索(指前驱和后驱)
typedef struct BiThrNode{
 char data;
 struct BiThrNode *lchild,*rchild;//左右孩子指针
 PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre;
void InThreading(BiThrTree p)
{
    if(p)
    {
      Inhreading(p->lchild);//左子树线索化
      if(!p->lchild)//左子树为空
      {
          p->LTag=Thread;//这个标记为线索
          p->lchild=pre;//前驱线索
      }
      if(!pre->rchild)//右子树为空
      {
          pre->RTag=Thread;
          pre->rchild=p;//后继线索
      }
      pre=p;//保持pre指向p的前驱。
      Inhreading(p->lchild);//右子树线索化
    }
}

void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
    {
        printf("内存分配失败!
");
        exit(0);
    }
    Thrt->LTag=Link;//左标志为0，表示有左孩子
    Thrt->RTag=Thread;//右标志位1,表示其后继 //建立头结点
    Thrt->rchild=Thrt;//这是指它的后继
    if(!T)
        Thrt->lchild=Thrt;//如果树为空，左指针也回指
    else
    {
          Thrt->lchild=T;//这是指结点的前驱
        pre=Thrt;//指向刚刚访问过的结点,为全局变量,Thrt能够改变也是因为它
        InThreading(T);
        pre->rchild=Thrt;
        pre->RTag=Thread;//最后一个结点线索化
        Thrt->rchild=pre;
    }
}
//中序遍历
void InOrderTraverse_Thr(BiThrTree T)
{
  BiThrTree p;
  p=T->lchild;
  while(p!=T)
  {
      while(p->LTag==Link)//表明有左结点
      {
          p=p->lchild;
      }
      printf("%c",p->data);//第一个左结点输出
      while(p->RTag==Thread&&p->rchild!=T)//此时判断一下其后继
      {
          p=p->rchild;
          printf("%c",p->data);//访问其后继
      }
      p=p->rchild;//有右孩子
  }
}

View Code

赫夫曼编码

已经两次赫夫曼编码。。惭愧了

第一次的：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 typedef struct{
  5 unsigned int weight;
  6 unsigned int parent,rchild,lchild;
  7 }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
  8 typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表
  9 
 10 void SelectNode(HuffmanTree &HT,int searchNodes,int &minIndex1,int &minIndex2)
 11 {
 12     minIndex1=minIndex2=0;
 13     for(int i=0;i<searchNodes;i++)
 14     {
 15         if(HT[i].parent==0)
 16         {
 17             if((minIndex1==0)&&(minIndex2==0))
 18             {
 19               minIndex1=i;
 20              /* do
 21               {
 22                   minIndex2=i+1;
 23               } while(HT[minIndex2].parent!=0);
 24             */      
 25               minIndex2=i+1;
 26               while(HT[minIndex2].parent!=0)
 27                   minIndex2++;
 28             //保证1为最小
 29             if(HT[i].weight>HT[i+1].weight)
 30             {
 31                 HTNode temp={0,0,0,0};
 32                 temp=HT[i];
 33                 HT[i]=HT[i+1];
 34                 HT[i+1]=temp;
 35                 int tempindex;
 36                 tempindex=minIndex1;
 37                 minIndex1=minIndex2;
 38                 minIndex2=tempindex;
 39             }
 40             }
 41 
 42             else
 43             {
 44               if(HT[i].weight<HT[minIndex1].weight)
 45               {
 46                HTNode temp={0,0,0,0};
 47                temp=HT[minIndex1];
 48                HT[minIndex1]=HT[i];
 49                HT[minIndex2]=HT[minIndex1];
 50                minIndex1=i;
 51                minIndex2=0;
 52               }
 53               if(HT[i].weight<HT[minIndex2].weight)
 54               {
 55                 HT[minIndex2]=HT[i];
 56                 minIndex2=i;
 57               }
 58             }//else
 59         }//if
 60     }//for
 61 }
 62 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
 63 //w存放n个(叶子结点)字符的权值，构造赫夫曼树HT，并且求出n个字符的赫夫曼编码HC
 64     if(n<=1)
 65         return;
 66     int m=2*n-1;//结点的总个数
 67     HT=(HuffmanTree)malloc((m)*sizeof(HTNode));//书中提到0号单元未用，这是为什么呢？理解HT的定义,我先让它可用
 68     HTNode *p;
 69     int i,s1,s2;
 70     for(p=HT,i=0;i<n;++i,++p,++w)
 71     {
 72         p->weight=*w;
 73         p->parent=0;
 74         p->lchild=0;
 75         p->rchild=0;
 76         printf("%d	",p->weight);
 77     }
 78     //    *p={*w,0,0,0};
 79     for(;i<=m;++i,++p)
 80     {
 81         p->weight=0;
 82         p->parent=0;
 83         p->lchild=0;
 84         p->rchild=0;
 85     }
 86     //    *p={0,0,0,0};
 87     for(i=n;i<m;++i)
 88     {  //建赫夫曼树
 89        //for(int k=m-1;k>=1;;k--)
 90           /* for(int j=1;j<m;j++)
 91            {
 92                if(((HT[j].parent==0)&&(HT[j+1].parent==0))&&(HT[j].weight>HT[j+1].weight))
 93                    s1=j+1;
 94            }
 95             for(int k=1;k<m;k++)
 96            {
 97                if(HT[k].weight >HT[s1].weight)
 98                s2=k;
 99                if(((HT[k].parent==0)&&(HT[k+1].parent==0))&&(HT[k].weight>HT[k+1].weight))
100                    s2=k+1;
101            }*/
102             SelectNode(HT,i,s1,s2);
103             HT[s1].parent=i;
104             HT[s2].parent=i;
105             HT[i].lchild=s1;
106             HT[i].rchild=s2;
107             HT[i].weight=HT[s1].weight+HT[s2].weight;
108     }
109     //从叶子到根逆向求每个字符的赫夫曼编码
110     HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
111     char *cd;
112     char *mm;
113     int end,f;
114     unsigned int c;
115     cd=(char *)malloc(n*sizeof(char));//编码的最大空间
116     cd[n-1]='';//编码结束符，为什么要编码结束符
117     for(i=0;i<n;i++)
118     {
119         //end=n-1;
120         int count=0;
121         for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
122             if(HT[f].lchild== c)
123                 cd[count++]='0';
124             else
125                 cd[count++]='1';
126         //    HC[i]=(char *)malloc((count)*sizeof(char));//为第i个字符编码分配空间
127             mm=cd;
128             for(int k=0;k<count;k++,mm++)
129                 printf("%c",*mm);
130         //    strcpy(HC[i],&cd[count]);
131             //printf("%s",cd);
132             //HC[i]=&cd[end];
133     }
134 
135 
136     HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
137 }
138 int main()
139 {
140     int n;
141     HuffmanTree HT;
142     HuffmanCode HC;
143     printf("请输入要编码的个数：
");
144     scanf("%d",&n);
145     int *p,*q,h;
146     p=(int *)malloc(n*sizeof(int));
147     q=p;
148 //    p=NULL;
149     printf("输入相应编码的权值：
");
150     for(int k=0;k<n;k++,q++)
151         scanf("%d",q);//指针的输入有问题？给它加另一个指针
152         //p=&weight;
153     for(h=0, q=p;h<n;h++,q++)
154     {
155     printf("%d
",*q);
156     }
157     HuffmanCoding(HT,HC,p,n);
158 //    printf("输出编码的值：
");
159 //    for(int i=0;i<n;i++)
160 //        printf("%s",HC[i]);
161 
162 }

View Code

第二次的：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef struct{
 4  int weight;
 5  int parent,lchild,rchild;
 6 }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树
 7 typedef char ** HuffmanCode;
 8 void Select(HuffmanTree HT,int i,int &s1,int &s2)
 9 {
10     int min1=100,min2=100,k,t=100;
11 
12     for( k=0;k<=i;k++)
13     {
14         if(HT[k].parent==0)
15         {
16             if(t>HT[k].weight)
17             {
18                 t=HT[k].weight;
19                 min1=k;
20             }
21         }
22     }
23     t=100;
24     for( k=0;k<=i;k++)
25     {
26         if(HT[k].parent==0)
27         {
28             if(t>HT[k].weight)
29             {
30                 if(k!=min1)
31                 {
32                 t=HT[k].weight;
33                 min2=k;
34                 }
35             }
36         }
37     }
38     s1=min1;
39     s2=min2;
40 }
41 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
42 {
43   if(n<=1)
44         return;
45   int i,m,s1,s2,f;
46   char *cd;
47   HuffmanTree p;
48   m=2*n-1;
49   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
50   for(p=HT,i=1;i<=n;++i,++p,++w)
51   {
52       
53      p->weight=*w;
54      p->parent=0;
55      p->lchild=0;
56      p->rchild=0;
57   }
58   for(;i<=m;i++,p++)
59   {
60      p->weight=0;
61      p->parent=0;
62      p->lchild=0;
63      p->rchild=0;
64   }
65   for(i=n;i<m;i++)
66   {
67     Select(HT,i-1,s1,s2);
68     HT[s1].parent=i;
69     HT[s2].parent=i;
70     HT[i].lchild=s1;
71     HT[i].rchild=s2;
72     HT[i].weight=HT[s1].weight+HT[s2].weight;
73   }
74 
75   //从叶子结点到根逆向求每个字符的赫夫曼编码
76   HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
77   cd=(char *)malloc(n*sizeof(char));
78   cd[n-1]='';
79   for(i=0;i<n;++i)
80   {
81       int start=n-1;
82     for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
83         if(HT[f].lchild==c)
84             cd[--start]='0';
85         else
86             cd[--start]='1';
87   HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
88   HC[i]=&cd[start];//这里应该是没问题的。。。
89   }
90   free(cd);
91 }
92 int main()
93 {
94   HuffmanTree HT;
95   HuffmanCode HC;
96   int a[8]={1,2,3,4,5,6,7};
97   HuffmanCoding(HT,HC,a,7);
98   printf("%c",**HC);//怎么访问二级指针会出错。。
99 }

View Code

学会变通，方法各种各样，还有很多需要改进。。。

作者：wj704 出处：http://www.cnblogs.com/wj204/