大家都知道数据结构很重要,有助于我们的思维和锻炼我们处理数据的能力,但是我们之中很少有人将其全部实现,一般都是纸上谈兵,或者认为C++的STL已经帮我们干完了所有的事情,几乎所有经典的数据结构和算法都在STL中找得到,我们拿来用就是了.其实不然
你是否会经常忘记一些数据结构和算法呢?你可能在纸上写了很久终于理解了一个数据结构或者算法,心理到是挺高兴的.不过过了一端时间后你会发现你又将那个算法忘了.又不得不再拿一张纸和一只笔出来再写一遍.这主要是因为它还不是大脑中的一部分.
大家都知道实践出真知.如果你将它拿去上一次机,效果大大的不同,本人就深有体会.写出程序拿到机子上练一次,记忆太深刻了,后来也就觉得那些数据结构也不过如此,我也能实现得了.那些算法也成为了身体的一部分,成为了我自己的东西了.

以下我将写一些常见的数据结构c语言实现代码出来,主要是让大家做个参考,也给那些正在学习数据结构却不知道怎么实现的蝈蝈们一些启示.我主要参考的严蔚敏老师的《数据结构》一书,PASCAL版本,91年出版的那种绿皮的书,其实这本我个人觉得要比后来的c语言版的要好懂一些.

由于是我个人写的代码,所以可能会有人看不贯我的编码风格,但是我力求能让大家都满意哈,程序都在TC2.0下编译通过,能正常的运行.

下列代码都可以直接复制,无须改动即可运行

好,现在给出第一个代码

一. 表达式求值
描述:用户输入一个表达式,包括四则运算和一系列的整数,也包括括号,以'#'号作为表达式的结束
如 5+(5*4-2)#

回车后输出结果 23


程序的漏洞: 因为用的int类型作为栈的元素类型,所以做除法的时候有局限性,只能取整,所以也请大家想想怎么改良.

原代码如下:

Copy code

#include<stdio.h>
#include<stdlib.h>
#define STACKMAX 50/*栈元素的最大存储结构*/
#define TRUE 1
#define FALSE 0

typedef char elemType;

typedef struct stack/*定义栈结构*/
{
  elemType elem[STACKMAX];/*存储栈元素的数组*/
  int top;/*栈顶元素的下标*/
}stack;

/*栈的初始化*/
void init(stack* s)
{
  s->top = 0;
}

/*压入元素入栈*/
int push(stack* s,char x)
{
  if( s->top == STACKMAX )
    return FALSE;
    else
      {
        s->top = s->top + 1;
        s->elem[s->top] = x;
        return TRUE;
      }
}

/*元素出栈*/
elemType pop(stack* s)
{
  if(s->top == 0)
    return NULL;
    else
        {
          s->top = s->top - 1;
          return s->elem[s->top+1];
        }
}


/*取栈顶元素*/
elemType gettop(stack* s)
{
  if(s->top == 0)
    return NULL;
    else
        return s->elem[s->top];
}


/* 判断操作符op1与操作符op2的优先级
* 如果op1优先于op2,则返回'>'
* 如果op2优先于op1,则返回'<'
* 如果op1与op2的优先级相同，则返回'='
*/
char precede(char op1, char op2)
{
  switch(op1)
  {
    case '+':
    case '-':
        if(op2 == '+' || op2 == '-' || op2 == ')' || op2 == '#')
          return '>';
          else
            return '<';

    case '*':
    case '/':
        if( op2 == '(')
          return '<';
          else
            return '>';

    case '(':
        if(op2 == '+' || op2 == '-' || op2 == '*' || op2 == '/' || op2 == '(')
          return '<';
          else if(op2 == ')')
            return '=';
            break;
    case ')':if(op2 == '+' || op2 == '-' || op2 == '*' || op2 == '/' || op2 == ')' || op2 == '#')
              return '>';
              break;
    case '#':if(op2 == '+' || op2 == '-' || op2 == '*' || op2 == '/' || op2 == '(')
              return '<';
              else if(op2 == '#')
                  return '=';
                  break;
    default: return NULL;

  }
}

/* 计算操作并且返回结果
* a为第一个操作数
* b为第二个操作数
* theta为操作符
*/
int operate(int a, char theta, int b)
{
  int c;
  switch(theta)
  {
    case '+': c = a + b;
            break;
    case '-': c = a - b;
            break;
    case '*': c = a * b;
            break;
    case '/': c = a / b;
            break;
    default:break;
  }
  return c;
}


/* 本算法的核心函数 */
int exp_reduced()
{
  stack *optr;/* 操作符栈 */
  stack *opnd;/* 操作数栈 */
  char w;/* 记录用户输入的字符 */
  int a,b;/* 记录每次计算的两个操作数 */
  char theta;/* 记录每次计算的操作符 */
  if ((optr=(stack*)malloc(sizeof(stack))) == NULL)
    {
        printf("overflow!\n");
        exit(1);
    }
  if ((opnd=(stack*)malloc(sizeof(stack))) == NULL)
    {
        printf("overflow!\n");
        exit(1);
    }

    init(optr);/* 初始化 */
    init(opnd);
    push(optr,'#');/* 将表达式左端的虚设字符’#’压入栈 */
    scanf("%c",&w);/* 读入第一个字符 */
   
    while ( !(w == '#' && gettop(optr) == '#'))/* 当用户输入的不是结束字符'#'并且操作符栈不为空时循环*/
    {
        /* 如果输入的字符是数字遍压入数字栈，并且输入下个字符 */
        if ( w >= '0' && w <='9')
        {
        push(opnd,w - '0');
        scanf("%c",&w);
      }
        else/* 输入的是操作符 */
            {
                switch ( precede(gettop(optr), w) )/* 比较输入的操作符与操作符栈顶元素的优先级 */
                {
                case '<': push(optr,w);/* 输入的操作符优先级小于栈顶元素优先级，将输入的操作符压入栈 */
                        scanf("%c",&w);/* 输入下一个字符 */
                        break;
              case '=': pop(optr);/* 消去括号 */
                      scanf("%c",&w);
                      break;
              case '>': theta = pop(optr);/*输入的操作符优先级大于栈顶元素的优先级，取出数字栈的两个元素进行计算，结果再压入数字栈*/
                      b = pop(opnd);
                      a = pop(opnd);
                  push(opnd, operate(a,theta,b));
                      break;
              default:break;
              }
            }

    }
    free(optr);
    free(opnd);
    return gettop(opnd);/* 返回计算的结果 */
}

main()
{
  int result;
  result = exp_reduced();
  printf("%d\n",result);

}

[ 此贴被kangtalc在2006-08-12 21:40重新编辑 ]

二:图的深度优先搜索
描述: 我用图的邻接矩阵作为图的存储结构,然后深度优先遍历整个图,依次输出图的各个接点

输入:先输入各个结点的名称,然后输入边的信息,注意文件头部定义的VTXNUM和EDGE的数值,分别表示你要输入的结点的个数和输入边的条数,你要在原文件自行的修改这两个数值,可能有人问为什么能在程序中提示输入,主要是我不想用动态数组的缘故.还请大家见谅.言归正传.
比如一个图有8个结点,9条边,那么请你将在原文件VTXNUM后面的数值改为8,将EDGE的数值改为9.




假设图的结点为a,b,c,d,e,f,g,h这8个结点,ac,ab,be,bd,cf,cg,dh,eh,fg这9条边,那么请你在程序运行的时候输入abcdefgha c 1a b 1b e 1b d 1c f 1c g 1d h 1e h 1f g 1回车
也就是先输入这8个点然后不加空格输入a c 1然后又不加空格输入b e 1...
回车后的结果为
a     b     d     h     e     c     f     g





好了,原代码如下:

Copy code

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define VTXNUM 8/* 图的接点个数 */
#define EDGE 9/* 边的条数 */
#define TRUE 1
#define FlASE 0

/* 结点的结构类型，有一个数据域存储接点名称 */
typedef struct vertex
{
   char ch;
}vertex;

/* 边的结构类型，ADJ存储边的权值 */
typedef struct arc
{
   int adj;
}arc;

