第五次数据结构作业答案

  1. 怎样判定循环队列的空和满?
答:有以下四种方法判定循环队列的空满(假设头为front尾为rear,循环队列的最大为Maxsize)
  • 预留一位:可以空余出来一个存储单元,不储存任何数,则判空条件是front%Maxsize == rear%Maxsize 判满条件是(front+1)%Maxsize == rear
  • 增加一个全局变量count:记录当前队列中的个数,则判空条件是count == 0 && front%Maxsize == rear%Maxsize,判满条件是count == Maxsize && front%Maxsize== rear%Maxsize
  • 设置两个全局变量in_count和out_count,并初始化为0,分别记录入队列和出队列的个数,则判空条件是front%Maxsize == rear%Maxsize && in_count == out_count, 判满条件是front%Maxsize == rear%Maxsize && in_count - out_count == Maxsize
  • 设置标志法:设置一个bool型的judge标记,初始化为false,如果入队列成功,judge为true,如果出队列成功,judge设为false,则判空条件是front%Maxsize == rear%Maxsize && judge == 0 ,判满条件是front%Maxsize == rear%Maxsize && judge == 1
  1. 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(EnQueue)和删除(DeQueue)算法。类的定义和函数声明同课本。
答:代码如下:
//循环队列
#include <iostream>
using namespace std;
const int defaultMaxSize = 10;
template <class T>
class SeqQueue
{
private:
int Front;
int Rear;
int maxSize;
T * element;
bool tag;
public:
SeqQueue(int sz = defaultMaxSize):Front(0),Rear(0),maxSize(sz)
{
element = new T[maxSize];
tag = false;
}
~SeqQueue()
{
delete[] element;
Front = 0;
Rear = 0;
}
bool EnQueue(const T&x)//新的元素x入队列
{
//如果队列已经满了
if(Front%maxSize == Rear%maxSize && tag == true)
{
return false;
}
element[Rear] = x;
Rear = (Rear+1)%maxSize;
tag = true;
return true;
}
bool DeQueue(T&x)//队头元素出队列
{
//如果队列是空的
if(Front%maxSize == Rear%maxSize && tag == false)
{
return false;
}
x = element[Front];
Front = (Front+1)%maxSize;
tag = false;
return true;
}
//重载进行输出
friend ostream&operator << (ostream&os,SeqQueue<T>&Q)
{
os << "front = " << Q.Front << " Rear = " << Q.Rear << endl;
bool judge = Q.tag;
for(int i = Q.Front; i != Q.Rear || judge ; i = (i+1)%Q.maxSize)
{
os << i << ":" << Q.element[i] << " ";
{
judge = false;
}
}
return os;
}
};
int main()
{
int sz;
cin >> sz;
SeqQueue<int> sq(sz);
//建立一个10为maxSize的队列空间,将1-10元素入队
for(int i = 0 ; i < sz; i++)
sq.EnQueue(i+1);
cout << sq << endl;
//将前五个元素出队
for(int i = 0 ; i < sz/2; i++)
{
int x;
sq.DeQueue(x);
cout << x << " ";
}
cout << endl;
cout << sq << endl;
//将前五个元素出队
for(int i = 0 ; i < sz/2; i++)
{
sq.EnQueue(i+sz/2);
}
cout << sq << endl;
return 0;
}
输入:10
说明:建立一个10为maxSize的队列空间,将1-10元素入队
输出:当前队列中的元素
改变:将前五个元素出队
输出:将队列中剩余元素打印出来
改变:将5-9元素入队
输出:将当前队列中元素打印出来
测试输出结果
  1. 假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为多少?
答:从当前开始到数组末尾,还能存储59-47+1 = 13个元素,剩下元素个数为50-13 = 37,则队为指针为rear = 37。
计算公式:设队尾指针值为x,由于50-13 = 37,说明 x < front,
则有:x + 60 - 47 = 50
解得:x = 37
  1. 二维数组A[4][5]按行优先顺序存储,若每个元素占2个存储单元,且第一个元素A[0][0]的存储地址为1000,则数组元素A[3][2]的存储地址为多少?
答:按照行优先进行讨论地址:a[n][m]
其中:a为首地址,k为每个元素占用的存储单元,m为每行的元素个数
a[i][j]的地址公式为:LOC(i,j) = a + i * m * k + j * k
将此题带入公式得:LOC(3,2) = 1000 + 3 * 5 * 2 + 2 * 2 = 1034
A[3][2]的存储地址为1034
  1. 设 n 阶对称矩阵按行优先方式存储下三角元素,元素 a00 存储在 sa[0] 元素中,元素 a[i][j]存储在 sa[100] 元素中,则下标 i、j 的值为多少?
答:根据对称矩阵的公式:
sa数组下表满足:LOC(i,j) = (i+1)*i/2 + j 并且 i >= j
原来矩阵每行第一个元素在sa数组中的下标,分别为0,1, 3,6,15,21,28,36,45,55,66,78,91,105....
所以由于13 * 14 / 2 = 91, i = 13, j = 100 - 91 = 9
sa[100]对应的矩阵中下标i = 13,j = 9
原文地址:https://www.cnblogs.com/pprp/p/7676503.html