BJFU|数据结构A（22下）实验2(2)——严蔚敏版教材头歌系统

仅供课外学习使用，任何个人与机构不得利用此文章进行任何形式的作弊。

08Ackermann函数递归求值

#include<iostream>
using namespace std;
int Ack(int m, int n)
{//Ackermann函数的递归求值
	if(m == 0)
		return n + 1;
	else if(m > 0 && n == 0)
		return Ack(m - 1, 1);
	else
		return Ack(m - 1, Ack(m, n - 1));
}

int main()
{
	int m,n;
	while(cin>>m>>n)
    {
        if(m==0&&n==0) break;
        cout<<Ack(m,n)<<endl;
    }
	return 0;
}

09Ackermann函数的非递归求值

#include<iostream>
using namespace std;
#define MAXSIZE 100
int Ack(int m, int n)
{//Ackermann函数的非递归求值
	int a[100][100];
	for(int i = 0; i < 100; i++)
		a[0][i] = i + 1;
	for(int i = 1; i <= m; i++)
	{
		a[i][0] = a[i - 1][1];
		for(int j = 1; j < 100; j++)
			a[i][j] = a[i - 1][a[i][j - 1]];
	}
	return (a[m][n]);
}

int main()
{
	int m,n;
	while(cin>>m>>n)
    {
        if(m==0&&n==0) break;
        cout<<Ack(m,n)<<endl;
    }
	return 0;
}

10递归求解单链表中的最大值

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode, * LinkList;
void CreateList_R(LinkList& L, int n)
{//后插法创建单链表
    int num = n;
    L = new LNode;
    L->next = NULL;
    LNode* p = L;
    while(num--)
    {
		LNode *t = new LNode;
		cin >> t->data;
		t->next = NULL;
		p->next = t;
		p = t;
	}
}

int GetMax(LinkList L)
{//递归求解单链表中的最大值
	if(!L->next)
		return L->data; 
	return max(GetMax(L->next),L->data);
}

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        L=L->next;    //指向首元结点
        cout<<GetMax(L)<<endl;
    }
    return 0;
}

11递归求解单链表中的结点个数

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode, * LinkList;
void CreateList_R(LinkList& L, int n)
{//后插法创建单链表
    L = new LNode;
	L->next = NULL;
	int num = n;
	LNode* p = L;
	while(num--)
	{
		LNode* t = new LNode;
		cin >> t->data;
		t->next = NULL;
		p->next = t;
		p = t;
	} 
}
int GetLength(LinkList L)
{//递归求解单链表中的结点个数
	if(!L->next)
		return 1;
	return (GetLength(L->next)) + 1;
}

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        L=L->next;    //L指向首元结点
        cout<<GetLength(L)<<endl;
    }
    return 0;
}

12递归求解单链表中的平均值

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode, * LinkList;
void CreateList_R(LinkList& L, int n)
{//后插法创建单链表
    L = new LNode;
	L->next = NULL;
	int num = n;
	LNode* p = L;
	while(num--)
	{
		LNode* t = new LNode;
		cin >> t->data;
		t->next = NULL;
		p->next = t;
		p = t;
	}    
}
double GetAverage(LinkList L, int n)
{//递归求解单链表中的平均值
	if(!L->next)
		return L->data;
	return (GetAverage(L->next, n - 1) * (n - 1) + L->data) / n;
}

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        L=L->next;//L指向首元结点
        printf("%.2f\n",GetAverage(L,n));//输出保留两位小数
    }
    return 0;
}

13基于循环链表的队列的基本操作

