java舞伴配对_实验报告——栈和队列的应用

1、查询

2、增加"); c=sc.nextInt(); if(c==1){

} else{

} sc.close(); c=sc.nextInt(); list3.enQ(c); while(!(list3.isEmpty())) System.out.printf("%d \n",list3.deQ()); while(!(list3.isEmpty())) System.out.printf("%d \n",list3.deQ()); list3.enQ(a[i]);

}

}

} list1.enQ(c); while(!(list1.isEmpty())) System.out.printf("%d \n",list1.deQ()); sc.close();

粘贴测试数据及运行结果：

三、

心得体会：(含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得)

实验总结报告—栈和队列

学号：

姓名： 时间：

一、目的 1.做实验的目的

加深对线性结构栈和队列的理解，学会定义栈和队列的存储结构，加强对栈和队列操作机制的理解，掌握栈和队列的基本操作，了解栈和队列的一些应用。 2.撰写实验报告的目的

对本次实验情况进行总结，加强对实验内容的理解，对实验过程有一个系统的认识，从中获得本次试验的经验，并对实验结果进行适当的分析，加深对栈和队列的理解和认识。

二、内容

1.说明实验次数及实验内容 本次实验用一次实验课时完成 实验内容：

(1)、编写函数CreatStack_sq(), DestoryStack_sq(), Push_sq(), Pop_sq(),StackEmpty_sq() 和

StackTraverse_sq(),分别完成创建空栈,销毁栈,入栈,出栈,判断栈是否为空,遍历栈底到栈顶依

次打印栈内元素等功能(不要修改原栈),完成后进行测试。 测试要求:在main 中,建立栈；判断栈是否为空；将0~9 入栈；将栈顶两个元素出栈, 两元素求和后再入栈；从栈底到栈顶依次打印元素,再从栈顶到栈底打印元素；销毁栈。

void CreatStack_sq(SqStack &S, int msize = STACK_INIT_SIZE) { ... } void DestoryStack_sq(SqStack &S) { ... }void Push_sq(SqStack &S, ElementType e) { ... } bool Pop_sq(SqStack &S, ElementType &e) { ... } bool StackEmpty_sq(SqStack S) { ... } bool StackTraverse_sq(SqStack S) { ... } (2)、编写函数, CreateQueue_L() , DestoryQueue_L() , EnQueue_L() ,DeQueue_L(),分别完

成创建队列,销毁队列,入队列,出队列等操作,完成后进行测试。 测试要求:在主程序中,建立队列,将0~9 依次入队列,按入队列顺序出队列并打印, 销毁队列。

void CreateQueue_L(LinkQueue &Q) { } void DestoryQueue_L(LinkQueue &Q) { } void EnQueue_L(LinkQueue &Q,int e) { } bool DeQueue_L(LinkQueue &Q, int &e) { } (3)、回文是指正读反读均相同的字符序列,如”abba”和”abdba”均是回文, 但”good”不是回文。根据第四章栈和队列所学内容,试写一个算法判

定给定的字符向量是否为回文。 测试数据: 2.1 char* ch = “abccba”; 2.2 char* ch = “abccbd”; (4)、(附加题)编写函数void Knapsack(int w[],int T,int n),完成背包求解问题。 测试数据: w[6] = {2,8,6,5,1,4}; 2.做实验完成情况

实验内容在实验课时时间内完成(提前编写了大概1/3部分的代码)，选做内容也完成。

本次实验内容较多，为使代码看着简洁有条理，采用了建工程的方式。 栈部分：

自定义了头文件 L_stack.h： /*自定义头文件*/ #include

#define STACK_INIT_SIZE 100; #define STACKINCREMENT 100;

/*自定义头文件(栈相关)*/

#includetypedef char ElemType; //typedef int ElemType;

/*栈的结构体定义*/ typedef struct{

ElemType *elem; int top; int stacksize; }SqStack;

void CreateStack_sq(SqStack &S,int msize);//创建栈，msize为栈的大小 void DestroyStack_sq(SqStack &S);//销毁栈

