数据结构栈及队列.doc

河南工业大学实验报告
课程 数据结构 _ 实验名称 实验二: 栈和队列的操作
院 系 专业班级 实验地点
姓 名 学 号 实验时间 2011-10-00
指导老师 实验成绩 批改日期
一. 实验目的
1. 熟悉栈和队列的相关概念
2. 掌握栈的顺序存储及相关操作
3. 掌握队列的链式及顺序存储及相关操作
二. 实验内容及要求
1. 利用顺序栈实现栈的判空、判满、入栈、出栈操作
2. 利用带头结点的单链表实现队列的判空、入队、出队操作，或用循环队列实现队列的判空、判满、入队、出队操作
三. 实验过程及结果
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define m 4 //3架飞机
#define n 5 //每架飞机5张票

struct node
{
char name[21];
char id[21];
int seat,plane,date;
node *next,*pre;
};
struct wait
{
char name[21];
char id[21];
char phone[8];
int seat,plane,date,count;
wait *next,*pre;
};
struct piao
{
int seat[n+1];
};

void makenull();
void makenull_piao();
void makenull_information();
void list_menu();
void list_piao();
void makenull_wait();
void list_information();
void plane_information(node *head);
void book();
void add_information(node *head,int x,int y);
void add_wait(int x,int y);
void search_delete(int x);
void write_to_file();
void show_wait();
bool comp(node *x,node*y);

node *head1,*head2,*head3,*q;
wait *wait_head,*wait_end;
char c;
piao a[m];

void main()
{

makenull();
do
{ list_menu();
cout<<endl<<"choose an operation: ";
cin>>c;
if (c!='6')
switch(c)
{
case '0' : show_wait();break;
case '1' : {list_piao();book();}break;
case '2' : search_delete(1);break;
case '3' : list_piao();break;
case '4' : list_information();break;
case '5' : search_delete(0);break;
default : break;
}
}while(c!='6');
cout<<"Exit System ";
}
void makenull()
{
makenull_piao();
makenull_information();
makenull_wait();
}
void list_menu()
{ cout<<endl<<"";
cout<<endl<<" 菜单";
cout<<endl<<" ************************";
cout<<endl<<" * 0 . 查看排队情况 *";
cout<<endl<<" * 1 . 订票 *";
cout<<endl<<" * 2 . 退票 *";
cout<<endl<<" * 3 . 查看剩余票 *";
cout<<endl<<" * 4 . 查看飞机信息 *";
cout<<endl<<" * 5 . 查看乘客信息 *";
cout<<endl<<" * 6 . 退出 *";
cout<<endl<<" ************************";
cout<<endl<<"";
}
void makenull_piao()
{
FILE *fp;
int i;
if((fp=fopen("piao.dat","r")) == NULL )
{
fp=fopen("piao.dat","w");
for (i=1;i<=m-1;i++)
fwrite(&a[i],sizeof(piao),1,fp);
fclose(fp);
fp=fopen("piao.dat","r");
}
for(i=1;i<=m-1;i++)
fread(&a[i],sizeof(piao),1,fp);
fclose(fp);
}
void makenull_information()
{
node *r;
FILE *fp;
int i,j,sum;

sum=a[1].seat[0]+a[2].seat[0]+a[3].seat[0];
fp=fopen("information.dat","r");
head1=new node;
head2=new node;
head3=new node;
head1->pre=NULL;
head1->next=NULL;
head2->pre=NULL;
head2->next=NULL;
head3->pre=NULL;
head3->next=NULL;
q=head1;
for(i=1;i<=sum;i++)
{
j=0;
r=new node;
fread(r,sizeof(node),1,fp);
q->next=r;
r->pre=q;
r->next=NULL;
q=q->next;
fclose(fp);
if(i==a[1].seat[0]+1) {
head2->next=q;
q->pre->next=NULL;
q->pre=head2;
}
if(i==a[1].seat[0]+a[2].seat[0]+1) {
head3->next=q;
q->pre->next=NULL;
q->pre=head3;
}
}
}