/* 图的结构类型，以邻接矩阵作为图的存储结构 */
typedef struct graph
{
   vertex vexs[VTXNUM + 1];
   arc arcs[VTXNUM + 1][VTXNUM + 1];
}gragh;


/* 建立一个图 */
void
crt_gragh(gragh * ga)
{
   int i;
   char c;/* 存储输入的接点名字 */
   int j;
   int k;
   vertex v1,v2;
int w;
   
   /* 输入各个顶点的名字 */
   for( i = 1; i <= VTXNUM; i++)
   {
       scanf("%c",&c);
       ga->vexs[i].ch = c;
   }
   
   /* 将各条边的权值初始化为0 */
   for(i = 1;i <= VTXNUM; i++)
      for(j = 1; j <= VTXNUM; j++)
        ga->arcs[i][j].adj = 0;

   /* 输入边的信息，v1为边的始点,v2为边的终点 ，w为边的权值*/
   for( k = 1; k <= EDGE; k++ )
   {
    scanf("%c %c %d", &(v1.ch), &(v2.ch), &w);
    i = LOCVERTEX( ga, v1);
    j = LOCVERTEX( ga, v2);
    ga->arcs[i][j].adj = w;
    ga->arcs[j][i].adj = w;
   }
}

/* 结点定位函数，输入一个结点的信息确定起在图中的位置 */
int LOCVERTEX(gragh * ga, vertex v)
{
   int i;
   for (i=1; i<=VTXNUM; i++)
       if (v.ch == ga->vexs[i].ch)
           break;
           if(i > VTXNUM)
               return 0;
               else return i;
}

/* 确定一个结点的第一个邻接结点 */
int FIRSTADJ(gragh * ga, int i)
{
   int j;
   for( j = 1; j <= VTXNUM; j++)
       if( ga->arcs[i][j].adj != 0)
           break;

       if( j > VTXNUM)
           return 0;
           else
               return j;
}

/* 确定结点i依靠的结点j的下一个邻接i结点 */
int NEXTADJ(gragh *ga,int i, int j)
{
   int k;
   k = j + 1;
   if(k >= VTXNUM)
       return 0;
       else
           {
                   for(; k <= VTXNUM ; k++)
                   if(ga->arcs[i][k].adj != 0)
                   break;
                   if( k > VTXNUM)
                       return 0;
                       else
                           return k;
        }
}

/* 对图中的各个结点进行深度优先搜索，遍历后的结点标号在visited数组中设为1*/
traver(gragh * ga, int visited[])
{
   int i;
   for( i = 1; i <= VTXNUM; i++)
   visited[i] = 0;
   for(i = 1; i <= VTXNUM; i++)
      if( !visited[i] )
         dfs(ga,i,visited);
}

dfs(gragh *ga, int v0, int visited[])
{
   int w;
   printf("%c\t",ga->vexs[v0].ch);/* 输出结点信息 */
   visited[v0] = 1;/* 表示已经遍历了该结点 */
   w = FIRSTADJ(ga,v0);/* 得v0的第一个邻接点*/
   while( w != 0 )
   {
       if( !visited[w] )/* 如果没有遍历过则进行深度优先搜索 */
           dfs(ga, w, visited);
           w = NEXTADJ (ga, v0, w);/* 求v0的下一个邻接点 */
   }
}

main()
{
   int visited[VTXNUM+1];
   gragh * ga;
   if((ga = (gragh *)malloc(sizeof(gragh))) == NULL )
        {
           printf("overflow!");
        exit(0);
        }
   crt_gragh(ga);
   traver(ga, visited);
   free(ga);
}

[ 此贴被kangtalc在2006-08-12 21:31重新编辑 ]

三. 图的广度优先搜索

描述:我用图的邻接矩阵作为图的存储结构,然后广度优先遍历整个图,依次输出图的各个接点

输入:先输入各个结点的名称,然后输入边的信息,注意文件头部定义的VTXNUM和EDGE的数值,分别表示你要输入的结点的个数和输入边的条数,你要在原文件自行的修改这两个数值,可能有人问为什么能在程序中提示输入,主要是我不想用动态数组的缘故.还请大家见谅.言归正传.
比如一个图有8个结点,9条边,那么请你将在原文件VTXNUM后面的数值改为8,将EDGE的数值改为9.(和上面深度优先搜索输入的方式一样)



假设图的结点为a,b,c,d,e,f,g,h这8个结点,ac,ab,be,bd,cf,cg,dh,eh,fg这9条边,那么请你在程序运行的时候输入abcdefgha c 1a b 1b e 1b d 1c f 1c g 1d h 1e h 1f g 1回车
也就是先输入这8个点然后不加空格输入a c 1然后又不加空格输入b e 1...
回车后的结果为
a   b     c     d     e     f     g     h



原代码如下:

Copy code

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAXSIZE 100
#define VTXNUM 8/* 图的接点个数 */
#define EDGE 9/* 边的条数 */
#define TRUE 1
#define FlASE 0

/* 定义队列结构 */
typedef struct queqe
{
   int elem[MAXSIZE+1];
   int rear, front;
}queue;

/* 定义结点类型, ch存储结点的信息 */
typedef struct vertex
{
   char ch;
}vertex;

/* 定义弧类型，adj存储权值 */
typedef struct arc
{
   int adj;
}arc;

/* 定义图类型，以邻接矩阵作为存储结构 */
typedef struct graph
{
   vertex vexs[VTXNUM + 1];
   arc arcs[VTXNUM + 1][VTXNUM + 1];
}gragh;



/* 初始化队列的函数 */
void iniqueue(queue * cq)
{
   cq->rear = cq->front;
}

/* 入队列函数 */
int enqueue(queue * cq, int x)
{
   if( (cq->rear + 1) % MAXSIZE == cq->front )
       return FlASE;
       else
           {
               cq->rear = (cq->rear + 1) % MAXSIZE;
               cq->elem[cq->rear] = x;
               return TRUE;
           }
}

/* 出队列函数 */
int dlqueue(queue * cq)
{
   int x;
   if (cq->front == cq->rear)
       return FlASE;
       else
           {
               x = cq->elem[cq->front];
               cq->front = (cq->front + 1) % MAXSIZE;
               return x;
           }
}

/* 队列判空函数 */
int empty(queue *cq)
{
   if(cq->front == cq->rear )
       return TRUE;
       else
           return FlASE;
}

/* 结点定位函数，返回结点在矩阵中位置的标号 */
int LOCVERTEX(gragh * ga, vertex v)
{
   int i;
   for( i = 1; i <= VTXNUM; i++)
       if( v.ch == ga->vexs[i].ch )
           break;
           if( i > VTXNUM )
               return 0;
               else return i;
}

/* 建立一个图 */
void crt_gragh(gragh * ga)
{
   int i,w;
   char c;
   int j;
   int k;
   vertex v1,v2;
   for( i = 1; i <= VTXNUM; i++)
   {
       scanf("%c",&c);
       ga->vexs[i].ch = c;
   }
   for(i = 1;i <= VTXNUM; i++)
      for(j = 1; j <= VTXNUM; j++)
        ga->arcs[i][j].adj = 0;

   for( k = 1; k <= EDGE; k++ )
   {
    scanf("%c %c %d", &(v1.ch), &(v2.ch), &w);
    i = LOCVERTEX( ga, v1);
    j = LOCVERTEX( ga, v2);
    ga->arcs[i][j].adj = w;
    ga->arcs[j][i].adj = w;
   }
}

/* 确定结点i依靠的结点j的下一个邻接i结点 */
int FIRSTADJ(gragh * ga, int i)
{
   int j;
   for( j = 1; j <= VTXNUM; j++)
       if( ga->arcs[i][j].adj != 0)
           break;

       if( j > VTXNUM)
           return 0;
           else
               return j;
}

/* 确定结点i依靠的结点j的下一个邻接i结点 */
int NEXTADJ(gragh *ga,int i, int j)
{
   int k;
   k = j + 1;
   if(k >= VTXNUM)
       return 0;
       else
           {
                   for(; k <= VTXNUM ; k++)
                   if(ga->arcs[i][k].adj != 0)
                   break;
                   if( k > VTXNUM)
                       return 0;
                       else
                           return k;
        }
}


