C語言如何用順序棧實(shí)現(xiàn)回文序列判斷

更新時(shí)間：2021年10月15日 16:00:51 作者：正在學(xué)c的小白

這篇文章主要為大家介紹了C語言如何用順序棧來實(shí)現(xiàn)回文序列的判斷，文中含有詳細(xì)的代碼示例及分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助

我是采用了兩個(gè)棧值得比較大小判斷得(可能比較浪費(fèi)空間但是代碼我感覺簡單一點(diǎn))

首先是定義一個(gè)棧的結(jié)構(gòu)元素,由于是字符串類型就直接定義一個(gè)char的數(shù)組就可以:.

typedef struct stack
{
    char data[MAX_SIZE];      //儲存字符串// 
    int top;                  //記錄棧頂// 
}SeqStack;

下來就是初始化,我這里是用的耿國華老師的方法就直接給一個(gè)top元素指向棧頂,傳入的指針地址:.

void Initstack(SeqStack *S)   //初始化棧,讓top指向棧頂// 
{
	S->top=-1;
}

下面就是創(chuàng)建順序棧了,元素只要沒滿就一直可以入住:

int Push(SeqStack *S,char x)  //壓棧,只要top小于MAX_SIZE-1就可以繼續(xù)入棧// 
{
	if(S->top<=MAX_SIZE-1)
	{
	S->top++;
	S->data[S->top]=x;
    }else{
    	return -1;;
	}
}

下面是核心函數(shù),操作實(shí)現(xiàn)回文序列的判斷,我注釋的比較清楚直接看就可以了:

void Pop(SeqStack *S)        //出棧操作，也是最主要的操作// 
{
	SeqStack *p;                       
	p=(SeqStack*)malloc(sizeof(SeqStack));  //建立一個(gè)新的空棧,由于是指針類型要分配動(dòng)態(tài)地址//
	Initstack(p);                           //給新的棧進(jìn)行初始化// 
	int i=S->top/2;                         //i用來分割兩個(gè)字符串，將第二個(gè)字符串賦給新的空棧// 
	int j=i-1;                              //j用來記錄除了@之外的其他字符數(shù)量大小// 
	while(S->top!=i)                        //開始對空棧進(jìn)行賦值,對原來的棧開始清空(清空一般大小)// 
	{
		p->top++;
		p->data[p->top]=S->data[S->top];
		S->top--;
    }
    S->top=S->top-2;                        //讓原來的棧直接指向數(shù)字，跨過了字符@// 
    for(int k=0;k<i-1;k++)                  //循環(huán)次數(shù)由i-1決定，也就是出去@字符之后的其他需要比較的字符// 
    {
    	if(S->data[S->top]==p->data[p->top])  //由于棧的特點(diǎn)先進(jìn)后出,所以新棧的存儲順序和去掉@字符之后的舊棧的存儲順序是一樣的,所以這里直接比較// 
    	{
    		j--;                             //j是定義需要比較字符的大小,只要兩個(gè)棧的元素ASCLL相等j就減一，如果全部相等j為0，該字符串就是互為回文序列// 
		}
		S->top--;                            //兩個(gè)top指針向下值// 
    	p->top--;
		if(j==0)                         //判斷// 
		{
			printf("兩個(gè)字符串互為回文序列!");
		}
	}
	if(j!=0)
	{
		printf("兩個(gè)字符串不互為回文序列!");
	}
	free(p);                       //free掉分配的空間// 
}

下面附上整個(gè)代碼:

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
typedef struct stack
{
    char data[MAX_SIZE];      //儲存字符串// 
    int top;                  //記錄棧頂// 
}SeqStack;
void Initstack(SeqStack *S)   //初始化棧,讓top指向棧頂// 
{
	S->top=-1;
}
int Push(SeqStack *S,char x)  //壓棧,只要top小于MAX_SIZE-1就可以繼續(xù)入棧// 
{
	if(S->top<=MAX_SIZE-1)
	{
	S->top++;
	S->data[S->top]=x;
    }else{
    	return -1;;
	}
}
void Pop(SeqStack *S)        //出棧操作，也是最主要的操作// 
{
	SeqStack *p;                       
	p=(SeqStack*)malloc(sizeof(SeqStack));  //建立一個(gè)新的空棧,由于是指針類型要分配動(dòng)態(tài)地址//
	Initstack(p);                           //給新的棧進(jìn)行初始化// 
	int i=S->top/2;                         //i用來分割兩個(gè)字符串，將第二個(gè)字符串賦給新的空棧// 
	int j=i-1;                              //j用來記錄除了@之外的其他字符數(shù)量大小// 
	while(S->top!=i)                        //開始對空棧進(jìn)行賦值,對原來的棧開始清空(清空一般大小)// 
	{
		p->top++;
		p->data[p->top]=S->data[S->top];
		S->top--;
    }
    S->top=S->top-2;                        //讓原來的棧直接指向數(shù)字，跨過了字符@// 
    for(int k=0;k<i-1;k++)                  //循環(huán)次數(shù)由i-1決定，也就是出去@字符之后的其他需要比較的字符// 
    {
    	if(S->data[S->top]==p->data[p->top])  //由于棧的特點(diǎn)先進(jìn)后出,所以新棧的存儲順序和去掉@字符之后的舊棧的存儲順序是一樣的,所以這里直接比較// 
    	{
    		j--;                             //j是定義需要比較字符的大小,只要兩個(gè)棧的元素ASCLL相等j就減一，如果全部相等j為0，該字符串就是互為回文序列// 
		}
		S->top--;                            //兩個(gè)top指針向下值// 
    	p->top--;
		if(j==0)                         //判斷// 
		{
			printf("兩個(gè)字符串互為回文序列!");
		}
	}
	if(j!=0)
	{
		printf("兩個(gè)字符串不互為回文序列!");
	}
	free(p);                       //free掉分配的空間// 
}
int main()
{
	SeqStack S;
	char x;
	int m=0;
	Initstack(&S);
	printf("請輸入第一串字符\n");
	while(m!=2)                            //因?yàn)橹恍枰斎雰蓚€(gè)字符串的判斷，判斷條件為m！=2// 
	{
	    scanf("%c",&x);
	    if(x=='@')                           //輸入@后表明第一個(gè)字符串結(jié)束// 
	    {
	    	m++;
	        if(m==1)
	        {
	        	printf("請輸入第二串字符:\n");
	     	}
    	}
     	Push(&S,x);
    }
    Pop(&S);
	return 0;
}

下面加一個(gè)例子:

判斷3+1與1+3是否為回文序列