《现代编译原理--C语言描述》(1) - 绪论

绪论

这是我们的开端，这里我们要实现一个小型的直线式程序解释器。

1.1模块与接口

通过了解编译器的模块和接口我们可以更容易理解编译器系统的实现。一个典型编译器的各个阶段都通过一到多个软件接口来实现。

将编译器分解为多个模块是为了能够重用各个模块，在之前龙书中提到，一个前端可以对饮多个后端来实现针对不同的目标机的机器语言编译，反之亦成立。例如当要改变当前目标机时，只要改变栈帧布局（Frame Layout）和指令选择（Instruction selection）模块就可以了；改变源语言时只要改变翻译模块之前的模块就可以了，该编译器也可以再抽象语法（Abstract Syntax）接口处与面向语言的语法编辑器相连。

编译器的各个阶段及其接口：

源程序
->词法分析->单词符号
->语法分析->归约
->语义动作->抽象语法
->语义分析<-表<-环境
->转换->翻译<-帧<-栈帧布局
->IR树->规范化
->IR树->指令选择
->汇编->控制流分析
->流图->数据流分析
->冲突图->寄存器分配
->寄存器指派->代码流出
->汇编语言->汇编器
->可重定位代码->连接器
->机器语言

编译器的各阶段:

阶段	描述
词法分析	将源文件分解为一个个单词符号tocken
语法分析	分解程序的短语结构
语义动作	建立每个短语对应的抽象语法树
语义分析	确定每个短语的含义,建立变量和声明的关联,检查表达式的类型,翻译每个短语
栈帧布局	按机器要求的方式将变量,函数参数分配于活跃记录(即栈帧)内
翻译	生成中间表示树(IR树),这是一种与任意程序设计语言和目标机体系结构无关的表示
规范化	提取表达式中的副作用,整理条件分支,方便下一阶段的处理
指令选择	将IR树节点组合成与目标机指令的动作相对应的块
控制流分析	分析指令的顺序并建立控制流图,以此图表示程序执行是所有可能流经的所有控制流
数据流分析	收集程序变量的数据流信息,例如活跃分析(liveness analysis)计算每一个变量仍需使用其值的地点(即它的活跃点)
寄存器分配	为程序中的每一个变量好临时数据选择一个寄存器,不在同一时间活跃的两个变量可以共享同一个寄存器
代码流出	用机器寄存器替代每一条指令中出现的临时变量名
### 1.2工具和软件
上下文无关文法(context-free grammar)

正则表达式(regular expression)

Yacc(or Bison)

Lex(or Flex)github

没有版本强迫症的可以直接在Ubuntu下输入:

sudo apt-get install flex bison

当然要从源码编译也可以…

树语言的数据结构

接着我们来分析书中的程序1.1，在绪论中有提到每个Stm是一个语句而每个Exp是一个表达式,所以程序1.1中只有三种语句分别是A_CompoundStm(复合语句),A_AssignStm(赋值语句)和A_PrintStm(输出语句)

typedef struct A_stm_ *A_stm;
typedef struct A_exp_ *A_exp;
typedef struct A_expList_ *A_expList;
typedef enum {A_plus,A_minus,A_times,A_div} A_binop;

struct A_stm_ {enum {A_compoundStm, A_assignStm, A_printStm} kind;
             union {struct {A_stm stm1, stm2;} compound;
                    struct {string id; A_exp exp;} assign;
                    struct {A_expList exps;} print;
                   } u;
            };
A_stm A_CompoundStm(A_stm stm1, A_stm stm2);
A_stm A_AssignStm(string id, A_exp exp);
A_stm A_PrintStm(A_expList exps);
//以上为Stm
struct A_exp_ {enum {A_idExp, A_numExp, A_opExp, A_eseqExp} kind;
             union {string id;
                    int num;
                    struct {A_exp left; A_binop oper; A_exp right;} op;
                    struct {A_stm stm; A_exp exp;} eseq;
                   } u;
            };
A_exp A_IdExp(string id);
A_exp A_NumExp(int num);
A_exp A_OpExp(A_exp left, A_binop oper, A_exp right);
A_exp A_EseqExp(A_stm stm, A_exp exp);
//以上为Exp
struct A_expList_ {enum {A_pairExpList, A_lastExpList} kind;
                   union {struct {A_exp head; A_expList tail;} pair;
                          A_exp last;
                         } u;
                  };