/* 广度遍历结点的函数，本算法的核心 */
bfs(gragh *ga,int v0, int visited[])
{
   queue *Q;
   int v,w;
   if((Q = (queue*)malloc(sizeof(queue))) == NULL )/* 申请队列空间 */
       {
           printf("overflow!");
           exit(0);
       }
       printf("%c\t",ga->vexs[v0].ch);/* 输出第一个结点的信息 */
       visited[v0] = 1;/* 表示这个结点已经被访问 */
       iniqueue(Q);/* 初始化队列 */
       enqueue(Q,v0);/* 第一个访问的结点入队列 */
       while( !empty(Q) )/* 队列不为空便循环 */
       {
           v = dlqueue(Q);/* 取队头元素 */
           w = FIRSTADJ(ga, v);/* 并且求得对头元素的第一个邻接点 */
           while( w != 0)/* 如果有第一个邻接点 */
           {
               if( !visited[w] )/* 并且这个邻接点没有被访问过 */
                   {
                       printf("%c\t",ga->vexs[w].ch);/* 输出此邻接点的信息 */
                       visited[w] = 1;/* 置此邻接点被访问过 */
                       enqueue(Q,w);/* 此邻接点入队列 */
                   }
                   w = NEXTADJ(ga,v,w);/* 求当前队头元素的下一个邻接点 */
           }
       }    
       free(Q);
}

/* 对图中的各个结点进行深度优先搜索，遍历后的结点标号在visited数组中设为1 */
traver(gragh * ga, int visited[])
{
   int i;
   for( i = 1; i <= VTXNUM; i++)
   visited[i] = 0;
   for(i = 1; i <= VTXNUM; i++)
      if( !visited[i] )
         bfs(ga,i,visited);
}
main()
{
   int visited[VTXNUM + 1];
   gragh * ga;
   if((ga = (gragh *)malloc(sizeof(gragh))) == NULL )/* 申请存储图的空间 */
        {
           printf("overflow!");
        exit(0);
        }
   crt_gragh(ga);
   traver(ga, visited);
   free(ga);
}

[ 此贴被kangtalc在2006-08-12 21:32重新编辑 ]

四. 网的最小生成树(prim算法)

描述:一个图每条边上都有权值,找一个拥有最小权值的生成树出来.一般采用prim算法
prim算法我就不说了,很好懂的,请参考《数据结构》一书,书上有详细的算法描述

输入:先输入各个结点的名称,然后输入边的信息,注意文件头部定义的VTXNUM和EDGE的数值,分别表示你要输入的结点的个数和输入边的条数,你要在原文件自行的修改这两个数值,可能有人问为什么能在程序中提示输入,主要是我不想用动态数组的缘故.还请大家见谅.言归正传.
比如一个图有6个结点,10条边,那么请你将在原文件VTXNUM后面的数值改为6,将EDGE的数值改为10.(和上面深度优先搜索输入的方式一样)

如图表示:


假设图的结点为a,b,c,d,e,f这6个结点,ab,ac,ad,bc,be,cd,cf,ce,df,ef这10条边,相应的边的权值分别为6,1,5,5,3,5,4,6,2,6那么请你在程序运行的时候输入abcdefa b 6a c 1a d 5b c 5b e 3c d 5c f 4c e 6d f 2e f 6回车
也就是先输入这6个点然后不加空格输入a b 6然后又不加空格输入a c 1...
回车后的结果会告诉最小的权值边为:
a     c
c     f
f     d
c     b
b     e

结果如图表示:

原代码如下:

Copy code

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

#define MAXVAL 32767/* 定义边权值的最大值 */
#define VTXNUM 6 /* 结点数目 */
#define EDGE 10/* 边的条数 */
#define TRUE 1
#define FALSE 0

/* 结点类型 */
typedef struct vertex
{
   char ch;
}vertex;

/* 弧类型，adj为弧权值 */
typedef struct arc
{
   int adj;
}arc;

/* 图的类型，用邻接矩阵表示 */
typedef struct graph
{
   vertex vexs[VTXNUM + 1];
   arc arcs[VTXNUM + 1][VTXNUM + 1];
}gragh;

/* 有关权值最小的边的信息结构 */
typedef struct edge
{
   int lowcost;/* 存储当前结点关联的所有边最小的权值，为0时表示此结点并入集合U */
   int vex;/* 存储该边依附于U集合中的顶点标号 */
}edge;



/* 结点定位函数，输入一结点返回结点在邻接矩阵中的标号 */
int LOCVERTEX(gragh * ga, vertex v)
{
   int i;
   for (i=1; i<=VTXNUM; i++)
       if (v.ch == ga->vexs[i].ch)
           break;
           if(i > VTXNUM)
               return 0;
               else return i;
}

/* 建立图的函数 */
void crt_gragh(gragh * ga)
{
   int i;
   char c;
   int j;
   int k;
   vertex v1, v2;
   int w;
   for( i = 1; i <= VTXNUM; i++)
   {
       scanf("%c",&c);
       ga->vexs[i].ch = c;
   }
   for(i = 1;i <= VTXNUM; i++)
      for(j = 1; j <= VTXNUM; j++)
        ga->arcs[i][j].adj = MAXVAL;/* 置每条边的权值为允许的最大值 */

   for( k = 1; k <= EDGE; k++ )
   {
    scanf("%c %c %d", &(v1.ch), &(v2.ch), &w);
    i = LOCVERTEX( ga, v1);
    j = LOCVERTEX( ga, v2);
    ga->arcs[i][j].adj = w;
    ga->arcs[j][i].adj = w;
   }
}

/* 本算法核心函数，以v0出发构造网ga的最小生成树 */
void prim(gragh *ga, int u0,edge closedge[])
{
   int i;
   int j;
   int k;

   for (i=1; i<=VTXNUM; i++)/* 初始化辅助数组closedge */
   {
       if (i != u0)
           {
               closedge[i].vex = u0;
               closedge[i].lowcost = ga->arcs[u0][i].adj;
           }
   }
   
   closedge[u0].lowcost = 0;/* 将v0并入U集合 */

   for (i=1; i<=VTXNUM-1; i++)/* 选出n-1条最小权值的边 */
   {
       k = minicost(closedge);/* 求得V-U集合外有最小权值边依附的结点标号 */
       printf("%c %c\n", ga->vexs[closedge[k].vex].ch, ga->vexs[k].ch);/* 输出此最小权值边依附的两个结点 */
       closedge[k].lowcost = 0;/* 将选出的结点并入U集合 */

       for (j=1; j<=VTXNUM; j++)/* 修改有关边的信息 */
       {
           if (ga->arcs[k][j].adj < closedge[j].lowcost)
               {
                   closedge[j].lowcost = ga->arcs[k][j].adj;
                   closedge[j].vex = k;
               }
       }

   }/* 在新的顶点并入U集合之后，重新选择具有最小代价的边 */
}

/* 选出V-U集合中最小权值边依附的结点标号 */
int minicost(edge closedge[])
{
   int i;
   int k;
   int minval = MAXVAL;

   for (i=1; i<=VTXNUM; i++)
   {
       if ((closedge[i].lowcost < minval) && (closedge[i].lowcost > 0))
           {
              minval = closedge[i].lowcost;
              k = i;
           }

   }

   return k;
}

main()
{
   gragh * ga;
   edge closedge[VTXNUM+1];/* 辅助数组 */

   if ((ga = (gragh *)malloc(sizeof(gragh))) == NULL)
        {
           printf("overflow!");
        exit(0);
        }

   crt_gragh(ga);
   prim(ga, 1, closedge);

   free(ga);
}

[ 此贴被kangtalc在2006-08-12 21:33重新编辑 ]

五. 拓扑排序
相信大家对拓扑排序还是比较熟悉了吧,其实就是个次序先后的问题,还不了解拓扑排序的同学请参阅相关的书籍并了解起算法

本次第一次用邻接表作为图的存储结构,并且存储的是有向图(无向图怎么可能有拓扑排序?呵呵)

输入:如果这个有向图有6个顶点,并且有8条边,那么请将程序开头的VTXNUM的数值改为6,将EDGE的数值改为8

如下图所示的图的输入的格式为a ba ca dc bc ed ef df e
a b的意思是a到b有边,如果a到c有边,同样输入a c,注意a ba c中的ba之间不要有空格



