目录
1. 约瑟夫环问题
【问题描述】用单向循环链表解决约瑟夫环问题，是否带头结点，大家自定。
【输入形式】输入n和m的值，其中n为总人数，m为密码
【输出形式】胜利者编号，也就是最后一个离开队伍的人
【样例输入】6 4
【样例输出】5
1.单向循环链表
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* next;
};
int main()
{
int n,m;
cin>>n>>m;
node*head=NULL;
node*L=NULL;
for(int i=1;i<=n;i++)//创建链表
{
node *p=new node;
p->data=i;
if(head==NULL)
{
head=p;
L=p;
}
else{
L->next=p;
p->next=head;
}
L=p;
}
for(int i=1;i<=m*(n-1);i++)//
{
if(i%m==0)
L->next=L->next->next;
else
{
L=L->next;
}
}
cout<<L->data;
}
2.其他方法自行查找
2. 双向循环链表排序
【问题描述】实现双向循环链表的创建，然后实现该双向循环链表上数据的排序。（方法自定）
【输入形式】随机的数据
【输出形式】排序后的数据
【样例输入】5 7 2 8 1 3 4 9 6 0
【样例输出】1 2 3 4 5 6 7 8 9
插入排序
参考该图像更好的理解插入排序。
#include <iostream>
using namespace std;
typedef struct Node
{
int data;
Node*prior,*next;
}Node,*LinkList;
void createlist(Node *head)//双向循环链表的创建
{
Node*a=head;
int num;
Node*s;
while (cin>>num)
{
if(num==0)
break;
else
{
s= new Node;
s->data=num;
a->next=s;
s->prior=a;
s->next=head;
head->prior=s;
a=s;
}
}
}
void Sort(Node *head)//插入排序
{ Node *L=head;
Node*p,*q,*r;
p=L->next;q=p->next;r=q->next;
while(q!=L)
{
while((p!=L)&&(p->data>q->data))
p=p->prior;
q->prior->next=r;
r->prior=q->prior;
q->next=p->next;
q->prior=p;
p->next->prior=q;
p->next=q;
q=r;
p=q->prior;
r=r->next;
}
}
void print(Node *head)
{ Node*L=head->next;
while (L!=head)
{
cout<<L->data<<" ";
L=L->next;
}
}
int main()
{ Node * head=new Node;
head->next=head;
head->prior=head;
createlist(head);
Sort(head);
print(head);
return 0;
}
3.字符串镜像
【问题描述】试写一个算法，识别依次读入的一个以“@”为结束符的字符序列是否为形如 “序列1&序列2” 模式的字符序列。其中序列1和序列2都不含字符 “&”，且序列2是序列1的逆序列。例如，“ a+b&b+a ”是属该模式的字符序列，而 “1+3&3-1”则不是。
【输入形式】
以@为结尾的一串字符【输出形式】
若符合模式则输出字符串长度，否则输出no【样例输入】
a+b&b+a@【样例输出】
3【注意】本题务必使用顺序栈或者链式栈的一种来实现，否则不给分。
#include<bits/stdc++.h>
using namespace std;
#define M 4000
typedef struct
{
char data[M];
int top;
}sqstack;
void push(sqstack * s)
{
char x;
while(1)
{
cin>>x;
if(x=='@') break;
s->top++;
s->data[s->top]=x;
}
}
void cz(sqstack *s)
{
int i=0;
for(i=0;i<=s->top;i++)
{
if(s->data[i]=='&') break;
}
for(int j=0;i-j>=0;j++)
{
if(s->data[i-j]!=s->data[i+j])
{
cout<<"no"<<endl;
return ;
}
}
cout<<i<<endl;
}
int main()
{
sqstack *s=new sqstack;
s->top=-1;
push(s);
cz(s);
return 0;
}
4. 表达式求值
【问题描述】栈的应用，给定一个以“#”作为结束符的算式，求出算式的结果
【输入形式】以“#”结尾的表达式，运算数为正整数。每个表达式占一行。
【输出形式】输出表达式运算的结果。
【样例输入1】4+2.53*3-10/5#
【样例输出1】9.59
【样例输入2】3*(7.91-2)#
【样例输出2】17.73
【样例输入3】2.4*3.6/2#
【样例输出3】4.32
【注意】分别运用C和C++语言如何处理表达式中带小数的数据，输出数据请保留2位小数。
#include<bits/stdc++.h>
using namespace std;
#define M 1000
char a[M];
typedef struct Stack
{
char elem[M];
double num[M];
int top,topi;
}sqstack;
void initial(sqstack *s)
{
s->top=-1;
s->topi=-1;
}
void push(sqstack *s,char x)
{
s->elem[++s->top]=x;
}
void push_i(sqstack *s,double x)
{
s->num[++s->topi]=x;
}
char pop(sqstack *s)
{
return s->elem[s->top--];
}
double pop_i(sqstack *s)
{
return s->num[s->topi--];
}
bool Is_operator(char x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':
return 1;
default:
return 0;
}
}
char Operator(char a,char b)
{
int i=0,j=0;
char pre[7][7]={
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='}
};
switch(a)
{
case '+':i=0;break;
case '-':i=1;break;
case '*':i=2;break;
case '/':i=3;break;
case '(':i=4;break;
case ')':i=5;break;
case '#':i=6;break;
}
switch(b)
{
case '+':j=0;break;
case '-':j=1;break;
case '*':j=2;break;
case '/':j=3;break;
case '(':j=4;break;
case ')':j=5;break;
case '#':j=6;break;
}
return pre[i][j];
}
double calculate(double a,double b,char c)
{
switch(c)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
}
return 0;
}
void fun(sqstack * s)
{
int i=0;
double x1,x2;
push(s,'#');
do
{
if(isdigit(a[i]))
{
x1=a[i]-'0';
push_i(s,x1);
if(isdigit(a[i+1]))
{
i++;
x2=a[i]-'0';
x1=x1*10+x2;
pop_i(s);
push_i(s,x1);
i++;
}
else if(a[++i]=='.')
{
int cnt=1;
i++;
while(isdigit(a[i]))
{
x2=a[i]-'0';
x1=x1+pow(0.1,cnt)*x2;
cnt++;
pop_i(s);
push_i(s,x1);
i++;
}
}
}
if(Is_operator(a[i]))
{
switch(Operator(s->elem[s->top],a[i]))
{
case '<':push(s,a[i]);i++;break;
case '>':x1=pop_i(s);x2=pop_i(s);
x1=calculate(x2,x1,pop(s));
push_i(s,x1);
break;
case '=':pop(s);i++;break;
}
}
}while(s->top!=-1);
}
int main()
{
sqstack *s=new sqstack;
initial(s);
cin>>a;
fun(s);
printf("%.2f",s->num[s->topi]);
//cout<<fixed<<setprecision(2)<<s->num[s->topi]<<endl;
return 0;
}
5. 学生信息管理
【问题描述】设有一个存储学生信息的结构体包含：学号（no），姓名（name ），班级号（classno），大学入学成绩总分（score），学生号指针（pno），班级号指针（pclass），成绩数指针（pscore）。设计一个程序将信息读取并记录到一个链表中，完成如下功能：
１．输入：添加一个学生记录，请按头插法添加
２．输出：输出全部学生记录
３．按no排序：通过pno指针将学生记录按no递增连接起来
４．按no输出：沿pno链输出全部学生记录
５．按classno排序：通过classno指针将学生记录按classno递增连接起来
６．按classno输出：沿classno链输出全部学生记录，当classno一致时，按score递增顺序输出
７．按score排序：通过pscore指针将学生记录按no递增连接起来
８．按score输出：沿pscore链输出全部学生记录，当score一致时，按no递增顺序输出
９．全清：删除学生的全部记录
１０．退出：退出运行程序
【目的】链表综合应用
【输入形式】学号，姓名，班级号，成绩
【输出形式】select:以及执行结果
【样例输入】select:1
06208 gaoya 2103 630
select:1
06209 lisi 2104 617
select:1
06210 lisi 2103 643
select:8
【样例输出】06209 lisi 2104 617
06208 gaoya 2103 630
06210 lisi 2103 643
【样例说明】添加各学生记录之后，建立链表，执行各种操作。
#include <bits/stdc++.h>
using namespace std;
typedef struct stu
{
int no;
string name;
int classno;
float score;
stu *pno;
stu *pclass;
stu *pscore;
stu *p;
}stu;
stu *head;
void headlist(int no, string name, int classno, int score){
stu* s = new stu;
s->p = head->p;
head->p = s;
s->pno = head->pno;
head->pno = s;
s->pclass = head->pclass;
head->pclass = s;
s->pscore = head->pscore;
head->pscore = s;
s->classno = classno;
s->name = name;
s->no = no;
s->score = score;
return;
}
void Sort_no(stu* head){
stu*pre,*cur,*next,*End;
End= NULL;
while(head->pno != End ){
for(pre = head , cur = pre->pno, next = cur->pno; next != End; pre = pre->pno , cur = cur->pno , next = next->pno){
if(cur->no > next ->no ){
pre->pno = next;
cur->pno = next->pno;
next->pno=cur;
stu* s = cur;
cur = next;
next = s;
}
}
End = cur;
}
}
void Sort_classno(stu* head){
stu*pre,*cur,*next,*End;
End = NULL;
while(head->pclass != End ){
for(pre = head , cur = pre->pclass, next = cur->pclass; next != End; pre = pre->pclass , cur = cur->pclass , next = next->pclass){
if(cur->classno > next ->classno || (cur->classno == next->classno && cur->score > next->score) ){
pre->pclass = next;
cur->pclass = next->pclass;
next->pclass=cur;
stu*s = cur;
cur = next;
next = s;
}
}
End = cur;
}
}
void Sort_score(stu* head){
stu *pre,*cur,*next,*End;
End = NULL;
while(head->pscore != End ){
for(pre = head , cur = pre->pscore, next = cur->pscore; next != End; pre = pre->pscore , cur = cur->pscore , next = next->pscore){
if(cur->score > next ->score || (cur->score == next->score && cur->no > next->no) ){
pre->pscore = next;
cur->pscore = next->pscore;
next->pscore=cur;
stu* s = cur;
cur = next;
next =s;
}
}
End = cur;
}
}
void print_all(stu* head){
stu* s= head->p;
while(s!=NULL){
cout << "0" << s->no << " " << s->name << " " << s->classno << " " << s->score << endl;
s = s->p;
}
}
void print_no(stu* head){
stu* s= head->pno;
while(s!=NULL){
cout << "0" << s->no << " " << s->name << " " << s->classno << " " << s->score << endl;
s= s->pno;
}
}
void print_classno(stu* head){
stu* s= head->pclass;
while(s!=NULL){
cout << "0" << s->no << " " << s->name << " " << s->classno << " " << s->score << endl;
s = s->pclass;
}
}
void print_score(stu* head){
stu*s= head->pscore;
while(s!=NULL){
cout << "0" << s->no << " " << s->name << " " << s->classno << " " << s->score << endl;
s = s->pscore;
}
}
void clear_head(stu* head){
stu* s= s->p;
while(s!= NULL){
stu* r = s;
s= s->p;
delete r;
}
}
int main()
{
head = new stu;
head->p = NULL;
head->pno = NULL;
head->pclass = NULL;
head->pscore = NULL;
int Input;
while(cin >> Input){
if(Input == 1 || Input == 10 ) cout<<"select:"<<endl;
if(Input == 1){
int no, classno, score;
string name;
cin >> no >> name >> classno >> score;
headlist(no, name, classno, score);
}
else if(Input == 2){
print_all(head);
}
else if(Input == 3){
Sort_no(head);
}
else if(Input == 4){
Sort_no(head);
print_no(head);
}
else if(Input == 5){
Sort_classno(head);
}
else if(Input == 6){
Sort_classno(head);
print_classno(head);
}
else if(Input == 7){
Sort_score(head);
}
else if(Input == 8){
Sort_score(head);
print_score(head);
}
else if(Input == 9){
clear_head(head);
}
else if(Input == 10){
break;
}
}
}
版权声明：本文为m0_62779494原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。