데이터 구조 실험 2 스 택 (문자열 의 중심 대칭 여 부 를 판단)

1. 실험 목적 1. 스 택 의 순서 와 체인 저장 구 조 를 익히 기 2. 스 택 의 기본 연산 파악 3. 스 택 의 기본 연산 을 이용 하여 스 택 응용 을 완성 할 수 있 는 연산 2. 실험 내용 1. 단일 체인 표 에 n 개의 문 자 를 저장 하고 알고리즘 을 작성 하여 이 문자열 이 중심 대칭 관계 가 있 는 지 판단 할 수 있 습 니 다. 예 를 들 어 xyzzyx 는 중심 대칭 문자열 입 니 다.(알림: 단일 체인 표 의 절반 문 자 를 먼저 스 택 에 들 어간 다음 에 스 택 에서 단일 체인 표 의 반쪽 문자 와 비교 합 니 다.)

//seqstack.h
//           ，  node（  ），linklist（   ），seqstack（   ）   
#include
using namespace std;

template<class T>
struct node                       //node 
{
    T data;
    node * next;
};

template<class T>               //linklist 
class linklist
{
    private:
        node * first;        //       
        node * p;
    public:
        linklist();            //       
        linklist(T a[],int n); //       ，     n 
        ~linklist(){}          //    
        int length();          //   
        T get(int i);          //   i     
        int locate(T x);       //    x      
        void insert(int i,T x); //   i  x
        T Delete(int i);        //   i   
        void printlist();       //    
};

template<class T>
linklist::linklist()   //       
{
    first=new node;
    p= new node;
    first->next=NULL;
    p=first->next;
}

template<class T>
linklist::linklist(T a[],int n)//       ，     n 
{
    node *s;
    first=new node;
    p= new node;
    first->next=NULL;
    for(int i=0;inew node;
        s->data=a[i];
        s->next=first->next;
        first->next=s;
    }
}

template<class T>
int linklist::length()//   
{

    int count=0;
    p=first->next;
    while(p!=NULL)
    {
        p=p->next;
        count++;
    }
    return count;

}

template<class T>
T linklist::get(int i)//   i     
{

    int count=1;
    p=first->next;
    while(p!=NULL&&countnext;
        count ++;
    }
    return p->data;
}

template<class T>
int linklist::locate(T x)//    x      
{

    int count=1;
    p=first->next;
    while(p!=NULL)
    {
        if(p->data==x)return count;
        p=p->next;
        count++;
    }
    return 0;
}

template<class T>      //   i  x
void linklist::insert(int i,T x)
{

    int count=0;
    p=first;
    while(p!=NULL&&count1)
    {
         p=p->next;
         count++;
    }
    s=new node;
    s->data=x;
    s->next=p->next;
    p->next=s;
}

template<class T>    //    i
T linklist::Delete(int i)
{

    p=first;
    int count=0;
    while(p!=NULL&&count1)
    {
        p=p->next;
        count++;
    }
    q=new node;int x;
    q=p->next;
    x=q->data;
    p->next=q->next;
    delete q;
    return x;
}

template<class T>    //  
void linklist::printlist()
{

    p=first->next;
    while(p!=NULL)
    {
        cout<data;
        p=p->next;
    }
}

const int size=10;      //size         
template<class T>
class seqstack          //seqstack   
{
    private:
        T data[size];
        int top;
    public:
        seqstack(){top=-1;}     
        ~seqstack(){}

        void push(T x);    //    
        T pop();           //    
        int hui(T a[],int n);  //          
        int dui(linklist a);  //             
};

template<class T>
void seqstack::push(T x) //    
{
    data[++top]=x;
}

template<class T>
T seqstack::pop()    //    
{
    T x;
    x=data[top--];
    return x;
}

template<class T>
int seqstack::hui(T a[],int n)  //          
{
    for(int i=0;i2;i++)
    {push(a[i]);}
    for(int j=0;j2;j++)
    {if(pop()!=a[n/2+1+j])return 0;}
    return 1;
}

template<class T>
int seqstack::dui(linklist a)  //             
{
    int n=a.length();
    for(int i=1;i<=n/2;i++)
    {push(a.get(i));}
    for(int j=1;j<=n/2;j++)
    {if(pop()!=a.get(n-n/2+j))return 0;}
    return 1;
}

//main.cpp
#include
#include"seqstack.h"
using namespace std;

int main()
{
    char test[10]="xxyyxx";    //     
    seqstack<char> m;          //   
    linklist<char> a(test,6);  //              
    int b;
    b=m.dui(a);              //          
    if(b==1)cout<"  "<//    
    else cout<"   "<return 0;
}