那么按照拓扑排序的规则,程序应该输出
f       a           c         b         d         e
如图:


原代码如下:

Copy code

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

#define VTXNUM 6/* 顶点个数 */
#define TRUE 1
#define FALSE 0
#define EDGE 8/* 边的条数 */

/* 弧接点类型 */
typedef struct arcnode
{
   int adjvex;/* 弧尾顶点 */
   struct arcnode *nextarc;/* 有相同弧尾的下一个弧结点 */
}arcnode;

/*图顶点结点结构类型*/
typedef struct vexnode
{
   char vexdata;/* 顶点数据 */
   int indegree;/* 顶点入度 */
   arcnode *firstarc;/* 以此顶点为弧尾的第一条边 */
}vexnode;

/* 顶点定位函数 */
int LOCVERTEX(vexnode dig[], char v)
{
   int i;
   for (i=1; i<=VTXNUM; i++)
       if (dig[i].vexdata == v)
           break;

   if (i > VTXNUM)
       return 0;
   else
       return i;
}

/* 以邻接表为存储结构创建图 */
void crt_adjlist(vexnode dig[])
{
   int i;
   char v1;
   char v2;
   int vex1;
   int vex2;
   arcnode *p;
   dig[0].vexdata = 'a'-1;

   for (i=1; i<=VTXNUM; i++)
   {
       dig[i].indegree = 0;
       dig[i].firstarc = NULL;
       dig[i].vexdata = dig[i-1].vexdata + 1;
   }

   for (i=1; i<=EDGE; i++)
   {
       scanf("%c %c", &v1, &v2);

       vex1 = LOCVERTEX(dig, v1);
       vex2 = LOCVERTEX(dig, v2);

       if ((p = (arcnode*)malloc(sizeof(arcnode))) == NULL)
           {
               printf("overflow");
               exit(0);
           }

           p->adjvex = vex2;
           p->nextarc = dig[vex1].firstarc;
        dig[vex1].firstarc = p;
        dig[vex2].indegree++;
   }
}

/* 初始化栈 */
void init(int *top)
{
   *top = 0;
}

/* 压入元素入栈 */
void push(int *top, int v, vexnode dig[])
{
   dig[v].indegree = *top;
   *top = v;
}

/* 元素出栈 */
int pop(int *top, vexnode dig[])
{
   int j = *top;
   *top = dig[*top].indegree;
   return j;
}

/* 判栈空函数 */
int empty(int *top)
{
   if ( !(*top) )
       return TRUE;
   else
       return FALSE;
}

/* 拓扑排序算法
* 设D是有n个顶点，e条弧的有向图
* dig是D的邻接表的表头向量，
* 若有向图中无回路，
* 则拓扑排序完成
* 返回函数值为“true”
* 否则返回值为false
*/
int topsort(vexnode dig[])
{
   int x = 0;
   int *top = &x;
   int i;
   int j;
   int k;
   int m;
   arcnode *q;
   crt_adjlist(dig);/* 建立邻接表dig */
   init(top);/* 栈初始化 */

   /* 建入度为0的顶点栈 */
   for (i=1; i<=VTXNUM; i++)
   {
       if (dig[i].indegree == 0)
           push(top, i, dig);
   }

   m = 0;/* m为记数器，计输出顶点数 */

   while( !empty(top) )
   {
       j = pop(top, dig);
       printf("%c\t",dig[j].vexdata);
       m++;/* 输出顶点vj并且记数 */
       q = dig[j].firstarc;/* q指示以vj为尾的第一条弧结点 */
       while (q != NULL)
       {
           k = q->adjvex;/* 顶点vk为vj的直接后继 */
           dig[k].indegree--;
           if ( dig[k].indegree == 0 )
               push(top, k, dig);/* 新的入度为0的顶点入栈 */
               q = q->nextarc;
       }
   }

   if (m < VTXNUM)
       return FALSE;
   else
       return TRUE;
}

main()
{
   vexnode dig[VTXNUM+1];
   int result;
   result = topsort(dig);
   if (result)
       printf("\nsuccessful\n");
   else
       printf("\nfail\n");
}

[ 此贴被kangtalc在2006-08-12 21:34重新编辑 ]

六. AOE网关键路径求解算法
关键路径是解决AOE网的工程最快完成时间的问题,还不了解关键路径求法的同学请参阅相关的书籍并了解起算法

用邻接表作为图的存储结构,并且存储的是有向图

输入:如果这个有向图有6个顶点,并且有8条边,那么请将程序开头的VTXNUM的数值改为6,将EDGE的数值改为8

如下图所示的图的输入的格式为a b 3a c 2b e 3b d 2c d 4c f 3d f 2e f 1



a b 3的意思是a到b有边,并且权值为3,如果a到c有边权值为2,同样输入a c 2,注意a b 3a c 2中的3a之间不要有空格

那么按照拓扑排序的规则,程序应该输出
f     a       c       b       d       e
如图:


原代码如下:

Copy code

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

#define VTXNUM 6/* 顶点个数 */
#define EDGE 8/* 边的条数 */
#define TRUE 1
#define FALSE 0

/* 弧结点类型 */
typedef struct arcnode
{
   int adjvex;/* 弧尾顶点 */
   int info;/* 弧的权值 */
   struct arcnode *nextarc;/* 有相同弧尾的下一个弧结点 */
}arcnode;

/*图顶点结点结构类型*/
typedef struct vexnode
{
   char vexdata;/* 顶点数据 */
   int indegree;/* 顶点入度 */
   arcnode *firstarc;/* 以此顶点为弧尾的第一条边 */
}vexnode;

/* 顶点定位函数 */
int LOCVERTEX(vexnode dig[], char v)
{
   int i;
   for (i=1; i<=VTXNUM; i++)
       if (dig[i].vexdata == v)
           break;

   if (i > VTXNUM)
       return 0;
   else
       return i;
}

/* 以邻接表为存储结构创建图 */
void crt_adjlist(vexnode dig[])
{
   int i;
   char v1;
   char v2;
   int vex1;
   int vex2;
   int value;
   arcnode *p;
   dig[0].vexdata = 'a'-1;

   for (i=1; i<=VTXNUM; i++)
   {
       dig[i].indegree = 0;
       dig[i].firstarc = NULL;
       dig[i].vexdata = dig[i-1].vexdata + 1;
   }

   for (i=1; i<=EDGE; i++)
   {
       scanf("%c %c %d", &v1, &v2, &value);

       vex1 = LOCVERTEX(dig, v1);
       vex2 = LOCVERTEX(dig, v2);

       if ((p = (arcnode*)malloc(sizeof(arcnode))) == NULL)
           {
               printf("overflow");
               exit(0);
           }

           p->adjvex = vex2;
           p->info = value;
           p->nextarc = dig[vex1].firstarc;
        dig[vex1].firstarc = p;
        dig[vex2].indegree++;
   }
}

/* 初始化栈 */
void init(int *top)
{
   *top = 0;
}

/* 压入元素入栈 */
void push(int *top, int v, vexnode dig[])
{
   dig[v].indegree = *top;
   *top = v;
}

/* 元素出栈 */
int pop(int *top, vexnode dig[])
{
   int j = *top;
   *top = dig[*top].indegree;
   return j;
}

/* 判栈空函数 */
int empty(int *top)
{
   if ( !(*top) )
       return TRUE;
   else
       return FALSE;
}

/* 返回顶点i到顶点j之间弧的权值 */
int weight(int i, int j,vexnode dig[])
{
   arcnode *p;
   int val;
   int k;
   p = dig[i].firstarc;
   while(p != NULL)
   {
       k = p->adjvex;
       if(k == j)
           return p->info;
       p = p->nextarc;
   }
   return 0;
}