A_expList A_PairExpList(A_exp head, A_expList tail);
A_expList A_LastExpList(A_exp last);
//以上为ExpList

每一个文法规则都有一个构造器，隶属于规则左部符号的联合（union）。

程序设计：直线式程序解释器

入门练习

环境(即符号表,它将变量名映射到这些变量相关的信息)
抽象语法(表示程序的短语结构的数据结构)
树数据结构的递归性
无赋值语句的函数式风格程序设计

虎书真的是猛啊,第一章的入门练习的实践性就这么强,直接要求读者自己根据绪论中的语法规则设计一个直线型程序解释器,我反复看了几遍才确信他就是让我这样去做,笑哭。人家作者都要求了,那咱就只能跟着做了。

(1)写一个函数int maxargs(A_stm)告知给定语句中任意子表达式内的print语句的参数个数,例如maxargs(prog)=2
prog:

A_stm prog(void) {

return
 A_CompoundStm(A_AssignStm("a",
                 A_OpExp(A_NumExp(5), A_plus, A_NumExp(3))),
  A_CompoundStm(A_AssignStm("b",
      A_EseqExp(A_PrintStm(A_PairExpList(A_IdExp("a"),
                 A_LastExpList(A_OpExp(A_IdExp("a"), A_minus,
                                       A_NumExp(1))))),
              A_OpExp(A_NumExp(10), A_times, A_IdExp("a")))),
   A_PrintStm(A_LastExpList(A_IdExp("b")))));
}

首先来了解一下宏语句#ifdef和#else还有#endif这是一组条件编译语句。条件编译命令最常见的形式为：

 #ifdef 标识符
  程序段1
  #else
  程序段2
  #endif

它的作用是：当标识符已经被定义过(一般是用#define命令定义)，则对程序段1进行编译，否则编译程序段2。其中#else部分也可以没有，即：

  #ifdef
  程序段1
  #endif

这里的“程序段”可以是语句组，也可以是命令行。这种条件编译可以提高C源程序的通用性。如果一个C源程序在不同计算机系统上系统上运行，而不同的计算机又有一定的差异。例如，我们有一个数据类型，在Windows平台中，应该使用long类型表示，而在其他平台应该使用float表示，这样往往需要对源程序作必要的修改，这就降低了程序的通用性。可以用以下的条件编译：

  #ifdef WINDOWS
  #define MYTYPE long
  #else
  #define MYTYPE float
  #endif

如果在Windows上编译程序，则可以在程序的开始加上

  #define WINDOWS

这样则编译下面的命令行：

  #define MYTYPE long

如果在这组条件编译命令之前曾出现以下命令行：

  #define WINDOWS 0

则预编译后程序中的MYTYPE都用float代替。这样，源程序可以不必作任何修改就可以用于不同类型的计算机系统。当然以上介绍的只是一种简单的情况，可以根据此思路设计出其它的条件编译。

回顾我们刚刚分析的程序1.1,其中有三种类型Stm,Exp和ExpList,
自然而然我们要对这三种情况分开判断,然后针对每一种类型的不同语句和构造器再分别判断。
这第一道题还是比较简单的就是一个大模拟。

好吧收回刚刚的话:-)，这第一个遇到的问题是头文件的引用重复，这样会使GCC编译出错，这里建议大家按照一定的规范来引用头文件，我是根据Google C++ Style的风格。

然后遇到的问题是Undefined reference to的问题，这个问题的原因有三种：

• 链接时缺失了相关目标文件（.o）
• 链接时缺少相关的库文件（.a/.so）
• 链接的库文件中又使用了另一个库文件
• 多个库文件链接顺序问题
• 在C++代码代码中链接C语言的库

很多时候错误非常隐蔽，因此，我们需要注意，在链接命令中给出所依赖的库时，需要注意库之间的依赖顺序，依赖其他库的库一定要放到被依赖库的前面，这样才能真正避免undefined reference的错误，完成编译链接。

回到题目本身，要求语句中print语句的参数个数，回顾slp.h文件，每个文法结构都有一个union域和kind域，通过这两个域我们可以确定是哪一个语句，并对当前的语句求出参数个数或者进行进一步的处理。

