5.4.1 Step 1: Search

The search step is an extended version of the corresponding code for BST insertion in <BST item insertion function 32>. The earlier code had only two variables to maintain: the current node the direction to descend from p. The AVL code does this, but it maintains some other variables, too. During each iteration of the for loop, p is the node we are examining, q is p's parent, y is the most recently examined node with nonzero balance factor, z is y's parent, and elements 0...k - 1 of array da[] record each direction descended, starting from z, in order to arrive at p. The purposes for many of these variables are surely uncertain right now, but they will become clear later.

148. <Step 1: Search AVL tree for insertion point 148> =
z = (struct avl_node *) &tree->avl_root;
y = tree->avl_root;
dir = 0;
for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) 
  {
int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param);
if (cmp == 0)
return &p->avl_data;
if (p->avl_balance != 0)
z = q, y = p, k = 0;
da[k++] = dir = cmp > 0;
}

This code is included in 146.

5.3 Operations

Now we'll implement for AVL trees all the operations that we did for BSTs. Here's the outline. Creation and search of AVL trees is exactly like that for plain BSTs, and the generic table functions for insertion convenience, assertion, and memory allocation are still relevant, so we just reuse the code. Of the remaining functions, we will write new implementations of the insertion and deletion functions and revise the traversal and copy functions.

145. <AVL functions 145> =
<BST creation function; bst => avl 30>
<BST search function; bst => avl 31>
<AVL item insertion function 146>
<Table insertion convenience functions; tbl => avl 592>
<AVL item deletion function 164>
<AVL traversal functions 178>
<AVL copy function 185>
<BST destruction function; bst => avl 84>
<Default memory allocation functions; tbl => avl 6>
<Table assertion functions; tbl => avl 594>

This code is included in 143.

5.1 Balancing Rule

A binary search tree is an AVL tree if the difference in height between the subtrees of each of its nodes is between -1 and +1. Said another way, a BST is an AVL tree if it is an empty tree or if its subtrees are AVL trees and the difference in height between its left and right subtree is between -1 and +1.

Here are some AVL trees:

These binary search trees are not AVL trees:

In an AVL tree, the height of a node's right subtree minus the height of its left subtree is called the node's balance factor (see balance factor). Balance factors are always -1, 0, or +1. They are often represented as one of the single characters -, 0, or +. Because of their importance in AVL trees, balance factors will often be shown in this chapter in AVL tree diagrams along with or instead of data items. Here are the AVL trees from above, but with balance factors shown in place of data values:

See also: [Knuth 1998b], section 6.2.3.

• Analysis of AVL Balancing Rule

5 AVL Trees

In the last chapter, we designed and implemented a table ADT using binary search trees. We were interested in binary trees from the beginning because of their promise of speed compared to linear lists.

But we only get these speed improvements if our binary trees are arranged more or less optimally, with the tree's height as small as possible. If we insert and delete items in the tree in random order, then chances are that we'll come pretty close to this optimal tree.¹

In “pathological” cases, search within binary search trees can be as slow as sequential search, or even slower when the extra bookkeeping needed for a binary tree is taken into account. For example, after inserting items into a BST in sorted order, we get something like the vines on the left and the right below. The BST in the middle below illustrates a more unusual case, a “zig-zag” BST that results from inserting items from alternating ends of an ordered list.

Unfortunately, these pathological cases can easily come up in practice, because sorted data in the input to a program is common. We could periodically balance the tree using some heuristic to detect that it is “too tall”. In the last chapter, in fact, we used a weak version of this idea, rebalancing when a stack overflow force it. We could abandon the idea of a binary search tree, using some other data structure. Finally, we could adopt some modifications to binary search trees that prevent the pathological case from occurring.

For the remainder of this book, we're only interested in the latter choice. We'll look at two sets of rules that, when applied to the basic structure of a binary search tree, ensure that the tree's height is kept within a constant factor of the minimum value. Although this is not as good as keeping the BST's height at its minimum, it comes pretty close, and the required operations are much faster. A tree arranged to rules such as these is called a balanced tree (see balanced tree). The operations used for minimizing tree height are said to rebalance (see rebalance) the tree, even though this is different from the sort of rebalancing we did in the previous chapter, and are said to maintain the tree's “balance.”

