判断串是否中心对称

设单链表中存放n个字符，试设计一个算法，使用栈判断该字符串是否中心对称，如xyzzyx即为中心对称字符串。

代码如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define Null 0#define MaxSize 50typedef char SElemType;typedef int ElemType;typedef int Status;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;Status InitStack(SqStack &S){S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}Status InitList_L(LinkList &L){L=(LinkList)malloc(sizeof(LNode));L->next=Null;return OK;}Status ListInsert_L(LinkList &L,int i,ElemType e){ElemType j=0;LinkList p=L,s;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)return ERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return OK;}Status DispList_L(LinkList &L){LinkList p=L->next;while(p){printf("%c ",p->data);p=p->next;}return OK;}Status ListLength_L(LinkList L){LinkList p=L->next;ElemType i=0;while(p){p=p->next;i++;}return(i);}Status ListGetElem_L(LinkList &L,int i,ElemType &e){LinkList p;ElemType j=1;p=L->next;while(p&&j<i){p=p->next;++j;}if(!p||j>i)return ERROR;e=p->data;return OK;}Status Push(SqStack &S,SElemType e1){if(S.top-S.base>=S.stacksize){S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e1;return OK;}Status Pop(SqStack &S,SElemType &e1){ if(S.top==S.base)return ERROR;e1=*--S.top;return OK;}Status StackEmpty(SqStack S){if(S.top==S.base)return TRUE;else return FALSE;}int main(){LinkList L,P;int flag=0;int i=1;int j=1;char t;ElemType e;SqStack S;SElemType e1;InitList_L(L);ListInsert_L(L,1,'a');ListInsert_L(L,2,'b');ListInsert_L(L,3,'c');ListInsert_L(L,4,'b');ListInsert_L(L,5,'a');printf("表为: ");DispList_L(L);InitStack(S);while(i<=ListLength_L(L)){ListGetElem_L(L,i,e);Push(S,e);i++;}printf("\n");printf("判断是否中心对称:");while(j<=ListLength_L(L)){ListGetElem_L(L,j,e);Pop(S,e1);if(e1==e);else {flag=1;break;}j++;}if(flag==1)printf("不对称\n");else printf("对称\n") ;}。

说明每个实验题目含有一个main函数和一些函数, 与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出, 供上机实验参考使用。

对于每个题目, 只需要根据题目要求设计算法, 补充函数定义, 然后对程序进行编译、调试。

实验一线性表一、实验目的1．熟悉线性表的顺序和链式存储结构2．掌握线性表的基本运算3．能够利用线性表的基本运算完成线性表应用的运算二、实验内容设有一个线性表E={e1, e2, …, en-1, en}, 设计一个算法, 将线性表逆置, 即使元素排列次序颠倒过来, 成为逆线性表E’={ en , en-1 , …, e2 , e1 }, 要求逆线性表占用原线性表空间, 并且用顺序表和单链表两种方法表示, 分别用两个程序来完成。

（文件夹: 顺序表逆置、单链表逆置）已知由不具有头结点的单链表表示的线性表中, 含有三类字符的数据元素（字母、数字和其他字符）, 试编写算法构造三个以循环链表表示的线性表, 使每个表中只含有同一类的字符, 且利用原表中的结点空间, 头结点可另辟空间。

（文件夹: 分解单链表）实验二栈和队列一、实验目的1．熟悉栈和队列的顺序和链式存储结构2．掌握栈和队列的基本运算3．能够利用栈和队列的基本运算完成栈和队列应用的运算二、实验内容1．设单链表中存放有n个字符, 试编写算法, 判断该字符串是否有中心对称的关系, 例如xyzzyx是中心对称的字符串。

（提示: 将单链表中的一半字符先依次进栈, 然后依次出栈与单链表中的另一半字符进行比较。

）（文件夹: 判字符串中心对称）假设以数组sequ[m]存放循环队列的元素, 同时设变量rear和quelen 分别指示循环队列中队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。

（文件夹：循环队列）实验三串一、实验目的1．熟悉串的顺序存储结构2．掌握串的基本运算及应用二、实验内容1. 串采用顺序存储结构, 编写朴素模式匹配算法, 查找在串中是否存在给定的子串。

课程设计题目：中心对称字符串问题作者：学号：所属院（系）：专业年级：指导老师：职称：时间：2011年6月28日目录需求分析----------------------------------- 概要设计----------------------------------- 抽象收据定义------------------------------- 详细设计----------------------------------- 测试调试----------------------------------- 总结--------------------------------------- 参考文献-----------------------------------一、需求分析1、应用环境设定(1)问题描述有n个字符的字符串，用c或c++语言编写程序判断该字符串是否中心对称。

例如，abbccdccbba与abba都是中心对称的字符串。

（2）要求采用单链表数据结构或栈数据结构的方法实现上述问题的求解。

如果采用两种或两种以上数据结构实现者，可加分。

系统编程中使用的工具主要有PC机上的编程工具，业务系统是基于Windows 7上开发的,开发工具选择的是Microsoft Visual Studio SP6。

