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

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

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

3、述初始化模塊棧、隊列等初始化輸入模塊字母序列輸入入棧模塊將輸入序列入棧入隊模塊將輸入序列入隊判斷模塊將序列正、逆比較輸出模塊判斷結(jié)果輸出2、模塊之間關(guān)系及其相互調(diào)用的圖示開始五、詳細設計及運行結(jié)果1、設計源代碼：#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、運行結(jié)果：2.1 、回文字符序列輸入:E:programC回文*hiuwenxe"pleaseinputastringendof©:qwertyytrewq©ThisispalindromesequenceJ圖22.2 非回文字符序列輸入：FdE:programC回文hru,'.en.exe"pleaseinputastringendof：qwerttreq©Thisisnotpalindzomesequence1六、調(diào)試情況，設計技巧及體會通過這次數(shù)據(jù)結(jié)構(gòu)試驗，我學習了鏈棧的建立及其一些基本的操作方法和隊列的建立及對其的一些基本操作，充分理解了棧和區(qū)別和聯(lián)系，棧和隊列都可以通過鏈表實現(xiàn)，區(qū)別在于對其操作的節(jié)點位置不同，更重要的是通過這次實踐操作學會了完成一個設計的基本方法和步驟，拿到一個問題不能急于開始書寫代碼要將問題理清楚、找清思路、分好模塊再開始敲代碼，代碼只是實現(xiàn)一個功能的工具，只有好的解決問題的