在mian.c中编写我们的程序

 #include <stdio.h>

 #inlcude <util.h>
 #include <slp.h>
 #include <prog.h>
 //注意头文件的引用顺序,先引用库文件再引用自己编写的文件
int maxargs(A_stm prog);

int maxargsexp(A_exp exp){
  if(exp->kind == A_eseqExp){
    return maxargs(exp->u.eseq.stm);
  }else if(exp->kind==A_opExp){
    int left = maxargsexp(exp->u.op.left);
    int right = maxargsexp(exp->u.op.right);
    return left+right;
  }else{
    return 0;
  }
}
//maxargs函数计算exp类型的参数个数
int exp_helper(A_expList list){
    if (list->kind == A_lastExpList){
                A_exp exp = list->u.last;
        if(exp->kind == A_idExp) return 1;
        if(exp->kind == A_numExp) return 1;
        if(exp->kind == A_opExp) return 1+maxargsexp(exp->u.op.left)+maxargsexp(exp->u.op.right);
        if(exp->kind == A_eseqExp) return 1+maxargs(exp->u.eseq.stm);
    }
    return 1+maxargsexp(list->u.pair.head) + exp_helper(list->u.pair.tail);
}
//帮助maxargs函数求print语句的值
int maxargs(A_stm prog){
    switch (prog->kind){
        case A_compoundStm :{
            int left = maxargs(prog->u.compound.stm1);
            int right = maxargs(prog->u.compound.stm2);
            return left+right;
        }
        case A_assignStm:{
            A_exp exp = prog->u.assign.exp;
            if (exp->kind == A_eseqExp){
                return maxargs(exp->u.eseq.stm);
             }else if(exp->kind == A_opExp){
                                int left=maxargsexp(exp->u.op.left);
                    int right=maxargsexp(exp->u.op.right);
                return left+right;
                }else{
                  return 0;
            }
        }
        case A_printStm:{
            A_expList list = prog->u.print.exps;
            return exp_helper(list);
        }
        default :
            return 0;
    }
}
//针对语句的maxargs
int main(){
    printf(">> Prog Section:\n");
    A_stm rp = prog();
    printf("the maximum number of arguments of any print statement is %d\n",maxargs(rp));
    return 0;
}

这里特别要注意的是题目中要求我们求所有print语句的参数个数,而print语句的参数中可能还包含print语句,在这里我假定一个包含print语句的参数算一个参数。

输入完成后打开Terminal输入

 $ make clean
 $ make a.out
 $ ./a.out

输出:

 >> Prog Section:
the maximum number of arguments of any print statement is 2

（2）写一个函数void interp(A_stm)，对一个用这种直线式程序语言写的程序进行“解释”。为了用“函数式程序设计”风格来编写该函数（这种风格不使用赋值语句），要在声明局部变量的同时
对它进行初始化。

首先将id×int表的声明加入slp.h中

typedef struct table *Table_;
typedef struct IntAndTable *iTable_;
struct table {string id; int value; Table_ tail;};
Table_ Table(string id,int value,struct table *tail);
struct IntAndTable {int value; Table_ t;};
iTable_ iTable(int value, Table_ t);

然后将实现加入slp.c中,并模仿Table写出iTable的实现

Table_ Table(string id,int value,struct table *tail){
  Table_ t = check_malloc(sizeof(*t));
  t->id=id; t->value=value; t->tail=tail;
  return t;
}

iTable_ iTable(int value, Table_ t){
    iTable_ it = checked_malloc(sizeof(*it));
    it->value = value; it->t = t;
    return it;
}

这样我们有了链表的结构,下一步要做的就是根据Table和iTable分别解释语句和表达式。在slp.c中只有A_PrintStm语句能够打印出内容，是唯一的副作用。链表中记录的是赋值映射，且靠表头的node中储存的映射优先级高于链表靠表尾的node，这样就保证了，映射关系的唯一性，我们所要做的工作就是将id和num的对应关系做好，并且在执行时输出正确的答案。同时还要考虑程序的鲁棒性，假设我们的代码针对语句完全合乎语法规则的时候是正确的，但是如果用户输入的语句并不是完全正确呢，我们的程序要能判断这种情况判断出这种情况。并输出

In statement ‘A_xxxx’
error: Identifier %s does not exist!

main.c:

#include <stdio.h>