2、程序的用户界面命令行界面按照一定规律输入字符串，然后开始检验字符串3、输入方式字符数输入字符串4、输出方式输出判定结果字符串中心对称字符串中心不对称5、数据存储方式全部在内存存放，不使用硬盘上的文件或其他数据源，程序执行过程中和结束后不保存数据。

6、程序功能判定是否为对称字符串二、概要设计单链表数据结构：用链表存储字符串，将链表前半部分倒置与后半部分比较。

单链表和栈数据结构：用单链表存储字符串，将字符串前半部分进栈、出栈行成新的链表和原来有链表比较。

三、抽象数据定义单链表数据结构typedef struct linknode{char data;struct linknode *next;} point;创建链表，将链表前半部分倒置在前半部分行程的新链表和后半部分链表逐个比较元素比较单链表和栈数据抽象typedef struct node{char data;struct node* next;}LinkList;typedef struct{char *base; //栈顶指针（始终指向栈顶元素的下一个位置） char *top; //栈底指针（始终指向栈底）}stack;LinkList* create(char s[])构造单链表void InitStack(stack &s)构造空栈void push(stack &s,char e)进栈，将字符串前半部分进栈char pop(stack &s,char &e)出栈，弹出字符进行比较int judge(LinkList *head)判断单链表是否对称四、详细设计A)单链表数据结构流程图主要功能模块抽象数据定义指针typedef struct linknode{char data;struct linknode *next;} point;输入字符数、字符串int i,n=0;point *f,*p,*q,*h,*s;cout<<"Input the number of character string: ";cin>>n;cout<<endl<<"Input the character string: ";p=(point *)malloc(sizeof(point));q=p;前半部分字符串倒置for(i=1; i<=n-1; i++){q->next=(point *)malloc(sizeof(point));q=q->next;}cin>>q->data;q->next=NULL;f=p;p=NULL;i=0;s=f;while(i<(n/2)){q=s;s=s->next;q->next=p;p=q;i++;}字符串为奇数，忽略中间数if(n%2==1)p=p->next;elseq=s;h=p;逐个比较元素值while((p!=NULL)&&(q!=NULL)&&(p->data==q->data)) {p=p->next;q=q->next;}得到判断结果if((p==NULL)&&(q==NULL))cout<<"中心对称!";elsecout<<"中心不对称!";}A)调试测试B)栈的数据结构流程图主要功能设计定义单链表的结点类型typedef struct node{char data;struct node* next;}LinkList;根据输入的字符(存储在字数组中)建立一个不带结点的单链表LinkList* create(char s[]){LinkList *head,*newNode, //newNode*tail; //tailfor(int i=0;s[i]!='\0';i++){newNode=(LinkList*)malloc(sizeof(LinkList)); //新开一个结点newNode->data=s[i];newNode->next=NULL;if(i==0) //如果只输入了一个字符{head=newNode;tail=head;}else{tail->next=newNode; //把新开的结点连接到链表的最后一个结点上tail=newNode;}}return head;}定义栈的存储类型typedef struct{char *base;char *top;}stack;void InitStack(stack &s) //栈的初始化{s.base=(char*)malloc(max*sizeof(char));s.top=s.base;}void push(stack &s,char e) //进栈函数{*s.top++=e;}char pop(stack &s,char &e) //出栈函数{e=*--s.top ;return e;}判断以单链表存储的字符串是否对称的函数int judge(LinkList *head){stack s;char e;InitStack(s); //定义一个栈并初始化LinkList* p=head; //把头指针赋给p,即让p指向第一个结点 while(p !=NULL){push(s,p->data);p=p->next;}p=head;while(p!=NULL) //将栈中的元素弹出，逐个与链表中的元素比较（可以看成是把链表换个方向，然后与原来的链表比较）switch(judge(create(str))) //根据输入的字符串(存储在字符数组中)建立单链表然后进行判断B)调试测试五、总结：更深沉次的了解数据结构，是一次比较好的集中训练。

设单链表中存放着n个字符,试编写算法,判断该字符串是否有中心对称关系#include#include#include#include <>#define LEN sizeof(struct node)#define MAX 147struct node{char cc;struct node *next;};int judge(struct node *head,int len){struct node *top,*p1,*p2;top = NULL;p1 = head->next;for(int i = 0 ; i < len/2 ; i++){p2 = (struct node *)malloc(LEN); p2->cc = p1->cc;p2->next = top;top = p2;p1 = p1->next;}if(len%2 == 1)p1 = p1->next;p2 = top;for(i = 0 ; i < len/2 ; i++){if(p2->cc != p1->cc)break;top = p2->next;p1 = p1->next;p2 = top;}if(!top)return 1;elsereturn 0;}int main(){int n=0;char str[MAX];struct node *head,*p;head = p = (struct node *)malloc(LEN); head->next = p->next = NULL;printf("请输入一个字符串：\n");gets(str);int len = strlen(str);while(n < len && str[0] != '\n'){p = (struct node *)malloc(LEN);p->cc = str[n];p->next = head->next;head->next = p;n++;}int flag = judge(head,len);if(flag)printf("%s是对称的!\n",str);elseprintf("%s不是对称的!\n",str);system("pause");return 0;}经过codeblocks 检验，完美运行——————adam如果提示error ：name lookup of i changed for iso for scoping 则在错误行输入 int i 就ok。