#include<iostream>
using namespace std;
typedef int Status;
typedef struct QNode
{//队列的链式存储结构
    int data;
    struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
    QueuePtr rear;    //只设一个队尾指针
}LinkQueue;
Status EmptyQueue(LinkQueue Q)
{//判断队列是否为空，空返回1，否则返回0
//队列只有一个头结点，即当头结点的指针域指向自己时，队列为空
	if(Q.rear->next->next == Q.rear->next)
		return 1;
	return 0;
}
void EnQueue(LinkQueue& Q, int e)
{//入队，插入元素e为Q的新的队尾元素
	QNode* p = new QNode;
	p->data = e;
	p->next = Q.rear->next;
	Q.rear->next = p;
	Q.rear = p;
}
void DeQueue(LinkQueue& Q)
{//出队，输出Q的队头元素值，后将其删除
	QNode* t = Q.rear->next->next;
	cout << t->data << " ";
	Q.rear->next->next = t->next;
	if(Q.rear == t)
		Q.rear = Q.rear->next->next;
	delete t;
}

int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		if(n==0&&m==0) break;
		LinkQueue Q;           //初始化一个带头结点的循环链表
		Q.rear=new QNode;
        Q.rear->next=Q.rear;
		while(n--)
		{//n个元素入队
			int e;cin>>e;
			EnQueue(Q,e);
		}
		while(m--)            //m个元素出队
			DeQueue(Q);
		if(EmptyQueue(Q))
			cout<<"0"<<endl;
		else
			cout<<"1"<<endl;
	}
	return 0;
}

14附加判定标志的循环队列的基本操作

#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 0
#define OVERFLOW -1
#define ERROR -2
typedef int Status;
typedef struct
{
	int* base;
	int front, rear, tag;
}SqQueue;
Status InitQueue(SqQueue& Q)
{//构造一个空队列Q
	Q.base = new int[MAXSIZE];
	Q.tag = 0;
	Q.front = 0;
	Q.rear = 0;
	return OK;
}
Status EnQueue(SqQueue& Q, int e)
{//插入元素e为Q的新的队尾元素
	if(Q.tag == 1 && Q.front == Q.rear)
		return ERROR;
	else
	{
		Q.base[Q.rear] = e;
		Q.rear = (Q.rear + 1) % MAXSIZE;
		if(Q.front == Q.rear)
			Q.tag = 1;
	}
	return OK;
}
Status DeQueue(SqQueue& Q)
{//删除Q的队头元素，用e返回其值
	int e;
	if(Q.tag == 0 && Q.front == Q.rear)
		return ERROR;
	else
	{
		e = Q.base[Q.front];
		Q.front = (Q.front + 1) % MAXSIZE;
	}
	return e;
}

int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		SqQueue Q;
		InitQueue(Q);             //初始化循环队列
		for(int i=0;i<n;i++)
		{//n个元素入队
			int x;cin>>x;
			EnQueue(Q,x);
		}
		for(int i=0;i<n-1;i++)
			cout<<DeQueue(Q)<<" ";
		cout<<DeQueue(Q)<<endl;
	}
	return 0;
}

15基于两端操作的循环队列的实现

#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{
	int* base;
	int front;
	int rear;
}SqQueue;
Status InitQueue(SqQueue& Q)
{//构造一个空队列Q
	Q.base = new int[MAXSIZE];
	Q.front = 0;
	Q.rear = 0;
	return OK;
}
Status EnQueue(SqQueue& Q, int e)
{//在Q的队头插入新元素e
	if(Q.rear == (MAXSIZE + Q.front - 1) % MAXSIZE)
		return ERROR;
	Q.base[Q.front] = e;
	Q.front = (MAXSIZE + Q.front - 1) % MAXSIZE;
	return OK;
}
Status DeQueue(SqQueue& Q)
{//删除Q的队尾元素，用e返回其值
	if(Q.front == Q.rear)
		return ERROR;
	int e = Q.base[Q.rear];
	Q.rear = (MAXSIZE + Q.rear - 1) % MAXSIZE;
	return e;
}

int main()
{
	int n;
	while(cin>>n&&n!=0)
	{
		SqQueue Q;
		InitQueue(Q);          //初始化循环队列
		for(int i=0;i<n;i++)
		{//n个元素入队
			int x;cin>>x;
			EnQueue(Q,x);
		}
		for(int i=0;i<n-1;i++)
			cout<<DeQueue(Q)<<" ";
		cout<<DeQueue(Q)<<endl;
	}
	return 0;
}