#include "util.h"
#include "slp.h"
#include "prog1.h"
//注意头文件引用顺序
int maxargs(A_stm prog);
Table_ interpExpList(A_expList, Table_);
Table_ interpStm(A_stm, Table_);
iTable_ interpExp(A_exp, Table_);
//定义解释函数，使用函数式风格，不使用赋值语句，在定义时就对变量进行初始化
int ID_VALID =1;
//ID_VALID变量判断当前的id名是否有效,这个变量是否声明过
int maxargsexp(A_exp exp){
  if(exp->kind == A_eseqExp){
    return maxargs(exp->u.eseq.stm);
  }else if(exp->kind==A_opExp){
    int left = maxargsexp(exp->u.op.left);
    int right = maxargsexp(exp->u.op.right);
    return left+right;
  }else{
    return 0;
  }
}

int exp_helper(A_expList list){
  if (list->kind == A_lastExpList){
    A_exp exp = list->u.last;
    if(exp->kind == A_idExp) return 1;
    if(exp->kind == A_numExp) return 1;
    if(exp->kind == A_opExp) return 1+maxargsexp(exp->u.op.left)+maxargsexp(exp->u.op.right);
    if(exp->kind == A_eseqExp) return 1+maxargs(exp->u.eseq.stm);
  }
  return 1+maxargsexp(list->u.pair.head) + exp_helper(list->u.pair.tail);
}

int maxargs(A_stm prog){
  switch (prog->kind){
  case A_compoundStm :{
    int left = maxargs(prog->u.compound.stm1);
    int right = maxargs(prog->u.compound.stm2);
    return left+right;
  }
  case A_assignStm:{
    A_exp exp = prog->u.assign.exp;
    if (exp->kind == A_eseqExp){
      return maxargs(exp->u.eseq.stm);
    }else if(exp->kind == A_opExp){
      int left=maxargsexp(exp->u.op.left);
      int right=maxargsexp(exp->u.op.right);
      return left+right;
    }else{
      return 0;
    }
  }
  case A_printStm:{
    A_expList list = prog->u.print.exps;
    return exp_helper(list);
  }
  default :
    return 0;
  }
}

int lookup(Table_ t, string id){
    while ((t != NULL) && (t->id != id)) {
        t = t->tail;
    }
  //当t不为空且id名符合时结束
    if (t != NULL){
        return t-> value;
    //t不为空时,返回t的值
    }else{
        ID_VALID = 0;
        return -1;
    //如果t为空证明表中不存在这个变量,原语句出错
    }
}
//lookup函数实现在链表中查找优先级最高的node
Table_ update(Table_ t, string id, int value){
    return Table(id, value, t);
}
//update函数实现链表的更新,在表头插入新的节点
Table_ interpStm(A_stm s, Table_ t){
    switch (s->kind) {
        case A_compoundStm:{
            t = interpStm(s->u.compound.stm1, t);
            t = interpStm(s->u.compound.stm2, t);
            return t;
        }
    //对复合语句递归调用interpStm
        case A_assignStm:{
            iTable_ it = interpExp(s->u.assign.exp, t);
      //新建一个表达式node并初始化
            t = update(it->t, s->u.assign.id, it->value);
      //在表头加入该node
            return t;
        }
        case A_printStm:{
            t = interpExpList(s->u.print.exps, t);
            printf("\n");
            return t;
        }
        default:
            return t;
    }
}
//interpStm函数对语句解释
iTable_ interpExp(A_exp e, Table_ t){
    switch (e->kind){
        case A_idExp:{
            int value = lookup(t, e->u.id);
            if (!ID_VALID){
                printf("In statement A_idExp\n");
                printf("error: Identifier %s does not exist!\n", e->u.id);
                ID_VALID = 1;
        //如果未在链表中找到变量,报错
            }
            return iTable(value, t);
      //如果找到变量则返回一个表达式node
        }
        case A_numExp:{
            iTable_ it = iTable(e->u.num, t);
            return it;
        }
        case A_opExp:{
            iTable_ left = interpExp(e->u.op.left, t);
            iTable_ right = interpExp(e->u.op.right, t);
            switch (e->u.op.oper) {
                case A_plus:
                    return iTable(left->value + right->value, t);
                case A_minus:
                    return iTable(left->value - right->value, t);
                case A_times:
                    return iTable(left->value * right->value, t);
                case A_div:
                    return iTable(left->value / right->value, t);
                default:
                    return NULL;
            }
        }
        case A_eseqExp:{
            t = interpStm(e->u.eseq.stm, t);
            iTable_ it = interpExp(e->u.eseq.exp, t);
            return it;
        }
        default:
            return NULL;
    }
}
//interExp对表达式进行解释
Table_ interpExpList(A_expList e, Table_ t){
  //只有print语句中会有explist型参数,所以我们要打印所有参数
    switch (e->kind) {
        case A_pairExpList:{
            iTable_ it = interpExp(e->u.pair.head, t);
      //对当前表达式求值
            printf("%d ", it->value);
      //打印结果
            t = interpExpList(e->u.pair.tail, it->t);
      //继续对剩下的explist递归调用interExpList
            return t;
        }
        case A_lastExpList:{
            iTable_ it = interpExp(e->u.last, t);
            printf("%d ", it->value);
            return it->t;
        }
        default:
            return t;
    }
}
//interpExpList处理ExpList的情况
void interp(A_stm prog){
    interpStm(prog, NULL);
}