void Push(SqStack &S, ElemType e); // 进栈操作，e为入栈元素 int Pop_sq(SqStack &S, ElemType &e);//出站操作，成功返回0，不成功返回-1 void Increment(SqStack &S, int inc_size);//增加栈空间 int StackEmpty_sq(SqStack S);//判断栈空，栈空返回0，栈非空返回-1； void StackTraverse_sq1(SqStack S);//遍历栈底到栈顶，若栈非空则依次打印栈中元素

void StackTraverse_sq2(SqStack S);//遍历栈顶到栈底，若栈非空则依次打印栈中元素

void Test_sq();//栈的检测程序

void MatchBracket_sq(char exp[]);// 括号匹配 void MatchWord_sq(char exp[]);//判断回文 void knapsack(int w[], int T, int n);//背包问题

在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。

栈的创建：

#include"L_stack.h"

void CreateStack_sq(SqStack &S,int msize){

S.elem = new ElemType[msize]; S.stacksize = msize; S.top = -1; }//end CreateStack_sq 此操作完成栈的创建，创建完成得到一个空栈。

栈的销毁：

#include"L_stack.h"

void DestroyStack_sq(SqStack &S){

delete S.elem; S.top = -1; S.stacksize = 0; }//end DestroyStack_sq 此操作将栈销毁。

入栈：

#include"L_stack.h" #include

void Push(SqStack &S, ElemType e){

if (S.top == S.stacksize0; break; case '}':

if (!Pop_sq(S, e) || e != '{') matchstat = 0; break; }//end switch ch = *exp++; }//end while

if (matchstat&&StackEmpty_sq(S)) printf("括号匹配\n"); else printf("括号不匹配\n"); }//end MatchBracket_sq 该操作完成括号的匹配；

回文判断：

#include"L_stack.h"

