哈尔滨师范大学计算机科学与信息工程学院实验报告手册.doc

1、哈尔滨师范大学计算机科学与信息工程学院实验报告手册课程名称：数据结构 指导教师：专业： 物联网工程专业 2017 年2018 年第一学期姓名： 学号：年级： 2016 级 班级： 02 班 实验报告填写及打印要求：1、 A4 纸正反面打印；2、 实验报告封面、封面上填写内容必须打印；3、 实验报告内容，学生可手写也可打印，可根据内容自行加页；4、 指导教师必须手写签名；5、 左侧装订。实验报告内容实验题目：线性表及其应用实验目的：掌握线性表的定义、不同存储结构及基本运算。实验要求： 约瑟夫(Joseph)问题描述为：编号为 1，2，3，n 的 n 个人按顺时针方向围坐一圈，从第 s 个人开始从

2、 1 报数，数到第 m 的人出列；然后从它在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。设计一个程序求出列顺序。实验器材：电脑DEVC+实验步骤/程序源代码：#include#includetypedef struct node/定义节点类型 (单链表的定义结构） int num;/用来对每个节点进行编号标序 struct node *next;/递归定义 LNode,*Linkls; /LNode;/typetef LNode * LinkListvoid create(int m,Linkls head=(LNode*)malloc(sizeof(LNod

3、e); /申请头结点的储存空间head-next =head;/让链表成为一个空的循环链表for(int i=m;i1;i-)if(!(p=(LNode*)malloc(sizeof(LNode)exit(-1);/申请存储空间p-num=i;p-next=head-next;head-next=p;head-num=1;int main()int n,i,m,s=1,j=1;LNode*head,*p,*q;printf(“请输入开始的总人数 n：n“);scanf(“%d“,printf(“请输入从第 s 个开始的 s 值：n“);scanf(“%d“, printf(“请输入 m 的值：

4、n“);scanf(“%d“,/输入数据create(n,head);/产生一个以 head 为头结点，有 n 个元素的循环列表printf(“进行一次删除操作：n“);for(i=1,p=head;inext;while(n-)for(i=1;inext;q=p-next;printf(“第%d 次出局的数：%dn“,j+,q-num);/输出数到得数字，后面进行删除p-next=q-next;p=p-next;free(q);/释放 q 所指向空间system(“pause“);return 0;实验结果分析：实验日期： 2017 年 10 月 23 日成绩评定：优秀（100-90 分）良

5、好（89-80 分）中等（79-70 分）及格（69-60 分）不及格（60-0 分）教师签名：年 月 日实验报告内容实验题目：栈和队列及其应用实验目的：掌握栈和队列的定义、存储结构及基本运算，理解栈与递归的应用。设计一个程序，演示用算符优先法对算术表达式求值的过程。实验要求：为实现算符优先算法求表达式的值，需要建立两个栈，一个是寄存运算符 OPTR，一个是寄存操作数或运算结果 OPND，先初始化栈，然后边扫描表达式边计算。实验器材：电脑DEVC+实验步骤/程序源代码：/*链栈实现表达式求值*/ #includeusing namespace std;const char oper7=+,-,

6、*,/,(,),#;#define OK 1#define ERROR 0#define OVERFLOW -2typedef char SElemType;typedef int Status;typedef struct SNode /链栈的定义格式 int data;struct SNode*next; /SNode 链栈的名字 SNode, *LinkStack;Status InitStack(LinkStack return OK;bool StackEmpty(LinkStack S) /判断链栈是否为空 if(!S)return true;return false;Status

7、 Push(LinkStack if(!p)return OVERFLOW;p-data = e; /插入元素 e p-next = S;S = p;return OK;Status Pop(LinkStack if(!S)return ERROR;e = S-data;p = S;S = S-next;delete p;return OK;Status GetTop(LinkStack return S-data;bool In(char ch) /判断 ch 是否是运算符 for(int i=0;i;char Operate(char first,char theta,char secon

8、d) /计算两数运算结果switch (theta) case +:return (first - 0) + (second - 0) + 48;case -:return (first - 0) - (second - 0) + 48;case *:return (first - 0) * (second - 0) + 48;case /:return (first - 0) / (second - 0) + 48;return 0;char EvaluateExpression() /算术表达式求值的算符优先算法，设 OPTR 和 OPND 分别为运算符栈和操作数栈LinkStack OP

9、TR, OPND;char ch, theta, a, b, x, top;InitStack(OPND); /初始化 OPND 栈InitStack(OPTR); /初始化 OPTR 栈Push(OPTR, #); /将表达式起始符“#”压入 OPTR 栈cin ch;while (ch != # | (GetTop(OPTR) != #) /表达式没有扫描完毕或 OPTR 的栈顶元素不为“#”if (!In(ch) Push(OPND, ch);cin ch; /ch 不是运算符则进 OPND 栈elseswitch (Precede(GetTop(OPTR), ch) /比较 OPTR

10、的栈顶元素和 ch 的优先级case ch; /当前字符 ch 压入 OPTR 栈，读入下一字符 chbreak;case :Pop(OPTR, theta); /弹出 OPTR 栈顶的运算符Pop(OPND, b);Pop(OPND, a); /弹出 OPND 栈顶的两个运算数Push(OPND, Operate(a, theta, b); /将运算结果压入 OPND 栈break;case =: /OPTR 的栈顶元素是“(”且 ch 是“)”Pop(OPTR, x);cin ch; /弹出 OPTR 栈顶的“(”，读入下一字符 chbreak; /switch /whilereturn

11、GetTop(OPND); /OPND 栈顶元素即为表达式求值结果int menu() int c;cout c;return c;int main( )while (1) switch (menu() case 1: cout “请输入要计算的表达式（操作数和结果都在 0-9 的范围内，以#结束）：“ endl;char res = EvaluateExpression();/算法 3.22 表达式求值cout “计算结果为“ res - 48 endl endl;break;case 0:cout “退出成功n“ endl;exit(0);default:break;return 0; 实验结果分析：实验日期： 2017 年 10 月 30 日成绩评定：优秀（100-90 分）良好（89-80 分）中等（79-70 分）及格（69-60 分）不及格（60-0 分）教师签名：年 月 日