数据结构实验报告

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

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

3、izeof(LNode); /申请头结点的储存空间 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,&n); printf(请输入从第s个开始的 s值：n); scanf(%d,&s

4、); printf(请输入m的值：n); scanf(%d,&m);/输入数据 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日成绩评

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

6、per7=+,-,*,/,(,),#;#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 &S) /构造一个空栈 S = NULL; return OK;bool StackEmpty(LinkStack S) /判断链栈是否为空 if(!S)

7、 return true; return false;Status Push(LinkStack &S,SElemType e) / 插入元素e，使之成为栈顶元素 SNode*p=new SNode; if(!p) return OVERFLOW; p-data = e; /插入元素e p-next = S; S = p; return OK;Status Pop(LinkStack &S,SElemType &e) /删除栈顶元素 SNode *p; if(!S) return ERROR; e = S-data; p = S; S = S-next; delete p; return OK

8、;Status GetTop(LinkStack &S) /返回栈顶元素 if(!S) return ERROR; return S-data;bool In(char ch) /判断ch是否是运算符 for(int i=0;i7;i+) if(ch=operi) return true; return false;char Precede(char theta1,char theta2) /判断运算符优先级 if (theta1 = ( & theta2 = ) | (theta1 = # & theta2 = #) return =; else if(theta1 = ( | theta1

9、 = # | theta2 = ( | (theta1 = + | theta1 = -) & (theta2 = * | theta2 = /) return ;char Operate(char first,char theta,char second) /计算两数运算结果 switch (theta) case +: return (first - 0) + (second - 0) + 48; case -: return (first - 0) - (second - 0) + 48; case *: return (first - 0) * (second - 0) + 48; c

10、ase /: return (first - 0) / (second - 0) + 48; return 0;char EvaluateExpression() /算术表达式求值的算符优先算法，设OPTR 和OPND 分别为运算符栈和操作数栈 LinkStack OPTR, OPND; char ch, theta, a, b, x, top; InitStack(OPND); /初始化OPND 栈 InitStack(OPTR); /初始化OPTR 栈 Push(OPTR, #); /将表达式起始符“#”压入OPTR 栈 cin ch; while (ch != # | (GetTop(O

11、PTR) != #) /表达式没有扫描完毕或OPTR 的栈顶元素不为“#” if (!In(ch) Push(OPND, ch); cin ch; /ch 不是运算符则进OPND 栈 else switch (Precede(GetTop(OPTR), ch) /比较OPTR 的栈顶元素和ch 的优先级 case ch; /当前字符ch 压入OPTR 栈，读入下一字符ch break; case : Pop(OPTR, theta); /弹出OPTR 栈顶的运算符 Pop(OPND, b); Pop(OPND, a); /弹出OPND 栈顶的两个运算数 Push(OPND, Operate(a

12、, theta, b); /将运算结果压入OPND 栈 break; case =: /OPTR 的栈顶元素是“(”且ch 是“)” Pop(OPTR, x); cin ch; /弹出OPTR 栈顶的“(”，读入下一字符ch break; /switch /while return GetTop(OPND); /OPND 栈顶元素即为表达式求值结果int menu() int c; cout 0-9 以内的多项式计算 endl; cout 1.计算 endl; cout 0.退出n endl; cout c; return c;int main( ) while (1) switch (men

13、u() 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分） 教师签名：年 月 日实验报告内容

14、实验题目：串及其应用实验目的： 掌握串的存储及模式匹配等应用。试写一统计某文本中某些字符串的出现次数和位置。实验要求： 在主串S中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符要主串S中出现的位置。分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符看其是否相等，相等j下移接着进行比较，不相等i,j下移接着进行比较。实验器材：电脑DEVC+实验步骤/程序源代码：#includeusing namespace std;int BF(string &tag,string &ptn,int pos) int i,j; i=pos; j=0; int tlen=tag.

15、size(); int plen=ptn.size(); while(itlen&jplen-1)couti-plen+1; else cout匹配失败; int main() string tag,ptn; int pos; couttag; coutptn; coutpos; BF(tag,ptn,pos); system(pause); 实验结果分析： 实验日期： 2017年11月6日成绩评定：优秀（100-90分）良好（89-80分）中等（79-70分）及格（69-60分）不及格（60-0分） 教师签名： 年 月 日实验报告内容实验题目：数组和广义表及其应用实验目的：掌握数组存储矩阵的

16、应用并实现矩阵转置操作。试写一程序实现求已知是n阶矩阵的转置矩阵。实验要求：(1) 将矩阵的行列值相互交换；(2) 将每个三元组中的i和j相互调换；(3) 重排三元组之间的次序便可实现矩阵的转置。 实验器材：电脑DEVC+实验步骤/程序源代码：#include#define maxsize 10000typedef structint i,j;int v;trituplenode;typedef structtrituplenode datamaxsize;int m,n,t;tritupletable;void input(tritupletable *a)int i,j,k=0;int x

17、;scanf(%d%d,&a-m,&a-n);for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&x);if(x)a-datak.i=i;a-datak.j=j;a-datak.v=x;k+;a-t=k;void output(tritupletable *a)int i,j,k;for(i=0;im;i+)for(j=0;jn;j+)for(k=0;kt;k+)if(a-datak.i=i&a-datak.j=j) break;if(k=a-t)printf(%5d,0);elseprintf(%5d,a-datak.v);printf(n);void transm

18、atrix(tritupletable *a,tritupletable *b)int p,q,col;b-m=a-n;b-n=a-m;b-t=a-t;q=0;for(col=0;coln;col+)for(p=0;pt;p+)if(a-datap.j=col)b-dataq.i=a-datap.j;b-dataq.j=a-datap.i;b-dataq.v=a-datap.v;+q;Int main()tritupletable A,B;input(&A);output(&A);transmatrix(&A,&B);output(&B);实验结果分析： 实验日期： 2017年11月13日成绩

19、评定：优秀（100-90分）良好（89-80分）中等（79-70分）及格（69-60分）不及格（60-0分） 教师签名： 年 月 日实验报告内容实验题目：树和二叉树及其应用实验目的：掌握树及二叉树的存储及二叉树的遍历的实现。试编写一程序实现树的孩子兄弟存储及先序、中序、后序遍历该二叉树。实验要求： 用二叉链表来存储二叉树，用递归或非递归的方式遍历二叉树。先建立二叉树的存储结构，然后进行遍历。实验器材：电脑DEVC+实验步骤/程序源代码：#include#includeusing namespace std;/建立二叉树的存储结构 typedef struct BiTNode char data

20、; /TElemType是char的数据类型 struct BiTNode*lchild,*rchild;BiTNode,*BiTree;/构造二叉树的顺序存储 void CreatTreeBiTree(BiTree &T) char ch;cin ch;if(ch=#) T=NULL;/递归结束，建空树elseT=new BiTNode;T-data=ch;/生成根结点CreatTreeBiTree(T-lchild);/递归创建左子树CreatTreeBiTree(T-rchild);/递归创建右子树/先序遍历 void PreOrderTraverse(BiTree &T) if(T)

21、coutdata; PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /中序遍历 void InOrderTraverse(BiTree &T) if(T) InOrderTraverse(T-lchild); coutdata; InOrderTraverse(T-rchild); /后续遍历void PostOrderTraverse(BiTree &T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutdata; int main()BiT

22、ree tree;cout请输入建立二叉树的序列：n;cout左子树或又子树为空用“#”表示 n; cout树的存储按照左根右的方式存储 n; CreatTreeBiTree(tree);cout先序遍历的结果为：n;PreOrderTraverse(tree);coutn;cout中序遍历的结果为：n;InOrderTraverse(tree); coutn; cout后序遍历的结果为：n;PostOrderTraverse(tree);coutn;system(pause);coutendl; 实验结果分析： 实验日期： 2017年11月20日成绩评定：优秀（100-90分）良好（89-8

23、0分）中等（79-70分）及格（69-60分）不及格（60-0分） 教师签名： 年 月 日实验报告内容实验题目： 图及其应用实验目的：掌握树和图在实际中的应用。设计一个校园导游程序，为来访的客人提供各种信息查询服务。实验要求： 用图的结构来表示实际的交通网络，图中顶点表示建筑物，边表示楼间的交通联系。先建立图的存储结构，然后用迪杰斯特拉算法求从某个源点到其余各顶点的最短路径。实验器材：电脑DEVC+实验步骤/程序源代码：#include using namespace std;#define MaxInt 32767 #define MVNum 100 typedef char VerTexT

24、ype; typedef int ArcType; int *D=new intMVNum; bool *S=new boolMVNum; int *Path=new intMVNum;typedef struct VerTexType vexsMVNum; ArcType arcsMVNumMVNum; int vexnum,arcnum; AMGraph;int LocateVex(AMGraph G , VerTexType v)for(int i = 0; i G.vexnum; +i)if(G.vexsi = v)return i; return -1;/LocateVexvoid

25、CreateUDN(AMGraph &G) int i , j , k;cout G.vexnum G.arcnum;cout endl;cout 输入点的名称:，如a endl; for(i = 0; i G.vexnum; +i) cout 请输入第 (i+1) G.vexsi; cout endl; for(i = 0; i G.vexnum; +i) for(j = 0; j G.vexnum; +j) G.arcsij = MaxInt; cout 输入边依附的顶点及权值，如a b 7 endl;for(k = 0; k G.arcnum;+k)VerTexType v1 , v2;

26、ArcType w;cout 请输入第 (k + 1) v1 v2 w;i = LocateVex(G, v1); j = LocateVex(G, v2);G.arcsij = w; G.arcsji = G.arcsij;为w /for/CreateUDNvoid ShortestPath_DIJ(AMGraph G, int v0) int v , i , w , min;int n = G.vexnum; for(v = 0; v n; +v) Sv = false; Dv = G.arcsv0v; if(Dv MaxInt) Path v = v0; else Path v = -1

27、; /for Sv0=true; Dv0=0; for(i = 1;i n; +i) min= MaxInt; for(w = 0; w n; +w) if(!Sw & Dw min)v = w; min = Dw;/if Sv=true; for(w = 0;w n; +w) if(!Sw & (Dv + G.arcsvw Dw) Dw = Dv + G.arcsvw; Path w = v; /if /for /ShortestPath_DIJvoid DisplayPath(AMGraph G , int begin ,int temp )if(Pathtemp != -1)Displa

28、yPath(G , begin ,Pathtemp);cout G.vexsPathtemp ;/DisplayPathint main()cout *算法6.10迪杰斯特拉算法* endl endl;AMGraph G; int i , j ,num_start , num_destination;VerTexType start , destination;CreateUDN(G);cout endl;cout *无向网G创建完成！* endl;for(i = 0 ; i G.vexnum ; +i)for(j = 0; j G.vexnum; +j)if(j != G.vexnum -

29、1)if(G.arcsij != MaxInt)cout G.arcsij t;elsecout t;elseif(G.arcsij != MaxInt)cout G.arcsij endl;elsecout endl;/forcout endl;cout start destination;num_start = LocateVex(G , start);num_destination = LocateVex(G , destination);ShortestPath_DIJ(G , num_start);cout endl 最短路径为：;DisplayPath(G , num_start

30、, num_destination);cout G.vexsnum_destinationendl;system(“pause”);实验结果分析： 实验日期： 2017年11月27日成绩评定：优秀（100-90分）良好（89-80分）中等（79-70分）及格（69-60分）不及格（60-0分） 教师签名：年 月 日实验报告内容实验题目：查找及其应用实验目的： 理解树、查找和排序的定义，掌握查找的基本运算。利用二叉排序树实现动态查找。实验要求： 二叉排序树或是一棵空树，或是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。（2）若它的右子树不空，则右子树上

31、所有结点的值均大于它的根结点的值。（3）若它的左、右子树也分别为二叉排序树。先建立二叉排序树的存储结构，然后实现查找。实验器材：电脑DEVC+实验步骤/程序源代码：#includeusing namespace std;#define ENDFLAG#/二叉树的二叉链表存储表示typedef struct ElemType char key;ElemType;typedef struct BSTNodeElemType data;BSTNode *lchild,*rchild;BSTNode,*BSTree;/二叉树的递归查找 BSTree SearchBST(BSTree T,char ke

32、y)if(!T)|key=T-data.key) return T;else if(keydata.key) return SearchBST(T-lchild,key);else return SearchBST(T-rchild ,key);/二叉树的插入 void InsertBST(BSTree &T,ElemType e)if(!T)BSTree S = new BSTNode;S=new BSTNode;S-data=e;S-lchild=S-rchild=NULL;T=S;else if(e.keydata.key) InsertBST(T-lchild,e);else if(e

33、.keyT-data.key) InsertBST(T-rchild,e); /二叉树的创建 void CreatBST(BSTree &T)T=NULL;ElemType e;cine.key;while(e.key!=ENDFLAG)InsertBST(T,e);cine.key; int main()BSTree T;cout请输入若干字符，用回车区分，以#结束输入endl;CreatBST(T);char key;cout请输入待查找字符key;BSTree result=SearchBST(T,key);if(result) cout找到字符keyendl;else cout未找到字符keyendl;实验结果分析： 实验日期： 2017年12月4日