A balanced tree arranged according to the first set of rebalancing rules that we'll examine is called an AVL tree (see AVL tree), after its inventors, G. M. Adel'son-Vel'skii< and E. M. Landis. AVL trees are the subject of this chapter, and the next chapter will discuss red-black trees, another type of balanced tree.

In the following sections, we'll construct a table implementation based on AVL trees. Here's an outline of the AVL code:

142. <avl.h 142> =
<License 1>
#ifndef AVL_H
#define AVL_H 1

#include <stddef.h>

<Table types; tbl => avl 14>
<BST maximum height; bst => avl 28>
<BST table structure; bst => avl 27>
<AVL node structure 144>
<BST traverser structure; bst => avl 61>
<Table function prototypes; tbl => avl 15>

#endif /* avl.h */

143. <avl.c 143> =
<License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avl.h"

<AVL functions 145>

• AVL Balancing Rule
• AVL Data Types
• AVL Operations
• Inserting into an AVL Tree
• Deleting from an AVL Tree
• Traversal of an AVL Tree
• Copying an AVL Tree
• Testing AVL Trees

See also: [Knuth 1998b], sections 6.2.2 and 6.2.3; [Cormen 1990], section 13.4.

Footnotes

[1] This seems true intuitively, but there are some difficult mathematics in this area. For details, refer to [Knuth 1998b] theorem 6.2.2H, [Knuth 1977], and [Knuth 1978].

在pthreads标准库里面， 库本身并不提供对信号量的支持，因为POSIX标准并没有对信号量做出定义，但是如果你一定要使用信号量来完成程序的话，那么所有的内容都会包含在semphore.h文件里

请注意：不要混合着使用系统V自带的信号量，系统V的信号量位于sys/sem.h文件中

 1#include <semaphore.h>  
 2#include <pthread.h>  
 3#include <stdio.h>  
 4#define THREADS 20  
 5sem_t   OKToBuyMilk;  
 6int     milkAvailable;  
 7void* buyer(void *arg)  
 8{  
 9    //P()  
10    sem_wait(&OKToBuyMilk);  
11    if(!milkAvailable)  
12    {  
13        //Buy Some Milk  
14        ++milkAvailable;  
15    }  
16    //V()  
17    sem_post(&OKToBuyMilk);  
18    return;  
19}  
20int main(int argc, char* argv[])  
21{  
22    int i;  
23    pthread_t threads[THREADS];  
24    milkAvailable=0;  
25    //initlization the semphore with a value of 1.  
26    //Note the second argument: passing zero denotes   
27    //that the semaphore is shared between threads (and   
28    //not processes)  
29    if(sem_init(&OKToBuyMilk,0,1))  
30    {  
31        printf("Could not initialization a semphore\n");  
32        return -1;  
33    }  
34    for(i=0;i<THREADS; ++i)  
35    {  
36        if(pthread_create(&threads[i],NULL,&buyer,NULL))  
37        {  
38            printf("Could not create thread %d\n",i);  
39            return -1;  
40        }  
41    }  
42    for(i=0;i<THREADS; ++i)  
43    {  
44        if(pthread_join(threads[i],NULL))  
45        {  
46            printf("Could not join thread %d\n",i);  
47            return -1;  
48        }  
49    }  
50    sem_destroy(&OKToBuyMilk);  
51    //Make sure we don't have too much milk,      
52    printf("Total milk: %d\n", milkAvailable);  
53    return 0;  
54}  
55

运行程序

关于Semphore的API有下面几点说明：

• sem_init: 初始化一个新的semphore变量，第二个参数指出信号量的共享方式，0意味着该信号量是在线程间共享的而不是在进程间共享，最后的一个参数说明了信号量初始化时候的初始值
• sem_destroy: 析构掉一个已经退出的semphore变量
• sem_wait: 相当于P()操作  
• sem_post: 相当于V()操作

下面让我们用表格的形式总结一下关于线程操作的一些方法

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/asiainfolf/archive/2010/10/02/5918625.aspx

