记数据结构第四次书面作业的一些算法题

本文主要是介绍记数据结构第四次书面作业的一些算法题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 栈与递归练习
- - 递归练习
  - 栈练习

栈与递归练习

递归练习

假设线性表的数据元素为整数，采用带头结点的单链式存储，请分别设计递归算法完成：
（1）求线性表的长度；
（2）求所有元素的平均值。
第一题所用函数如下：

int len(struct node *t){if(t->next==NULL)return 1;else{t=t->next;return 1+len(t);}}

第二题所用函数如下：

double average(struct node *t){if(t->next==NULL)return 1.0*t->data/len(head);else{return 1.0*t->data/len(head)+average(t->next);}}

完整代码如下（可用来验证算法的正确性）

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<int,int> m_i_i;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
const ll INF=0x3f3f3f3f;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 2000005
#define M 100005
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set<int>::iterator
#define fs(n) fixed<< setprecision(n)
const double e=2.71828182845;
const double pi = acos(-1.0);
class List1
{public:struct node{int data;struct node *next;};struct node *p,*q,*t,*head,*head1;void create(int *a,int n){head=NULL;rep(i,1,n){p=(struct node*)malloc(sizeof(struct node));p->data=a[i];p->next=NULL;if(head==NULL){head=p;}else{q->next=p;}q=p;}head1=(struct node *)malloc(sizeof(struct node));head1->data=NULL;head1->next=head;//t=(struct node*)malloc(sizeof(struct node));//t=head;}void bianli(){p=head;while(p!=NULL){cout<< p->data <<endl;p=p->next;}}int len(struct node *t){if(t->next==NULL)return 1;else{t=t->next;return 1+len(t);}}double average(struct node *t){if(t->next==NULL)return 1.0*t->data/len(head);else{return 1.0*t->data/len(head)+average(t->next);}}
};
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;int a[n+1];rep(i,1,n){cin>>a[i];}List1 list1;list1.create(a,n);//list1.bianli();int lens=list1.len(list1.head);cout<<lens<<endl;double aver=list1.average(list1.head);cout<<aver<<endl;return 0;
}

栈练习

假设输入序列为1，2，……，n，设计一个算法判断一个由1到n构成的序列p1，p2，……，pn是否为合法的出栈序列。

典型火车进站问题，直接上代码：

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<int,int> m_i_i;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
const ll INF=0x3f3f3f3f;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 2000005
#define M 100005
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set<int>::iterator
#define fs(n) fixed<< setprecision(n)
const double e=2.71828182845;
const double pi = acos(-1.0);
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;int a[n+1];rep(i,1,n){cin>>a[i];}stack<int>st;int u=1;rep(i,1,n){if(i==a[u]){u++;while(!st.empty()&&u<=n){int p=st.top();if(p!=a[u]){break;}else{u++;st.pop();}}}else{st.push(i);}}int flag=0;while(!st.empty()){int p=st.top();st.pop();if(p!=a[u]){flag=1;break;}elseu++;}if(flag==0)cout<<"YES";elsecout<<"NO";return 0;
}