void makenull_wait()
{
wait *tempw;
FILE *fp;
tempw=new wait;
int i;
if((fp=fopen("wait.txt","r")) ==NULL )
{
fp=fopen("wait.txt","w");
fclose(fp);
}
wait_end=new wait;
wait_head=new wait;
wait_end->next=NULL;
wait_end->pre=NULL;
wait_head=wait_end;
wait_head->count=0;
fp=fopen("wait.txt","r");
fread(wait_head,sizeof(wait),1,fp);
for(i=1;i<=wait_head->count;i++)
{
fread(tempw,sizeof(wait),1,fp);
wait_end->next=tempw;
tempw->pre=wait_end;
tempw->next=NULL;
wait_end=tempw;
}
}

void list_piao()
{
int i,j;
for(i=1;i<=m-1;i++)
{
if(a[i].seat[0]!=n)
{
cout<<endl<<"第 "<<i<<" 架飞机剩余的票 :"<<endl;
for(j=1;j<=n;j++)
if (a[i].seat[j]==0) cout<<" "<<j;
cout<<endl;
}
else cout<<endl<<"The "<<i<<" plane is full !"<<endl<<endl;
}
}
void list_information()
{
int x;
do {cout<<endl<<"显示哪架飞机的信息 ? "; cin>>x;cout<<endl;}while(x<1 || x>=m);
cout<<endl<<"第 "<<x<<" 架飞机的信息如下 "<<endl;
if(x==1) plane_information(head1);
if(x==2) plane_information(head2);
if(x==3) plane_information(head3);
}

void plane_information(node *head)
{
node *q;
char ch;
int x=0;
if(head!=NULL && head->next!=NULL)
q=head->next;
else {
q=NULL;
cout<<"飞机空,无预订票 !"<<endl;
}
while(q!=NULL)
{
cout<<endl<<"*******************"<<endl;
q->date=q->plane;
cout<<"日期 :"<<q->date<<endl;
cout<<"座位号 : "<<q->seat<<endl;
cout<<"姓名 : "<<q->name;
cout<<endl<<"ID 号 : "<<q->id;
q=q->next;x++;
if (x % 3 ==0) ch=getch();
}
cout<<endl;
}
void book()
{
int i,j,p;
cout<<endl<<"请选择地点：（1、2、3） ";
do {
cin>>i;
if (i<1 || i>=m) {
cout<<endl<<"**** 超出范围！****"<<endl<<"请重新输入：";
}
else
{cout<<endl<<"你要订的是到"<<i<<"地的飞机"<<endl;
cout<<endl<<"第 "<<i<<" 架飞机剩余的票 :"<<endl;
for(p=1;p<=n;p++)
if (a[i].seat[p]==0) cout<<" "<<p;
cout<<endl;
break;}
}while(1);
cout<<endl<<"请选择座位号 : ";
do {
cin>>j;
if (j<1 || j>n) {
cout<<endl<<"**** 超出范围！****"<<endl<<"请重新输入：";
}
else
{
q->date=i;
cout<<endl<<"您的订票日期 : "<<q->date<<endl;
break;
}
}while(1);

if (a[i].seat[j]==0) {
a[i].seat[j]=1;
cout<<endl;
a[i].seat[0]++;
if(i==1) add_information(head1,1,j);
if(i==2) add_information(head2,2,j);
if(i==3) add_information(head3,3,j);
}
else
{
cout<<endl<<"**** 对不起,该座位已被预订，您被安排到订票等候队列 ****"<<endl;
add_wait(i,j);
}

}
void add_wait(int x,int y)
{
wait *tempw;
tempw=new wait;
tempw->next=NULL;
cout<<"请输入个人信息"<<endl;
cout<<endl<<"*************"<<endl;
cout<<"姓名 : ";cin>>tempw->name;
cout<<"ID号 : ";cin>>tempw->id;
cout<<"电话 :";cin>>tempw->phone;
tempw->seat=y;
tempw->plane=x;
wait_end->next=tempw;
tempw->pre=wait_end;
wait_end=wait_end->next;
cout<<endl<<"**** 正在排队等候 ****"<<endl;
wait_head->count++;
write_to_file();
}
void show_wait()
{
wait *tempw;
tempw=wait_head->next;
if (tempw==NULL) cout<<endl<<"排队中没有人！"<<endl;
while(tempw!=NULL)
{
cout<<tempw->name<<" - ";
tempw=tempw->next;
}
}
void add_information(node *head,int x,int y)
{
node *temp;
temp=new node;
temp->pre=NULL;
temp->next=NULL;
cout<<"请输入个人信息"<<endl;
cout<<endl<<"*************"<<endl;
cout<<"姓名 : ";cin>>temp->name;
cout<<"ID号 : ";cin>>temp->id;
temp->seat=y;
temp->plane=x;
temp->next=head->next;
temp->pre=head;
if (head->next!=NULL) head->next->pre=temp;
head->next=temp;
write_to_file();
cout<<endl<<"**** 订票成功 ****"<<endl;
}
void search_delete(int x)
{
node *p,*q,*r;
wait *tempw,*tempw2,*tempw3;
int step=1,t1,t2,i;
char ch;
p=new node;
tempw=new wait;
tempw2=new wait;
tempw3=new wait;
q=head1;
cout<<endl<<"请输入个人信息"<<endl;
cout<<"*************"<<endl;
cout<<endl<<"姓名 : ";cin>>p->name;
do{
q=q->next;
if ( (q!=NULL) &&
(comp(q,p)) )
{
cout<<endl;
q->date=q->plane;
cout<<"Located!"<<endl;
cout<<"****************";
cout<<endl<<"姓名 : "<<q->name;
cout<<endl<<"ID号 : "<<q->id;
cout<<endl<<"座位号 : "<<q->seat;
cout<<endl<<"班机号 : "<<q->plane;
cout<<endl<<"日期 : "<<q->date<<endl;
if (x==1) {
cout<<"删除该纪录 ? [Y/N] ";
cin>>ch;
if (ch=='Y' || ch=='y') {
t1=q->plane;
t2=q->seat;
a[t1].seat[t2]=0;
a[t1].seat[0]--;
r=q;q=q->pre;
r->pre->next=r->next;
if(r->next!=NULL) r->next->pre=r->pre;
delete(r);
cout<<"**** 记录删除成功 ! ****";
write_to_file();
tempw=wait_head;
for(i=0;i<wait_head->count;i++)
{
tempw=tempw->next;
if(tempw==NULL) break;
if((tempw->plane==t1) && (tempw->seat==t2))
{
strcpy(tempw3->name,tempw->name);
strcpy(tempw3->phone,tempw->phone);
cout<<endl<<"等候的人中有可以订票的了："<<endl;
cout<<endl<<"姓名 : "<<tempw->name;
cout<<endl<<"ID号 : "<<tempw->id<<endl;
a[t1].seat[0]++;
a[t1].seat[t2]=1;
if(tempw->plane==1) add_information(head1,1,tempw->seat);
if(tempw->plane==2) add_information(head2,2,tempw->seat);
if(tempw->plane==3) add_information(head3,3,tempw->seat);
tempw2=tempw->pre;
tempw2->next=tempw->next;
if(tempw->next==NULL) wait_end=tempw2;
else tempw->next->pre=tempw2;
delete(tempw);
wait_head->count--;
write_to_file();
cout<<endl<<"等候的"<<tempw3->name<<"已经成功订票，已经由电话"<<tempw3->phone<<"通知了"<<endl;
break;
}
}

}
}continue;
}
else
{
if (q==NULL)
{
step++;
if(step==2) q=head2;
if(step==3) q=head3;
if(step==4) {cout<<endl<<"**** 信息检索完毕 ****";break;}
}
}
}while(1);
}
bool comp(node *x,node *y)
{
node *p,*q;
int i,j,k;
p=x;
q=y;
i=j=0;
do
{
while ( (p->name[i] != q->name[j]) && (p->name[i] != '\0') ) i++;

if (p->name[i] == '\0') {return(false);break;}
else
{
k=i;
while ( (p->name[k] == q->name[j]) && (q->name[j]!='\0') ) {k++;j++;}
if (q->name[j]=='\0') return(true);
else
{
j=0;
i++;
}
}
}while( (q->name[j]!='\0') && (p->name[i] != '\0') );
return(false);
}

void write_to_file()
{
FILE *fp;
int i,j;
int x[m];
node *p;
wait *tempw;
tempw=new wait;
tempw=wait_head;
fp=fopen("piao.dat","w");
for (i=1;i<=m-1;i++)
{
fwrite(&a[i],sizeof(piao),1,fp);
}
fclose(fp);

fp=fopen("information.dat","w");
x[0]=0;x[1]=a[1].seat[0];
for(i=0,j=1;j<=m-1;j++) {i=i+a[j].seat[0];x[j]=a[j].seat[0]+x[j-1];}
j=1;p=head1->next;
for(j=1;j<=i;j++)
{
if(j==x[1]+1) p=head2->next;
if(j==x[2]+1) p=head3->next;
if(p==NULL)break;
fwrite(p,sizeof(node),1,fp);
p=p->next;
}
fclose(fp);

fp=fopen("wait.txt","w");
for(j=0;j<=wait_head->count;j++)
{
if(tempw==NULL)break;
fwrite(tempw,sizeof(wait),1,fp);
tempw=tempw->next;
}
fclose(fp);
}

2
#include<iostream.h>

int HTryX[]={2,1,-1,-2,-2,-1,1,2}; //数组记录八个可走方向的横坐标
int HTryY[]={1,2,2,1,-1,-2,-2,-1}; //数组记录八个可走方向的纵坐标
int chessboard[8][8]; //定义了一个记录8*8的棋盘的数组函数
void Init(); //初始化棋盘,将各点置零函数
int outroad(int m,int n); //计算出从该点出发，有多少个出口可走函数
bool check(int m,int n); //判断某个方向是否可行函数
int dir(int m,int n); //计算出从该点走,路径的最优选择函数
void print(); //打印棋盘结果函数

void Init() //初始化棋盘，将所有的格子初始化为零
{int i,j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
chessboard[i][j]=0;
}

int dir(int m,int n) //计算出从该点走,路径的最优选择函数
{
int dir=0,num=8,k=0,i; //dir为记录出口数最少的路径，num记录最大出口数,K为中间变量
for(i=0;i<8;i++){
if(check( (m+HTryX[i]),(n+HTryY[i]) )){ //判断某个方向是否可行
k=outroad((m+HTryX[i]),(n+HTryY[i])); //计算该方向的出口数目
if( k &&(k<num) ) { //求出口数最少
num=k;
dir=i;
}
}
}
if(dir==0) { //当step=63时，由于所有方向的出口数均为零，需要特殊考虑
for(i=0;i<8;i++)
if(check((m+HTryX[i]),(n+HTryY[i]))) return i;
}
return dir; //返回最小出口数的方向
}

int outroad(int m,int n) //计算出从该点出发，有多少个出口可走函数
{
int i,out=0;
for(i=0;i<8;i++)
if(check((m+HTryX[i]),(n+HTryY[i]))) out++; //如果某个方向可行，出口数+1
return out; //返回出口数
}

bool check(int m,int n) //判断该点是否已经走过，也即某个方向是否可行，可行返回1，否则返回0
{
if( (m>=0)&&(m<8)&&(n>=0)&&(n<8)&&(chessboard[m][n]==0) ) return 1; //没有出棋盘的边缘，并且没有走过，即为可行
else return 0;
}

void print() //将棋盘的信息打印，也即将走满的格子中的步数信息显示出来
{
for(int i=0;i<8;i++){
cout<<endl<<endl;
for(int j=0;j<8;j++){
cout.width(6);
cout<<chessboard[i][j];
}
}
cout<<endl<<endl;
}

void main()
{ cout<<endl;
cout<<"----------------------------------马踏棋盘--------------------------------------"<<endl;
cout<<" "<<endl;
int choice=0;
do{
cout<<endl<<"---------------------------------------------------------------------"<<endl;
cout<<" MENU "<<endl;
cout<<" <1> 输入初始位置 "<<endl;
cout<<" <2> 退出系统 "<<endl;
cout<<"---------------------------------------------------------------------"<<endl;
cout<<"您的选择:";
cin>>choice;
int x=0,y=0,step=1,i=0 ;
Init();
if(choice==1){
cout<<endl<<"请输入横坐标(1--8) x="; //用户的输入过程
cin>>x;
cout<<"请输入纵坐标(1--8) y=";
cin>>y;
x--;y--;
chessboard[x][y]=step; //记录初始位置，将该点的坐标定义为步数step
for(step=2;step<65;step++){ // 每一步
i=dir(x,y); //求从某点出发可走的方向中，出口数最小的方向
x+=HTryX[i]; //前进一步
y+=HTryY[i];
chessboard[x][y]=step;

print();
}

}
}while(choice!=2);
}

实验中的问题及心得

通过这次作业，使我对栈与队列有了更深的理解。