某些并行计算需要面临某些在计算进行前的某些单通瓶颈点，这种情况下，当然可以使用信号量的方式来进行处理，但是还存在着另外的一种处理方式是更加方便的，它就是：栅栏（在pthread库里面被定义成为类型 pthread_barrier_t），下面我们来看一段程序作为示例

 1#define _XOPEN_SOURCE 600
 2
 3#include <pthread.h>
 4#include <stdlib,h>
 5#include <stdio.h>
 6
 7#define ROWS        10000
 8#define COLS        10000
 9#define THREADS        10
10
11double initial_matrix[ROWS][COLS];
12double final_matrix[ROWS][COLS];
13
14//Barrier variable
15pthread_barrier_t barr
16
17extern void DotProduct(int row, int col, double source[ROWS][COLS], double destination[ROWS][COLS]);
18extern void determinant(double matrix[ROWS][COLS]);
19
20void * entry_point(void * arg)
21{
22    int rank = (int)arg;
23    int row;
24    for(row=rank*ROWS/THREADS; row < (rank+1)*THREADS;++row)
25        for(int col=0;col<COLS;++col)
26            DotProduct(row,col,initial_matrix,final_matrix);
27
28    //synchronization pointer
29    int rc = pthread_barrier_wait(&barr);
30    if(rc!=0 && rc != PTHREAD_BARRIER_SERIAL_THREAD)
31    {        
32        printf("Could not wait on barrier\n");
33        exit(-1);
34    }
35
36    for(row=rank*ROWS/THREADS; row < (rank+1)*THREADS;++row)
37        for(int col=0;col<COLS;++col)
38            DotProduct(row,col,final_matrix,initial_matrix);
39}
40
41int main(int argc, char* argv[])
42{
43    int i;
44    pthread_t thr[THREADS];
45
46    //Barrier initialization
47    if(pthread_barrierattr_init(&barr,NULL,THREADS))
48    {
49        
50        printf("Could not create a barrier\n");
51        return -1;
52    }
53
54    for(i=0;i<THREADS;++i)
55    {
56        if(pthread_create(&thr[i],NULL,&entry_point, (void*)i))
57        {
58            
59            printf("Could not create thread %d\n", i);
60            return -1;
61        }
62    }
63
64    for(i=0;i<THREADS;++i)
65    {
66        if(pthread_join(thr[i],NULL))
67        {
68            
69            printf("Could not join thread %d\n", i);
70            return -1;
71        }
72    }
73
74    double det = determinant(initial_matrix);
75    printf("The determinant of M^4 = %f\n", det);
76
77    return 0;
78        
79}

这段程序产生出许多个线程，并且分配给每个线程计算矩阵乘法的一部分，然后每个线程使用这次计算的结果，继续进行下一步的计算：另一个矩阵的乘法

几点关于API的说明：

1. barrier 变量必须在最开始声名为全局变量
2. barrier 变量的初始化必须在main函数里进行初始化
3. 在点上每一个线程都会等待它的对端完成工作

注意

在程序顶部的宏定义 _XOPEN_SOURCE 是非常重要的；如果没有这个变量，那么barrier类型就会在pthread.h中被屏蔽掉，这个定义必须在所有的头文件引用之前被定义出来

将任意正整数转换为四进制或八进制数。

刘峰六: 
(1)  请小心一个问题，对于8禁止，相当于3位一段，32位是不能被三整除的，也就会导致结果不正确
(2)  对于1111111000011这样的数字，如果数字式正数，如果前面补足N个0，那么其实数字的大小是不变的，所以这里我传入了sizeof(int)+1,也就是33
      但是如果是负数，那么只有2,4进制是正确的，因为它们不需要补位，但是对于8进制的话，如果开始是1，表示的是负数，那么就会涉及符号位的问题
      是补零还是补充一是不一定的，不同的编译器有着不同的处理，有的补1，有的补0(见《C语言教程》-- 谭浩强，昨儿刚查滴… … )(因为int是32位，所以
      永远是2和1滴倍数)
