数据结构实验报告Word文件下载.docx
《数据结构实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告Word文件下载.docx（37页珍藏版）》请在冰点文库上搜索。
,&
n）;
从第m个人开始数起，请输入m:
m）;
数到第k个人，该人出列，请输入k:
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;
data=i;
//第i个置编号i
}
next=head;
//末首相连，形成环
人员序号为：
//输出人员的序号
temp=head;
for（i=0;
i<
n;
i++）
%d"
temp->
data）;
temp=temp->
\n"
m-1;
i++）//use指向第m-1个，为了从m位开始数
use=use->
printf（"
人员出列顺序为：
while（n）{
for（i=1;
k;
i++）//掠过k－1个
temp=use->
//temp指向第k个
next=temp->
//第k个从环中脱钩
temp->
free（temp）;
//释放第k个表元占用的空间
n--;
}
return0;
//利用数组
intmain（）
inti,k,m,n,num[50],*p;
输入总人数n：
n="
p=num;
*（p+i）=i+1;
//从1到n给每个人编号
i=0;
//i为每次循环时计数变量
k=0;
//k为按1,2,3报数时的计数变量
m=0;
//m为退出时的人数
while（m<
n-1）//当退出人数比n-1少时执行循环体
if（*（p+i）!
=0）k++;
if（k==3）
出局人序号:
%d\n"
*（p+i））;
*（p+i）=0;
//将退出时的人的编号置为0
//k报道3后，重置为0
m++;
//退出时的人数加1
i++;
if（i==n）i=0;
//报数到n后，i恢复为0
while（*p==0）p++;
//如果p指向的值等于0，就执行p++让它指向下一个元素，直到不为0
留下的人的编号是:
*p）;
//p指向的编号就是最后留下来的人
system（"
pause"
实验结果分析：
（1）利用链表
实验日期：
2017年9月8日
成绩评定：
□优秀（100-90分）
□良好（89-80分）
□中等（79-70分）
□及格（69-60分）
□不及格（60-0分）
教师签名：
年月日
栈和队列及其应用
掌握栈和队列的定义、存储结构及基本运算，理解栈与递归的应用
设计一个程序，演示用算符优先法对算术表达式求值的过程。
计算机
#include<
string.h>
#defineNULL0
#defineOK1
#defineERROR-1
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT20
/*定义字符类型栈*/
typedefstruct{
intstacksize;
char*base;
char*top;
}Stack;
/*定义整型栈*/
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（!
base）returnERROR;
s->
top=s->
base;
stacksize=STACK_INIT_SIZE;
returnOK;
}
intInitStack2（Stack2*s）//构造操作数栈
base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
intIn（charch）//判断字符是否是运算符，运算符即返回1
return（ch=='
+'
||ch=='
-'
*'
/'
（'
）'
#'
intPush（Stack*s,charch）//运算符栈插入ch为新的栈顶元素
*s->
top=ch;
top++;
return0;
intPush2（Stack2*s,intch）//操作数栈插入ch为新的栈顶元素
charPop（Stack*s）//删除运算符栈s的栈顶元素，用p返回其值
charp;
top--;
p=*s->
top;
returnp;
intPop2（Stack2*s）//删除操作数栈s的栈顶元素，用p返回其值
intp;
charGetTop（Stacks）//用p返回运算符栈s的栈顶元素
charp=*（s.top-1）;
intGetTop2（Stack2s）//用p返回操作数栈s的栈顶元素
intp=*（s.top-1）;
/*判断运算符优先权，返回优先权高的*/
charPrecede（charc1,charc2）
inti=0,j=0;
staticchararray[49]={
'
>
'
<
='
!
};
switch（c1）
/*i为下面array的横标*/
case'
:
break;
i=1;
i=2;
i=3;
i=4;
i=5;
i=6;
switch（c2）
/*j为下面array的纵标*/
j=0;
j=1;
j=2;
j=3;
j=4;
j=5;
j=6;
return（array[7*i+j]）;
/*返回运算符*/
/*操作函数*/
intOperate（inta,charop,intb）
switch（op）
return（a+b）;
return（a-b）;
return（a*b）;
return（a/b）;
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）!
）
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））
:
Push（&
OPTR,c）;
x=Pop（&
OPTR）;
theta=Pop（&
b=Pop2（&
OPND）;
a=Pop2（&
OPND,Operate（a,theta,b））;
returnGetTop2（OPND）;
intmain（）
请输入正确的表达式以'
结尾:
do{
gets（expr）;
}while（!
*expr）;
InitStack（&
/*初始化运算符栈*/
OPTR,'
/*将#压入运算符栈*/
InitStack2（&
/*初始化操作数栈*/
表达式结果为:
EvalExpr（））;
2017年9月22日
串及其应用
掌握串的应用
试写一统计某文本中某些字符串的出现次数和位置。
涉及到串的模式匹配算法。
chara[80]="
abcdefghab\0"
charch;
inti,m,b[80];
intflag=0;
请输入要查找的子串"
ch=getchar（）;
//获取一个字符
m=strlen（a）;
//统计主串的长度
for（i=0;
m;
i++）{
if（a[i]==ch）{//找到了，直接判断是否相等
b[flag]=i+1;
//记录位置
flag+=1;
if（flag==0）printf（"
主串中没有这个子串"
else{
printf（"
出现的次数：
flag）;
flag;
i++）{//对位置进行输出，用循环
出现过的位置：
b[i]）;
实验日期：
2017年10月20日
图及其应用
掌握树和图在实际中的应用
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
运用图的存储结构，和最短路径知识来解决。
#include<
process.h>
#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;
=n;
i++）
for（j=0;
j<
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"
\t\t\t2.退出系统……………请按e键\n"
\n\t\t\t**************下面是景点列表*************\n"
\t\t\t\t1.行知楼\n"
\t\t\t\t2.崇师楼\n"
\t\t\t\t3.图书馆\n"
\t\t\t\t4.理工楼\n"
\t\t\t\t5.体育馆\n"
\t\t\t\t请选择服务:
scanf（"
\n%c"
switch（k）
{
case'
s'
printf（"
进入最短路径查询:
shortestdistance（）;
break;
e'
exit（0）;
default:
输入信息错误！
\n请输入字母s或e.\n"
}
}
}/*main*/
voidintroduce（）
{/*景点介绍*/
inta;
printf（"
请输入想查询的景点编号:
scanf（"
a）;
getchar（）;
switch（a）
case1:
行知楼:
学校主楼，各行政办公室所在处，学校日常事务办公点，师大的标志性建筑。
建筑中西结合，行知楼背后为每届毕业班照相处。
\n\n"
case2:
崇师楼：
为红白四方环形建筑，外观华美。
共六层，分A、B、C、D四区，教学重地。
case3:
图书馆：
学校的标志湖泊，分一为三。
有情人桥伫立其上，荷花，黑天鹅在下。
\n\n"
case4:
理工楼：
位于路，分为理工一、李工二、理工三三栋楼，主要为理工科学生上课重地。
case5:
体育馆：
是师大全校最大设施最先进齐全的运动馆，平时各类室内体育比赛都在这里进行。
default:
景点编号输入错误！
请输入1->
5的数字编号！
break;
}/*introduce*/
intshortestdistance（）
{/*要查找的两景点的最短距离*/
请输入要查询的两个景点的编号（1->
5的数字编号并用'
间隔）:
%d-%d"
i,&
j）;
if（i>
n||i<
=0||j>
n||j<
0）
请输入要查询的两个景点的编号（1->
'
%d,%d"
else
floyed（）;
display（i,j）;
}
return1;
}/*shortestdistance*/
voidfloyed（）
{/*用floyed算法求两个景点的最短路径*/
inti,j,k;
for（i=1;
for（j=1;
shortest[i][j]=cost[i][j];
path[i][j]=0;
for（k=1;
k<
k++）
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;
您要查询的两景点间最短路径是:
if（shortest[i][j]!
=INT_MAX）
if（i<
j）
升级会员 