int main(){
  printf(">> Right Prog Section:\n");
  A_stm rp = right_prog();
  printf("the maximum number of arguments of any print statement is %d\n",maxargs(rp));
  interp(rp);

  printf(">> Error Prog Section:\n");
  A_stm ep = error_prog();
  printf("the maximum number of arguments of any print statement is %d\n",maxargs(ep));
  interp(ep);
  return 0;
}

prog1.h

A_stm prog(void);
A_stm right_prog(void);
A_stm error_prog(void);

prog1.c

#include "util.h"
#include "slp.h"

A_stm prog(void) {
// a = 5 + 3;
// b = (print(a, a-1), 10*a);
// print b;
return
 A_CompoundStm(A_AssignStm("a",
                 A_OpExp(A_NumExp(5), A_plus, A_NumExp(3))),
  A_CompoundStm(A_AssignStm("b",
      A_EseqExp(A_PrintStm(A_PairExpList(A_IdExp("a"),
                 A_LastExpList(A_OpExp(A_IdExp("a"), A_minus,
                                       A_NumExp(1))))),
              A_OpExp(A_NumExp(10), A_times, A_IdExp("a")))),
   A_PrintStm(A_LastExpList(A_IdExp("b")))));
}

A_stm right_prog(void)
{
// a = 5 + 3;
// b = (print(a, a-1), 10*a);
// print b;
// a = (a = a+b, a);
     A_stm stm1 = prog();
     return
         A_CompoundStm( stm1, A_AssignStm("a",
      A_EseqExp(A_AssignStm("a", A_OpExp(A_IdExp("a"), A_plus, A_IdExp("b"))),
              A_IdExp("a"))));

}

A_stm error_prog(void)
{
// a = 5 + 3;
// b = (print(a, a-1), 10*a);
// print b;
// a = c;
     A_stm stm1 = prog();
     return
         A_CompoundStm( stm1, A_AssignStm("a", A_IdExp("c")));

}

输出：

>> Right Prog Section:
the maximum number of arguments of any print statement is 3
8 7
80
>> Error Prog Section:
the maximum number of arguments of any print statement is 3
8 7
80
In statement A_idExp
error: Identifier c does not exist!

习题

1.1a

即二叉树的查找

tree.h

typedef struct tree *T_tree;
struct tree {T_tree left; string key;T_tree right;};
T_tree Tree(T_tree l, string k,T_tree r);
T_tree insert(string key,T_tree t);
bool member(string key, T_tree t);

tree.c

 #include <string.h>
#include "util.h"
#include "tree.h"

T_tree Tree(T_tree l, string k,T_tree r){
  T_tree t = checked_malloc(sizeof(*t));
  t->left=l; t->key=k; t->right=r;
  return t;
}

T_tree insert(string key,T_tree t){
  if(t==NULL) return Tree(NULL, key, NULL);
  else if(strcmp(key,t->key) < 0)
    return Tree(insert(key,t->left),t->key,t->right);
  else if(strcmp(key,t->key) > 0)
    return Tree(t->left,t->key,insert(key,t->right));
  else return Tree(t->left,key,t->right);
}