(3) 本体米有涉及16进制，涉及了也很简单，只要多个大于10就用 ‘A’ + ((unsigned )(x&(1<<(n-1))) >>(n-1))); 就OK了，因为32也是4的倍数，所以
      还是八进制最复杂~~~~~~~

   1:  

   2: /*

   3:  * A converter for Decimal to Binary Quaternary or Octal

   4:  */

   5:  

   6: #include <stdio.h> 

   7:  

   8: void printbin(int, int); 

   9: void printQuater(int,int); 

  10: void printOtc(int,int); 

  11:  

  12: int main(void) 

  13: { 

  14:         int x; 

  15:         printf("Input Number: "); 

  16:         scanf("%d", &x); 

  17:  

  18:     //Binary 

  19:         printf("it's binary form: "); 

  20:         printbin(x, sizeof(int)*8); 

  21:         putchar('\n'); 

  22:  

  23:     //Quaternary

  24:     printf("it's Quaternary form: "); 

  25:     printQuater(x, (sizeof(int)*8)); 

  26:     putchar('\n'); 

  27:  

  28:     //OTC 

  29:     printf("it's Otc form: "); 

  30:     printOtc(x, (sizeof(int)*8+1)); 

  31:     putchar('\n'); 

  32:  

  33:     return 0;

  34: } 

  35:  

  36: //Binary

  37: void printbin(int x, int n) 

  38: { 

  39:         if(n>0) 

  40:         { 

  41:                 putchar('0'+((unsigned) ( x &amp; (1 << (n-1)))  >> (n-1))); 

  42:                 printbin(x,n-1); 

  43:         } 

  44: } 

  45:  

  46:  

  47: // Quaternary

  48: void printQuater(int x,int n) 

  49: { 

  50:     if(n>0) 

  51:     { 

  52:         putchar('0'+ ((unsigned)( x &amp; ( 3 << (n-2))) >> (n-2) ) ); 

  53:         printQuater(x,n-2); 

  54:     } 

  55: } 

  56:  

  57: //Octal

  58: void printOtc(int x, int n) 

  59: { 

  60:     if(n>0) 

  61:     { 

  62:         putchar('0'+ ((unsigned)( x &amp; ( 7 << (n-3))) >> (n-3) ) ); 

  63:         printOtc(x,n-3); 

  64:     } 

  65:  

  66: } 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/asiainfolf/archive/2010/09/07/5867499.aspx

在VRP平台中，实现了strncpy类似的函数，定义如下

   1: #define CHAR  char   

   2: #define ULONG unsigned long   

   3: #define VOID  void   

   4:  

   5: #define MACRO_COPYWORLDLENGTH    4   

   6:  

   7: CHAR *VOS_strncpy(CHAR *pcDest, const CHAR *szSrc, ULONG ulLength)   

   8: {   

   9:     CHAR *pcPoint=pcDest;  

  10:  

  11:     if((NULL==szSrc)||(NULL==pcDest))  

  12:     {  

  13:             return NULL;  

  14:     }

  15:    

  16:      while(ulLength && (*pcPoint=*szSrc))  

  17:      {

  18:          pcPoint++;

  19:          szSrc++;

  20:          ulLenght--;

  21:      }

  22:      if(!ulLength)

  23:      {

  24:           *pcPoint='\0';

  25:      }

  26:      return pcDest;

  27: }

  28:  

  29: void main(void)

  30: {

  31:      CHAR szStrBuf[] ="1234567890";

  32:      CHAR szStrBuf1[]="1234567890";

  33:      CHAR *szHelloWorld = "Hello World!"

  34:      strncpy(szStrBuf, szHelloWorld, MACRO_COPYWORLDLENGTH);

  35:      VOS_strncpy(szStrBuf1, szHelloWorld, MACRO_COPYWORLDLENGTH);

  36:      printf("%s %s", szStrBuf, szStrBuf1);

  37: }

程序的输出结果是_____

