2015级软件工程专业《数据结构与算法》上机题目.doc

1868: 2015级软件班《数据结构与算法》实验1：线性表的应用Description 输入一个字符串，按照字符串的输入顺序创建一个线性表A。线性表A中包含有三类字符：数字字符、字母字符、其他字符。试写一个函数实现对线性表A的拆分，使得线性表A、B、C分别各自指向同一类字符。要求如下： （1）在拆分时，必须使用原表A的结点空间，不能额外创建新结点。 （2）拆分后，原表A指向数字字符，且其内容的前后次序与原表中的前后次序必须一致，新的表B指向字母字符，新的表C指向其他字符。其中要求删除B中的重复结点（如“abbcdexec”，变为“abcdex”）。 （3）判断拆分后的表A是否是中心对称的（如123321或12321都是中心对称的），若是，则输出1，否则输出0。 Input 输入格式要求：输入一行字符串，可以带空格，并以‘？’做为输入结束标志，中间不能输入’？‘。字符串长度不做限制。 如可以输入： 1aabccd2e3f(!3c2g1？ Output 输出格式要求：前3行分别输出表A、B、C的内容（若某个表为空表，则相应行输出-1），第4行输出表A是否为对称的标志。 如输出： 123321 (A的内容) abcdef g (拆分后表B的内容) (! (拆分后表C的内容) 1 (拆分后表A是中心对称的) Sample Input 1aabccd2e3f(!3c2g1? Sample Output 123321 abcdefg (! 1 HINT 为了方便判断线性表是否为中心对称的，可以使用双向链表结构（但不是必须的）。 1869: 2015级软件工程专业《数据结构与算法》实验2：表达式求值 Description 表达式求值是计算机实现程序设计语言中的基本问题之一，也是栈应用的一个典型例子，通过本实验，对输入的一个表达式进行求值。 [实验目的] 掌握栈的应用；掌握算符优先表达式求值的算法；掌握字符串处理和数值的转换。 具体要求如下： （1）表达式以字符串形式输入，并以‘#’结束。如输入：12*（12.4+20.15）/25# （2）运算数可以是实数，运算符有+ - * / ，带括号，可以输入以下4个函数：平方sqr()、正弦sin() 、余弦cos()、四舍五入取整rd()。函数的优先级要高于+ - * /。 （3）对输入的表达式进行计算，计算结果要求必须保留小数点后2位。 （4）能够有效判别表达式的输入格式是否有误（如缺失操作数、括号不匹配、函数名错误等），若输入格式错误，输出为“error！”。 Input 表达式以字符串形式输入，并以‘#’结束，可输入的符号为：数字、小数点、“+ - * /”4个运算符、括号、以及指定的4个函数名，其他符号为非法符号，如出现则意味着输入格式错误。下面是一些输入示例： 12*(12.4+20.15)/25#?????????? ? ?? ? ---格式正确 12.001+(2*5/37#????????????????????? ?? ---格式错误 12*sin(30)+sqr(2.3)#????????????????? ---格式正确 12ab+5#????????????????????????????????? ? ? ---格式错误 12+5-*2 #? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ---格式错误 sin(20)+cosa(30)# ? ? ? ? ? ? ? ? ? ?? ---格式错误 Output 若表达式输入格式正确，则输出计算结果，结果要求必须保留2位小数，如输入：12*(12.4+20.15)/25# ，输出为：15.62。如输出为16或15.624，都为错误。 若表达式输入格式错误，则输出为：error！，如输入：15.4/(2-sin(5.12)*)+21#，输出为：error！。 ? Sample Input 12*(12.4+20.15)/25# Sample Output 15.62 HINT 1. 核心算法用栈结构来实现； 2. 首先需对输入的表达式字符串进行解析，分离出操作数和运算符，在分离过程中，可以对非法的操作数和运算符进行判错。若输入的操作数和运算符正确，则分别入栈； 3. 函数可以看成是单目运算符，即只需一个操作数； 4. 注意函数的优先级要高于其他的运算符，请正确设置运算符优先级表； 5. 在出栈的过程中，可以判别括号匹配和操作数匹配的错误。 1870: 2015级软件工程专业《算法与数据结构》实验3：面向数字图像的Huffman编/译码器的设计与实现 Description “Huffman-树”不仅能对文本数据进行编码、译码，提高文本数据的传输效率，同时它也能对多媒体