bool member(string key, T_tree t){
  if(key==NULL) return FALSE;
  else if(t==NULL) return FALSE;
  else if(strcmp(key,t->key) < 0)
    return member(key,t->left);
  else if(strcmp(key,t->key) > 0)
    return member(key,t->right);
  else
    return TRUE;
}

test_tree.c

#include <stdio.h>
#include "util.h"
#include "tree.h"

int main(){
  T_tree t1 = NULL;
  t1 = insert(String("t"),t1);
  t1 = insert(String("s"), t1);
  t1 = insert(String("p"), t1);
  t1 = insert(String("i"), t1);
  t1 = insert(String("p"), t1);
  t1 = insert(String("f"), t1);
  t1 = insert(String("b"), t1);
  t1 = insert(String("s"), t1);
  t1 = insert(String("t"), t1);

  printf("The tree tspipfbst has element:\n");
  string element[27] ={ String("a"),String("b"),String("c"),String("d"),String("e"),
   String("f"),String("g"),String("h"),String("i"),String("j"),
   String("k"),String("l"),String("m"),String("n"),String("o"),
   String("p"),String("q"),String("r"),String("s"),String("t"),
   String("u"),String("v"),String("w"),String("x"),String("y"),
   String("z")};
  int i=0;
  while(i<26){
    if(member(String(element[i]),t1)){
      printf("%s ",element[i]);
    }
    i++;
  }
  printf("\n");

  T_tree t2 = NULL;
  t2 = insert(String("a"), t2);
  t2 = insert(String("b"), t2);
  t2 = insert(String("c"), t2);
  t2 = insert(String("d"), t2);
  t2 = insert(String("e"), t2);
  t2 = insert(String("f"), t2);
  t2 = insert(String("g"), t2);
  t2 = insert(String("h"), t2);
  t2 = insert(String("i"), t2);

  return 0;
}

makefile:

a.out: main.o prog1.o slp.o util.o
    cc -g main.o prog1.o slp.o util.o

b.out: test_tree.o util.o tree.o
    cc -g test_tree.o util.o tree.o -o b

test_tree.o: test_tree.c tree.h util.h
    cc -g -c test_tree.c

tree.o: tree.c tree.h util.h
    cc -g -c tree.c

main.o: main.c slp.h util.h
    cc -g -c main.c

prog1.o: prog1.c slp.h util.h
    cc -g -c prog1.c

slp.o: slp.c slp.h util.h
    cc -g -c slp.c

util.o: util.c util.h
    cc -g -c util.c

clean:
    rm -f a.out util.o prog1.o slp.o main.o tree.o

1.1b

题目的意思是二叉树的node不再是普通的字符串,而是一个pair,同时我们要通过lookup函数使得到的键值对是唯一的(一一对应)。

binding.h

typedef struct tree *T_tree;
typedef struct binding *T_binding;
struct binding {string key; void *value;};
T_binding Binding(string key, void *value);
struct tree {T_tree left; T_binding binding;T_tree right; };
T_tree Tree(T_tree l, T_binding b ,T_tree r);
T_tree insert(string key, void *binding, T_tree t);
void * lookup(string key, T_tree t);
bool member(string key, T_tree t);

binding.c

 #include <string.h>
#include "util.h"
#include "binding_tree.h"

T_tree Tree(T_tree l, T_binding b,T_tree r){
  T_tree t = checked_malloc(sizeof(*t));
  t->left=l; t->binding = b ; t->right=r;
  return t;
}

T_binding Binding(string key, void *value){
  T_binding b = checked_malloc(sizeof(*b));
  b->key=key; b->value=value;
}

T_tree insert(string key, void *value, T_tree t){
  if(t==NULL) return Tree(NULL, Binding(key, value), NULL);
  else if(strcmp(key,t->binding->key) < 0)
    return Tree(insert(key, value, t->left),t->binding,t->right);
  else if(strcmp(key,t->binding->key) > 0)
    return Tree(t->left,t->binding,insert(key, value, t->right));
  else return Tree(t->left,Binding(key, value),t->right);
}

void *lookup(string key, T_tree t){
  if(key==NULL||t==NULL) return NULL;
  else if(strcmp(key, t->binding->key) > 0)
    return lookup(key, t->right);
  else if(strcmp(key, t->binding->key) < 0)
    return lookup(key, t->left);
  else
    return t->binding->value;
}
bool member(string key, T_tree t){
  if(key==NULL) return FALSE;
  else if(t==NULL) return FALSE;
  else if(strcmp(key,t->binding->key) < 0)
    return member(key,t->left);
  else if(strcmp(key,t->binding->key) > 0)
    return member(key,t->right);
  else
    return TRUE;
}