【分析与解答】

          这个程序考察的是对C字符串处理内部机制的了解情况。
         cstring一族中：  strlen(const char* str) 返回的是字符串的长度，不包含 ‘\0’

                                    所以对strcpy的调用我们一般都是 :

                                          char * copy = new char[strlen(src)+1];
                                          strncpy(copy,src,strlen(src)); // strncpy 如果没有指定长度，那么同样也是不会复制’\0’的
                                          copy[strlen(src)+1]=’\0’

          为什么会不去复制’\0’呢？

          因为cstring库是memory.h库的底层实现，也就是说memcpy函数的底层实现是由unsigned char 类型的strncpy实现的，所以如果加上了NULL
          那么就会发生内存的截取，从而会导致的程序退出时，不能完全的删除内存(NULL后面的部分没有删除)，就会内存泄露，所以在标准库里面的
          strncpy是没有NULL的
          下面是某标注库的memory.h的定义：

   1: /*

   2:  * This file is part of the Mingw32 package.

   3:  *

   4:  * memory.h maps to the standard string.h header.

   5:  */

   6:  

   7: #include    <string.h>

         有了这个知识点，就很容易解答上面的程序了

          第一个输出，使用的是strncpy,所以只是起到了内存的覆盖的作用，输出是覆盖掉前4个字符的字符串  Hell567890
          第二个输出，调用了我们自己的程序，其中使用了字符串截断符NULL，所以输出的结果是前四个字符 Hell

【答案】 Hell1234567890  Hell

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/asiainfolf/archive/2010/09/05/5864093.aspx

在屏幕上显示杨辉三角形

            1
          1 1
        1 2 1
       1 3 3 1
      1 4 6 4 1
   1 5 10 10 5 1
………………………………..

【问题分析与算法设计】
     杨辉三角形中的数，正是(x+y)的N次方幂展开式各项的系数。从杨辉三角形的特点出发，可以总结出：
         1)第N行有N+1个值(设起始行为第0行)
         2)对于第N行的第J个值：(N>=2)
            当J=1或J=N+1时： 其值为1
            当J!=1且J!=N+1时：其值为第N-1行的第J-1个值与第N-1行第J个值之和
    将这些特点提炼成数学公式可表示为：
          1）x=1或x=N+1
          2）c(x,y)= c(x-1,y-1)+c(x-1,y)  这样便可以根据递归数学表达式来进行程序编写了。

【程序说明与注释】

  1: #include <stdio.h>
  2: #define WIDTH  4
  3: 
  4: int c(int,int);
  5: 
  6: int main(void)
  7: {
  8:     int i,j,n=13;
  9:     printf("N=");
 10:     
 11:     /*控制输入正确的值以保证屏幕显示的图形正确*/
 12:     while(n>12) scanf("%d",&n); 
 13: 
 14:     /*控制输出N行*/
 15:     for(i=0;i<=n;++i)
 16:     {
 17:         //every line
 18:         for(j=0;j<(12-i)/2*WIDTH;j++)
 19:             printf(" "); /*控制输出第i行前面的空格*/
 20:         for(j=1;j<i+2;j++)
 21:             printf("%4d",c(i,j)); /*输出第i行的第j个值*/
 22:         printf("\n");
 23:     }
 24:     system("PAUSE");    
 25:     return 0;
 26: 
 27: }
 28: 
 29: int c(int x, int y)
 30: {
 31:     int z;
 32:     if((y==1)||(y==x+1))
 33:         return 1;
 34:     z=c(x-1,y-1)+c(x-1,y);
 35:     return z;
 36: }
 37: 
 38: 

输出结果

                           1

                       1   1

                       1   2   1

                   1   3   3   1

                   1   4   6   4   1

               1   5  10  10   5   1

               1   6  15  20  15   6   1

           1   7  21  35  35  21   7   1

           1   8  28  56  70  56  28   8   1

       1   9  36  84 126 126  84  36   9   1

       1  10  45 120 210 252 210 120  45  10   1

   1  11  55 165 330 462 462 330 165  55  11   1

   1  12  66 220 495 792 924 792 495 220  66  12   1

VRRP

   本文介绍了VRRP的基本原理、特点和应用。

----------------------------------

VRRP概述

随着Internet的发展，人们对网络的可靠性的要求越来越高。对于局域网用户来说，能够时刻与外部网络保持联系是非常重要的。