/* 对有向网进行拓扑排序，
* 求得个顶点事件的最早发生时间ve值
* top1和top2为栈顶指针
* 建入度为0的顶点栈top1
* 建存储拓扑有序序列的栈指针top2
*/
int toporder(vexnode dig[], int ve[], int *top1, int *top2)
{
   int i;
   int j;
   int k;
   int m = 0;
   arcnode *q;
   init(top1);
   init(top2);

   for (i=1; i<=VTXNUM; i++)
   {
       if (dig[i].indegree == 0)
           push(top1, i, dig);/* 入度为0的顶点入栈 */
           ve[i] = 0;/* 初始化ve值为0 */
   }

   while ( !empty(top1) )
   {
       j = pop(top1, dig);
       push(top2, j, dig);
       m++;

       q = dig[j].firstarc;
       while (q != NULL)
       {
           k = q->adjvex;
           dig[k].indegree--;
           if (dig[k].indegree == 0)
               push(top1, k, dig);

           if ((ve[j]+weight(j, k, dig)) > ve[k])
               ve[k] = ve[j] + weight(j, k, dig);

           q = q->nextarc;
       }
   }

   if (m < VTXNUM)
       return FALSE;
   else
       return TRUE;
}

/* 设dig[1...n]为含有n个顶点，e条边的有向图的邻接表
* 本算法输出该有向图中各项关键活动
*/
void critical_path(vexnode dig[], int ve[], int vl[], int *top1, int *top2)
{
   int i;
   int j;
   int k;
   arcnode *q;
   int ee;
   int el;

   crt_adjlist(dig);/* 用邻接表建立有向图 */
   if ( !toporder(dig, ve, top1, top2) )
       {
           printf("Has a cycle");
           exit(1);
       }
   else
       {
           for (i=1; i<=VTXNUM; i++)
               vl[i] = ve[VTXNUM];/* 初始化顶点最迟发生时间 */

           /* 逆拓扑有序求各顶点的vl值 */
           while ( !empty(top2) )
           {
               j = pop(top2, dig);
               q = dig[j].firstarc;

               while (q != NULL)
               {
                   k = q->adjvex;
                   if (vl[k]-weight(j, k ,dig) < vl[j])
                       vl[j] = vl[k] - weight(j, k, dig);
                   q = q->nextarc;
               }
           }

           /* 求ee，el和关键活动 */
           for (i=1; i<=VTXNUM; i++)
           {
               q = dig[i].firstarc;
               while (q != NULL)
               {
                   k = q->adjvex;
                   ee = ve[i];
                   el = vl[k]-weight(i, k, dig);
                   if (ee == el)
                       printf("%c   %c\n",dig[i].vexdata, dig[k].vexdata);/* 输出关键活动 */
                   q = q->nextarc;
               }
           }
       }
}

main()
{
int x = 0;
int y = 0;
int *top1 = &x;
int *top2 = &y;
vexnode dig[VTXNUM+1];
int ve[VTXNUM+1];
int vl[VTXNUM+1];
critical_path(dig, ve, vl, top1, top2);
}

[ 此贴被kangtalc在2006-08-12 21:36重新编辑 ]

七:最短路径迪杰斯特拉算法(单一源点各个终点最短路径)

描述:给定带权的有向图D和源点v,求v到D中其余各顶点的最短路径(权值之和最小的路径)



如上图所示的图可知,a到b没有路径,a到c的最短路径为ac,a到d的最短路径为aed,a到e的最短路径为ae,a到f的最短路径为aedf

输入:先输入各个结点的名称,然后输入边的信息,注意文件头部定义的VTXNUM和EDGE的数值,分别表示你要输入的结点的个数和输入边的条数,你要在原文件自行的修改这两个数值,
如上面那个图有6个结点,8条边,那么请你将在原文件VTXNUM后面的数值改为6,将EDGE的数值改为8

假设图的结点为a,b,c,d,e,f,这6个结点,ac,ae,af,bc,cd,df,ef,ed这8条边,权值依次为100,10,30,5,50,10,60,20,那么请你在程序运行的时候输入abcdefa f 100 a c 10 a e 30 b c 5 c d 50 d f 10 e f 60 e d 20 a回车(最后的这个a代表从a源点出发到其余各个顶点)
也就是先输入这6个点然后不加空格输入a f 100然后空格输入b e 1...当输入完最后一条弧e d 20时再空一格输入源点a

结果如下:


原代码如下:

Copy code

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define VTXNUM 6/* 顶点个数 */
#define EDGE 8/* 弧的条数 */
#define MAX 1000/* 弧权的最大值 */
#define TRUE 1
#define FALSE 0

/* 顶点结点类型 */
typedef struct vertex
{
   char ch;
}vertex;

/* 弧结点类型，adj为权值 */
typedef struct arc
{
   int adj;
}arc;

/* 以邻接矩阵存储图的信息 */
typedef struct graph
{
   vertex vexs[VTXNUM + 1];
   arc arcs[VTXNUM + 1][VTXNUM + 1];
}gragh;

/* 源点到顶点的最短路径 */
typedef struct set
{
   char shortest[VTXNUM+1];
}set;



/* 以邻接矩阵建立图，输入顶点以及边的权值 */
void
crt_gragh(gragh * ga)
{
   int i;
   char c;
   int j;
   int k;
   vertex v1,v2;
int w;
   for( i = 1; i <= VTXNUM; i++)
   {
       scanf("%c",&c);
       ga->vexs[i].ch = c;
   }
   for(i = 1;i <= VTXNUM; i++)
      for(j = 1; j <= VTXNUM; j++)
        ga->arcs[i][j].adj = MAX;/* 如果顶点i到顶点j没有相邻，弧ij的权值为MAX*/

   for( k = 1; k <= EDGE; k++ )
   {
    scanf("%c %c %d ", &(v1.ch), &(v2.ch), &w);
    i = LOCVERTEX( ga, v1);
    j = LOCVERTEX( ga, v2);
    ga->arcs[i][j].adj = w;
   }
}

int LOCVERTEX(gragh * ga, vertex v)
{
   int i;
   for (i=1; i<=VTXNUM; i++)
       if (v.ch == ga->vexs[i].ch)
           break;
           if(i > VTXNUM)
               return 0;
               else return i;
}

/* 修改当前最短路径的函数 */
void changepath(set path[], int strSrc,int strDest, gragh *ga)
{
   int k = strlen(path[strSrc].shortest);
   strcpy(path[strDest].shortest, path[strSrc].shortest);
   path[strDest].shortest[k] = ga->vexs[strDest].ch;
   path[strDest].shortest[k+1] = '\0';
}

/* 本节核心算法，迪杰斯特拉算法
* ga为有带权有向图的邻接矩阵，v0为指定的源点
* path[1...VTXNUM]将存储始点到个终点的最短路径
* dist存储相应的路径长度，max是计算机允许的最大值
*/
void dijkstra(gragh *ga, vertex v, int dist[], set path[],int s[])
{
   int i;
   int j;
   int k;
   int wm;
   int v0 = LOCVERTEX(ga, v);/* 确定源点在图中的位置 */

   for (i=1; i<=VTXNUM; i++)
   {
       dist[i] = ga->arcs[v0][i].adj;/* 初始化源点到个路径的最段长度 */
       if (dist[i] < MAX)/* 如果源点到一些点相邻，那么这些相邻的顶点的最短路径就被确定了 */
           {
               path[i].shortest[0] = ga->vexs[v0].ch;
               path[i].shortest[1] = ga->vexs[i].ch;
               path[i].shortest[2] = '\0';
           }
       else
           {
               path[i].shortest[0] = '\0';/* 和源点不相邻的顶点的路径还没有，初始化为0 */
           }
    }
       for (i=1; i<=VTXNUM; i++)
           s[i] = 0;
           s[v0] = 1;/* s为存储已经找到最短路径的顶点集，1表示在这个集合中，0表示没在这个集合中 */

       for (k=1; k<=VTXNUM-1; k++)
       {
           wm = MAX;
           j = v0;/* j初始化为源点 */

           /* 找出最小的dist[i]，然后将这个顶点归并入集合s */
           for (i=1; i<=VTXNUM; i++)
           {
               if ( !s[i] && (dist[i] < wm) )
                   {
                       j = i;
                       wm = dist[i];
                   }
           }
           s[j] = 1;

           for (i=1; i<=VTXNUM; i++)
           {
               if( !s[i] && (dist[j]+ga->arcs[j][i].adj < dist[i]) )
                   {
                       dist[i] = dist[j]+ga->arcs[j][i].adj;/* 修改dist[i] */
                       changepath(path, j, i, ga);/* 修改源点到终点的最短路径 */
                   }
           }
       }
}

