數(shù)據(jù)結(jié)構(gòu)-回文序列判斷

1、西安郵電學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告回文序列判斷班級(jí)：班內(nèi)序號(hào)：學(xué)生姓名：指導(dǎo)教師：時(shí)間：2011/10/13一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)內(nèi)容2三、數(shù)據(jù)結(jié)構(gòu)及算法思想2四、模塊劃分21、對(duì)各個(gè)模塊進(jìn)行功能的描述22、模塊之間關(guān)系及其相互調(diào)用的圖示3五、詳細(xì)設(shè)計(jì)及運(yùn)行結(jié)果31、設(shè)計(jì)源代碼：32、運(yùn)行結(jié)果：7六、調(diào)試情況，設(shè)計(jì)技巧及體會(huì)71、熟悉并掌握棧的的創(chuàng)建、入棧和出棧等基本用法并能運(yùn)用棧完成一些特定的任務(wù)。2、熟悉并掌握隊(duì)列的的創(chuàng)建、入隊(duì)和出隊(duì)等基本用法并能運(yùn)用隊(duì)列完成一些特定的任務(wù)。3、運(yùn)用棧和隊(duì)列實(shí)現(xiàn)對(duì)“回文”序列的判斷。二、實(shí)驗(yàn)內(nèi)容編寫(xiě)一個(gè)算法，判斷一次讀入一個(gè)以劭束符的字母序列，是否為形如序列18

2、序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'。且序列2是序列1的逆序列。例如，'a+b&b+si是屬于該模式的字符序列，'a+b&b-a'則不是。三、數(shù)據(jù)結(jié)構(gòu)及算法思想運(yùn)用棧和隊(duì)列算法，在序列依次輸入時(shí)將序列分別入棧和入隊(duì)列，利用棧FILO和隊(duì)列FIFO的特點(diǎn)，通過(guò)出棧和出隊(duì)列實(shí)現(xiàn)序列順序和逆序的比較，根據(jù)題目描述的回文序列判斷并輸出結(jié)果。四、模塊劃分1、對(duì)各個(gè)模塊進(jìn)行功能的描述本次設(shè)計(jì)共分為六個(gè)模塊，分別是：初始化模塊、輸入模塊、入棧模塊、入隊(duì)模塊、判斷模塊、輸出模塊。各個(gè)模塊功能如下表。表格1模塊功能描

3、述初始化模塊棧、隊(duì)列等初始化輸入模塊字母序列輸入入棧模塊將輸入序列入棧入隊(duì)模塊將輸入序列入隊(duì)判斷模塊將序列正、逆比較輸出模塊判斷結(jié)果輸出2、模塊之間關(guān)系及其相互調(diào)用的圖示開(kāi)始五、詳細(xì)設(shè)計(jì)及運(yùn)行結(jié)果1、設(shè)計(jì)源代碼：#include"stdio.h"#include"conio.h"#include"malloc.h"typedefstructNODEchardata;structNODE*next;LinkStack;typedefstructNode(chardata;structNode*next;LinkQueueNode;typ

4、edefstruct(LinkQueueNode*front;LinkQueueNode*rear;LinkQueue;voidInitStack(LinkStack*top)(top->next=NULL;charPush(LinkStack*top,chara)(LinkStack*temp;temp=(LinkStack*)malloc(sizeof(LinkStack);if(temp=NULL)return(0);temp->data=a;temp->next=top->next;top->next=temp;return(1);charPop(Link

5、Stack*top)(LinkStack*temp;chara;temp=top->next;if(temp=NULL)return(0);top->next=temp->next;a=temp->data;free(temp);return(a);intLengthStack(LinkStack*top)(LinkStack*temp;intcount=0;temp=top->next;while(temp!=NULL)(count+;temp=temp->next;return(count);voidInitQueue(LinkQueue*q)(q-&g

6、t;front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);q->rear=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);q->rear=q->front;q->front->next=NULL;charEnterQueue(LinkQueue*q,chara)(LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL)(NewNode->dat

7、a=a;NewNode->next=NULL;q->rear->next=NewNode;q->rear=NewNode;return(1);elsereturn(0);charOutQueue(LinkQueue*q)(LinkQueueNode*temp;chara;if(q->rear=q->front)return(0);temp=q->front->next;q->front->next=temp->next;if(q->rear=temp)q->rear=q->front;a=temp->da

8、ta;free(temp);return(a);)voidmain()(chara100,flag1=0,flag2=0,n,m;inti=0,t=0;LinkStack*top=(LinkStack*)malloc(sizeof(LinkStack);LinkQueue*q=(LinkQueue*)malloc(sizeof(LinkQueue);InitStack(top);InitQueue(q);printf("pleaseinputastringendof:n");while(ai-1!=64)(scanf("%c”,&ai);i+;)for(t

9、=0;t<i;t+)(if(at!=64)(Push(top,at);EnterQueue(q,at);)t=LengthStack(top);if(t%2=0)printf("Inputwrong!");else(for(i=0;i<t;i+)(n=Pop(top);m=OutQueue(q);if(n!=m)flag1=1;if(i=t/2)&&(n!=38)flag2=1;)if(flag1|flag2)printf("Thisisnotpalindromesequence!");elseprintf("Thi

10、sispalindromesequence!");)getch();2、運(yùn)行結(jié)果：2.1 、回文字符序列輸入:E:programC回文*hiuwenxe"pleaseinputastringendof©:qwertyytrewq©ThisispalindromesequenceJ圖22.2 非回文字符序列輸入：FdE:programC回文hru,'.en.exe"pleaseinputastringendof：qwerttreq©Thisisnotpalindzomesequence1六、調(diào)試情況，設(shè)計(jì)技巧及體會(huì)通過(guò)這次數(shù)據(jù)結(jié)構(gòu)試驗(yàn)，我學(xué)習(xí)了鏈棧的建立及其一些基本的操作方法和隊(duì)列的建立及對(duì)其的一些基本操作，充分理解了棧和區(qū)別和聯(lián)系，棧和隊(duì)列都可以通過(guò)鏈表實(shí)現(xiàn)，區(qū)別在于對(duì)其操作的節(jié)點(diǎn)位置不同，更重要的是通過(guò)這次實(shí)踐操作學(xué)會(huì)了完成一個(gè)設(shè)計(jì)的基本方法和步驟，拿到一個(gè)問(wèn)題不能急于開(kāi)始書(shū)寫(xiě)代碼要將問(wèn)題理清楚、找清思路、分好模塊再開(kāi)始敲代碼，代碼只是實(shí)現(xiàn)一個(gè)功能的工具，只有好的解決問(wèn)題的