通常情况下，内部网络中的所有主机都设置一条相同的缺省路由，指向出口网关（即图1中的路由器RouterA），实现主机与外部网络的通信。当出口网关发生故障时，主机与外部网络的通信就会中断。

配置多个出口网关是提高系统可靠性的常见方法，但局域网内的主机设备通常不支持动态路由协议，如何在多个出口网关之间进行选路是个问题。

IETF（Internet Engineering Task Force，因特网工程任务组）推出了VRRP（Virtual Router Redundancy Protocol）虚拟路由冗余协议，来解决局域网主机访问外部网络的可靠性问题。

VRRP是一种容错协议，它通过把几台路由设备联合组成一台虚拟的路由设备，并通过一定的机制来保证当主机的下一跳设备出现故障时，可以及时将业务切换到其它设备，从而保持通讯的连续性和可靠性。

使用VRRP的优势在于：既不需要改变组网情况，也不需要在主机上配置任何动态路由或者路由发现协议，就可以获得更高可靠性的缺省路由。

VRRP协议对应的是RFC3768，该协议仅适用于IPv4。

----------------------------------------

VRRP的基本概念

以下是与VRRP协议相关的基本概念：

-------------------------------------------------------------------

VRRP的工作原理

VRRP将局域网的一组路由器构成一个备份组，相当于一台虚拟路由器。局域网内的主机只需要知道这个虚拟路由器的IP地址，并不需知道具体某台设备的IP地址，将网络内主机的缺省网关设置为该虚拟路由器的IP地址，主机就可以利用该虚拟网关与外部网络进行通信。

VRRP将该虚拟路由器动态关联到承担传输业务的物理路由器上，当该物理路由器出现故障时，再次选择新路由器来接替业务传输工作，整个过程对用户完全透明，实现了内部网络和外部网络不间断通信。

如图1所示，虚拟路由器的组网环境如下：

• RouterA、RouterB和RouterC属于同一个VRRP组，组成一个虚拟路由器，这个虚拟路由器有自己的IP地址10.110.10.1。虚拟IP地址可以直接指定，也可以借用该VRRP组所包含的路由器上某接口地址。

• 物理路由器RouterA、RouterB和RouterC的实际IP地址分别是10.110.10.5、10.110.10.6和10.110.10.7。

• 局域网内的主机只需要将缺省路由设为10.110.10.1即可，无需知道具体路由器上的接口地址。

主机利用该虚拟网关与外部网络通信。路由器工作机制如下：

• 根据优先级的大小挑选Master设备。Master的选举有两种方法：

  • 比较优先级的大小，优先级高者当选为Master。

  • 当两台优先级相同的路由器同时竞争Master时，比较接口IP地址大小。接口地址大者当选为Master。

• 其它路由器作为备份路由器，随时监听Master的状态。

  • 当主路由器正常工作时，它会每隔一段时间（Advertisement_Interval）发送一个VRRP组播报文，以通知组内的备份路由器，主路由器处于正常工作状态。

  • 当组内的备份路由器一段时间（Master_Down_Interval）内没有接收到来自主路由器的报文，则将自己转为主路由器。一个VRRP组里有多台备份路由器时，短时间内可能产生多个Master，此时，路由器将会将收到的VRRP报文中的优先级与本地优先级做比较。从而选取优先级高的设备做Master。

从上述分析可以看到，主机不需要增加额外工作，与外界的通信也不会因某台路由器故障而受到影响。

-----------------------------------------------------------

VRRP协议介绍

• VRRP的报文结构
• VRRP的状态机

----------------------------------------------------

VRRP的报文结构

VRRP协议只有一种报文，即VRRP报文。VRRP报文用来将Master设备的优先级和状态通告给同一虚拟路由器的所有VRRP路由器。

VRRP报文封装在IP报文中，发送到分配给VRRP的IPv4组播地址。在IP报文头中，源地址为发送报文的主接口地址（不是虚拟地址或辅助地址），目的地址是224.0.0.18，TTL是255，协议号是112。VRRP报文的结构如图1所示。

图1 VRRP报文结构

各字段的含义：