大数据结构实验报告材料.docx
- 文档编号:770544
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:37
- 大小:569.34KB
大数据结构实验报告材料.docx
《大数据结构实验报告材料.docx》由会员分享,可在线阅读,更多相关《大数据结构实验报告材料.docx(37页珍藏版)》请在冰点文库上搜索。
大数据结构实验报告材料
实验报告手册
课程名称:
数据结构指导教师:
专业:
计算机科学与技术20年—20年第学期
姓名:
学号:
年级:
级班级:
实验报告内容
实验题目:
线性表及其应用
实验目的:
掌握线性表的定义,掌握不同存储结构及基本运算
实验要求:
实现约瑟夫(Joseph)问题描述:
约瑟夫(Joseph)问题描述为:
编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,从第s个人开始从1报数,数到第m的人出列;然后从它在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。
设计一个程序求出列顺序。
实验器材:
计算机
实验电路图/程序流程图:
(1)利用链表
(2)利用数组
实验步骤/程序源代码:
//利用链表
#include
#include
#include
typedefintElemType;
typedefstructSingleNode
{
ElemTypedata;
structSingleNode*next;
}SLL,*LinkList;
intmain()
{
SLL*head,*use,*temp;
inti,n,m,k,a=0;
printf("请输入总人数n:
");
scanf("%d",&n);
printf("从第m个人开始数起,请输入m:
");
scanf("%d",&m);
printf("数到第k个人,该人出列,请输入k:
");
scanf("%d",&k);
head=use=(SLL*)malloc(sizeof(SLL));//建立链表,形成链表头
head->data=1;
for(i=2;i<=n;i++)//形成其余的n-1个
{
use->next=(SLL*)malloc(sizeof(SLL));
use=use->next;
use->data=i;//第i个置编号i
}
use->next=head;//末首相连,形成环
printf("人员序号为:
");//输出人员的序号
temp=head;
for(i=0;i { printf("%d",temp->data); temp=temp->next; } printf("\n"); for(i=0;i { use=use->next; } printf("人员出列顺序为: "); while(n){ for(i=1;i use=use->next; temp=use->next;//temp指向第k个 use->next=temp->next;//第k个从环中脱钩 printf("%d",temp->data); free(temp);//释放第k个表元占用的空间 n--; } printf("\n"); return0; } //利用数组 #include #include intmain() { inti,k,m,n,num[50],*p; printf("输入总人数n: n="); scanf("%d",&n); p=num; for(i=0;i *(p+i)=i+1;//从1到n给每个人编号 i=0;//i为每次循环时计数变量 k=0;//k为按1,2,3报数时的计数变量 m=0;//m为退出时的人数 while(m { if(*(p+i)! =0)k++; if(k==3) { printf("出局人序号: %d\n",*(p+i)); *(p+i)=0;//将退出时的人的编号置为0 k=0;//k报道3后,重置为0 m++;//退出时的人数加1 } i++; if(i==n)i=0;//报数到n后,i恢复为0 } while(*p==0)p++;//如果p指向的值等于0,就执行p++让它指向下一个元素,直到不为0 printf("留下的人的编号是: %d\n",*p);//p指向的编号就是最后留下来的人 system("pause"); } 实验结果分析: (1)利用链表 (2)利用数组 实验日期: 2017年9月8日 成绩评定: □优秀(100-90分) □良好(89-80分) □中等(79-70分) □及格(69-60分) □不及格(60-0分) 教师签名: 年月日 实验报告内容 实验题目: 栈和队列及其应用 实验目的: 掌握栈和队列的定义、存储结构及基本运算,理解栈与递归的应用 实验要求: 设计一个程序,演示用算符优先法对算术表达式求值的过程。 实验器材: 计算机 实验电路图/程序流程图: 实验步骤/程序源代码: #include #include #include #defineNULL0 #defineOK1 #defineERROR-1 #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT20 /*定义字符类型栈*/ typedefstruct{ intstacksize; char*base; char*top; }Stack; /*定义整型栈*/ typedefstruct{ intstacksize; int*base; int*top; }Stack2; /*-----------------全局变量---------------*/ StackOPTR;/*定义运算符栈*/ Stack2OPND;/*定义操作数栈*/ charexpr[255]="";/*存放表达式串*/ char*ptr=expr; intInitStack(Stack*s)//构造运算符栈 { s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); if(! s->base)returnERROR; s->top=s->base; s->stacksize=STACK_INIT_SIZE; returnOK; } intInitStack2(Stack2*s)//构造操作数栈 { s->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(! s->base)returnERROR; s->stacksize=STACK_INIT_SIZE; s->top=s->base; returnOK; } intIn(charch)//判断字符是否是运算符,运算符即返回1 { return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'); } intPush(Stack*s,charch)//运算符栈插入ch为新的栈顶元素 { *s->top=ch; s->top++; return0; } intPush2(Stack2*s,intch)//操作数栈插入ch为新的栈顶元素 { *s->top=ch; s->top++; return0; } charPop(Stack*s)//删除运算符栈s的栈顶元素,用p返回其值 { charp; s->top--; p=*s->top; returnp; } intPop2(Stack2*s)//删除操作数栈s的栈顶元素,用p返回其值 { intp; s->top--; p=*s->top; returnp; } charGetTop(Stacks)//用p返回运算符栈s的栈顶元素 { charp=*(s.top-1); returnp; } intGetTop2(Stack2s)//用p返回操作数栈s的栈顶元素 { intp=*(s.top-1); returnp; } /*判断运算符优先权,返回优先权高的*/ charPrecede(charc1,charc2) { inti=0,j=0; staticchararray[49]={ '>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','! ', '>','>','>','>','! ','>','>', '<','<','<','<','<','! ','='}; switch(c1) { /*i为下面array的横标*/ case'+': i=0;break; case'-': i=1;break; case'*': i=2;break; case'/': i=3;break; case'(': i=4;break; case')': i=5;break; case'#': i=6;break; } switch(c2) { /*j为下面array的纵标*/ case'+': j=0;break; case'-': j=1;break; case'*': j=2;break; case'/': j=3;break; case'(': j=4;break; case')': j=5;break; case'#': j=6;break; } return(array[7*i+j]);/*返回运算符*/ } /*操作函数*/ intOperate(inta,charop,intb) { switch(op) { case'+': return(a+b); case'-': return(a-b); case'*': return(a*b); case'/': return(a/b); } return0; } intnum(intn)//返回操作数的长度 { charp[10]; itoa(n,p,10);//把整型转换成字符串型 n=strlen(p); returnn; } intEvalExpr()//主要操作函数 { charc,theta,x;intn,m; inta,b; c=*ptr++; while(c! ='#'||GetTop(OPTR)! ='#') { if(! In(c)) {if(! In(*(ptr-1)))ptr=ptr-1; m=atoi(ptr);//取字符串前面的数字段 n=num(m); Push2(&OPND,m); ptr=ptr+n; c=*ptr++; } else switch(Precede(GetTop(OPTR),c)) { case'<': Push(&OPTR,c); c=*ptr++; break; case'=': x=Pop(&OPTR); c=*ptr++; break; case'>': theta=Pop(&OPTR); b=Pop2(&OPND);a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b)); break; } } returnGetTop2(OPND); } intmain() { printf("请输入正确的表达式以'#'结尾: "); do{ gets(expr); }while(! *expr); InitStack(&OPTR);/*初始化运算符栈*/ Push(&OPTR,'#');/*将#压入运算符栈*/ InitStack2(&OPND);/*初始化操作数栈*/ printf("表达式结果为: %d\n",EvalExpr()); return0; } 实验结果分析: 实验日期: 2017年9月22日 成绩评定: □优秀(100-90分) □良好(89-80分) □中等(79-70分) □及格(69-60分) □不及格(60-0分) 教师签名: 年月日 实验报告内容 实验题目: 串及其应用 实验目的: 掌握串的应用 实验要求: 试写一统计某文本中某些字符串的出现次数和位置。 涉及到串的模式匹配算法。 实验器材: 计算机 实验电路图/程序流程图: 实验步骤/程序源代码: #include #include intmain() { chara[80]="abcdefghab\0"; charch; inti,m,b[80]; intflag=0; printf("请输入要查找的子串"); ch=getchar();//获取一个字符 m=strlen(a);//统计主串的长度 for(i=0;i if(a[i]==ch){//找到了,直接判断是否相等 b[flag]=i+1;//记录位置 flag+=1; } } if(flag==0)printf("主串中没有这个子串"); else{ printf("出现的次数: %d\n",flag); for(i=0;i printf("出现过的位置: %d",b[i]); } printf("\n"); } return0; } 实验结果分析: 实验日期: 2017年10月20日 成绩评定: □优秀(100-90分) □良好(89-80分) □中等(79-70分) □及格(69-60分) □不及格(60-0分) 教师签名: 年月日 实验报告内容 实验题目: 图及其应用 实验目的: 掌握树和图在实际中的应用 实验要求: 设计一个校园导游程序,为来访的客人提供各种信息查询服务。 运用图的存储结构,和最短路径知识来解决。 实验器材: 计算机 实验电路图/程序流程图: 实验步骤/程序源代码: #include #include #defineINT_MAX10000//定义符号常量 #definen10//定义符号常量 /*定义全局变量*/ intcost[n][n];//边的值 intshortest[n][n];//两点间的最短距离 intpath[n][n];//经过的景点 /*自定义函数原型说明*/ voidintroduce(); intshortestdistance(); voidfloyed(); voiddisplay(inti,intj);//个人分工 (1)景点信息查询2)两景点的最短距离3)两个景点之间的路径 intmain() {/*主函数*/ inti,j; chark; for(i=0;i<=n;i++) for(j=0;j<=n;j++) cost[i][j]=INT_MAX; cost[1][2]=cost[2][1]=300; cost[2][3]=cost[3][2]=100; cost[3][4]=cost[4][3]=2000; cost[3][5]=cost[5][3]=60; cost[1][5]=cost[5][1]=45; cost[2][5]=cost[5][2]=40; cost[4][5]=cost[5][4]=30; cost[1][4]=cost[4][1]=150; cost[4][5]=cost[5][4]=1500; cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; while (1) { printf("\n\t\t\t********欢迎使用哈师大校园导游程序*********\n"); printf("\t\t\t1.景点最短路径查询…请按s键\n"); printf("\t\t\t2.退出系统……………请按e键\n"); printf("\n\t\t\t**************下面是景点列表*************\n"); printf("\t\t\t\t1.行知楼\n"); printf("\t\t\t\t2.崇师楼\n"); printf("\t\t\t\t3.图书馆\n"); printf("\t\t\t\t4.理工楼\n"); printf("\t\t\t\t5.体育馆\n"); printf("\t\t\t\t请选择服务: \n"); scanf("\n%c",&k); switch(k) { case's': printf("进入最短路径查询: "); shortestdistance(); break; case'e': exit(0); default: printf("输入信息错误! \n请输入字母s或e.\n"); break; } } }/*main*/ voidintroduce() {/*景点介绍*/ inta; printf("请输入想查询的景点编号: "); scanf("%d",&a); getchar(); printf("\n"); switch(a) { case1: printf("行知楼: 学校主楼,各行政办公室所在处,学校日常事务办公点,师大的标志性建筑。 建筑中西结合,行知楼背后为每届毕业班照相处。 \n\n");break; case2: printf("崇师楼: 为红白四方环形建筑,外观华美。 共六层,分A、B、C、D四区,教学重地。 \n\n");break; case3: printf("图书馆: 学校的标志湖泊,分一为三。 有情人桥伫立其上,荷花,黑天鹅在下。 \n\n");break; case4: printf("理工楼: 位于路,分为理工一、李工二、理工三三栋楼,主要为理工科学生上课重地。 \n\n");break; case5: printf("体育馆: 是师大全校最大设施最先进齐全的运动馆,平时各类室内体育比赛都在这里进行。 \n\n");break; default: printf("景点编号输入错误! 请输入1->5的数字编号! \n\n");break; } }/*introduce*/ intshortestdistance() {/*要查找的两景点的最短距离*/ inti,j; printf("请输入要查询的两个景点的编号(1->5的数字编号并用'-'间隔): "); scanf("%d-%d",&i,&j); if(i>n||i<=0||j>n||j<0) { printf("输入信息错误! \n\n"); printf("请输入要查询的两个景点的编号(1->5的数字编号并用','间隔): \n"); scanf("%d,%d",&i,&j); } else { floyed(); display(i,j); } return1; }/*shortestdistance*/ voidfloyed() {/*用floyed算法求两个景点的最短路径*/ inti,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { shortest[i][j]=cost[i][j]; path[i][j]=0; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) {/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/ shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; } }/*floyed*/ voiddisplay(inti,intj) { /*打印两个景点的路径及最短距离*/ inta,b; a=i; b=j; printf("您要查询的两景点间最短路径是: \n\n"); if(shortest[i][j]! =INT_MAX) { i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 材料