暨南大学本科实验报告专用纸
课程名称数据结构实验成绩评定
实验项目名称习题3.16 3.18 4.13 4.16 指导教师孙世良
实验项目编号实验4 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005
学院电气信息学院系专业软件工程
实验时间年月日午～月日午温度℃湿度(一)实验目的
掌握栈和队列这两种抽象数据结构类型的特性，并能在相应的应用问题中正确选用它们。
掌握栈类型的实现方法，即两种储存结构表示时的基本操作实现算法。
熟悉串的七种基本操作定义，并能利用这些基本操作实现串的其他各种操作的方法。
熟练掌握在串的定长顺序储存结构上实现串的各种操作的方法。
了解串操作的应用方法和特点。
(二)实验内容和要求
3.16火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）
等待调度，试编写算法，输出对这节车厢进行调度的操作（即入账或出栈操作）序列，以使所有的软席车厢都被调到硬席车厢之前。
3.18试写一个判别表达式中开、闭括号是否配对出现的算法。
4.13编写算法，从串s中删除所有和串t相同的子串。
4.16编写算法，实现串的基本操作StrCompare(S,T)。
(三)主要仪器设备
实验环境：Microsoft Visual Studio 2012
(四)源程序
3.16程序：
#include
#include
#include
void Switch(char *rs, char *S){ int i,k,len;
strcpy(rs,"\0");
k=0;
len=strlen(S);
for(i=0;iif(S[i] =='S')
strcat(rs,"IO");
else{
strcat(rs,"I");
k++;
}
while(k>0){
k--;
strcat(rs,"O");
}
}
int main()
{
char Queue[20];
char rs[40];
scanf("%s",Queue);
Switch(rs,Queue);
puts(rs);
return 0;
}
3.18程序：
#include
int main()
{
char queue[20],x;
int i=0;
while((x=getchar())!=EOF){ if(x == '(')
i++;
else
if(x == ')')
i--;
if(i<0){
printf("error\n");
return 0;
}
}
printf("right\n");
return 0;
}
4.13程序：
#include
#include
int main()
{
char s[20];
scanf("%s",s);
char t[20];
scanf("%s",t);
for(int i=0;iint k=0,j=i;
for(;kif(s[j]==t[k])
continue;
else
break;
if(k==strlen(t)){
s[i]='\0';
char* str=s+i+k;
strcat(s,str);
i--;
}
}
}
printf("%s",s);
return 0;
}
4.16程序：
#include
#include
int StrCompare(char* s,char*t){ int i;
for(i=0;i<=strlen(s);i++){ if(s[i]==t[i])
continue;
if(s[i]>t[i])
return 1;
if(s[i]return -1;
}
if(i==strlen(s)+1)
return 0;
}
int main()
{
char str1[100],str2[100];
scanf("%s",str1);
scanf("%s",str2);
printf("%d",StrCompare(str1,str2));
return 0;
}
(五)数据调试
3.16调试结果：
3.18调试结果：
4.13调试结果：
4.16调试结果：
(六)实验结果分析与总结
3.16：输入序列“HSHHSS”，其中H代表硬座，S代表软座，输出结果
为“IIOIIIOIOOOO”，其中I代表入站，O代表出站。检验可得该结果正确，程序运行正确。
3.18：输入表达式”34*(35+36)/(1+2)”，判断结果为right；
输入表达式”34*35+36)/(1+2”，判断结果为error。
可见程序运行正确。
4.13：输入串s：6547832783456783，输入串t：783。从串s中删除串t，
得到结果为：6542456。可见程序运行正确。
4.18：输入”abcdefg”和”bcd”比较，程序返回负值；
输入”polont”和”abgek”比较，程序返回正值；
输入”abdc”和”abdc”比较，程序返回0。
可见程序运行正确。
总结：
1 通过本次实验掌握了栈和串的一些基本操作，如构造空的栈，入栈和出栈，返回栈顶元素，删除栈顶元素等；串的定义以及串的建立，计算串的长度，删除子串、比较串的大小以及相关函数的定义与调用。
2 “后进先出”是栈的一个特点，后进栈的元素先进行处理，通常栈用顺序表存储，分配一块连续的存储空存放栈中的元素，并用一个元素指向当前的栈顶。
3 串是一种特殊的线性表，它的每一个结点仅由一个字符组成，因此存储
串的方法也就是存储线性表的一般方法。
