中心对称字符串问题.doc

课程设计 题目：中心对称字符串问题 目录 需求分析----------------------------------- 概要设计----------------------------------- 抽象收据定义------------------------------- 详细设计----------------------------------- 测试调试----------------------------------- 总结--------------------------------------- 参考文献-----------------------------------  一、需求分析 应用环境设定 (1)问题描述 有n个字符的字符串，用c或c++语言编写程序判断该字符串是否中心对称。例如，abbccdccbba与abba都是中心对称的字符串。 （2）要求 采用单链表数据结构或栈数据结构的方法实现上述问题的求解。如果采用两种或两种以上数据结构实现者，可加分。 系统编程中使用的工具主要有PC机上的编程工具，业务系统是基于Windows 上开发的,开发工具选择的是Microsoft Visual Studio 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; coutInput the number of character string: ; cinn; coutendlInput 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; } cinq-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; else q=s; h=p; 逐个比较元素值 while((p!=NULL)(q!=NULL)(p-data==q-data)) { p=p-next; q=q-next; } 得到判断结果 if((p==NULL)(q==NULL)) cout中心对称!; else cout中心不对称!; } A)调试测试 B)栈的数据结构 流程图 主要功能设计 定义单链表的结点类型 typedef struct node { char data; struct node* next; }LinkList; 根据输入的字符(存储在字数组中)建立一个不带结点的单链表 LinkList* create(char s[]) { LinkList *head,