main.c

 #include <stdio.h>
#include "util.h"
#include "binding_tree.h"

int main(){
  T_tree t1 = NULL;

  t1 = insert(String("t"),(void *) 1, t1);
  t1 = insert(String("s"),(void *) 2, t1);
  t1 = insert(String("p"),(void *) 3, t1);
  t1 = insert(String("i"),(void *) 4, t1);
  t1 = insert(String("p"),(void *) 5, t1);
  t1 = insert(String("f"),(void *) 6, t1);
  t1 = insert(String("b"),(void *) 7, t1);
  t1 = insert(String("s"),(void *) 8, t1);
  t1 = insert(String("t"),(void *) 9, t1);

  printf("The tree tspipfbst has element:\n");
  string element[27] ={ String("a"),String("b"),String("c"),String("d"),String("e"),
   String("f"),String("g"),String("h"),String("i"),String("j"),
   String("k"),String("l"),String("m"),String("n"),String("o"),
   String("p"),String("q"),String("r"),String("s"),String("t"),
   String("u"),String("v"),String("w"),String("x"),String("y"),
   String("z")};
  int i=0;
  while(i<26){
    if(member(String(element[i]),t1)){
      long int num = (long int)lookup(String(element[i]),t1);
      printf("%s-%ld ",element[i],num);
    }
    i++;
  }
  printf("\n");

  /*T_tree t2 = NULL;
  t2 = insert(String("a"), t2);
  t2 = insert(String("b"), t2);
  t2 = insert(String("c"), t2);
  t2 = insert(String("d"), t2);
  t2 = insert(String("e"), t2);
  t2 = insert(String("f"), t2);
  t2 = insert(String("g"), t2);
  t2 = insert(String("h"), t2);
  t2 = insert(String("i"), t2);
*/
  return 0;
}

makefile

 a.out: main.o prog1.o slp.o util.o
    cc -g main.o prog1.o slp.o util.o

b.out: test_tree.o util.o tree.o
    cc -g test_tree.o util.o tree.o -o b

c.out: test_binding_tree.o util.o binding_tree.o
    cc -g test_binding_tree.o util.o binding_tree.o -o c

test_binding_tree.o: test_binding_tree.c binding_tree.h util.h
    cc -g -c test_binding_tree.c

binding_tree.o: binding_tree.c util.h
    cc -g -c binding_tree.c

test_tree.o: test_tree.c tree.h util.h
    cc -g -c test_tree.c

tree.o: tree.c tree.h util.h
    cc -g -c tree.c

main.o: main.c slp.h util.h
    cc -g -c main.c

prog1.o: prog1.c slp.h util.h
    cc -g -c prog1.c

slp.o: slp.c slp.h util.h
    cc -g -c slp.c

util.o: util.c util.h
    cc -g -c util.c

clean:
    rm -f a.out util.o prog1.o slp.o main.o tree.o test_tree.o test_binding_tree.o binding_tree.o b c

1.1cc

这个一眼就不平衡啊

(1)

                t
             s__|__t
          p__|__s
       i__|__NULL
    f__|__NULL
 b__|__NULL

(2)

       a
 NULL__|__b
    NULL__|__c
       NULL__|__d
          NULL__|__e
             NULL__|__f
                NULL__|__g
                   NULL__|__h
                      NULL__|__i

1.1d

将前面题目中的树改为AVL(平衡二叉搜索树)，详情看Segwick的course。

test_avl_tree.c

 #include <stdio.h>
