合工大 算法与数据结构实验报告.doc
文本预览下载声明
算法与数据结构实验报告
实验一:栈和队列
实验目的：
掌握栈和队列特点、逻辑结构和存储结构
熟悉对栈和队列的一些基本操作和具体的函数定义。
利用栈和队列的基本操作完成一定功能的程序。
实验任务
给出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数N与其它d进制数的转换。（如N=1357,d=8）
实验原理:将十进制数N转换为八进制时，采用的是“除取余数法”，即每次用8除N所得的余数作为八进制数的当前个位，将相除所得的商的整数部分作为新的N值重复上述计算，直到N为0为止。此时，将前面所得到的各余数反过来连接便得到最后的转换结果。
程序清单
#includeiostream
#includecstdlib
using namespace std;
typedef int DATA_TYPE;
const int MAXLEN=100;
enum error_code
{
success,overflow,underflow
};
class stack
{
public:
stack();
bool empty()const;
error_code get_top(DATA_TYPE x)const;
error_code push(const DATA_TYPE x);
error_code pop();
bool full()const;
private:
DATA_TYPE data[MAXLEN];
int count;
};
stack::stack()
{
count=0;
}
bool stack::empty()const
{
return count==0;
}
error_code stack::get_top(DATA_TYPE x)const
{
if(empty())
return underflow;
else
{
x=data[count-1];
return success;
}
}
error_code stack::push(const DATA_TYPE x)
{
if(full())
return overflow;
else
{
data[count]=x;
count++;
}
}
error_code stack::pop()
{
if(empty())
return underflow;
else
{
count--;
return success;
}
}
bool stack::full()const
{
return count==MAXLEN;
}
void main()
{
stack S;
int N,d;
cout请输入一个十进制数N和所需转换的进制dendl;
cinNd;
if(N==0)
{
cout输出转换结果:Nendl;
}
while(N)
{
S.push(N%d);
N=N/d;
}
cout输出转换结果:endl;
while(!S.empty())
{
S.get_top(N);
coutN;
S.pop();
}
coutendl;
}
while(!S.empty())
{
S.get_top(x);
coutx;
S.pop();
}
}
测试数据：N=1348 d=8
运行结果：
给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内容。(n=8)
实验原理：杨辉三角的规律是每行的第一和最后一个数是1，从第三行开始的其余的数是上一行对应位置的左右两个数之和。因此，可用上一行的数来求出对应位置的下一行内容。为此，需要用队列来保存上一行的内容。每当由上一行的两个数求出下一行的一个数时，其中的前一个便需要删除，而新求出的数就要入队。
程序清单：
#includeiostream
#includecstdlib
using namespace std;
typedef int DATA_TYPE;
const int MAXLEN=100;
enum error_code
{
success,underflow,overflow
};
class queue
{
public:
queue();
bool empty()const;
error_code get_front(DATA_TYPE x)const;
error_code append(const DATA_TYPE x);
error_code serve();
bool full()const;
private:
int front,rear;
DATA_TYPE data[MAXLEN];
};
queue::queue()
{
rear=0;
front=0;
}
bool queue::empty()con
显示全部