void MatchWord_sq(char exp[]){

int i, len=0,flag=1; SqStack S; CreateStack_sq(S, 100); char ch,e; for (i = 0; exp[i]!='\0'; i++) len++; //printf("%d\n", len); if (len % 2 != 0){ printf("非回文序列\n"); return; }//序列长度为奇数，不可能为回文序列

else{

for (i = 0; i < (len / 2); i++){

ch = exp[i];

Push(S,ch);

}//前一半元素入栈

while (i < len&&flag){

ch = exp[i];

if (!Pop_sq(S, e) || e != ch)

flag = 0;

i++; }//end while }//end else if (flag == 1) printf("回文序列\n"); else printf("非回文序列\n"); } 该操作完成回文的判断；

主函数：

#include#include

//元素与栈顶元素不匹配 #include"L_stack.h"

//#define STACK_INIT_SIZE 100;

int main(){

char exp1[20] = { '(', '8', '+', '9', ')', '/', '{', '[', '(', 'a', '*', 'b', ')', '/', '7', ']', '+', '9', '}', '#' }, exp2[20]

=

{

'}',

'8','+', '9',')','/','{','[','(','a','*','b',')','/','7',']','+','9','}','#'},

} exp3[] = "abccba", exp4[] = "abccbd"; int w[6] = { 2, 8, 6, 5, 1, 4 }; Test_sq(); MatchBracket_sq(exp1); MatchBracket_sq(exp2); MatchWord_sq(exp3); MatchWord_sq(exp4); //knapsack(w, 10, 6);

system("pause"); return 0; 主函数中调用test()完成栈的检验，以及实现括号匹配和回文判断。 实验结果：

为方便后面实现括号匹配和回文判断，我直接将0~9定义成的char型，头文件中ElemType定义成char。

第一步将0~9入栈；第二步从栈底到栈顶遍历栈中元素并打印，可以看出正确创建了栈并成功将0~9入栈；第

三、四步将栈顶元素出栈，并分别赋给e[0]、e[1]，打印操作之后的结果可以看出成功操作；第五步将e[0]、e[1]相加并入栈，从遍历栈结果来看成功操作(由于0~9存的是char型，所以是ASCII码相加得到q)；第六步从栈顶到栈底遍历栈中元素，操作正确；第七步销毁栈，从遍历栈的结果来看成功销毁栈。到此栈的功能检验结束。然后进行括号匹配和回文判断，结果正确。

接下来利用栈进行背包问题：

由于背包问题是对int型数据进行处理，为了偷点懒直接在上面的程序中进行修改

首先将头文件中ElemType定义为int;背包问题中用到的函数为 CreateStack_sq()、Pop_sq()、Push()、StackTraverse_sq1()、StackEmpty_sq()、DestroyStack_sq()，对这些函数涉及到char型的改成int型；然后将主函数中test()、MatchBracket_sq()、MatchWord_sq()注释掉；最后调用背包问题的函数： #include"L_stack.h"

void knapsack(int w[], int T, int n){

SqStack S; int k = 0,r; CreateStack_sq(S, 100); do{

while (T > 0 && k < n){

if (T - w[k] >= 0){ Push(S, k); T -= w[k]; }//end if k++; }//end while if (T == 0){

}

} printf("The Result is:\n"); StackTraverse_sq1(S); if (!StackEmpty_sq(S)){

r=Pop_sq(S, k); T += w[k]; k++; }//end if } while (!StackEmpty_sq(S) || k != n); DestroyStack_sq(S); 主函数：

#include#include#include"L_stack.h"

//#define STACK_INIT_SIZE 100;

int main(){

char exp1[20] = { '(', '8', '+', '9', ')', '/', '{', '[', '(', 'a', '*', 'b', ')', '/', '7', ']', '+', '9', '}', '#' },

exp2[20] = { '}', '8','+', '9',')','/','{','[','(','a','*','b',')','/','7',']','+','9','}','#'},

} 输出结果： exp3[] = "abccba", exp4[] = "abccbd"; int w[6] = { 2, 8, 6, 5, 1, 4 }; //Test_sq(); //MatchBracket_sq(exp1); //MatchBracket_sq(exp2); //MatchWord_sq(exp3); //MatchWord_sq(exp4); knapsack(w, 10, 6);

system("pause"); return 0;

可见操作正确。 队列部分： 自定义了头文件 Queue.h： /*自定义头文件*/

#include/*队列的结构体定义*/ typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList;

typedef LinkList Queueptr;

typedef struct{ Queueptr front; Queueptr rear; }LinkQueue;

/*自定义函数*/ void CreateQueue_L(LinkQueue &Q);//创建队列 void DestroyQueue_L(LinkQueue &Q);//销毁队列 void EnQueue_L(LinkQueue &Q, int e); //入队列操作

int DeQueue_L(LinkQueue &Q, int &e);//出队列操作，并将队首元素赋给e，返回1，队空返回0 void QueueTraverse_L(LinkQueue Q);//遍历队列元素并打印 void test();//检查队列是否正确

头文件中声明了需要用到的自定义函数，各个函数的功能见注释

创建队列：

void CreateQueue_L(LinkQueue &Q){

Q.front = Q.rear = new LNode; Q.front->next = NULL; }//end CreateQueue_L 销毁队列：

#include"Queue.h"

void DestroyQueue_L(LinkQueue &Q){

while (Q.front){

Q.rear = Q.front->next; delete Q.front; Q.front = Q.rear; }//end while }//end DestroyQueue_L 进队列： #include"Queue.h"

void EnQueue_L(LinkQueue &Q, int e){

LinkList p; p = new LNode; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; }//end EnQueue_L 出队列：

#include"Queue.h"

int DeQueue_L(LinkQueue &Q, int &e){

LinkList p; p = new LNode; if (Q.front == Q.rear) return 0; p = Q.front->next; Q.front->next = p->next;

e = p->data; if (Q.rear == p) Q.rear = Q.front; delete p; return 1; }//end DeQueue_L 主函数：

#include#include#include"Queue.h"

int main(){

} 主函数调用test()函数检验队列的正确性 test()函数： #include"Queue.h" system("pause"); return 0; test(); void test(){

} 输出结果： LinkQueue Q; int i,a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },b[10],r[10]; CreateQueue_L(Q); for (i = 0; i < 10; i++) EnQueue_L(Q, a[i]); QueueTraverse_L(Q); for (i = 0; i < 10; i++){

} r[i] = DeQueue_L(Q, b[i]); QueueTraverse_L(Q);

从输出结果来看符合要求，队列正确。

三、总结