main()
{
   gragh * ga;
   int i;
   int dist[VTXNUM+1];
   set path[VTXNUM+1];
   int s[VTXNUM+1];
   vertex v;
   if ((ga = (gragh *)malloc(sizeof(gragh))) == NULL )
        {
           printf("overflow!");
        exit(0);
        }
   crt_gragh(ga);
   scanf("%c", &(v.ch));
   dijkstra(ga, v, dist, path, s);
   for (i=1; i<=VTXNUM; i++)
   {
       printf("the shortest path of %c is %s, \tweight is %d\n", ga->vexs[i].ch, path[i].shortest, dist[i]);
   }
   free(ga);
   ga = NULL;
}

[ 此贴被kangtalc在2006-08-12 21:37重新编辑 ]

八.有向带权图任何两个顶点的最短路径(弗洛依德算法)

描述:其实可以用迪杰斯特拉算法做,不过代码复杂不容易理解.弗洛依德提出的这个算法很容易理解和读懂,并且复杂度和迪杰斯特拉算法的复杂度一样.



如上图所示的图可知,a到b的最短路径为ab,a到c的最短路径为abc,b到a的最短路径为bca,b到c的最短路径为bc,c到a的最短路径为ca,c到b的最短路径为cab

输入:先输入各个结点的名称,然后输入边的信息,注意文件头部定义的VTXNUM和EDGE的数值,分别表示你要输入的结点的个数和输入边的条数,你要在原文件自行的修改这两个数值,
如上面那个图有3个结点,5条边,那么请你将在原文件VTXNUM后面的数值改为3,将EDGE的数值改为5

如上图的结点为a,b,c这3个结点,ab,ba,ac,ca,bc这5条边,权值依次为4,6,11,3,2,那么请你在程序运行的时候输入abca b 4b a 6a c 11c a 3b c 2回车
a b 4的意思是a到b有边,并且权值为4,注意a b 4b a 6中的4b之间不要有空格

程序运行结果如下:



原代码如下:

Copy code

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define VTXNUM 3/* 顶点个数 */
#define MAX 1000/* 弧的最大权值 */
#define EDGE 5

/* 顶点结构类型 */
typedef struct vertex
{
  char ch;
}vertex;

/* 弧结构类型 */
typedef struct arc
{
  int adj;
}arc;

/* 图结构类型，以邻接矩阵存储图 */
typedef struct graph
{
  vertex vexs[VTXNUM + 1];
  arc arcs[VTXNUM + 1][VTXNUM + 1];
}gragh;

/* 存储最短路径 */
typedef struct set
{
  char shortest[VTXNUM+1];
}set;


typedef struct pathinfo
{
  int length[VTXNUM+1][VTXNUM+1];
  set path[VTXNUM+1][VTXNUM+1];
}pathinfo;

/* 以邻接矩阵建立图的函数 */
void
crt_gragh(gragh * ga)
{
  int i;
  char c;
  int j;
  int k;
  vertex v1,v2;
int w;
  for( i = 1; i <= VTXNUM; i++)
  {
    scanf("%c",&c);
    ga->vexs[i].ch = c;
  }
  for(i = 1;i <= VTXNUM; i++)
    for(j = 1; j <= VTXNUM; j++)
      {
        if( i!= j)
          ga->arcs[i][j].adj = MAX;
        else
            ga->arcs[i][j].adj = 0;
      }

  for( k = 1; k <= EDGE; k++ )
  {
    scanf("%c %c %d", &(v1.ch), &(v2.ch), &w);
    i = LOCVERTEX( ga, v1);
    j = LOCVERTEX( ga, v2);
    ga->arcs[i][j].adj = w;
  }
}

/* 顶点定位函数 */
int LOCVERTEX(gragh * ga, vertex v)
{
  int i;
  for (i=1; i<=VTXNUM; i++)
    if (v.ch == ga->vexs[i].ch)
        break;
        if(i > VTXNUM)
          return 0;
          else return i;
}

/* 最短路径变更函数 */
void changepath(pathinfo *pa, int i,int j, int k)
{
  int len = strlen(pa->path[i][k].shortest);
  strcpy(pa->path[i][j].shortest, pa->path[i][k].shortest);
  pa->path[i][j].shortest[len-1] = '\0';
strcat(pa->path[i][j].shortest, pa->path[k][j].shortest);
}


/* 本节的核心函数
* 弗洛依德算法
* ga为带权有向图的邻接矩阵
* pa->length[i,j]为从i到j的最短路径的长度
* pa->path[i,j]为相应的最短路径
*/
void floyd(gragh *ga, pathinfo *pa)
{
  int i;
  int j;
  int k;
  for (i=1; i<=VTXNUM; i++)
    for (j=1; j<=VTXNUM; j++)
    {
        pa->length[i][j] = ga->arcs[i][j].adj;
        if ((pa->length[i][j]<MAX) && (pa->length[i][j]!= 0))
          {
              pa->path[i][j].shortest[0] = ga->vexs[i].ch;
            pa->path[i][j].shortest[1] = ga->vexs[j].ch;
            pa->path[i][j].shortest[2] = '\0';
          }
      else
          {
            pa->path[i][j].shortest[0] = '\0';
          }
    }

    for (k=1; k<=VTXNUM; k++)
        for (i=1; i<=VTXNUM; i++)
          for (j=1; j<=VTXNUM; j++)
          {
            if ( (pa->length[i][k]+pa->length[k][j]) < pa->length[i][j])
                {
                  pa->length[i][j] = pa->length[i][k] + pa->length[k][j];
                  changepath(pa, i, j, k);
                }
          }
}

main()
{
  gragh * ga;
  int i;
  int j;
  pathinfo *pa;
  if ((ga = (gragh *)malloc(sizeof(gragh))) == NULL )
      {
        printf("overflow!");
      exit(0);
      }

  if ((pa = (pathinfo *)malloc(sizeof(pathinfo))) == NULL )
      {
        printf("overflow!");
      exit(0);
      }
     
  crt_gragh(ga);
  floyd(ga, pa);
  for (i=1; i<=VTXNUM; i++)
    for(j=1; j<=VTXNUM; j++)
        {
          if(i != j)
            printf("the shortest path of %c to %c is %s\n", ga->vexs[i].ch, ga->vexs[j].ch, pa->path[i][j].shortest);
        }
  free(pa);
  free(ga);
  ga = NULL;
  pa = NULL;
}

九.静态查找(次优二叉查找树的建立)

描述:次优二叉查找树是一种静态的查找树,和最优二叉查找树的效率几乎一样,并且算法比最优二叉查找树的简单得很多,最优二叉查找树是指带权路径长度最之和最小的查找树,如果还不知道什么是二叉查找树的同学请参阅《数据结构》一书.

如果有N个结点来构成这棵树,那么请你在原程序中将VTXNUM后面的值改为N,比如我给的例子是有9个结点来构造,所以VTXNUM后面的数值为9

程序中输入N个数据,每一个数据表示一个结点的权值,如给出的例子:ABCDEFGHI的权值依次为 1,1,2,5,3,4,4,3,5那么请你在程序中输入1回车1回车....5回车,一共输入VTXNUM那么多个数据

接着是程序将会打印出先序和中序遍历这棵次优二叉查找树的接点顺序
结果如下

Copy code

原代码:
#include<stdio.h>
#include<stdlib.h>

#define VTXNUM 9 /* 结点个数 */
#define TRUE 1
#define FALSE 0

typedef char keytype;/* 键值类型 */

/* 含关键字的有序表元素类型 */
typedef struct rectype
{
  keytype key;/* 关键字 */
  int weight;/* 权值 */
}rectype;

/* 树结点类型 */
typedef struct bnodetp
{
  rectype data;
  struct bnodetp *lchild;
  struct bnodetp *rchild;
}bnodetp;

