3.19Code

本文主要是介绍3.19Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【几个双指针问题！！！】

查找链表中倒数第k个结点（上一章做的不对(⊙_⊙)）

#include<iostream>using namespace std;typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;void Init(LinkList &L){L=new LNode;L->next=NULL;
}void CreateList(LinkList &L,int len){LinkList t=L;for(int i=0;i<len;i++){LinkList p;Init(p);cin>>p->data;t->next=p;t=p;}
}void GetLastK(LinkList &L,int k){//设置双指针p q,q比p快k个，q指向表尾时，p指向的就恰好是倒数第k个LinkList p=L->next;LinkList q=L->next;int cnt=1;while(q && cnt<k){q=q->next;cnt++;} while(q->next){q=q->next;p=p->next;}cout<<p->data<<endl;
}int main(){int n;cin>>n;while(n!=0){LinkList L;Init(L);CreateList(L,n);int k;cin>>k;GetLastK(L,k);cin>>n;}
} 

删除链表中绝对值相等的节点

#include<iostream>
#include<stdlib.h>
#include<string.h>using namespace std;#define MAXSIZE 1000typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;void Init(LinkList &L){L=new LNode;L->next=NULL;
}void CreateList(LinkList &L,int len){LinkList t=L;for(int i=0;i<len;i++){LinkList p;Init(p);cin>>p->data;t->next=p;t=p;}
}void DeleteAbs(LinkList &L){int Array[MAXSIZE]={0};LinkList p=L->next;LinkList pre=L;while(p){if(Array[abs(p->data)]==0){Array[abs(p->data)]++; //空间换时间		if(p->next==NULL){pre->next=NULL;break;}	pre=p;p=p->next;}else{LinkList d=p;pre->next=p->next;p=p->next;delete(d);}}}void PrintList(LinkList &L){LinkList p=L->next;while(p){cout<<p->data;if(p->next)cout<<" ";p=p->next;}cout<<endl;
}int main(){int n;cin>>n;while(n!=0){LinkList L;Init(L);CreateList(L,n);DeleteAbs(L);PrintList(L);cin>>n;}
} 

求解两个升序序列的中位数

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<cmath>using namespace std;#define MAXSIZE 1000typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;void Init(LinkList &L){L=new LNode;L->next=NULL;
}//返回链表长度 
void CreateList(LinkList &L,int len){LinkList t=L;for(int i=0;i<len;i++){LinkList p;Init(p);cin>>p->data;t->next=p;t=p;}
}int GetMid(LinkList &A,LinkList &B,int len){LinkList pa=A->next;LinkList pb=B->next;int cnt=0;int target=ceil(len/2);int myP;while(pa && pb){if(pa->data<pb->data){myP=pa->data;pa=pa->next;cnt++;}else if(pb->data<pa->data){myP=pb->data;pb=pb->next;cnt++;}else{myP=pa->data;pa=pa->next;pb=pb->next;cnt++;}if(cnt==target)return myP;} if(pa && cnt!=target){myP=pa->data;pa=pa->next;}else if(pb && cnt!=target){myP=pb->data;pb=pb->next;}return myP;
}void PrintList(LinkList &L){LinkList p=L->next;while(p){cout<<p->data;if(p->next)cout<<" ";p=p->next;}cout<<endl;
}int main(){int n;cin>>n;while(n!=0){LinkList A,B;Init(A);Init(B);CreateList(A,n);CreateList(B,n);cout<<GetMid(A,B,n*2)<<endl;cin>>n;}
} 

猴子选大王

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<cmath>using namespace std;#define MAXSIZE 1000typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;void Init(LinkList &L){L=new LNode;L->next=L;
}void CreateList(LinkList &L,int len){LinkList t=L;for(int i=0;i<len;i++){LinkList p;Init(p);p->data=i+1;t->next=p;t=p;}t->next=L;
}void Delete(LinkList &L,int toD){LinkList pre=L;LinkList p=L->next;while(p->data!=toD){pre=pre->next;p=p->next;}pre->next=p->next;}void PrintList(LinkList &L){LinkList p=L->next;while(p->next->next!=L){cout<<p->data;if(p->next)cout<<" ";p=p->next;}cout<<endl;
}void OurKing(LinkList &L,int n){int cnt=0;LinkList p=L;while(L->next->next!=L){ //表中只有一个元素时退出while(cnt!=n){p=p->next;cnt++;if(p==L)p=p->next;}cout<<p->data<<" ";//别把p指针丢了 ,下一个从它开始数 LinkList tmp=p->next==L?p->next->next:p->next; Delete(L,p->data);p=tmp; cnt=1;}cout<<L->next->data;cout<<endl;
} int main(){int n,m;cin>>m>>n;while(n!=0 && m!=0){LinkList M; //猴猴序号链表 Init(M);CreateList(M,m);OurKing(M,n);cin>>m>>n;	}
} 

基于栈的中缀表达式求值（我赌这个不考，，）

#include <iostream>
#include<cmath>
#include <iomanip>
#define MAXSIZE 1000
using namespace std;
char op[7] = { '+', '-', '*', '/', '(', ')', '=' };typedef struct 
{char *base;char *top;int stacksize;}SqStackOPTR;typedef struct 
{double *base;double *top;int stacksize;}SqStackOPND;int InitStack(SqStackOPTR &S)
{S.base=new char [MAXSIZE];if(!S.base) return 0;S.top=S.base;S.stacksize=MAXSIZE;return 1;
}int InitStack(SqStackOPND &S)
{S.base=new double [MAXSIZE];if(!S.base) return 0;S.top=S.base;S.stacksize=MAXSIZE;return 1;
}int Push(SqStackOPTR &S,char e)
{if(S.top-S.base==S.stacksize) return 0;	*S.top=e;S.top++;return 1;
}int Push(SqStackOPND &S,double e)
{if(S.top-S.base==S.stacksize) return 0;	*S.top=e;S.top++;return 1;
}double GetTop(SqStackOPND S)
{if(S.top!=S.base)return *(S.top-1);
}char GetTop(SqStackOPTR S)
{if(S.top!=S.base)return *(S.top-1);
}int Pop(SqStackOPTR &S,char &e)
{if(S.top==S.base) return 0;S.top--;e=*S.top;return 1;
}int Pop(SqStackOPND &S,double &e)
{if(S.top==S.base)	return 0;S.top--;e=*S.top;return 1;
}int In(char ch) {//判断ch是否为运算符for (int i = 0; i < 7; i++) {if (ch == op[i]) {return 1;}}return 0;
}
char Precede(char c1, char c2)
{if((c1=='('&&c2==')')||(c1=='='&&c2=='=') )return '=';elseif(((c1=='+'||c1=='-'||c1=='*'||c1=='/'||c1==')') && (c2=='+'||c2=='-'||c2==')'||c2=='='))||((c1=='*'||c1=='/'||c1==')')&&(c2=='*'||c2=='/')))return '>';elseif(((c1=='('||c1=='=')&&c2!=')'&&c2!='=')|| ((c1=='+'||c1=='-')&&(c2=='*'||c2=='/'))||c1=='('||c2=='(') return '<';else cout<<c1<<" "<<c2<<"没有输出"<<endl; 
}
double Operate(double first, char theta, double second) {//计算两数运算结果switch (theta) {case '+':return first + second;case '-':return first - second;case '*':return first * second;case '/':return first / second;}return 0;
}double EvaluateExpression(char ch) {//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈SqStackOPTR OPTR;SqStackOPND OPND;char theta;double a, b;char x, top;InitStack(OPTR);InitStack(OPND); Push(OPTR, '=');//cout<<"此时ch为："<<ch<<endl;while (ch != '=' || (GetTop(OPTR) != '=')) //表达式没有扫描完毕或OPTR的栈顶元素不为“=”{char sign='+';if(ch=='-'){sign=ch;}if(!In(ch))//不是运算符则解析数字字符串然后进操作数栈{double m=0,n=0;while(ch!='.'&&ch>='0'&&ch<='9'){//解析整数部分m=m*10+(ch-48);cin >> ch;}if(ch=='.')//解析小数部分cin >> ch;int k=1;while(ch>='0'&&ch<='9'){n=n+(ch-48)*pow(10.0,-k);k++;cin>>ch;}//	cout<<"此时ch为："<<ch<<endl;//	cout<<"数解析为:"<<m+n<<endl;if(sign=='-'){Push(OPND,-(m+n));//		cout<<"进栈:" <<-(m+n)<<endl; }	else{Push(OPND,m+n);//		cout<<"进栈:" <<m+n<<endl; }//	cout<<"此时ch为："<<ch<<endl;//	cout<<"此时栈顶元素为"<<GetTop(OPTR)<<endl;}//while 解析第一个数，整合整数部分和小数部分并将其压入栈 else//如果不是数，则比较运算符优先级 switch (Precede(GetTop(OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级{case '<'://还暂时不用对数栈运算 //	cout<<GetTop(OPTR)<<"<"<<ch<<endl;Push(OPTR, ch);//	cout<<"进栈:" <<ch<<endl;cin >> ch; //当前字符ch压入OPTR栈，读入下一字符ch//	cout<<"此时ch为："<<ch<<endl;break;case '>'://弹出该运算符并弹出两个数，进行运算 //	cout<<GetTop(OPTR)<<">"<<ch<<endl;Pop(OPTR, theta); //弹出OPTR栈顶的运算符Pop(OPND, b);Pop(OPND, a); //弹出OPND栈顶的两个运算数//	cout<<"出栈:" <<b<<theta<<a<<endl;Push(OPND, Operate(a, theta, b)); //将运算结果压入OPND栈//cout<<a<<theta<<b<<":"<<Operate(a, theta, b)<<endl;//cout<<"进栈:" <<Operate(a, theta, b)<<endl;break;case '=': //OPTR的栈顶元素是“(”且ch是“)”，括号内容已经运算完毕，现在去括号 //cout<<GetTop(OPTR)<<"="<<ch<<endl;Pop(OPTR, x);//cout<<"出栈:" <<x<<endl;cin >> ch; //弹出OPTR栈顶的“(”，读入下一字符ch//cout<<"此时ch为："<<ch<<endl;break;} //switch} //while//cout<<"GetTop(OPND);"<<GetTop(OPND)<<endl;return GetTop(OPND); //OPND栈顶元素即为表达式求值结果
}int main()
{while (1){			char ch;cin >> ch;//cout << "请输入要计算的表达式" << endl;if(ch=='=')break;double res = EvaluateExpression(ch);//算法3.22　表达式求值cout <<setiosflags(ios::fixed)<<setprecision(2)<< res <<endl;}return 0;
}

双栈的基本操作

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<cmath>using namespace std;#define MAXSIZE 1000
typedef  int  SElemType; 
typedef struct{int top[2], bot[2];      //栈顶和栈底指针(2元素因为0号1号栈)SElemType *V;        //栈数组int m;          //栈最大可容纳元素个数}DblStack;void InitDS(DblStack *S,int size){S->m=size;S->V=new SElemType[S->m * sizeof(SElemType)];S->top[0]=0;S->bot[0]=0;S->top[1]=S->m-1;S->bot[1]=S->m-1;
} int IsEmpty0(DblStack S){if(S.top[0]==S.bot[0])return 0;elsereturn 1;
} int IsEmpty1(DblStack S){if(S.top[1]==S.bot[1])return 0;elsereturn 1;
} int IsFull(DblStack S){if(S.top[0]>S.top[1])return 1;elsereturn 0;
}void Push0(DblStack *S,SElemType e){S->V[S->top[0]]=e;S->top[0]++;
}void Push1(DblStack *S,SElemType e){S->V[S->top[1]]=e;S->top[1]--;
}void Pull0(DblStack *S){S->top[0]--;cout<<S->V[S->top[0]]<<" ";}void Pull1(DblStack *S){S->top[1]++;cout<<S->V[S->top[1]]<<" ";
}int main(){int m;cin>>m; while(m!=0){DblStack S;InitDS(&S,m);int e0,e1,d0,d1;cin>>e0>>e1>>d0>>d1;for(int i=0;i<e0;i++){int e;cin>>e;Push0(&S,e);}for(int j=0;j<e1;j++){int e;cin>>e;Push1(&S,e);}cout<<IsFull(S)<<endl;for(int k=0;k<d0;k++){Pull0(&S);}cout<<IsEmpty0(S)<<endl;for(int r=0;r<d1;r++){Pull1(&S);}cout<<IsEmpty1(S)<<endl;cin>>m;}} 

回文串

中心思想是存一半！如果是奇数长度，栈顶指针就往后移动一位

栈中空间是base指针开辟的char数组

输入的是string类型

通过str.length()来获得字符串长度

#include <iostream>
#define MAXSIZE 10000
#include<string>
using namespace std;typedef struct 
{char *base;char *top;int stacksize;}SqStack;int InitStack(SqStack &S){if(!S.base) return 0;S.base=new char [MAXSIZE];S.top=S.base;S.stacksize=MAXSIZE;return 1;}int Push(SqStack &S,char e)
{if(S.top-S.base==S.stacksize)return 0;//cout<<"PUSH ERROR"<<endl;*S.top=e;S.top++;return 1;
}int GetTop(SqStack S)
{if(S.top!=S.base)return *(S.top-1);
}int Pop(SqStack &S,char &e)
{if(S.top==S.base){cout<<"POP ERROR"<<endl;return 0;}//cout<<GetTop(S)<<endl;S.top--;e=*S.top;//cout<<"e:"<<e<<endl;return 1;
}int main()
{int n=0;int num;char temp;while(1){	SqStack S;InitStack(S);string str;int i;cin>>str;if(str=="0")break;n=str.length();//cout<<n<<endl;for(i=0;i<n/2;i++){//cout<<"i:"<<i<<endl;Push(S,str[i]);}if(n%2!=0) i++;//cout<<"i:"<<i<<endl;while(i<n){char e;//cout<<"temp:"<<temp<<endl;//cout<<"i:"<<i<<"stri:"<<str[i]<<endl;Pop(S,e);temp=e;if(temp!=str[i]){//cout<<str<<endl;//cout<<"!!!	"<<temp<<"	***	"<<str[i]<<"	!!!"<<endl;cout<<"NO"<<endl; break;}if(i==n-1){cout<<"YES"<<endl;break;}i++;//cout<<"i:"<<i<<"stri:"<<str[i]<<endl;	}	}return 0;
}

这篇关于3.19Code的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---