大家都知道数据结构很重要,有助于我们的思维和锻炼我们处理数据的能力,但是我们之中很少有人将其全部实现,一般都是纸上谈兵,或者认为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重新编辑 ]

恩。..要学习STL还是要看其源代码
不过基础的数据结构要熟练掌握。.
这个是语言方面的性能问题