石 家 庄 铁 道 大 学
实 验 任 务 书
课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院
石 家 庄 铁 道 大 学
14学年—15学年第 2学期 数据结构实验任务书
专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 王明明 实验题目：线性表的基本操作
实验环境： Visual C++ 实验目的：
1、掌握线性表的定义；
2、掌握线性表的基本操作，如建立、查找、插入和删除等。
实验内容：
定义一个包含学生信息（学号，姓名，成绩）的的顺序表或链表，使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息；
(3) 根据姓名进行查找，返回此学生的学号和成绩；
(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。
实验提示：
学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int price; //成绩 }Student;
顺序表的定义
typedef struct { Student *elem; //指向数据元素的基地址
int length; //线性表的当前长度 }SqList；
链表的定义：
typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList;
实验要求：
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。
石 家 庄 铁 道 大 学
14学年—15学年第 2 学期 数据结构实验任务书
专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 李冬梅
实验题目：栈的应用－算术表达式求值
实验环境： Visual C++ 6.0 实验目的：
1．掌握栈的定义及实现；
2．掌握利用栈求解算术表达式的方法。
实验内容：
通过修改完善教材中的算法3.4，利用栈来实现算术表达式求值的算法。对算法3.4中调用的几个函数要给出其实现过程：
(1) 函数In(c)：判断c是否为运算符；
(2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级； (3) 函数Operate(a,theta,b)：对a和b进行二元运算theta。
程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号），便可输出相应的计算结果。如下图：
实验提示：（仅供参考，每个函数的具体实现可以有多种方法，希望有创新）
1.将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序sy2.cpp中包含此头文件（即#include“stack.h”）。 2.表达式求值源程序sy2.cpp的具体实现 (1) 主函数如下： void main() { cout
(2) 函数EvaluateExpreion的实现见算法3.10 (3) 函数In(c)的实现可以采用以下方式：
Status In(SElemType c)// 应在前面有定义typedef char SElemType; { // 判断c是否为运算符 switch(c) { case\'+\':return TRUE; „„//补充完整
default:return FALSE; } } (4) 函数Precede(t1,t2)的实现可以采用以下形式： SElemType Precede(SElemType t1,SElemType t2) { //根据教材表3.1，判断两个运算符的优先关系 SElemType f; switch(t2) { case \'+\': case \'-\':if(t1==\'(\'||t1==\'#\') f=\'\'; break; „„//补充完整 } return f; } (5) 函数Operate(a,theta,b)的实现可以采用以下方式：
SElemType Operate(SElemType a,SElemType theta,SElemType b) { SElemType c; a=a-48; b=b-48; switch(theta) { case\'+\':c=a+b+48; break; „„//补充完整 } return c; }
选做内容1：进一步改进，使表达式的中间值及最终结果不局限于0～9之间的个位数。（如
果完成要在实验报告中注明），如下图：
选做内容2：
将表达式转化成后缀表达式输出，利用后缀表达式求表达式的值并输出。
将中缀表达式转化成后缀表达式存储在队列中，然后利用后缀表达式求表达式的值并输出。
将中缀表达式转化成后缀的思想：
（1）创建一空队列，用来存放后缀表达式，建立并初始化操作符栈OPTR，将表达式起始符“#”压入OPTR栈。
（2）依次读入表达式中每个字符ch，循环执行（3）至（5），直至求出整个表达式转换完毕。
（3）取出OPTR的栈顶元素，当OPTR的栈顶元素和当前读入的字符ch均为“#”时，整个中缀表达式转换完毕。
（4）若ch不是运算符，则进队，读入下一字符ch。
（5）若ch是运算符，则根据OPTR的栈顶元素和ch的优先权比较结果，做不同的处理。
① 若是小于，则ch压入OPTR栈，读入下一字符ch。 ② 若是大于，则弹出OPTR栈顶的运算符，进队。 ③ 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于去掉括号，然后读入下一字符ch。 对后缀表达式进行计算的具体步骤为：
建立一个栈S从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X运算符Y”的形式计算出结果，再压进栈S中。如果后缀表达式未读完，重复执行上面过程，最后输出栈顶的数值即可结束。
实验要求：
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出表达式求值算法的流程图。
