数据结构实验3栈和队列.doc

《数据结构实验3栈和队列.doc》由会员分享，可在线阅读，更多相关《数据结构实验3栈和队列.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验（三）实验目的：1、 掌握栈的顺序存储结构的特点及算法描述。2、 掌握顺序栈的基本操作实现，熟悉应用方法。3、 掌握队列顺序存储结构的特点及算法描述4、 掌握顺序队列基本操作的实现，熟悉应用的方法。实验课时：4课时实验内容1、 在键盘上接收一串带括号的字符串 ，判断括号是否匹配，如果匹配，输出正确，如果不匹配，输出第一对不匹配的括号，并显示错误。例如：pp)输出 and and )errorerror具体程序如下，请同学们仔细阅读，并在提示下，在有下划线的地方填上程序，#include datastru.h#include stdio.hvoid initstack(SEQSTAC

2、K *s)/*顺序栈初始化*/ s-top = 0; DATATYPE1 sempty(SEQSTACK *s) /*判栈空*/if(s-top= 0)return 1;else return 0; int push(SEQSTACK *s, DATATYPE1 x)/*元素x入栈*/ if(s-top = MAXSIZE - 1) printf(栈满n); return 0; else s-top+; (s-data)s-top = x; return 1; DATATYPE1 pop(SEQSTACK *s) /*返回栈顶元素并删除栈顶元素*/DATATYPE1 x; if(s-top =

3、 0) x = 0; else x = (s-data)s-top; s-top-; return x; DATATYPE1 gettop(SEQSTACK *s)/*返回栈顶元素*/ DATATYPE1 x; if(s-top = 0) printf(栈空n); x = 0; else x = (s-data)s-top; return x; void check(SEQSTACK *s)char ch,dh;printf(n请输入一串括号，回车键结束 ：);ch = getchar();while(ch != n) if(ch=(|ch=|ch=) /如果遇到左括号 push(s,ch);

4、 /把左括号入栈 if(ch=)|ch=|ch=) /如果遇到右括号 /出栈，并把出栈的值赋给变量dh if(sempty(s) /如果栈为空 printf(缺失左括号！);break; /跳出循环 dh=pop(s); printf(%c和%cn,dh,ch); if(ch=(&dh!=)|ch=&dh!=|ch=&dh!=)/如果dh和ch不匹配 printf(n括号匹配错误n); break; /跳出循环 ch = getchar(); /*继续处理*/ if(ch=n & sempty(s) /如果字符串结束并且栈为空printf(n括号配对正确n); if(sempty(s)=0)

5、/如果栈不为空printf(n缺失右括号n);main() SEQSTACK st, *s; s = &st; initstack(s); check(s);2、添加一个函数dTOb(),利用栈的原理实现十进制转换成二进制。 #define DATATYPE1 int#include math.h#include stdio.h#define MAXSIZE 100typedef struct DATATYPE1 dataMAXSIZE; int top;SEQSTACK;void initstack(SEQSTACK *s) /*初始化空栈*/s-top = 0; int empty(SEQ

6、STACK *s) /*判栈空*/if(s-top = 0)return 1;else return 0; int push(SEQSTACK *s, DATATYPE1 x) /*进栈*/ if(s-top = MAXSIZE - 1) printf(Overflown); return 0;elses-top+; s-datas-top = x; return 1; DATATYPE1 pop(SEQSTACK *s) /*出栈*/DATATYPE1 x;if(empty(s)printf(Underflown); x = NULL;else x = (s-data)s-top; s-to

7、p-;return x;int stacklen(SEQSTACK *s) /*计算栈中元素个数*/return(s-top ); void output_stack(SEQSTACK *s) /*输出栈中元素*/int i;printf(buttom:);for(i=1;itop;i+) printf(%d:,s-datai);printf(topn);DATATYPE1 dTOb(DATATYPE1 x) int j,i,er=0;if(x!=0) for(i=1;x!=1;i+) j=x%2; x=x/2;er+=j*pow(10,(i-1); er+=1*pow(10,(i-1);re

8、turn er; main()SEQSTACK s;DATATYPE1 a;int com,i,m,k;initstack(&s); /*初始化空栈*/doprintf(n1:进栈 2: 出栈 3: 输出栈中元素 4: 栈中元素个数 5:十进制转二进制 0:退出n); printf(enter a number(0-4):); scanf(%d,&com); switch(com) case 1:printf( enter a element:); scanf(%d,&a); push(&s,a); output_stack(&s); break; case 2:a = pop(&s); pr

9、intf(pop :%d n ,a); break; case 3:output_stack(&s); break; case 4:printf(栈中有%d个元素 n,stacklen(&s); break; case 5: printf(请输入要转换的十进制数：); scanf(%d,&k);m=dTOb(k);printf(二进制为：%d,m); while(com!=0);2、队列的相关操作在循环队列中，队头指针和队尾指针在插入和删除中会发生移动而不确定，有时候Front在Rear之前，有时候Rear在Front之前，请同学们列出多种情况来输出队列。/ queueDisplay.java

10、/ displays contents of queue/ to run this program: Cjava DisplayAppimport java.io.*; / for I/O/class Queue private final int maxSize; private long queArray; private int front; private int rear; private int nItems;/- public Queue(int s) /构造队列 maxSize = s; queArray = new longmaxSize; front = 0; rear =

11、 -1; nItems = 0; /- public void insert(long j) / 入队 if(rear = maxSize-1) / deal with wraparound rear = -1; queArray+rear = j; / increment rear and insert nItems+; / one more item /- public long remove() / 出队 long temp = queArrayfront+; / get value and incr front if(front = maxSize) / deal with wrapa

12、round front = 0; nItems-; / one less item return temp; /- public long peekFront() /显示队头的第一个元素 return queArrayfront; /- public boolean isEmpty() / 判断队列是否为空 return (nItems=0); /- public boolean isFull() / 判断队列是否为满 return (nItems=maxSize); /- public void display() System.out.print(Array: ); for(int j=0

13、; jmaxSize; j+) / 输出数组元素 System.out.print( queArrayj + ); System.out.println(); System.out.print(Queue: ); if( isEmpty() = false ) / 输出队列元素 if(_) / 如果front指针在Rear指针之前 for(_) System.out.print( queArrayj + ); else / 分开输出队列 for(_) System.out.print( queArrayj + ); for(_) System.out.print( queArrayj + );

14、 System.out.println(n); / end display()/- / end class Queue/class DisplayApp public static void main(String args) throws IOException Queue theQueue = new Queue(5); / queue holds 5 items long value; while(true) System.out.print(Enter first letter of ); System.out.print(show, insert, remove: ); int ch

15、oice = getChar(); switch(choice) case s: theQueue.display(); break; case i: if( !theQueue.isFull() ) System.out.print(Enter value to insert: ); value = getLong(); theQueue.insert(value); theQueue.display(); else System.out.print(* Queue is full *n); break; case r: if( !theQueue.isEmpty() ) value = t

16、heQueue.remove(); System.out.println(Removed + value); theQueue.display(); else System.out.print(* Queue is empty *n); break; default: System.out.print(Invalid entryn); / end switch / end while / end main()/ - public static String getString() throws IOException InputStreamReader isr = new InputStrea

17、mReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; / - public static char getChar() throws IOException String s = getString(); if(s.length() = 0) / if immediate Enter return #; else return s.charAt(0); /- public static long getLong() throws IOException String s = getString(); return (long)Integer.parseInt(s); / - / end class DisplayApp/