#include "util.h"
#include "avl_tree.h"
int flag=0;
void printtree(A_tree t){
  if(t!=NULL){
    printf("%s",t->key);
    flag=t->height;
    printtree(t->left);
    printtree(t->right);
  }
}
int main(){
  A_tree t1 = NULL;
  t1 = insert(String("t"), t1);
  t1 = insert(String("s"), t1);
  t1 = insert(String("p"), t1);
  t1 = insert(String("i"), t1);
  t1 = insert(String("p"), t1);
  t1 = insert(String("f"), t1);
  t1 = insert(String("b"), t1);
  t1 = insert(String("s"), t1);
  t1 = insert(String("t"), t1);

  printf("The tree tspipfbst has element:\n");
  string element[27] ={ String("a"),String("b"),String("c"),String("d"),String("e"),
   String("f"),String("g"),String("h"),String("i"),String("j"),
   String("k"),String("l"),String("m"),String("n"),String("o"),
   String("p"),String("q"),String("r"),String("s"),String("t"),
   String("u"),String("v"),String("w"),String("x"),String("y"),
   String("z")};
  int i=0;
  while(i<26){
    if(member(String(element[i]),t1)){
      printf("%s ",element[i]);
    }
    i++;
  }
  printf("\n");

  printf("The tree is only %d floor",t1->height);

  printtree(t1);

  return 0;
}

avl_tree.h

 typedef struct avltree *A_tree;
struct avltree {A_tree left; string key;A_tree right; int height;};
int max(int a,int b);
A_tree Tree(A_tree l, string k,A_tree r);
A_tree insert(string key,A_tree t);
bool member(string key, A_tree t);
int getBalance(A_tree t);
A_tree rightRoate(A_tree t);
A_tree leftRoate(A_tree t);
void updateHeight(A_tree t);

avl_tree.c

 #include <string.h>
#include <stdio.h>
#include "util.h"
#include "avl_tree.h"
int KEY_VAILD=1;
int ILEFT=1;
int max(int a, int b){
 return (a) > (b) ? (a) : (b) ;
}

A_tree Tree(A_tree l, string k, A_tree r){
  A_tree t = checked_malloc(sizeof(*t));
  t->left=l; t->key=k; t->right=r; t->height=0;
  return t;
}

A_tree insert(string key,A_tree t){
  KEY_VAILD=1;
  ILEFT=1;
  if(t==NULL)
    return Tree(NULL, key, NULL);
  else if(strcmp(key,t->key) < 0){
    ILEFT=1;
    t->left = insert(key,t->left);
  }
  else if(strcmp(key,t->key) > 0){
    ILEFT=0;
    t->right = insert(key, t->right);
  }
  else {
    KEY_VAILD=0;
    return Tree(t->left,key,t->right);
  }
  updateHeight(t);
  if(KEY_VAILD){
    int balance = getBalance(t);

    if(balance > 1){
        printf("%s-%s\n",key,t->left->key);
        if(ILEFT)
          return leftRoate(t);
        else{
          printf("LR\n");
          t->left = rightRoate(t->left);
          return leftRoate(t);
        }
    }
    else if(balance < -1){
      if(t->right != NULL){
        if(ILEFT==0)
          return rightRoate(t);
        else{
          t->right = leftRoate(t->right);
          return rightRoate(t);
        }
      }
    }
  }
  return t;
}


bool member(string key, A_tree t){
  if(key==NULL) return FALSE;
  else if(t==NULL) return FALSE;
  else if(strcmp(key,t->key) < 0)
    return member(key,t->left);
  else if(strcmp(key,t->key) > 0)
    return member(key,t->right);
  else
    return TRUE;
}

int getBalance(A_tree t){
  if(t->left==NULL && t->right==NULL) return 0;
  else if(t->left==NULL) return (-1)-t->right->height;
  else if(t->right==NULL) return t->left->height-(-1);
  else return t->left->height - t->right->height;
  return 0;
}

A_tree rightRoate(A_tree t){
printf("rightr");
  A_tree r1 = Tree(t->right->left,t->right->key,t->left->right);
  r1=t->right;
  t->right = r1->left;
  r1->left = t;
  updateHeight(r1);
  updateHeight(t);
  return t;
}

A_tree leftRoate(A_tree t){
printf("leftr\n");
  A_tree l1 = Tree(t->left->left,t->left->key,t->left->right);
  l1=t->left;
  t->left= l1->right;
  l1->right=t;
  updateHeight(l1);
  updateHeight(t);
  return l1;
}

void updateHeight(A_tree t){
  if(t->left==NULL&&t->right==NULL){
    t->height=0;
  }else{
    if(t->left==NULL) t->height=1+t->right->height;
    else if(t->right==NULL) t->height=1+t->left->height;
    else t->height = 1+max(t->left->height,t->right->height);
  }
}

推荐阅读

1.C Interfaces and Implementations: Techniques for Creating Reusable Software

2.tong zy