数据结构第4章 (4)

｝// 算法结束。

11.[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。

void InvertStore(char A[]) //字符串逆序存储的递归算法。 { char ch;

static int i = 0;//需要使用静态变量 scanf (\

if (ch!= '.') //规定'.'是字符串输入结束标志 {InvertStore(A);

A[i++] = ch;//字符串逆序存储 }

A[i] = '\\0'; //字符串结尾标记 }//结束算法InvertStore。

12. 串s'''可以看作由以下两部分组成：'caabcbca...a'和 'ca...a'，设这两部分分别叫串s1和串s2，要设法从s,s' 和s''中得到这两部分，然后使用联接操作联接s1和s2得到s''' 。

i=index(s,s'); //利用串s'求串s1在串s中的起始位置 s1=substr(s,i,length(s) - i + 1); //取出串s1

j=index(s,s''); //求串s''在串s中的起始位置，s串中'bcb'后是'ca...a') s2=substr(s,j+3,length(s) - j - 2); //形成串s2 s3=concat(s1,s2);

13．[题目分析]对读入的字符串的第奇数个字符，直接放在数组前面，对第偶数个字符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中。限于篇幅，这里编写算法，未编程序。

void RearrangeString()

//对字符串改造，将第偶数个字符放在串的后半部分，第奇数个字符前半部分。 {char ch,s[],stk[]; //s和stk是字符数组（表示字符串）和字符栈 int i=1,j; //i和j字符串和字符栈指针 while((ch=getchar())!=’#’)// ’#’是字符串结束标志

s[i++]=ch; //读入字符串

s[i]=’\\0’; //字符数组中字符串结束标志 i=1;j=1;

while(s[i]) //改造字符串

{if(i%2==0) stk[i/2]=s[i]; else s[j++]=s[i]; i++; }//while

i--; i=i/2; //i先从’\\0’后退，是第偶数字符的个数 while(i>0) s[j++]=stk[i--] //将第偶数个字符逆序填入原字符数组

}

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

struct // 定义符号类别数据结构 {char data[7]; //符号

char code[7]； //符号类码 }TYPL；

typedef struct //定义TOKEN的元素 {int typ； //符号码

int addr； //变量、常量在名字表中的地址 }cmp；

struct {cmp data[50]；//定义TOKEN表长度<50 int last； //表达式元素个数

}TOKEN；

struct {char data[15]； //设变量个数小于15个 int last； //名字表变量个数 }NAMEL；

struct {char data[15]； //设常量个数小于15个 int last； //常量个数 }CONSL；

int operator（char cr） //查符号在类码表中的序号 {for（i=3；i<=6；i++）

if（TYPL.data[i]==cr） return（i）； }

void PROCeString（）

//从键盘读入字符串表达式（以‘#’结束），输出其TOKEN表示。

{NAMEL.last=CONSL.last=TOKEN.last=0； //各表元素个数初始化为0 TYPL.data[3]=‘*’；TYPL.data[4]=‘+’；TYPL.data[5]=‘（’； TYPL.data[6]=‘）’； //将操作符存入数组 TYPL.code[3]=‘3’；TYPL.code[4]=‘4’；TYPL.code[5]=‘5’； TYPL.code[6]=‘6’； //将符号的类码存入数组 scanf（“%c”，&ch）； //从左到右扫描（读入）表达式。 while（ch！=‘#’） //‘#’是表达式结束符

{switch（ch）of

{case‘A’: case ‘B’: case ‘C’: //ch是变量

TY=0； //变量类码为0

for（i=1；i<=NAMEL.last；i++）

if（NAMEL.data[i]==ch）break；//已有该变量，i记住其位置

if（i>NAMEL.last）{NAMEL.data[i]=ch；NAMEL.last++；}//变量加入 case‘0’: case‘1’: case‘2’: case‘3’: case‘4’: case‘5’://处理常量 case‘6’: case ‘7’:case‘8’: case‘9’: TY=1；//常量类码为1 for（i=1；i<=CONSL.last；i++）

if（CONSL.data[i]==ch）break；////已有该常量，i记住其位置

if（i>CONSL.last）｛CONSL.data[i]=ch；CONSL.last++；｝//将新常量加入 default: //处理运算符

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

i=’\\0’； //填入TOKEN的addr域（期望输出空白） }//结束switch，下面将ch填入TOKEN表

TOKEN.data［++TOKEN.last］.typ=TY；TOKEN.data［TOKEN.last］.addr=i； scanf（“％c”，&ch）； //读入表达式的下一符号。 }//while }//算法结束

[程序讨论]为便于讨论，各一维数组下标均以1开始，在字符为变量或常量的情况下，将其类码用TY

记下，用i记下其NAMEL表或CONSL表中的位置，以便在填TOKEN表时用。在运算符（‘+’，‘*’，‘（’，‘）’）填入TOKEN表时，TOKEN表的addr域没意义，为了程序统一，这里填入了’\\0’。本题是表达式处理的简化情况（只有3个单字母变量，常量只有0..9，操作符只4个），若是真实情况，所用数据结构要相应变化。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技数据结构第4章 (4)全文阅读和word下载服务。