下载文档原格式
数据结构栈和队列实验报告实验报告：数据结构栈和队列一、实验目的1.了解栈和队列的基本概念和特点；2.掌握栈和队列的基本操作；3.掌握使用栈和队列解决实际问题的方法。
二、实验内容1.栈的基本操作实现；2.队列的基本操作实现；3.使用栈和队列解决实际问题。
三、实验原理1.栈的定义和特点：栈是一种具有后进先出(LIFO)特性的线性数据结构，不同于线性表，栈只能在表尾进行插入和删除操作，称为入栈和出栈操作。
2.队列的定义和特点：队列是一种具有先进先出(FIFO)特性的线性数据结构，不同于线性表，队列在表头删除元素，在表尾插入元素，称为出队和入队操作。
3.栈的基本操作：a.初始化：建立一个空栈；b.入栈：将元素插入栈的表尾；c.出栈：删除栈表尾的元素，并返回该元素；d.取栈顶元素：返回栈表尾的元素，不删除。
4.队列的基本操作：a.初始化：建立一个空队列；b.入队：将元素插入队列的表尾；c.出队：删除队列表头的元素，并返回该元素；d.取队头元素：返回队列表头的元素，不删除。
四、实验步骤1.栈的实现：a.使用数组定义栈，设置栈的大小和栈顶指针；b.实现栈的初始化、入栈、出栈和取栈顶元素等操作。
2.队列的实现：a.使用数组定义队列，设置队列的大小、队头和队尾指针；b.实现队列的初始化、入队、出队和取队头元素等操作。
3.使用栈解决实际问题：a.以括号匹配问题为例，判断一个表达式中的括号是否匹配；b.使用栈来实现括号匹配，遍历表达式中的每个字符，遇到左括号入栈，遇到右括号时将栈顶元素出栈，并判断左右括号是否匹配。
4.使用队列解决实际问题：a.以模拟银行排队问题为例，实现一个简单的银行排队系统；b.使用队列来模拟银行排队过程，顾客到达银行时入队，处理完业务后出队，每个顾客的业务处理时间可以随机确定。
五、实验结果与分析1.栈和队列的基本操作实现：a.栈和队列的初始化、入栈/队、出栈/队以及取栈顶/队头元素等操作均能正常运行；b.栈和队列的时间复杂度均为O(1)，操作效率很高。
数据结构栈与队列的实验报告实验概述本次实验的目的是通过对栈和队列进行实现和应用，加深对数据结构中的栈和队列的理解和巩固操作技能。
栈和队列作为常见的数据结构在程序开发中得到了广泛的应用，本次实验通过 C++ 语言编写程序，实现了栈和队列的基本操作，并对两种数据结构进行了应用。
实验内容1. 栈的实现栈是一种先进后出的数据结构，具有后进先出的特点。
通过使用数组来实现栈，实现入栈、出栈、输出栈顶元素和清空栈等操作。
对于入栈操作，将元素插入到数组的栈顶位置；对于出栈操作，先将数组的栈顶元素弹出，再使其下移，即将后面的元素全部向上移动一个位置；输出栈顶元素则直接输出数组的栈顶元素；清空栈则将栈中所有元素全部清除即可。
3. 栈和队列的应用利用栈和队列实现八皇后问题的求解。
八皇后问题，是指在8×8 的国际象棋盘上放置八个皇后，使得任意两个皇后都不能在同一行、同一列或者同一对角线上。
通过使用栈来保存当前八皇后的位置，逐个放置皇后并检查是否有冲突。
如果当前位置符合要求，则将位置保存到栈中，并继续查询下一个皇后的位置。
通过使用队列来进行八数码问题的求解。
八数码问题，是指在3×3 的矩阵中给出 1 至 8 的数字和一个空格，通过移动数字，最终将其变为 1 2 3 4 5 6 7 8 空的排列。
通过使用队列，从初始状态出发，枚举每种情况，利用队列进行广度遍历，逐一枚举状态转移，找到对应的状态后进行更新，周而复始直到找到正确的答案。
实验结果通过使用 C++ 语言编写程序，实现了栈和队列的基本操作，并对八皇后和八数码问题进行了求解。
程序执行结果如下：栈和队列实现的基本操作都能够正常进行，并且运行效率较高。
栈和队列的实现方便了程序编写并加速了程序运行。
2. 八皇后问题的求解通过使用栈来求解八皇后问题，可以得到一组成立的解集。
图中展示了求解某一种八皇后问题的过程。
从左到右是棋盘的列数，从上到下是棋盘的行数，通过栈的操作，求出了在棋盘上符合不同要求（不在同一行、同一列和斜线上）的八皇后位置。
竭诚为您提供优质文档/双击可除栈和队列的实验报告篇一：栈和队列实验报告（规格为A4纸或A3纸折叠）篇二：数据结构栈和队列实验报告《数据结构》课程实验报告注：空间不够，可以增加页码。
篇三：数据结构栈和队列实验报告一、实验目的和要求(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。
二、实验环境和方法实验方法：（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。
（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。
（三）根据实验内容，编译程序。
实验环境：windowsxpVisualc++6.0三、实验内容及过程描述实验步骤：①进入Visualc++6.0集成环境。
②输入自己编好的程序。
③检查一遍已输入的程序是否有错（包括输入时输错的和编程中的错误），如发现有错，及时改正。
④进行编译和连接。
如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，根据提示找到出错位置和原因，加以改正。
再进行编译，如此反复直到不出错为止。
⑤运行程序并分析运行结果是否合理。
在运行是要注意当输入不同的数据时所得结果是否正确，应运行多次，分别检查在不同情况下结果是否正确。
实验内容：编译以下题目的程序并调试运行。
1）、编写一个程序algo3-1.cpp，实现顺的各种基本运算，并在此基础上设计一程序并完成如下功能：（1）初始化栈s；（2）判断栈s是否非空；序栈个主（3）依次进栈元素a,b,c,d,e；（4）判断栈s是否非空；（5）输出出栈序列；（6）判断栈s是否非空；（7）释放栈。
图3.1proj3_1工程组成本工程proj3_1的组成结构如图3.1所示。
数据结构栈和队列实验报告数据结构栈和队列实验报告1.实验目的本实验旨在通过设计栈和队列的数据结构，加深对栈和队列的理解，并通过实际操作进一步掌握它们的基本操作及应用。
2.实验内容2.1 栈的实现在本实验中，我们将使用数组和链表两种方式实现栈。
我们将分别实现栈的初始化、入栈、出栈、判断栈是否为空以及获取栈顶元素等基本操作。
通过对这些操作的实现，我们可将其用于解决实际问题中。
2.2 队列的实现同样地，我们将使用数组和链表两种方式实现队列。
我们将实现队列的初始化、入队、出队、判断队列是否为空以及获取队头元素等基本操作。
通过对这些操作的实现，我们可进一步了解队列的特性，并掌握队列在实际问题中的应用。
3.实验步骤3.1 栈的实现步骤3.1.1 数组实现栈（详细介绍数组实现栈的具体步骤）3.1.2 链表实现栈（详细介绍链表实现栈的具体步骤）3.2 队列的实现步骤3.2.1 数组实现队列（详细介绍数组实现队列的具体步骤）3.2.2 链表实现队列（详细介绍链表实现队列的具体步骤）4.实验结果与分析4.1 栈实验结果分析（分析使用数组和链表实现栈的优缺点，以及实际应用场景）4.2 队列实验结果分析（分析使用数组和链表实现队列的优缺点，以及实际应用场景）5.实验总结通过本次实验，我们深入了解了栈和队列这两种基本的数据结构，并利用它们解决了一些实际问题。
我们通过对数组和链表两种方式的实现，进一步加深了对栈和队列的理解。
通过实验的操作过程，我们也学会了如何设计和实现基本的数据结构，这对我们在日后的学习和工作中都具有重要意义。
6.附件6.1 源代码（附上栈和队列的实现代码）6.2 实验报告相关数据（附上实验过程中所产生的数据）7.法律名词及注释7.1 栈栈指的是一种存储数据的线性数据结构，具有后进先出(LIFO)的特点。
栈的操作主要包括入栈和出栈。
7.2 队列队列指的是一种存储数据的线性数据结构，具有先进先出(FIFO)的特点。
“数据结构和算法II”课程实验报告实验名称：栈和队列的综合应用班级姓名学号实验日期：实验机时：2 学时实验成绩：-------------------------------------------------------------------------------一.实验目的：1.熟悉栈的定义和基本操作2.熟悉队列的定义和基本操作3.掌握递归和非递归算法的实现技术和实际应用4.加深对栈结构的理解，培养解决实际问题的编程能力。
二.实验内容：（1）基本实验内容：实现Hanoi 塔的问题；完成迷宫问题或马踏棋盘问题求解。
三.程序及注释：1.Hanoi塔问题：typedef int ElementType;#ifndef _Stack_h#define _Stack_hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty( Stack S );Stack CreateStack( void );void DisposeStack( Stack S );void MakeEmpty( Stack S );void Push( ElementType X, Stack S );ElementType Top( Stack S );void Pop( Stack S );#endif#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) #include <stdlib.h>struct Node//定义栈的结构{ElementType Element;PtrToNode Next;char bianhao;};int IsEmpty( Stack S )//判断栈是否为空{return S->Next == NULL;}Stack CreateStack()//创建一个空栈{Stack S;S = malloc( sizeof( struct Node ) );if( S == NULL )FatalError( "Out of space!!!" );S->Next = NULL;MakeEmpty( S );return S;}void MakeEmpty( Stack S )//将栈置空{if( S == NULL )Error( "Must use CreateStack first" );elsewhile( !IsEmpty( S ) )Pop( S );}Void DisposeStack( Stack S )//销毁栈{MakeEmpty( S );free( S );}void Push( ElementType X, Stack S )//向栈S中插入元素n{PtrToNode TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space!!!" );else{TmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;}}Void Pop( Stack S )//推出栈顶元素{PtrToNode FirstCell;if( IsEmpty( S ) )Error( "Empty stack" );else{FirstCell = S->Next;S->Next = S->Next->Next;free( FirstCell );}}void Move(Stack x,int n,Stack z)//将第编号为n的圆盘从x移动到z{Pop(x);Push(n,z);printf("%2d:将原盘 %d 从 %c 移动到 %c\n",++c,n,x->bianhao,z->bianhao);} void hanoi(int n,Stack x,Stack y,Stack z)//汉诺塔问题解决函数{if (n==1)Move(x,1,z);else{hanoi(n-1,x,z,y);//将编号为1到n-1的圆盘从x利用z移动到yMove(x,n,z);//将编号为n的圆盘从x移动到zhanoi(n-1,y,x,z);}}// 将编号为1到n-1的圆盘从y利用x移动到zint main(){int n,i;Stack x=CreateStack();x->bianhao='x';//对栈x进行编号Stack y=CreateStack();y->bianhao='y';//对栈y进行编号Stack z=CreateStack();z->bianhao='z';//对栈z进行编号printf("请输入Hanoi塔的高度\n");scanf("%d",&n);for(i=n;i>0;i--)Push(i,x);hanoi(n,x,y,z);printf("移动完成！！！");DisposeStack(x);//销毁栈xDisposeStack(y);//销毁栈yDisposeStack(z);//销毁栈z}2.马踏棋盘typedef int ElementType;#ifndef _Stack_h#define _Stack_hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty( Stack S );Stack CreateStack( void );void DisposeStack( Stack S );void MakeEmpty( Stack S );void Push( ElementType X, Stack S );ElementType Top( Stack S );void Pop( Stack S );#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) #include <stdlib.h>struct Node//定义栈的结构{ElementType Element;PtrToNode Next;};int IsEmpty( Stack S )//判断栈是否为空{return S->Next == NULL;}Stack CreateStack()//创建一个栈{Stack S;S = malloc( sizeof( struct Node ) );if( S == NULL )FatalError( "Out of space!!!" );S->Next = NULL;MakeEmpty( S );return S;}void MakeEmpty( Stack S )//将栈制空{if( S == NULL )Error( "Must use CreateStack first" );elsewhile( !IsEmpty( S ) )Pop( S );}void DisposeStack( Stack S )//销毁栈{MakeEmpty( S );free( S );}void Push( ElementType X, Stack S )//向栈内输入一个值{PtrToNode TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space!!!" );else{TmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;}}int e;//用来暂时储存从栈里pop出的元素void Pop( Stack S )//输出栈顶的元素{PtrToNode FirstCell;if( IsEmpty( S ) )Error( "Empty stack" );else{e=S->Next->Element;FirstCell = S->Next;S->Next = S->Next->Next;free( FirstCell );}}void solve(int a,int b,Stack x,Stack y)//棋盘问题函数{int qipan[9][9]={0};qipan[a][b]=1;int i,m,n,step[10][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1},{9,0,0}}; //定义棋子行走规则Push(a,x);//向栈x输入起始位置x的值Push(b,y);//向栈y输入起始位置y的值int c[65]={0};//用于储存棋子在每个位置时所选择的路径编号for(i=1;i<3;i++){c[i]++;if(c[i]==9)//如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop出上一步棋子的位置，并设置为当前位置{c[i]=0;i=i-2;qipan[a][b]=0;Pop(x);a=e;Pop(y);b=e;continue;}m=a+step[c[i]][1];n=b+step[c[i]][2];while((!(m>0&&m<9&&n>0&&n<9))||(qipan[m][n]!=0))//当所选路径不合法时，选择下一条路径{c[i]++;//路径编号递增m=a+step[c[i]][1];n=b+step[c[i]][2];if(c[i]==9)//如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop出上一步棋子的位置，并设置为当前位置{qipan[a][b]=0;Pop(x);a=e;Pop(y);b=e;break;}}if(c[i]==9)//若当前棋子无路可走，将路径编号置0后，将位置编号回溯{c[i]=0;i=i-2;continue;}qipan[m][n]=i+1;//若路径可用，将移动后的位置输入栈内，并将当前位置设置为移动后的位置Push(m,x);Push(n,y);a=m;b=n;}int p,q;for(p=1;p<9;p++)//输出解决方案{for(q=1;q<9;q++)printf("%3d",qipan[p][q]);printf("\n");}}int main()//主函数{int a,b;Stack x=CreateStack();Stack y=CreateStack();printf("请输入马的初始位置（x,y），以空格隔开，其中x、y均为1~8区间内的整数\n");scanf("%d%d",&a,&b);solve(a,b,x,y);DisposeStack(x);DisposeStack(y);｝四.运行结果：1.hanoi塔问题：2.马踏棋盘：五.实验心得：在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。
一、实验目的1. 理解栈和队列的基本概念及其特点。
2. 掌握栈和队列的顺序存储和链式存储实现方法。
3. 熟悉栈和队列的基本操作，如入栈、出栈、入队、出队等。
4. 通过编程实践，加深对数据结构理论知识的理解。
二、实验环境1. 编程语言：Python2. 开发环境：PyCharm三、实验内容本实验主要实现栈和队列的顺序存储和链式存储，并完成以下基本操作：1. 栈的顺序存储和链式存储实现2. 队列的顺序存储和链式存储实现3. 栈的基本操作：入栈、出栈、判断栈空、获取栈顶元素4. 队列的基本操作：入队、出队、判断队空、获取队首元素四、实验代码```python# 栈的顺序存储实现class Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop() return Nonedef peek(self):if not self.is_empty():return self.items[-1] return None# 栈的链式存储实现class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedListStack:def __init__(self):self.head = Nonedef is_empty(self):return self.head is Nonedef push(self, data):new_node = Node(data)new_node.next = self.head self.head = new_nodedef pop(self):if not self.is_empty():data = self.head.dataself.head = self.head.next return datareturn Nonedef peek(self):if not self.is_empty():return self.head.datareturn None# 队列的顺序存储实现class Queue:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def enqueue(self, item):self.items.append(item)def dequeue(self):if not self.is_empty():return self.items.pop(0) return Nonedef peek(self):if not self.is_empty():return self.items[0]return None# 队列的链式存储实现class NodeQueue:def __init__(self):self.head = Noneself.tail = Nonedef is_empty(self):return self.head is Nonedef enqueue(self, data):new_node = Node(data)if self.tail is None:self.head = self.tail = new_node else:self.tail.next = new_nodeself.tail = new_nodedef dequeue(self):if not self.is_empty():data = self.head.dataself.head = self.head.nextif self.head is None:self.tail = Nonereturn datareturn Nonedef peek(self):if not self.is_empty():return self.head.datareturn None# 测试代码if __name__ == "__main__":stack = Stack()stack.push(1)stack.push(2)stack.push(3)print("栈的顺序存储：", stack.items)print("栈顶元素：", stack.peek())print("出栈元素：", stack.pop())print("栈的顺序存储：", stack.items)linked_stack = LinkedListStack()linked_stack.push(1)linked_stack.push(2)linked_stack.push(3)print("栈的链式存储：", [node.data for node in linked_stack.head]) print("栈顶元素：", linked_stack.peek())print("出栈元素：", linked_stack.pop())print("栈的链式存储：", [node.data for node in linked_stack.head]) queue = Queue()queue.enqueue(1)queue.enqueue(2)queue.enqueue(3)print("队列的顺序存储：", queue.items)print("队首元素：", queue.peek())print("出队元素：", queue.dequeue())print("队列的顺序存储：", queue.items)linked_queue = NodeQueue()linked_queue.enqueue(1)linked_queue.enqueue(2)linked_queue.enqueue(3)print("队列的链式存储：", [node.data for node in linked_queue.head]) print("队首元素：", linked_queue.peek())print("出队元素：", linked_queue.dequeue())print("队列的链式存储：", [node.data for node in linked_queue.head]) ```五、实验总结通过本次实验，我们实现了栈和队列的顺序存储和链式存储，并完成了基本操作。
数据结构实验报告栈和队列
栈（Stack）和队列（Queue）都是常用的数据结构。
它们都是有限的数据存储结构，主要用于记录数据的存储和检索。
它们具有许多相同的特征，可以根据每一个实例的需要而定制遍历，并可以使用相同的存储方法。
但是，从数据操作和操作数据的角度来看，它们仍有差异。
首先，栈和队列的数据操作模式不同。
栈是遵循“先进后出”（LIFO）的原则，只有最后一个元素可以被弹出或者取出；而队列则是遵循“先进先出”（FIFO）的原则，第一个元素是最先被取出或弹出的。
此外，栈不允许插入新元素，而队列允许任何位置插入和删除元素。
此外，栈只能被依次访问，而队列允许改变已有元素的位置。
此外，栈和队列可以用相似的实现方式来构建。
一般来说，它们都使用 .链表，数组或者树来存储数据，并使用相同的Pointers来指向数据结构中的元素。
栈和队列也可以使用交换的方式来改变其存储方式，从而提高其效率。
对于实际应用来说，栈和队列都有自己的优势，具体取决于应用中的需求。
比如，栈通常被用于数据的深度优先遍历，而队列则可以用于数据的广度优先遍历。
此外，栈也可以用于处理函数调用，而队列可以用于处理操作系统任务或者打印池中的任务等。
实验报告三栈和队列一、实验目的：（1）掌握栈的基本操作的实现方法。
（2）利用栈先进后出的特点，解决一些实际问题。
（3）掌握链式队列及循环队列的基本操作算法。
（4）应用队列先进先出的特点，解决一些实际问题。
二、实验内容：1、使用一个栈，将一个十进制转换成二进制。
粘贴源程序：package Q1;public class SeqStack {public int element[];public int top;public static SeqStack p;public SeqStack(int size){this.element=new int[size];this.top=-1;}public void push(int x){this.top++;this.element[this.top]=x;}public int pop(){return this.top==-1 ? -1: (int)this.element[this.top--];}public int get(){return this.top==-1 ? -1: (int)this.element[this.top];}public static void disp(SeqStack p){int t = -2;while(t!=-1){t=p.pop();if(t!=-1)System.out.printf("%d",t);}}public static void fun(int x){int t;while(x!=1){t=x%2;x=x/2;p.push(t);}if(x==1)p.push(x);}public static void main(String args[]){p=new SeqStack(13);fun(99);disp(p);}}粘贴测试数据及运行结果：2、回文是指正读反读均相同的字符序列，如“acdca”、“dceecd”均是回文，但“book”不是回文。
数据结构栈与队列实验报告学院：数学与计算机学院班级：计算机科学与技术姓名：***学号：************实验三栈与队列一、实验目的：（1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。
（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；（4）掌握栈的应用；二、实验要求：(1) 给出程序设计的基本思想、原理和算法描述。
(2) 对源程序给出注释。
(3) 记录程序的运行结果，并结合程序进行分析。
三、程序设计的基本思想、原理和算法描述：四、实验内容：1、利用栈的基本操作将一个十进制的正整数转换成R进制数据，并将其转换结果输出。
#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define stack_init_size 100#define stackincrement 10typedef struct sqstack {int *base;int *top;int stacksize;} sqstack;int StackInit(sqstack *s){ s->base=(int *)malloc(stack_init_size *sizeof(int));if(!s->base)return 0;s->top=s->base;s->stacksize=stack_init_size;return 1;}int Push(sqstack *s,int e){if(s->top-s->base>=s->stacksize){s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int));if(!s->base)return 0;s->top=s->base+s->stacksize;s->stacksize+=stackincrement;}*(s->top++)=e;return e;}int Pop(sqstack*s,int e){if(s->top==s->base)return0;e=*--s->top;return e;}int stackempty(sqstack*s){if(s->top==s->base){return1;}else{return0;}}int conversion(sqstack*s){int n,e=0,flag=0;printf("输入要转化的十进制数：\n");scanf("%d",&n);printf("要转化为多少进制：2进制、8进制、16进制填数字！\n"); scanf("%d",&flag);printf("将十进制数%d转化为%d进制是：\n",n,flag);while(n){Push(s,n%flag);n=n/flag;}while(!stackempty(s)){e=Pop(s,e);switch(e){case10:printf("A");break;case11:printf("B");break;case 12: printf("C");break;case 13: printf("D");break;case 14: printf("E");break;case 15: printf("F");break;default: printf("%d",e);}}printf("\n");return 0; }int main(){sqstack s;StackInit(&s);conversion(&s);return 0;}2、回文数判断#include<stdio.h>#include<string.h>#define MAX 50#define FALSE 0#define TURE 1//定义栈typedef struct{char elem[MAX];int top;}SeqStack;//定义循环队列typedef struct{char element[MAX];int front;int rear;}SeqQuene;//初始化栈void InitStack(SeqStack *S){S->top = -1;//构造一个空栈}//入栈int Push(SeqStack *S,char x,int cnt) {if(S->top == cnt-1)return(FALSE);S->top++;S->elem[S->top] = x;return(TURE);}//出栈int Pop(SeqStack * S,char * x){if(S->top == -1)return(FALSE);else{*x = S->elem[S->top];S->top--;return(TURE);}}//初始化队列void InitQuene(SeqQuene *Q){Q->front = Q->rear = 0;}//入队int EnterQuene(SeqQuene *Q,char x,int cnt) {if((Q->rear+1)%(cnt+1) == Q->front)return(FALSE);Q->element[Q->rear] = x;Q->rear = (Q->rear+1)%(cnt+1);return(TURE);}//出队int DeleteQuene(SeqQuene *Q,char *x,int cnt) {if(Q->front == Q->rear)return(FALSE);*x = Q->element[Q->front];Q->front = (Q->front+1)%(cnt+1);return(TURE);}//主函数void main(){int i,cnt,flag;SeqStack s;SeqQuene q;char a[MAX],b[MAX],c[MAX];flag=0;printf("请输入由*结束且小于%d的回文序列：\n",MAX); for(i = 0;i<MAX+1;i++){scanf("%c",&a[i]);if(a[i] == '*')break;}cnt = i;InitStack(&s);InitQuene(&q);for(i = 0;i<cnt;i++){EnterQuene(&q,a[i],cnt);Push(&s,a[i],cnt);}for(i = 0;i<cnt+1;i++){DeleteQuene(&q,&b[i],cnt);printf("%c",b[i]);}printf("\n");for(i = 0;i<cnt+1;i++){Pop(&s,&c[i]);printf("%c",c[i]);}printf("\n");for(i = 0;i<cnt+1;i++){if(b[i] == c[i])flag = 1;else{flag = 0;break;}}if(flag)printf("Right");elseprintf("Wrong");printf("\n"); }五、运行结果。
“数据结构和算法II”课程实验报告实验名称：栈和队列的综合应用班级姓名学号实验日期：实验机时：2 学时实验成绩：-------------------------------------------------------------------------------一.实验目的：1.熟悉栈的定义和基本操作2.熟悉队列的定义和基本操作3.掌握递归和非递归算法的实现技术和实际应用4.加深对栈结构的理解，培养解决实际问题的编程能力。
二.实验内容：（1）基本实验内容：实现Hanoi 塔的问题；完成迷宫问题或马踏棋盘问题求解。
三.程序及注释：1.Hanoi塔问题：typedef int ElementType;#ifndef _Stack_h#define _Stack_hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty( Stack S );Stack CreateStack( void );void DisposeStack( Stack S );void MakeEmpty( Stack S );void Push( ElementType X, Stack S );ElementType Top( Stack S );void Pop( Stack S );#endif#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) #include <stdlib.h>struct Node//定义栈的结构{ElementType Element;PtrToNode Next;char bianhao;};int IsEmpty( Stack S )//判断栈是否为空{return S->Next == NULL;}Stack CreateStack()//创建一个空栈{Stack S;S = malloc( sizeof( struct Node ) );if( S == NULL )FatalError( "Out of space!!!" );S->Next = NULL;MakeEmpty( S );return S;}void MakeEmpty( Stack S )//将栈置空{if( S == NULL )Error( "Must use CreateStack first" );elsewhile( !IsEmpty( S ) )Pop( S );}Void DisposeStack( Stack S )//销毁栈{MakeEmpty( S );free( S );}void Push( ElementType X, Stack S )//向栈S中插入元素n{PtrToNode TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space!!!" );else{TmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;}}Void Pop( Stack S )//推出栈顶元素{PtrToNode FirstCell;if( IsEmpty( S ) )Error( "Empty stack" );else{FirstCell = S->Next;S->Next = S->Next->Next;free( FirstCell );}}void Move(Stack x,int n,Stack z)//将第编号为n的圆盘从x移动到z{Pop(x);Push(n,z);printf("%2d:将原盘 %d 从 %c 移动到 %c\n",++c,n,x->bianhao,z->bianhao);} void hanoi(int n,Stack x,Stack y,Stack z)//汉诺塔问题解决函数{if (n==1)Move(x,1,z);else{hanoi(n-1,x,z,y);//将编号为1到n-1的圆盘从x利用z移动到yMove(x,n,z);//将编号为n的圆盘从x移动到zhanoi(n-1,y,x,z);}}// 将编号为1到n-1的圆盘从y利用x移动到zint main(){int n,i;Stack x=CreateStack();x->bianhao='x';//对栈x进行编号Stack y=CreateStack();y->bianhao='y';//对栈y进行编号Stack z=CreateStack();z->bianhao='z';//对栈z进行编号printf("请输入Hanoi塔的高度\n");scanf("%d",&n);for(i=n;i>0;i--)Push(i,x);hanoi(n,x,y,z);printf("移动完成！！！");DisposeStack(x);//销毁栈xDisposeStack(y);//销毁栈yDisposeStack(z);//销毁栈z}2.马踏棋盘typedef int ElementType;#ifndef _Stack_h#define _Stack_hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty( Stack S );Stack CreateStack( void );void DisposeStack( Stack S );void MakeEmpty( Stack S );void Push( ElementType X, Stack S );ElementType Top( Stack S );void Pop( Stack S );#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) #include <stdlib.h>struct Node//定义栈的结构{ElementType Element;PtrToNode Next;};int IsEmpty( Stack S )//判断栈是否为空{return S->Next == NULL;}Stack CreateStack()//创建一个栈{Stack S;S = malloc( sizeof( struct Node ) );if( S == NULL )FatalError( "Out of space!!!" );S->Next = NULL;MakeEmpty( S );return S;}void MakeEmpty( Stack S )//将栈制空{if( S == NULL )Error( "Must use CreateStack first" );elsewhile( !IsEmpty( S ) )Pop( S );}void DisposeStack( Stack S )//销毁栈{MakeEmpty( S );free( S );}void Push( ElementType X, Stack S )//向栈内输入一个值{PtrToNode TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space!!!" );else{TmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;}}int e;//用来暂时储存从栈里pop出的元素void Pop( Stack S )//输出栈顶的元素{PtrToNode FirstCell;if( IsEmpty( S ) )Error( "Empty stack" );else{e=S->Next->Element;FirstCell = S->Next;S->Next = S->Next->Next;free( FirstCell );}}void solve(int a,int b,Stack x,Stack y)//棋盘问题函数{int qipan[9][9]={0};qipan[a][b]=1;int i,m,n,step[10][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1},{9,0,0}}; //定义棋子行走规则Push(a,x);//向栈x输入起始位置x的值Push(b,y);//向栈y输入起始位置y的值int c[65]={0};//用于储存棋子在每个位置时所选择的路径编号for(i=1;i<3;i++){c[i]++;if(c[i]==9)//如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop出上一步棋子的位置，并设置为当前位置{c[i]=0;i=i-2;qipan[a][b]=0;Pop(x);a=e;Pop(y);b=e;continue;}m=a+step[c[i]][1];n=b+step[c[i]][2];while((!(m>0&&m<9&&n>0&&n<9))||(qipan[m][n]!=0))//当所选路径不合法时，选择下一条路径{c[i]++;//路径编号递增m=a+step[c[i]][1];n=b+step[c[i]][2];if(c[i]==9)//如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop出上一步棋子的位置，并设置为当前位置{qipan[a][b]=0;Pop(x);a=e;Pop(y);b=e;break;}}if(c[i]==9)//若当前棋子无路可走，将路径编号置0后，将位置编号回溯{c[i]=0;i=i-2;continue;}qipan[m][n]=i+1;//若路径可用，将移动后的位置输入栈内，并将当前位置设置为移动后的位置Push(m,x);Push(n,y);a=m;b=n;}int p,q;for(p=1;p<9;p++)//输出解决方案{for(q=1;q<9;q++)printf("%3d",qipan[p][q]);printf("\n");}}int main()//主函数{int a,b;Stack x=CreateStack();Stack y=CreateStack();printf("请输入马的初始位置（x,y），以空格隔开，其中x、y均为1~8区间内的整数\n");scanf("%d%d",&a,&b);solve(a,b,x,y);DisposeStack(x);DisposeStack(y);｝四.运行结果：1.hanoi塔问题：2.马踏棋盘：五.实验心得：在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。