/* 建立次优二叉查找树
* 由序列r[l...h]构造次优二叉查找树
* t为树的根结点
* 累积权值和存放在sw[0...n]中,sw[0] = 0
*/
bnodetp * sndoptimal(bnodetp *t, rectype r[], int sw[], int l, int h)
{
  int i;
  int j;
  int min = sw[h] - sw[l-1];
  int dw = sw[h] + sw[l-1];
  i = l;

  /* 选△pi取最小值的i */
  for (j=l; j<=h; j++)
    {
      if (dw-sw[j]-sw[j-1] >= 0)
          {
        if ((dw-sw[j]-sw[j-1]) < min)
        {
          i = j;
          min = dw - sw[j] - sw[j-1];
        }
          }
      else
        if ( -(dw-sw[j]-sw[j-1]) < min)
        {
          i = j;
          min = dw - sw[j] - sw[j-1];
        }
    }

  /* 申请结点空间 */
  if ((t=(bnodetp *)malloc(sizeof(bnodetp))) == NULL)
    {
        printf("overflow!\n");
        exit(1);
    }
    t->data = r[i];

    if (i==l)
        t->lchild = NULL;/* 如果选出的i是最左边的结点,令其左链域为空 */
    else
        t->lchild = sndoptimal(t->lchild, r, sw, l, i-1);/* 要不然以根结点的左链域为根结点继续构造二叉树*/

    if (i==h)
        t->rchild = NULL;/* 如果选出的i是最右边的结点,令其右链域为空 */
    else
        t->rchild = sndoptimal(t->rchild, r, sw, i+1, h);/* 要不然以根结点的右链域为根结点继续构造二叉树*/
    return t;
}

void PreOrderTraverse(bnodetp *root)/* 先序遍历次优二叉查找树 */
{
  if(root != NULL)
    {
        printf("%c ",root->data.key);
        PreOrderTraverse(root->lchild);
    PreOrderTraverse(root->rchild);
    }
}

void MidOrderTraverse(bnodetp *root)/* 先序遍历次优二叉查找树 */
{
  if(root != NULL)
    {
        MidOrderTraverse(root->lchild);
        printf("%c ",root->data.key);
    MidOrderTraverse(root->rchild);
    }
}

main()
{
  int i;
  rectype r[VTXNUM+1];/* 有序结点数组 */
  int sw[VTXNUM+1];/* 累计权值数组 */
  bnodetp *root = NULL;/* 根结点 */
  int h = VTXNUM;
  r[0].key = 'a' - 1;
  sw[0] = 0;

  for (i=1; i<=VTXNUM; i++)
  {
    r[i].key = r[i-1].key + 1;
    scanf("%d", &(r[i].weight));
    sw[i] = sw[i-1] + r[i].weight;
  }

    root = sndoptimal(root, r, sw, 1, h);
    printf("Previous Order is:");
    PreOrderTraverse(root);
    printf("\n");
    printf("Middle Order is:");
    MidOrderTraverse(root);
    printf("\n");
    free(root);
}

十.动态查找(二叉排序树的建立,查找,删除,遍历)

描述:二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
(1)   若他的左子树不空,则左子树上的所有结点的值都小于它的根结点的值
(2)   若它的右子树不空,则右子树上的所有结点的值都大于它的根结点的值
(3)   它的左右子树也分别是二叉排序树

二叉排序树之所以是动态的查找树,主要是因为在查找的过程中如果没有此结点,就直接在树上插入此结点,所以是动态查找

输入:如果有N个结点来构成这棵树,那么请你在原程序中将VTXNUM后面的值改为N,比如我给的例子是有10个结点来构造,所以VTXNUM后面的数值为10

直接输入10个值表示要插入的关键字的值:比如45,12,53,3,37,100,34,61,90,78,100
那么构成的二叉树如下
s.GIF

运行结果:
sort_tree1.GIF

原代码:

Copy code

#include <stdio.h>

#define TRUE 1
#define FALSE 0
#define VTXNUM 10         /* 输入的结点个数 */

/* 树结点类型 */
typedef struct node
{
   int key;             /* 关键字*/
   struct node *lchild;     /* 指向左子树的指针 */
   struct node *rchild;     /* 指向右子树的指针 */
}node;



/* 在根指针为bst的二叉排序树上查找关键字等于k的接点
* 若存在，则found为真
* 并且返回指向该结点的指针
* 否则found为假
* 返回指向查找路径上最后一个结点的指针
* f初始值为NULL
*/
node* srch_bstree(node **f, node *bst, int k, int *found)
{
   if (bst == NULL)                     /* 树为空表示没找到 */
       {
           *found = FALSE;
           return *f;
       }
   else if (bst->key == k)                 /* 树的根即是所查找的结点 */
       {
           *found = TRUE;
           return bst;
       }
   else if (bst->key < k)                 /* 如果查找的值小于当前结点的值 */
       {
           *f = bst;
           return srch_bstree(f, bst->rchild, k, found);/* 继续在左子树上进行查找 */
       }
   else if (bst->key >k)                   /* 如果超找的值大于当前结点的值 */
       {
           *f = bst;
           return srch_bstree(f, bst->lchild, k, found);/* 继续在右子树上进行查找 */
       }
}

/* 在根指针为bst的二叉排序树上插入关键字为k的结点
* 若为空，则插入结点为新的根结点
* 否则根据k小于或则大于结点F中的关键字而插入为F的左子树或则右子树的根
*/
node * ins_bstree(node **f, node *bst, int k)
{
   node *s;
   if ((s=(node *)malloc(sizeof(node))) == NULL)   /* 申请新的结点 */
       {
           printf("overflow!\n");
           exit(1);
       }
   s->key = k;
   s->lchild = s->rchild = NULL;               /* 初始化该结点 */
   if (bst == NULL)                       /* 如果树空就将此结点作为根 */
       bst = s;
   else if (k < (*f)->key)                     /* 如果键值小于最后访问的结点 */
       (*f)->lchild = s;                       /* 将此结点作为F的左子树 */
   else if (k > (*f)->key)
       (*f)->rchild = s;                       /* 否则为右子树 */
   return bst;                           /* 返回根结点 */
}

/* 在根指针为bst的二叉排序树上删除结点p
*/
void del_bstree(node *bst, node **f,node *p)
{
   node *q, *s;
   if (p == bst)                                 /* 如果删除的结点为根结点 */
       {
           if (p->lchild == NULL && p->rchild == NULL)           /* 当根结点无左右子树时 */
               {
                   free(bst);                             /* 直接删除此结点 */
                bst = NULL;
               }
           else if (p->lchild != NULL && p->rchild == NULL)       /* 如果根结点只有左子树没有右子树 */
               {
                   s = bst;
                   bst = p->lchild;                         /* 将根结点的左子树根作为新的根结点 */
                   free(s);
               }
           else if (p->lchild == NULL && p->rchild != NULL)       /* 如果根结点只有左子树没有右子树 */
               {
                   s = bst;
                   bst = p->rchild;                         /* 将根结点的左子树根作为新的根结点 */
                   free(s);
               }
           else if (p->lchild != NULL && p->rchild != NULL)       /* 如果根结点有左右子树 */
               {
                   q = p;
                   s = p->lchild;
                   while (s->rchild != NULL)                   /* 找到p的直接前继s */
                   {
                       q = s;
                       s = s->rchild;
                   }
                   p->key = s->key;                         /* 令s代替p */
                   if (p != q)
                       q->rchild = s->lchild;
                   else
                       p->lchild = s->lchild;                     /* q = p时，s为p的左小孩 */
                   free(s);
               }
       }
   else                                       /* 如果删除的不是根结点，以下方法同是根结点类似的方法处理 */
       {
           if (p->lchild == NULL && p->rchild == NULL)
               {
                   if (p == (*f)->lchild)
                       {
                           (*f)->lchild = NULL;
                           free(p);
                       }
                   else if (p == (*f)->rchild)
                       {
                           (*f)->rchild = NULL;
                           free(p);
                       }
               }
               else if (p->lchild != NULL && p->rchild == NULL)
                   {
                       if (p == (*f)->lchild)
                           {
                               (*f)->lchild = p->lchild;
                               free(p);
                           }
                       else if (p == (*f)->rchild)
                        {
                            (*f)->rchild = p->lchild;
                            free(p);
                        }
                   }
               else if (p->lchild == NULL && p->rchild != NULL)
                   {
                       if (p == (*f)->lchild)
                           {
                               (*f)->lchild = p->rchild;
                               free(p);
                           }
                       else if (p == (*f)->rchild)
                        {
                            (*f)->rchild = p->rchild;
                            free(p);
                        }
                   }
               else if (p->lchild != NULL && p->rchild != NULL)
                   {
                       q = p;
                    s = p->lchild;
                       while (s->rchild != NULL)
                       {
                           q = s;
                           s = s->rchild;
                       }
                       p->key = s->key;
                       if (p != q)
                           q->rchild = s->lchild;
                       else
                           p->lchild = s->lchild;

                       free(s);
                   }
       }
}

