数据结构考研分类复习真题 第四章 答案[22]

[题目分析]本题是对字符串表达式的处理问题首先定义种数据结构符号的类码符号的TOKEN 表示变量名表NAMEL和常量表CONSL这四种数据结构均定义成结构体形式数据部分用一维数组存储同时用指针指出数据的个数算法思想是从左到右扫描表达式对读出的字符先查出其符号类码若是变量或常量就到变量名表和常量表中去查是否已有若无则在相应表中增加之并返回该字符在变量名表或常量表中的下标;若是操作符则去查其符号类码对读出的每个符号均填写其TOKEN表如此下去直到表达式处理完毕先定义各数据结构如下

struct //定义符号类别数据结构

{char data[]; //符号

char code[]; //符号类码

}TYPL;

typedef struct //定义TOKEN的元素

{int typ; //符号码

int addr; //变量常量在名字表中的地址

}cmp;

struct {cmp data[];//定义TOKEN表长度<

int last; //表达式元素个数

}TOKEN;

struct {char data[]; //设变量个数小于个

int last; //名字表变量个数

}NAMEL;

struct {char data[]; //设常量个数小于个

int last; //常量个数

}CONSL;

int operator（char cr）//查符号在类码表中的序号

{for（i=;i<=;i++）

if（TYPLdata[i]==cr） return（i）;

}

void PROCeString（）//从键盘读入字符串表达式（以#结束）输出其TOKEN表示

{NAMELlast=CONSLlast=TOKENlast=; //各表元素个数初始化为

TYPLdata[]=*;TYPLdata[]=+;TYPLdata[]=（;

TYPLdata[]=）; //将操作符存入数组

TYPLcode[]=;TYPLcode[]=;TYPLcode[]=;

TYPLcode[]=; //将符号的类码存入数组

scanf（%c&ch）; //从左到右扫描（读入）表达式

while（ch！=#） //#是表达式结束符

{switch（ch）of

{caseA: case B: case C: //ch是变量

TY=; //变量类码为

for（i=;i<=NAMELlast;i++）

if（NAMELdata[i]==ch）break;//已有该变量i记住其位置

if（i>NAMELlast）{NAMELdata[i]=ch;NAMELlast++;}//变量加入

case: case: case: case: case: case://处理常量

case: case :case: case: TY=;//常量类码为

for（i=;i<=CONSLlast;i++）

if（CONSLdata[i]==ch）break;////已有该常量i记住其位置

if（i>CONSLlast）｛CONSLdata[i]=ch;CONSLlast++;｝//将新常量加入

default: //处理运算符

TY＝operator（ch）;//类码序号

i=\; //填入TOKEN的addr域（期望输出空白）

}//结束switch下面将ch填入TOKEN表

TOKENdata［++TOKENlast］typ=TY;TOKENdata［TOKENlast］addr=i;

scanf（％c&ch）; //读入表达式的下一符号

}//while

}//算法结束

[程序讨论]为便于讨论各一维数组下标均以开始在字符为变量或常量的情况下将其类码用TY记下用i记下其NAMEL表或CONSL表中的位置以便在填TOKEN表时用在运算符（+*（））填入TOKEN表时TOKEN表的addr域没意义为了程序统一这里填入了\本题是表达式处理的简化情况（只有个单字母变量常量只有操作符只个）若是真实情况所用数据结构要相应变化

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []