代码1.txt

实用数据结构课后习题解答

输出栈顶指针与栈中的元素： 
top=6
100
90
80
70
60
50
栈顶元素： 100
输出退栈元素： 
100
90
80
再次输出栈顶指针与栈中的元素： 
top=3
70
60
50


//文件名L2_5.cpp
//将字符串转换成实数
double shishu(char *s, int *k)
{ double x, y=1.0;
intflag=1;
char c;
x=0.0;
c=s\[*k\];//取得当前符号
while(c>='0'&&c<='9'||c=='.')//为数字符号或小数点需要转换
{ *k=*k+1;//扫描指针进一
if (c>='0'&&c<='9')//为数字符号
if (flag==0)//转换小数点后的数值，并整数部分
{ y=y*0.1; x=x+(c-48)*y; }
else//转换整数部分的数值
x=10*x+(c-48); 
else flag=0;//为小数点“.”
c=s\[*k\];//取当前符号
}
return(x);//返回转换得到的实数值
}
//计算运算符的优先级
int pp(char c)
{ int k;
switch(c)
{ case '*':k=2; break;
case '/':k=2; break;
case '+':k=1; break;
case '-':k=1; break;
case '(':k=0; break;
case ')':k=0; break;
case '\\0': k=-1; break;
}
return(k);
}
//主函数
#include "sq_Stack.h"//包含顺序栈类
int main()
{ sq_Stack<double> sv(50);
sq_Stack<char> sp(20);
char s\[60\], c;
intflag=1, k;
double x, y;
sp.ins_sq_Stack('\\0');//表达式结束符进运算符栈
cout <<"input s:" <<endl;
cin >>s;
k=0;//扫描指针初始化
c=s\[k\];//取当前字符
while(flag)
{ if (c>='0'&&c<='9'||c=='.') //当前字符为数字字符或小数点
sv.ins_sq_Stack(shishu(s, &k));//转换成实数值进操作数栈
else if (c=='('||pp(c)>pp(sp.read_sq_Stack())) 
//当前字符为“(”或读出的运算符优先级大于运算符栈栈顶运算符优先级
{ sp.ins_sq_Stack(c); //运算符进运算符栈 
k=k+1;//扫描指针进一
}
else if ((c=='\\0')&&(sp.read_sq_Stack()=='\\0')) 
//当前符号为表达式结束符且运算符栈栈顶运算符也是表达式结束符
flag=0; //置表达式处理结束标志
else if ((c==')')&&(sp.read_sq_Stack()=='(')) 
//当前符号为"）"，且运算符栈栈顶运算符为"（"
{ sp.del_sq_Stack();//从运算符栈栈顶退出左括号"（"
k=k+1;//扫描指针进一
}
else if (pp(c)<=pp(sp.read_sq_Stack()))
//当前读出的运算符优先级不大于运算符栈栈顶运算符的优先级
{ y=sv.del_sq_Stack();//从操作数栈取右操作数
x=sv.del_sq_Stack();//从操作数栈取左操作数
c=sp.del_sq_Stack();//从运算符栈取运算符
switch(c)//根据运算符做相应的运算
{ case '*': x=x*y; break;
case '/': x=x/y; break;
case '+': x=x+y; break;
case '-': x=x-y; break;
}
sv.ins_sq_Stack(x);//将运算结果进操作数栈
}
c=s\[k\];//取得字符
}
cout <<s <<"=" <<sv.read_sq_Stack() <<endl;//输出计算结果
return 0;
}


inputs:
3.5*(6.5-2.5)/2+(5.5-1)/3
3.5*(6.5-2.5)/2+(5.5-1)/3=8.5


using namespace std;
template <typename T>//模板声明，T为类型参数
voidinit_Queue(T *q，int m，int *front，int *rear，int *s)
{q＝new T\[m\];
*front＝m；*rear＝m；*s＝0；
return；
}


using namespace std;
template <typename T>//模板声明，T为类型参数
voidaddcq(T *q，int m，int *rear，int *front，int *s，T x)
{ if((*s＝＝1) && (*rear＝＝ *front))
{ printf("Queue－OVERFLOW \\n")； return；}
*rear＝ *rear＋1；
if(*rear＝＝m＋1)*rear＝1；
q\[*rear－1\]＝x；*s＝1；return；
}


using namespace std;
template <typename T>//模板声明，T为类型参数
Tdelcq(T *q，int m，int *rear，int *front，int *s)
{ T y;
if(*s＝＝0){ printf("Queue－UNDERFLOW \\n")； return；}
*front＝ *front＋1；
if(*front＝＝m＋1)*front＝1；
*y＝q\[*front－1\]；
if(*front＝＝ *rear)*s＝0；
return；
}


//文件名sq_Queue.h
#include <iostream>
using namespace std;
//定义循环队列类
template <class T>//模板声明，数据元素虚拟类型为T
classsq_Queue
{ private://数据成员
int mm;//存储空间容量
int front;//排头指针
int rear;//队尾指针
int s;//标志
T *q;//循环队列存储空间首地址
public://成员函数
sq_Queue(int);//构造函数，建立空循环队列 
void prt_sq_Queue();//输出排头与队尾指针以及队中元素
int flag_sq_Queue();//检测循环队列的状态
void ins_sq_Queue(T);//入队
T del_sq_Queue();//退队
};
//建立容量为mm的空循环队列
template <class T>
sq_Queue<T>∷sq_Queue(int m)
{ mm=m;//存储空间容量
q=new T\[mm\];//动态申请存储空间
front=mm;rear=mm;s=0;
return; 
}
//输出排头与队尾指针以及队中元素
template <class T>
void sq_Queue<T>∷prt_sq_Queue()
{ int i;
cout <<"front=" <<front <<endl;
cout <<"rear=" <<rear <<endl;
if (s==0) { cout <<"队列空！" <<endl; return; }
i=front;
do { i=i+1; 
if (i==mm+1) i=1;
cout <<q\[i-1\] <<endl;
} while (i!=rear);
return;
}
//检测循环队列的状态
template <class T>
int sq_Queue<T>∷flag_sq_Queue()
{ if ((s==1)&&(rear==front)) return(-1);//存储空间已满，返回-1
if (s==0) return(0);//循环队列为空，返回0
return(1);//正常返回1
}
//入队
template <class T>
void sq_Queue<T>∷ins_sq_Queue(T x) 
{ if ((s==1)&&(rear==front))//存储空间已满，上溢错误
{ cout <<"Queue_overflow!" <<endl;return; }
rear=rear+1;//队尾指针进一
if (rear==mm+1) rear=1;
q\[rear-1\]=x;//新元素入队
s=1;//入队后队列非空
return;
}
//退队
template <class T>
T sq_Queue<T>∷del_sq_Queue()
{ T y;
if (s==0)//队列为空，下溢错误
{ cout <<"Queue_underflow!" <<endl;return(0); }
front=front+1;//排头指针进一
if (front==mm+1) front=1;
y=q\[front-1\];//将退队元素赋给变量
if (front==rear) s=0;
return(y);//返回退队的元素
}


if (q.flag_sq_Queue()!=-1) q.ins_sq_Queue(25);//循环队列非满进行插入操作
else{ 上溢处理 }


if (q.flag_sq_Queue()!=0) y=q.del_sq_Queue();//循环队列非空进行退队操作
else{ 下溢处理 }


//文件名L2_6.cpp
#include "sq_Queue.h"
int main()
{ sq_Queue<int> q(10);//建立容量为10的空循环队列，元素为整型
cout <<"输出排头与队尾指针以及队中元素:" <<endl;
q.prt_sq_Queue();//输出排头与队尾指针以及队中元素
q.ins_sq_Queue(50);
q.ins_sq_Queue(60);
q.ins_sq_Queue(70);
q.ins_sq_Queue(80);
q.ins_sq_Queue(90);
q.ins_sq_Queue(100);
cout <<"输出排头与队尾指针以及队中元素:" <<endl;
q.prt_sq_Queue();//输出排头与队尾指针以及队中元素
cout <<"输出退队元素:" <<endl;
cout <<q.del_sq_Queue() <<endl;
cout <<q.del_sq_Queue() <<endl;
cout <<q.del_sq_Queue() <<endl;
cout <<"再次输出排头与队尾指针以及队中元素:" <<endl;
q.prt_sq_Queue(); //再次输出排头与队尾指针以及队中元素
return 0;
}


输出排头与队尾指针以及队中元素： 
front=10
rear=10
队列空！
输出排头与队尾指针以及队中元素： 
front=10
rear=6
50
60
70
80
90
100
输出退队元素： 
50
60
70
再次输出排头与队尾指针以及队中元素： 
front=3
rear=6
80
90
100


//文件名L2_8.cpp
#include "sq_Queue.h"//包含循环队列类
//模拟汽车排队
template <class T>
void simuauto(sq_Queue<T> &cq, int *num, double dt, double g, double rnd)
{ if (rnd<=dt/g)
{ *num= *num+1;
cq.ins_sq_Queue(*num);
}
return;
}
//模拟油泵工作
template <class T>
void simupump(sq_Queue<T> &cq,double dt,double d,double *flag,int *aut,int i)
{ int n;
if (flag\[i-1\]<=0)
{ n=cq.del_sq_Queue();
if (n==0)flag\[i-1\]=0;
else
{ aut\[i-1\]=n;
flag\[i-1\]=d-dt;
}
}
elseflag\[i-1\]=flag\[i-1\]-dt;
return;
}
//模拟结果输出
template <class T>
void out(sq_Queue<T> &cq, double flag\[\], int aut\[\])
{ cq.prt_sq_Queue();
cout <<"flag(1)=" <<flag\[0\] <<", " <<"aut\[1\]=" <<aut\[0\] <<endl;
cout <<"flag(2)=" <<flag\[1\] <<", " <<"aut\[2\]=" <<aut\[1\] <<endl;
cout <<"