void InOrderTraverse(node *root)/* 中序遍历次优二叉查找树 */
{
   if(root != NULL)
       {

           InOrderTraverse(root->lchild);
           printf("%d\t",root->key);
           InOrderTraverse(root->rchild);
       }
}

main()
{
   node *bst = NULL;
   node **f = NULL;
   node *p = NULL;
   int state = FALSE;
   int *found = &state;
   int k;
   int i;
   int delkey;
   if ((f = (node **)malloc(sizeof(node *))) == NULL)
       {
           printf("overflow!");
           exit(1);
       }
   *f = NULL;
   for(i=1; i<=VTXNUM; i++)
   {
       scanf("%d",&k);                                 /* 输入各个关键字 */
       *f = srch_bstree(f, bst, k, found);                   /* 查找该结点是否存在 */
       if(*found)                                   /* 如果存在，打印此结点 */
           printf("yes, found it! the key is %d\n", bst->key);
       else
           bst = ins_bstree(f, bst, k);                       /* 不存在就插入该结点 */
       *found = FALSE;
       *f = NULL;
   }
   InOrderTraverse(bst);                             /* 中序遍历该二叉排序树 */
   for(i=0; i<2; i++)
   {
       printf("\nPlease input the key you want to delete:");        
    scanf("%d", &delkey);                             /* 输入要删除的结点键值 */
    p = srch_bstree(f, bst, delkey, found);                 /* 查找该结点是否在树中 */
    if (*found)                                     /* 如果在就删除它并且打中序遍历新的树 */
       {
      del_bstree(bst, f, p);
      InOrderTraverse(bst);
      printf("\n");
    }
    else
           printf("the key is not exsit! So I can delete nothing!\n");                   /* 不在的话打印出不能删除的信息 */
   }
   free(f);
   f = NULL;
}

[ 此贴被kangtalc在2006-08-16 22:29重新编辑 ]

十一.平衡二叉树

描述:平衡二叉树或者是一棵空树,或者是具有下列性质的二叉树:
(1)   平衡二叉树是一棵二叉排序树
(2)   它的左右子树也分别是平衡二叉树
(3)   左子树和右子树的深度之差不超过1

二叉树上的结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度,可见平衡二叉树的所有结点的平衡因子只能是0,-1,1.如果是其他的数值就不平衡

输入:如果有N个结点来构成这棵树,那么请你在原程序中将VTXNUM后面的值改为N,比如我给的例子是有5个结点来构造,所以VTXNUM后面的数值为5

直接依次输入5个值表示要插入的关键字的值:比如 13, 24, 37, 90, 53

那么构成的二叉树如下
avl.JPG

先序遍历此平衡二叉树的次序为: 24, 13, 53, 37, 90

结果如下:
avl1.JPG

原代码如下:

Copy code

#include<stdio.h>

#define TRUE 1
#define FALSE 0
#define VTXNUM 5

/* 树结点结构类型 */
typedef struct node
{
  int bf;
  int key;
  struct node *lchild;
  struct node *rchild;
}node;

/* 先序遍历次优二叉查找树 */
void PreOrderTraverse(node *root)
{
  if(root != NULL)
    {

        printf("%d\t",root->key);
        PreOrderTraverse(root->lchild);
        PreOrderTraverse(root->rchild);
    }
}


/* 在根为t的平衡二叉树上插入键为k的新结点 s*/
node *ins_AVLtree(node *t, int k)
{
  int d;
  int balanced = TRUE;
  node *f = NULL;                   /* 记录离插入结点最近的且平衡因子不为0的结点的双亲结点 */
  node *p = t;
  node *q = NULL;                   /* 记录要插入结点的双亲结点 */
  node *a = t;                     /* 记录离插入结点最近的切平衡因子不为0的结点 */
  node *s = NULL;                   /* 要插入的结点 */
  node *b = NULL;                   /* 记录a的子结点 */
  node *c = NULL;                   /* */
  if ((s=(node *)malloc(sizeof(node))) == NULL)
    {
        printf("overflow!");
        exit(1);
    }

  s->bf = 0;
  s->key = k;
  s->lchild = s->rchild = NULL;

  if (t == NULL)                   /* 如果树空就将插入的结点作为根结点 */
    t = s;
  else
    {
        while (p != NULL)
        {
          if (p->bf != 0)
            {
                a = p;
                f = q;
            }
          q = p;
          if (k < p->key)
            p = p->lchild;
          else
            p = p->rchild;
        }                             /* 找到要插入的位置q */
      if (k < q->key)                   /* 将s插入为q的左子树或者右子树 */
        q->lchild = s;
      else
        q->rchild = s;


      /* 记录a 结点平衡因子的改变量为d */
      if (k < a->key)
        {
          p = a->lchild;
          b = p;
          d = 1;
        }
      else
        {
            p = a->rchild;
            b = p;
            d = -1;
          }


    /* 修改a到s路径上各个结点的平衡因子值 */
        while (p != s)
        {
          if (k < p->key)
            {
                p->bf = 1;
                p = p->lchild;
            }
          else
            {
                p->bf = -1;
                p = p->rchild;
            }
        }

          /* 如果a结点还是平衡的只修改a结点的平衡因子 */
          if (a->bf == 0)
            a->bf = d;
          else if ((a->bf+d) == 0)
            a->bf = 0;

          /* 如果a不平衡 */
          else
            {
                balanced = FALSE;               /* 表示树不平衡 */
                if (d == 1)
                {
                    if(b->bf == 1)             /* 是LL型 */
                    {
                      a->lchild = b->rchild;
                      b->rchild = a;
                      a->bf = 0;
                      b->bf = 0;
                    }
                    else if (b->bf == -1)         /* 是LR型 */
                      {
                        c = b->rchild;
                        a->lchild = c->rchild;
                        b->rchild = c->lchild;
                        if (c->bf == 1)
                            {
                              a->bf = -1;
                              b->bf = 0;
                            }
                        else if (c->bf == -1)
                            {
                              a->bf = 0;
                              b->bf = 1;
                            }
                        else if (c->bf == 0)
                            {
                              a->bf = 0;
                              b->bf = 0;
                        }
                        c->bf = 0;
                        b = c;
                    }
                }
              else if (d == -1)
                {
                    if (b->bf == -1)                 /* 是RR型 */
                      {
                        a->rchild = b->lchild;
                        b->lchild = a;
                        a->bf = 0;
                        b->bf = 0;
                      }
                    else if (b->bf == 1)               /* 是RL型 */
                      {
                        c = b->lchild;
                        a->rchild = c->lchild;
                        b->lchild = c->rchild;
                        c->lchild = a;
                        c->rchild = b;
                        if (c->bf == 1)
                            {
                              a->bf = 0;
                              b->bf = -1;
                            }
                        else if (c->bf == -1)
                            {
                              a->bf = 1;
                              b->bf = 0;
                            }
                        else if (c->bf == 0)
                            {
                              a->bf = 0;
                              b->bf = 0;
                            }
                        c->bf = 0;
                        b = c;
                      }
                }
          }

          if ( !balanced )                     /* 修改a原来a结点的双亲结点f的指针域 */
              {
                if (f == NULL)
                  t = b;
                else if (f->lchild == a)
                  f->lchild = b;
                else if (f->rchild == a)
                  f->rchild = b;
              }
    }
    return t;
}

main()
{
  int i;
  int k;
  node *root = NULL;

  for (i=1; i<= VTXNUM; i++)
  {
    scanf("%d", &k);
    root = ins_AVLtree(root, k);
  }
  printf("PreOrderTraveres the tree:");
  PreOrderTraverse(root);
  printf("\n");
  free(root);
}