实验二 堆栈和队列基本操作的编程实现

实验二栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。

2、会用栈和队列解决简单的实际问题。

二、实验内容（可任选或全做）题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。

所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。

相关常量及结构定义：# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define OK 1# define ERROR 0typedef int SElemType;//栈类型定义typedef struct SqStack{ SElemType *base;SElemType *top;int stacksize;}SqStack;设计相关函数声明：判断函数：int IsReverse()栈：int InitStack(SqStack &S )int Push(SqStack &S, SElemType e )int Pop(SqStack &S,SElemType &e)int StackEmpty(s)题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。

[实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。

题目三、RailsDescriptionThere is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited thattime. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.InputThe input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.The last block consists of just one line containing 0.OutputThe output contains the lines corresponding to the lines with permutations in the input.A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition,there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null'' block of the input. Sample Input51 2 3 4 55 4 1 2 366 5 4 3 2 1Sample OutputYesNoYes题目四、Sliding WindowDescriptionAn array of size n≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:The array is [1 3 -1 -3 5 3 6 7], and k is 3.Window position Minimum value Maximum value[1 3 -1] -3 5 3 6 7 -131 [3 -1 -3] 5 3 6 7 -331 3 [-1 -3 5] 3 6 7 -351 3 -1 [-3 5 3] 6 7 -351 3 -1 -3 [5 3 6] 7 361 3 -1 -3 5 [3 6 7]37Your task is to determine the maximum and minimum values in the sliding window at each position.InputThe input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.OutputThere are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.Sample Input8 31 3 -1 -3 5 3 6 7Sample Output-1 -3 -3 -3 3 33 3 5 5 6 7题目五（选作考查串知识）DNA Evolution【Description】Evolution is a seemingly random process which works in a way which resembles certain approaches we use to get approximate solutions to hard combinatorial problems. You are now to do something completely different.Given a DNA string S from the alphabet {A,C,G,T}, find the minimal number of copy operations needed to create another string T. You may reverse the strings you copy, and copy both from S and the pieces of your partial T. You may put these pieces together at any time. You may only copy contiguous parts of your partial T, and all copied strings must be used in your final T.Example: From S= “ACTG” create T= “GTACTAATAAT”1.Get GT......... by copying and reversing "TG" from S.2.Get GT AC... by copying "AC" from S.3.Get GTAC TA….. by copying "TA" from the partial T.4.Get GTACTA AT by copying and reversing "TA" from the partial T.5.Get GTACTAAT AAT by copying "AAT" from the partial T.【Input】The first line of input gives a single integer, 1 ≤k≤10, the number of test cases. Then follow, for each test case, a line with the string S , length of S is less then 19, and a line with the string T , length of T is less then 19.【Output】Output for each test case the number of copy operations needed to create T from S, or "impossible" if it cannot be done.【Sample Input】4ACGTTGCAACACGTTCGATCGAAAAAAAAAAAAAAAAAAAA【Sample output】1impossible46题目六（选作考查数组知识）Magic Squares描述Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:1 2 3 48 7 6 5In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:∙'A': exchange the top and bottom row,∙'B': single right circular shifting of the rectangle,∙'C': single clockwise rotation of the middle four squares.Below is a demonstration of applying the transformations to the initial squares given above:A:8 7 6 51 2 3 4B:4 1 2 35 8 7 6C:1 72 48 6 3 5All possible configurations are available using the three basic transformations.You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.输入A single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.输出样例输入2 6 8 4 5 73 1样例输出7BCABCCB三、实验步骤㈠、数据结构与核心算法的设计描述㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结四、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）//int IsReverse(){ ….while( (e=getchar())!='@'){e 依次入栈、入队 //push(S,e);EnQueue(Q,e);……..}While(!StackEmpty(S)) { pop(S,a);DeQueue(Q,b);If(a!=b) return 0;}return 1;}。

实验二栈和队列的操作一、实验目的1．熟悉栈和队列的存储结构；2．熟悉栈和队列的相关操作；3．利用栈和队列求解一些常见问题。

二、实验内容1、表达式求值任何一个算术表达式都是由操作数(operand) 、运算符(operator) 和界限符(edlimiter) 组成的。

为了简化问题．这里假设算术表达式中的操作数为单个数字表示的变量：运算符有加“ + ”、减“—”、乘“ * ”、除“／”和括号，表达式以“#”结束。

运算法则是括号优先级最高，先乘除，后加减，同级运算自左至右。

程序设计时需设置两个工作栈。

一个称为运算符栈，用OP 表示，用于存放表达式中的运算符：另一个称为操作数栈，用S 表示，用于存放操作数或运算结果。

这两个栈的初始状态均为空。

计算机从左至右扫描表达式，凡遇操作数一律进S 栈；若遇运算符，则要把它的优先数和栈顶运算符的优先数进行比较：若前者大，则该运算符进OP 栈；否则，栈顶运算符退栈、并进行计算，运算对象为S 栈顶上的两个元素，且先退栈的元素在运算量的右侧，后退栈的在运算量的左侧。

试编写一程序，先输入一个表达式，再求表达式的值。

2、数制转换假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

从计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。

因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按“后进先出”的规律进行的，所以用栈最合适。

试编写一个程序，实现将十进制数转换成八进制数并输出。

三、主要任务1、完成算法设计和程序设计，并分析算法时间复杂度和空间复杂度；2、写出程序运行情况，写出输入数据及运行结果；3、撰写实验报告，写出算法设计小结和心得。

四、思考题1、为什么说栈是一种特殊线性表？它的操作与线性表有什么不同？2、对于数制转换算法，如果不用栈如何实现？。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==队列操作实验报告篇一：栈和队列基本操作实验报告实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求：堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】验证性实验（学时数：2H）【实验内容】内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。

可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【实验分析、说明过程】【思考问题】【实验小结】 ( 总结本次实验的重难点及心得、体会、收获)【附录-实验代码】篇二：队列存储与操作实验报告实验四队列存储与操作一. 实验目的1、掌握队列顺序存储结构（循环队列）及实现及操作2、掌握队列的链接存储结构及实现及操作二. 实验内容1、建立一个空顺序存储结构队列；对已建立的队列进行插入、删除、取队头元素等基本操作。

2、建立一个空链式存储结构队列；对已建立的队列进行插入、删除、取队头元素等基本操作。

三、详细设计：1、顺序队列的实现：#include<iostream>using namespace std;const int Size=100;typedef char DataType;class CirQueue{public:CirQueue() { } ~CirQueue(){} void EnQueue(DataType x){if((rear+1)%Size==front) {} cout<<"队列已经满了"<<endl; return; front=rear=0;//构造队列，初始化一个空的循环队列，front和rear指向};} data[rear]=x; cout<<x<<"已入队"<<endl; return; DataTypeGetQueue()//取队头 { } DataType DeQueue() { } int isEmpty()//是否为空{ } DataType data[Size]; int front,rear; if(front==rear) { } else{ } return 0; return 1; if(isEmpty()) {} front=(front+1)%Size;//队头指针在循环的意义下加 return data[front]; cout<<"队列为空"<<endl; return 0; if(isEmpty()) {} int i; i=(front+1)%Size; return data[i]; cout<<"队列为空"<<endl; return 0; private:int main(){int index; DataType temp; do{cout<<"**********************************"<<endl; cout<<"1、入队操作"<<endl; cout<<"2、取队头操作"<<endl; cout<<"3、出队操作"<<endl;cout<<"4、判断队列是否为空"<<endl; cout<<"5、退出"<<endl;cout<<"**********************************"<<endl; cin>>index;if(index==5){return 0;} switch(index) { case 1:cout<<"请输入要入队的元素"<<endl; cin>>temp; a.EnQueue(temp); break; temp=a.GetQueue();if(temp!=0) { } cout<<"队头的元素为"<<temp<<" "<<endl;case 2: break; temp=a.DeQueue(); if(temp!=0) { } cout<<"出队的元素为"<<temp<<""<<endl; case 3: break; bool temp; temp=a.isEmpty(); if(temp){cout<<"空队"<<endl; cout<<"非空队"<<endl; }else{ case 4:} } break; }while(index); return 0;2、链队列的实现： #include<iostream> using namespace std;const int Size=100; typedef char DataType; struct Node{};class LinkQueue {public:LinkQueue() { } ~LinkQueue(){} void EnQueue(DataType x) {} DataType GetQueue()//取?队ó头? {if(isEmpty()) {} cout<<"队ó列为a空?"<<endl; return 0; auto s=new Node; s->data=x; s->next=NULL;//申Θ?请?一?个?数簓据Y域?为aX的?结á点?s rear->next=s; rear=s; auto head=new Node; head->next=NULL; front=rear=head; DataType data; Node *next;};} return front->next->data; DataType DeQueue() { } int isEmpty()//是?否?为a空? { } Node*front,*rear;//队ó头?和í队ó尾2指?针?if(front==rear) { } else{ } return 0; return 1; if(isEmpty()) {} auto p=new Node;//用?于?暂Y存?队ó头?元a素? DataType x;//用?于?暂Y存?队ó头?数簓据Y p=front->next; x=p->data; front->next=p->next;if (p->next==NULL) { } delete p; return x; rear=front; cout<<"队ó列为a空?"<<endl; return 0; private:int main() {LinkQueue a; int index; DataType temp; do{cout<<"**********************************"<<endl; cout<<"1、￠入?队ó操ù作痢?<<endl;篇三：队列存储与操作实验报告实验四队列存储与操作一、实验目的1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活运用。

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
数据结构
实验报告
实验二堆栈和队列基本操作的编程实现
【实验目的】
堆栈和队列基本操作的编程实现
要求：
堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】
验证性实验（学时数：2H）
【实验内容】
内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。

可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【注意事项】
1.开发语言：使用C。

2.可以自己增加其他功能。

【实验分析、说明过程】
【思考问题】
【实验小结】 (总结本次实验的重难点及心得、体会、收获)。

栈和队列基本操作实验报告实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求:堆栈和队列基本操作的编程实现(2学时，验证型)，掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】验证性实验(学时数:2H)【实验内容】内容:把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。

可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【实验分析、说明过程】分析:进栈操作先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下: 将新结点p的指针域指向原栈顶S(执行语句p->next=S)。

将栈顶S指向新结点p(执行语句S=p)。

注:进栈操作的?与?语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。

出栈操作先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下: 结点p 指针域指向原栈顶S(执行语句p=S)。

栈顶S指向其的下一个结点(执行语句S=S->next)释放p结点空间(执行语句free(p))。

队列分析:用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。

队列中元素的结构和前面单链表中的结点的结构一样。

为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。

【思考问题】1. 栈的顺序存储和链表存储的差异,答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。

链表存储:通过链表的存储可以实现链表中任意位置的插入元素，删除任意元素，可以实现无序进出。

2. 还会有数据移动吗,为什么,答:栈的顺序存储不会有数据移动，移动的只是指向该数据地址的指针。

实践教学*******************软件学院2012学年秋季学期上机实验报告册课程名称：_________________________实验名称：_________________________指导教师：_________________________小组成员： ********************* ********************* ***********堆栈和队列的基本操作(上机二）一实验目的1.熟悉栈这种特殊现行结构特性；2.熟悉并掌握栈在顺序存储结构和链表存储结构下的基本运算；3.熟悉队列这种特殊线性结构的特性；4.熟悉掌握队列在链表存储结构下的基本运算；二实验原理堆栈顺序存储结构下的基本算法堆栈链式存储结构下的基本算法队列顺序存储结构下的基本算法队列顺序存储结构下的基本算法1、堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。

允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。

2、堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。

每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。

3、堆栈的存储结构：（1）顺序存储结构：栈的顺序存储结构称为顺序栈。

顺序栈的本质是顺序表的简化。

（2）链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。

链栈的插入和删除操作只需处理栈顶的情况。

4、队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。

允许进行插入的一端称为队尾，允许进行删除的一端称为队头。

队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。

5、队列的存储结构队列的存储结构同线性表一样，可以分为顺序结构和链式结构。

数据结构实验报告实验名称：实验2——栈和队列1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2 实验内容利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析主程序：#include<iostream>using namespace std;const int StackSize=8; //皇后的个数int num=0;template <class T>class SeqStack //定义顺序栈模板类{public:SeqStack(){top=-1;} //构造函数，初始化空栈void Push(T x); //入栈操作void Pop();//出栈操作void PlaceQueen(int row); //放置皇后bool Judgement();//判断是否符合条件void Print();//输出符合条件的皇后排列bool Empty(){if(top==-1) return true;else return false;}; //判断栈是否为空private:T data[StackSize]; //定义数组int top; //栈顶指针};template <class T>void SeqStack<T>::Push(T x) //入栈操作{if(top>=StackSize-1) throw"上溢";top++;//栈顶指针上移data[top]=x;}template <class T>void SeqStack<T>::Pop()//出栈操作{if(Empty()) throw"下溢";top--;//栈顶指针下移}template <class T>bool SeqStack<T>::Judgement()//判断该位置是否合适{for(int i=0;i<top;i++)if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否满足任意两个皇后不在同列同一斜线return false;return true;}template <class T>void SeqStack<T>::PlaceQueen(int row) //放置皇后{for (int i=0;i<StackSize;i++){Push(i); //入栈if (Judgement())//判断位置是否合适{if (row<StackSize-1)PlaceQueen(row+1); //如果合适满足条件则放置一个皇后,递归调用else{num++;//不满足条件则到下一行Print();//输出符合条件的皇后}}Pop();//出栈}}template <class T>void SeqStack<T>::Print()//输出皇后函数{cout<<"NO."<<num<<":"<<endl; for(int i=0;i<StackSize;i++){for(int j=0;j<data[i];j++){cout<<"□";}cout<<"■";for(int j=StackSize-1;j>data[i];j--){cout<<"□";}cout<<endl;}cout<<endl;}void main(){SeqStack<int> Queen;Queen.PlaceQueen(0);cout<<"总共有"<<num<<"种摆放方法。

实验2 堆栈与队列
实验目的
1．会定义顺序栈和链栈的结点类型。

2．掌握栈的插入和删除结点在操作上的特点。

3．熟悉对栈的一些基本操作和具体的函数定义。

4．会定义顺序队列和链队列的结点类型。

实验内容
程序1 舞伴问题
（1）问题描述
假设在周末舞会上，男士和女士进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一个配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

编写程序模拟上述舞伴配对问题。

（2）问题分析
根据问题描述可知，新来人员将根据性别分别在队尾插入到男队或女队。

排在队头的男士或女士优先出队，并与另一个队中的队头成员组成舞伴。

由此可见，舞伴问题中的成员关系存在着先进先出的特点，可以采用队列这种数据结构来存储两队信息。

舞伴问题中，不断有队头成员出队组成新的舞伴及新成员在队尾插入的操作，如果采用的顺序队列，由于队头元素删除后，存储空间的不可重复操作性，将导致存储空间浪费，从而造成假溢出现象的发生。

根据以上分析，采用循环队列进行存储。

程序2回文数
由于输入的一个回文数可能无穷大，所以要求使用单链表存储该数。

[问题描述]
将用户输入的数以一个单链表的方式存储。

从头扫描该单链表，将前面的一半元素入栈，若元素的总个数为奇数，则跳过中间的那个元素，然后开始循环：边退栈边在单链表中后移指针，若当前栈顶元素与单链表中当前节点的值域不相等，则退出循环。

最后如果栈空且链表比较完毕，则是回文数，否则不是回文数。

2007级数据结构实验报告实验名称：实验二栈和队列日期：2008年11月15日1．实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容2.1题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构存储结构：特殊线性表：栈，队列栈顶 栈底 链栈2.2 关键算法分析共享栈的入栈算法伪码（Push ）： 1．如果栈满，抛出上溢异常。

2．判断是插在栈1还是栈2：2.1如果在栈1插入，则栈顶指针top1加1，在top1处填入元素x ； 2.2如果在栈2插入，则栈顶指针top2加1，在top2处填入元素x 。

共享栈的出栈算法伪码（Pop ）：1. 判断是在栈1删除还是在栈2删除。

2. 若是在栈1删除，则2.1 若栈1为空栈，抛出下溢异常； 2.2 删除并返回栈1的栈顶元素；3. 若是在栈2删除，则3.1 若栈2为空栈，抛出下溢异常； 3.2 删除并返回栈2的栈顶元素。

非空链队列 空链队列共享栈的取栈顶元素算法伪码（GetTop）：1．判断是在栈1取还是栈2取；2．如果在栈1取，则2.1 若栈1不空，返回栈顶元素的值，不删除；2.2 若栈1空，返回0；3．如果在栈2取，则3.1 若栈2不空，返回栈顶元素的值，不删除；3.2 若栈2空，返回0。

链栈的入栈算法伪码（Push）：1．申请一个新的结点，数据域为x；2．将新结点插在栈顶；3．栈顶指针重新指向栈顶元素。

链栈的出栈算法伪码（Pop）：1．如果栈空，抛出下溢异常；2．暂存栈顶元素；3．将栈顶结点摘链；4．删除该结点，返回该元素的值。

链栈的取栈顶元素算法的伪码（GetTop）：1．如果栈非空，返回栈顶元素的值，不删除。

实验二栈与队列的基本操作与实现一、实验目的：利用高级程序设计语言来实现抽象数据类型栈与队列，进一步熟悉其表示和实现方法，用已经实现的操作来组合新的操作，为以后的利用栈和队列分析和解决问题打下基础。

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验要求：1、定义栈的抽象数据类型，并用顺序栈或链栈实现其基本操作：初始化，判断栈空、栈满，出栈、入栈，取栈顶元素等2、定义队列的抽象数据类型，构造循环队列实现其基本操作：初始化，判断队空、队满，出队、入队等3、编写和调试完成程序4、保存和打印程序的运行结果三、测试数据字符的序列为ABCDEFG执行进出栈的次序为：XXYXXYYXXXY（其中X表示进栈，Y表示出栈）栈中的元素为：AEF执行进出队的次序为：XXYXXYYXXXY（其中X表示进队，Y表示出队）栈中的元素为：EFG四、实现提示：1、栈与队列可以用数组进行存储，并定义为全局变量，以减少函数调用时参数的传递。

（即在函数体外面定义变量，全局变量可以为本文件中其他函数所共用，其有效范围为从定义变量的位置开始到本源文件结束）栈：#define MAXN 26char stack[MAXN];int top=0;队列：#define MAXN 26char q[MAXN];int head = 0, tail = 0;2、主控函数示例：void main(){int n,x1,x2,select;char x,y;printf("input a stack length(1<=n<=26)):\n");scanf("%d",&n);printf("select 1:Display()\n");//显示栈中的元素printf("select 2:Push()\n");//进栈printf("select 3:Pop()\n");//出栈printf("select 4:StackTop()\n");//取出栈顶的元素，但并不出栈printf("select 0:exit\n");//退出printf("input a your select(0-4):\n");scanf("%d",&select);while(select!=0){switch(select){ case 1: Display();break;case 2: printf("input a push a value:\n");scanf("%c",&x);scanf("%c",&y);Push(x);break;case 3: x1=Pop();printf("x1->%d\n",x1);break;case 4: x2=StackTop();printf("x2->%d",x2);break;}printf("select 1:Display()\n");printf("select 2:Push()\n");printf("select 3:Pop()\n");printf("select 4:StackTop()\n");printf("select 0:exit");printf("input a your select(0-4):\n");scanf("%d",&select);}}3、队列基本操作的实现与栈类似，可以分开写，也可以写在一个主函数中。

实验2 栈和队列的基本操作和应用1实验目的(1)熟练掌握顺序栈的基本操作。

(2)掌握顺序栈的应用。

(3)掌握顺序循环队列的基本操作。

(4)掌握链式队列的基本操作。

2实验内容(1)设计一个顺序栈的基本操作的演示程序；(2)利用顺序栈，进行整数的不同进制之间的转换；(3)设计一个顺序循环队列的基本操作演示程序；(4)设计一个链式队列的基本操作演示程序。

【基本要求】I.实验内容(1)的基本要求：编写一个程序，将一个顺序栈的元素依次取出，并打印其元素值。

II.实验内容(2)的基本要求：编写一个程序，将一个非负的十进制整数转换成二进制。

III.实验内容(3)的基本要求：编写一个程序，将一个顺序队列的元素依次取出，并打印其元素值。

IV.实验内容(4)的基本要求：编写一个程序，将一个链式队列的元素依次取出，并打印其元素值。

【测试数据】自定3实验结果按照学校实验格式要求撰写实验报告，内容主要包括1）实验目的；2）实验内容；3）实验环境和方法；4）实验过程描述；5）实验心得体会参考程序如下：实验内容（1）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;//typedef char ElemType;typedef struct SqStack {ElemType *base;ElemType *top;int stacksize;}SqStack;enum Status{OK,ERROR,OVERFLOW};/*sqStackOp.h文件*/#include "sqStack.h"Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"Status InitStack(SqStack &S) {//构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(! S.base) exit(OVERFLOW); //存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;return OK;} //InitStackStatus GetTop(SqStack S,ElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top==S.base) return ERROR;e=*(S.top-1);return OK;} //GetTopStatus Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*S.top++=e;return OK;} //PushStatus Pop(SqStack &S,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(--S.top);return OK;} //Push//判断栈是否为空bool StackEmpty(SqStack &S){if(S.top == S.base)return true;elsereturn false;}/*main.cpp文件*/#include <stdio.h>#include <stdlib.h>#include "sqStackOp.h"void main(){printf("Hellow stack \n");SqStack S; //定义顺序栈Sif(OK != InitStack(S)) {printf("顺序栈初始化出错，退出....\n");exit(-1);}Push(S, 1);Push(S,2);Push(S,3);int e;Pop(S, e);printf("出栈元素= %d \n",e);Push(S,4);Push(S,5);while(!StackEmpty(S)){Pop(S, e);printf("出栈元素= %d \n",e);}/*SqStack S; char x,y;InitStack(S); x='c';y='k';Push(S,x); Push(S,'a'); Push(S,y);Pop(S,x); Push(S,'t'); Push(S,x);Pop(S,x); Push(S,'s');while(!StackEmpty(S)){ Pop(S,y);printf("%c ",y); };printf("%c ",x);*/getchar();}实验内容（2）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;typedef struct SqStack {ElemType *base;ElemType *top;int stacksize;}SqStack;enum Status{OK,ERROR,OVERFLOW};/*sqStackOp.h文件*/#include "sqStack.h"Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"Status InitStack(SqStack &S) {//构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(! S.base) exit(OVERFLOW); //存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;return OK;} //InitStackStatus GetTop(SqStack S,ElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(S.top-1);return OK;} //GetTopStatus Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*S.top++=e;return OK;} //PushStatus Pop(SqStack &S,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(--S.top);return OK;} //Push//判断栈是否为空bool StackEmpty(SqStack &S){if(S.top == S.base)return true;elsereturn false;}/*main.cpp文件*/#include <stdio.h>#include <stdlib.h>#include "sqStackOp.h"void main(){SqStack s;int x;InitStack(s);scanf("%d",&x); //%d--十进制输入；%O--八进制输入；%x--十六进制输入//修改这里输入进制和下面整除和余数计算，就可以获得其他进制的转换while(x!=0){Push(s,x%8);x=x/8;}while(!StackEmpty(s)){Pop(s,x);printf("%d ",x);}printf("\n");getchar();}实验内容（3）参考程序/*sqQueue.h 文件*/#define MAXQSIZE 100typedef int QElemType;typedef struct SqQueue {QElemType *base;int front;int rear;}SqQueue;enum Status{OK,ERROR,OVERFLOW};/*sqQueueOp.h 文件*/#include "sqQueue.h"Status InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Status DeQueue (SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);int QueueLength(SqQueue Q);/*sqQueueOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "sqQueueOp.h"Status InitQueue (SqQueue &Q) {// 构造一个空队列QQ.base = (QElemType *) malloc(MAXQSIZE *sizeof (QElemType));if (!Q.base) exit (OVERFLOW);// 存储分配失败Q.front = Q.rear = 0;return OK;}Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素if ((Q.rear+1) % MAXQSIZE == Q.front)return ERROR; //队列满Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MAXQSIZE;return OK;}Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，// 用e返回其值，并返回OK; 否则返回ERRORif (Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front+1) % MAXQSIZE;return OK;}//判断队列是否为空bool QueueEmpty(SqQueue &Q){if(Q.front== Q.rear)return true;elsereturn false;}//计算循环队列长度int QueueLength(SqQueue Q){return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;}/*main.cpp 文件*/#include <stdio.h>#include <stdlib.h>#include "sqQueueOp.h"void main(){printf("Hello Queue \n");SqQueue Q; //定义顺序队列QQElemType e;if(OK != InitQueue(Q)) {printf("顺序队列初始化出错，退出....\n");exit(-1);}EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);printf("当前队列长度= %d \n",QueueLength(Q));DeQueue(Q,e);printf("队首元素%d出队，当前队列长度=%d\n",e,QueueLength(Q));EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)){DeQueue(Q,e);printf("队首元素%d出队，当前队列长度=%d\n",e,QueueLength(Q));}getchar();}实验内容（4）参考程序/*linkQueue.h 文件*/typedef int QElemType;typedef struct QNode {// 结点类型QElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct { // 链队列类型QueuePtr front; // 队头指针QueuePtr rear; // 队尾指针} LinkQueue;enum Status{OK,ERROR,OVERFLOW};/*linkQueueOp.h 文件*/#include "linkQueue.h"Status InitQueue (LinkQueue &Q) ;Status EnQueue (LinkQueue &Q, QElemType e); Status DeQueue (LinkQueue &Q, QElemType &e) ; bool QueueEmpty(LinkQueue &Q);/*linkQueueOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "linkQueueOp.h"Status InitQueue (LinkQueue &Q) {// 构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if (!Q.front) exit (OVERFLOW);//存储分配失败Q.front->next = NULL;return OK;}Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素QueuePtr p = (QueuePtr) malloc (sizeof (QNode));if (!p) exit (OVERFLOW); //存储分配失败p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;}Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，//用e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR;QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p) Q.rear = Q.front;free (p);return OK;}//判断队列是否为空bool QueueEmpty(LinkQueue &Q){if(Q.front == Q.rear)return true;elsereturn false;}/*main.cpp 文件*/#include <stdio.h>#include <stdlib.h>#include "linkQueueOp.h"void main(){printf("Hello LinkQueue \n");LinkQueue Q; //定义顺序队列QQElemType e;if(OK != InitQueue(Q)) {printf("顺序队列初始化出错，退出....\n");exit(-1);}EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);DeQueue(Q,e);printf("队首元素%d出队，\n",e);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)){DeQueue(Q,e);printf("队首元素%d出队，\n",e);}getchar();}。

栈和队列的基本操作的实现栈和队列是两种常用的数据结构，它们都是线性表的特殊形式，但在元素的添加和删除方式上有所不同。

本文将详细介绍栈和队列的基本操作以及它们的实现方式。

一、栈的基本操作1.初始化栈：栈可以用数组或链表实现，初始化操作通常是创建一个空的数组或链表，并将栈顶指针指向-12. 入栈（push）：将一个元素添加到栈的顶部。

入栈操作需要将栈顶指针加1，并将元素存储在栈顶位置。

3. 出栈（pop）：从栈中删除栈顶元素，并返回该元素的值。

出栈操作需要先将栈顶元素弹出，然后将栈顶指针减14. 获取栈顶元素（top）：返回栈顶元素的值，但并不删除它。

这个操作只需要返回栈顶指针对应的位置的元素值即可。

5. 判断栈是否为空（isEmpty）：检查栈是否为空，即栈顶指针是否指向-1、如果为空，则返回真；否则返回假。

6. 获取栈的大小（size）：返回栈中元素的个数，即栈顶指针加1的值。

二、队列的基本操作1.初始化队列：队列可以用数组或链表实现，初始化操作通常是创建一个空的数组或链表，并初始化队头指针和队尾指针为-12. 入队（enqueue）：将一个元素添加到队列的尾部。

入队操作需要将队尾指针加1，并将元素存储在队尾位置。

3. 出队（dequeue）：从队列中删除队头元素，并返回该元素的值。

出队操作需要将队头元素弹出，然后将队头指针加14. 获取队头元素（front）：返回队头元素的值，但并不删除它。

这个操作只需要返回队头指针对应的位置的元素值即可。

5. 判断队列是否为空（isEmpty）：检查队列是否为空，即队头指针是否等于队尾指针。

如果为空，则返回真；否则返回假。

6. 获取队列的大小（size）：返回队列中元素的个数，即队尾指针减去队头指针的值。

三、栈和队列的实现方式1.数组实现：栈可以使用一维数组来实现，队列可以使用一维数组或循环数组来实现。

数组的优点是访问速度快，但大小固定，添加或删除元素时需要移动其他元素。

目录实验一线性表基本操作的编程实现 (201)实验二堆栈或队列基本操作的编程实现 (49)实验四二维数组基本操作的编程实现 (18)实验五二叉树基操作的编程实现 (20)实验六图基本操作的编程实现 (45)（特别提示：程序设计包含两个方面的错误。

其一是错误，其二是能错误。

为了提高学生的编程和能力，本指导书给出的程序代码并的两种错误。

并且也不保证程序的完整性，有一些语句已经故意删除，就是要求学生自己编制完成，这样才能达到我们的要求。

希望大家以自己所学高级语言的基本功和点为基础，不要过于依赖给出的参考代码，这样才能有所进步。

如果学生能够根据要求完全自己编制，那就不好了。

）实验一线性表基本操作的编程实现【实验目的】线性表基本操作的编程实现要求：线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结分主要功能，也可以用菜单进行管理完成大部分功能。

还鼓励学生利用基本操作进行一些更实际的应用型程序设计。

【实验性质】【实验内容】把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。

建议实现键盘输入数据以实现程序的通据的函数。

【注意事项】【思考问题】1.线性表的顺序存储和链表存储的差异？优缺点分析？2.那些操作引发了数据的移动？3.算法的时间效率是如何体现的？4.链表的指针是如何后移的？如何加强程序的健壮性？【参考代码】（一）利用顺序表完成一个班级学生课程成绩的简单管理1、预定义以及顺序表结构类型的定义(1)#define ListSize //根据需要自己设定一个班级能够容纳的最大学生数(2)typedef struct Stu{int num; //学生的学号char name[10]; //学生的姓名float wuli; //物理成绩float shuxue; //数学成绩float yingyu; //英语成绩}STUDENT; //存放单个学生信息的结构体类型typedef struct List{stu[ListSize]; //存放学生的数组定义，静态分配空间int length; //记录班级实际学生个数}LIST; //存放班级学生信息的顺序表类型2、建立班级的学生信息void listcreate(LIST *Li,int m) //m为该班级的实际人数{int i;Li->length=0;for(i=0;i<m;i++) //输入m个学生的所有信息{printf("please input the %dth student's information:\n",i+1);printf("num=");scanf("%d", ); //输入第i个学生的学号printf("name=");scanf("%s", ); //输入第i个学生的姓名printf("wuli=");scanf("%f", ); //输入第i个学生的物理成绩printf("shuxue=");scanf("%f", ); //输入第i个学生的数学成绩printf("yingyu=");scanf("%f", ); //输入第i个学生的英语成绩Li->length++; //学生人数加1}}3、插入一个学生信息int listinsert(LIST *Li,int i) //将学生插入到班级Li的第i个位置。

实验二堆栈和队列的基本操作一、上机目的:1、掌握栈的思想及其存储实现，掌握栈，队列的类型定义方法。

2、明确栈是特殊的线性表。

3、掌握栈的常见算法的程序实现：初始化栈、判栈为空、出栈、入栈，出队入队等运算。

4、掌握顺序栈，链栈，队列的简单应用。

5、理解栈，队列的算法思想，能够根据实际情况选择合适的存储结构。

二、上机要求:1、认真阅读和掌握本实验的算法。

2、上机将本算法实现。

3、保存和打印出程序的运行结果，并结合程序进行分析。

三、上机内容:堆栈（包括顺序结构、链式结构）和队列的基本操作：初始化栈、判断栈空、出栈、入栈等运算。

四．实验代码（详细设计）：顺序栈的基本操作：#include"String"typedef char ElemType;#define StackSize 100 /*顺序栈的初始分配空间*/typedef struct{ElemType data[StackSize]; /*保存栈中元素*/int top; /*栈顶指针*/} SqStack;void InitStack(SqStack &st){st.top=-1;}int Push(SqStack &st,ElemType x) /*进栈运算*/{if (st.top==StackSize-1) /*栈满*/return 0;else /*栈不满*/{st.top++;st.data[st.top]=x;return 1;}}int Pop(SqStack &st,ElemType &x) /*出栈运算*/{if (st.top==-1) /*栈空*/return 0;else /*栈不空*/{x=st.data[st.top];st.top--;return 1;}}int GetTop(SqStack st,ElemType &x) /*取栈顶元素*/ {if (st.top==-1) /*栈空*/return 0;else{x=st.data[st.top];return 1;}}int StackEmpty(SqStack st) /*判断栈空运算*/{if (st.top==-1) /*栈空*/return 1;else /*栈不空*/return 0;}void main(){ SqStack st;ElemType e;InitStack(st);printf("栈%s\n",(StackEmpty(st)==1?"空":"不空"));printf("a进栈\n");Push(st,'a');printf("b进栈\n");Push(st,'b');printf("c进栈\n");Push(st,'c');printf("d进栈\n");Push(st,'d');printf("栈%s\n",(StackEmpty(st)==1?"空":"不空"));GetTop(st,e);printf("栈顶元素:%c\n",e);printf("出栈次序:");while (!StackEmpty(st)){ Pop(st,e);printf("%c ",e);}printf("\n");}运行结果链栈的基本操作：#include <stdio.h>#include <malloc.h>typedef int ElemType;typedef struct lsnode{ElemType data;struct lsnode *next;}LinkStack;void InitStack(LinkStack *&ls){ls=NULL;}void Push(LinkStack *&ls,ElemType x){LinkStack *p;p=(LinkStack *)malloc(sizeof(LinkStack));p->data=x;p->next=ls;ls=p;}int Pop(LinkStack *&ls,ElemType &x){LinkStack *p;if(ls==NULL)return 0;else{p=ls;x=p->data;ls=p->next;free(p);return 1;}}int GetTop(LinkStack *&ls,ElemType &x){if(ls==NULL)return 0;else{x=ls->data;return 1;}}int StackEmpty(LinkStack *ls){if (ls==NULL)return 1;elsereturn 0;}void main(){LinkStack *ls;ElemType e;InitStack(ls);printf("栈%s\n",(StackEmpty(ls)==1?"空":"不空"));printf("a进栈\n");Push(ls,'a');printf("b进栈\n");Push(ls,'b');printf("c进栈\n");Push(ls,'c');printf("d进栈\n");Push(ls,'d');printf("栈%s\n",(StackEmpty(ls)==1?"空":"不空"));GetTop(ls,e);printf("栈顶元素:%c\n",e);printf("出栈次序:");while(!StackEmpty(ls)){Pop(ls,e);printf("%c",e);}printf("\n");}运行结果队列顺序结构的基本操作：#include"stdio.h"#include"String"#define QueueSize 100typedef char ElemType;typedef struct{ElemType data[QueueSize]; /*保存队中元素*/int front,rear; /*队头和队尾指针*/} SqQueue;void InitQueue(SqQueue &qu){qu.rear=qu.front=-1; /*指针初始化*/}int EnQueue(SqQueue &qu,ElemType x){if ((qu.rear+1)%QueueSize==qu.front) /*队满*/return 0;qu.rear=(qu.rear+1)%QueueSize; /*队尾指针进1*/qu.data[qu.rear]=x;return 1;}int DeQueue(SqQueue &qu,ElemType &x) /*出队运算*/ {if (qu.rear==qu.front)return 0;qu.front=(qu.front+1)%QueueSize; /*队头指针进1*/ x=qu.data[qu.front];return 1;}int GetHead(SqQueue qu,ElemType &x) /*取队头元素运算*/ {if (qu.rear==qu.front) /*队空*/return 0;x=qu.data[(qu.front+1)%QueueSize];return 1;}int QueueEmpty(SqQueue qu) /*判断队空运算*/{if (qu.rear==qu.front) /*队空*/return 1;elsereturn 0;}void main(){ SqQueue qu;ElemType e;InitQueue(qu);printf("队%s\n",(QueueEmpty(qu)==1?"空":"不空"));printf("a进队\n");EnQueue(qu,'a');printf("b进队\n");EnQueue(qu,'b');printf("c进队\n");EnQueue(qu,'c');printf("d进队\n");EnQueue(qu,'d');printf("队%s\n",(QueueEmpty(qu)==1?"空":"不空"));GetHead(qu,e);printf("队头元素:%c\n",e);printf("出队次序:");while (!QueueEmpty(qu)){ DeQueue(qu,e);printf("%c ",e);}printf("\n");}运行结果队列链式结构的基本操作：#include<stdio.h>#include<stdlib.h>#define OVERFLOW -2typedef struct QNode{//创建队成员int data;//数据成员struct QNode *next;}QNode,*QueuePtr;typedef struct{//队头队尾指针QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueue(LinkQueue &Q)//初始化队列{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//开辟空间 if(!Q.front) exit ( OVERFLOW);//开辟失败则退出Q.front ->next = NULL;//return 1;}int EnQueue(LinkQueue &Q)//入队操作{int e;QueuePtr p;printf("请输入入队元素:");scanf("%d",&e);p=(QueuePtr)malloc(sizeof(QNode));if (p==NULL) exit (OVERFLOW);p->data = e; p->next = NULL;Q.rear->next=p;//把p插入队尾Q.rear=p;//把p变为队尾return 1;}int DeQueue(LinkQueue &Q)//出队操作{QueuePtr p;int e;if ( Q.front == Q.rear){printf("队列为空\n");return -1;}p=Q.front->next;//头指针为空e=p->data;printf("%d 出对\n",e);Q.front->next =p->next;//指针后移if (Q.rear == p) Q.rear = Q.front;//如果p为队尾 free(p);//释放preturn 1;}void tip(){printf("*************\n");printf("*输入1 进队*\n");printf("*输入2 出对*\n");printf("*请选择: *\n");printf("*************\n");}int main(){int k;LinkQueue Q;InitQueue(Q);//初始化队列tip();while(scanf("%d",&k),k){switch(k){case 1:EnQueue(Q);tip();printf("操作完毕\n");break;case 2:DeQueue(Q);tip();printf("操作完毕\n");break;}}return 0;}运行结果。

栈和队列的基本操作实验项目：栈和队列的基本操作［［实验3-2］栈的链式表示和实现实验内容与要求编写一个程序实现链栈的各种基本运算.并在此基础上设计一个主程序，完成如卜-功能:（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈分析：链栈是没有附加头结点的运算受限的单链表。

栈顶指针就是链表的头指针。

注意：（1）LmkStack结构类型的定义可以方便地在函数体中修改top指针本身（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。

（3）链栈中的结点是动态分配的，所以可以不考虑上溢。

实验目的熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；二、实验内容1、实验需求（1）输入的形式和输出值的范围：scanf/#defineStack_Size100#defineSTACKINCREMENT10（2）输出的形式：int型（3）程序所能达到的功能：初始化顺序栈、插入元素、删除栈顶元素、取栈顶元素、遍历顺序栈、置空顺序栈（4）测试数据：111555666的出栈入栈2.数据结构定义确定数据对象及结构对用到的数据结构进行定义,顺序存储结构和链式存储结构存储结构的选择和定义需要说明本实验采用了什么存储结构，并给出对应程序中的定义，在栈的顺序存储结构和链式存储结构上的实现可用以下程序来定义：#defineStack_Size100#defineSTACKINCREMENT10typedefstruct{StackElementTypeelem[ Stack_Size];//用来存放栈中元素的一维数组inttop;/用来存放栈顶元素的下标，top为-1表示空栈/}SeqStack;3.主程序的流程及各程序模块之间的调用关系（1）根据实验内容确定需要实现的全部函数。

voidInitStack(SeqStackS)初始化顺序栈函数intIsEmpty(SeqStackS)判断栈S 为空栈时返回值为真，反之为假{return(S->top==-1?TRUE:FALSE);}intPush(SeqStackS,StackElementTypex)入栈函数intPop(SeqStackS,StackElementTypex)出栈函数StackDisplay(SeqStackS)显示栈SintGetT op(SeqStackS,StackElementTypex)获取栈顶元素函数if(S->top==-1)return(FALSE);else{x=S->elem[S->top];return(TRUE);}（2）主程序的调用流程图，及调用关系（入口出口）选择要进行的操作512345三、程序实现#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStackElementType;//-----栈的顺序存储表示-----#defineStack_Size100#defineSTACKINCREMENT10typedefstruct{StackElementTypeel em[Stack_Size];//用来存放栈中元素的一维数组inttop;/用来存放栈顶元素的下标，top为-1表示空栈/}SeqStack;/初始化顺序栈函数/voidInitStack(SeqStackS){/构造一个空栈S/S->top=-1;}/判栈空/intIsEmpty(SeqStackS)/判断栈S为空栈时返回值为真，反之为假/{return(S->top==-1?TRUE:FALSE);}/入栈函数/intPush(SeqStackS,StackElementTypex){//请完成本函数的功能if(S->top==Stack_Size-1)return(FALSE);/栈已满/S->top++;S->elem[S->top]=x;return(TRUE);}/出栈函数/intPop(SeqStackS,StackElementTypex){/将栈S的栈顶元素弹出，放到x所指的存储空间中///请完成本函数的功能if(S->top==-1)return(FALSE);else{x=S->elem[S->top];S->top--;return(TRUE);}}/获取栈顶元素函数/intGetT op(SeqStackS,StackElementTypex){/将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变///请完成本函数的功能if(S->top==-1)return(FALSE);else{x=S->elem[S->top];return(TRUE);}}intStackDisplay(SeqStackS){//显示栈Sinti=0;if( IsEmpty(S)){printf("堆栈已空!\n");returnOK;}while(i<=S->top)printf("[%d:%d]",++i,S->elem[i]);printf("\n");returnOK;}//StackDis playintmain(){SeqStackSt;inttemp;intflag=1,ch;inte;InitStack(&S t);//初始化堆栈Stwhile(flag){printf("请选择:\n");printf("1.显示栈中所有元素\n");printf("2.入栈\n");printf("3.出栈\n");printf("4.取栈顶元素\n");printf("5.退出程序\n");scanf("%d",&ch);switch(ch){case1:StackDisplay(&St);break;case2:printf("请输入要入栈的元素(一个整数):");scanf("%d",&e);//输入要入栈的元素temp=Push(&St,e);//入栈if(temp!=TRUE)printf("堆栈已满!入栈失败!\n");else{printf("成功入栈!\n");//成功入栈StackDisplay(&St);}break;case3:temp=Pop(&St,&e);//出栈if(te mp==FALSE)printf("堆栈已空!\n");else{printf("成功出栈一个元素:%d\n",e);//成功出栈StackDisplay(&St);}break;case4:temp=GetT op(&St,&e);//取得栈顶元素if(temp==FALSE)printf("堆栈已空!\n");elseprintf("栈顶元素是:%d\n",e);//显示栈顶元素break;default:flag=0;printf("程序结束，按任意键退出!\n");getchar();}}}四、调试分析（1）记录至少三个过程中所遇到的问题及解决办法：问题一：最初调试时数据结构中定义了栈底，后来调试过程中太过复杂，报错多，就把栈底的定义给去掉了（遵从单进单出），只用了栈顶。

《数据结构》实验报告一软件1321徐蜀实验二栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验内容1．回文判断三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。

3、严格按照数据结构实验报告模板和规范，及时完成实验报告。

四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。

附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、栈的初始长度与需要再增加的长度#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef char SElemType;//定义SElemType为char型2、栈的顺序存储表示typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;3、队列的链式表示方法typedef struct QNode{SElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;4、初始化栈/* 函数功能：对栈进行初始化参数：栈（SqStack &S）成功返回1，否则返回0 */int InitStack(SqStack &S){S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));//申请内存if(!S.base) //判断有无申请到空间return ERROR; //没有申请到内存，返回0S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}5、入栈操作/* 函数功能：将元素入栈参数：栈（SqStack &S）,插入元素e插入成功返回1，否则返回0 */int Push(SqStack &S, SElemType e){if(S.top - S.base >= S.stacksize) //判断栈顶与栈底的差是否大于栈的//容量{S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); //栈满了，重新申请内存if(!S.base) //判断是否申请成功return ERROR; //不成功返回0S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}6、出栈操作/* 函数功能：将栈中的元素弹出参数：栈(SqStack &S),记录元素e */int Pop(SqStack &S, SElemType &e){if(S.top == S.base) //判断栈是否为空return ERROR;e = *(--S.top) ;return OK;}7、初始化队列/* 函数功能：初始化队列参数：队列（LinkQueue &Q）成功返回1，否则返回0 */int InitQueue(LinkQueue &Q){Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));//申请结点的内存if(!Q.front) //判断有无申请到空间return ERROR; //没有返回0Q.front ->next = NULL;return OK;}8.在队列队尾插入元素/* 函数功能：在队列队尾插入元素参数：队列（LinkQueue &Q），插入元素e成功返回1，否则返回0 */ int EnQueue(LinkQueue &Q, QElemType e){p = (QueuePtr)malloc(sizeof(QNode)); //申请新的结点if(!p)return ERROR;p -> data = e;p -> next = NULL;Q.rear -> next = P;Q.rear = p;return OK;}9.删除队头元素/* 函数功能：删除对头元素参数：队列（LinkQueue &Q），记录值e成功返回1，否则返回0 */ int DeQueue(LinkQueue &Q, QElemType &e){if(Q.front == Q.rear) //判断队列是否为空return ERROR;p = Q.front -> next;e = p -> data;Q.front -> next = p -> next;if(Q.rear == p)Q.rear = Q.front;free(p);return OK;}10、主函数int main(){SqStack S; //声明一个栈LinkQueue Q; //声明一个队列char m,k,c;int n=0,i,j,t=0,z=0;while(!t){cout << "请输入你要判断回文的字符串，输入@结束：";InitQueue (Q);InitStack (S);while((c=getchar())!='@')//对字符的判断不断输入字符{EnQueue (Q,c);Push (S,c);n++;}for( j=1;j<=n;j++){OutQueue (Q,m);Pop (S,k);if(m!=k)break;}if(j>n) //如果j > n则说明全部相等cout << "这个字符串不是回文字符串" << endl;elsecout << "这个字符串是回文字符串" << endl;}return 0;}说明：通过调用序列号不同的函数进行各种操作。

《数据结构与算法》实验报告专业班级学号实验项目实验二栈和队列的基本操作。

实验目的1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。

2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。

实验容题目1：进制转换。

利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法提示：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要X不为0重复做下列动作将X%R入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素题目2：利用队列的方式实现辉三角的输出。

算法设计分析（一）数据结构的定义1、栈的应用实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。

因此，运用栈先进后出的性质，即可完成进制转换。

栈抽象数据结构描述typedef struct SqStack /*定义顺序栈*/{int *base; /*栈底指针*/int *top; /*栈顶指针*/int stacksize; /*当前已分配存储空间*/} SqStack;2、队列的应用由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。

即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。

队列抽象数据结构描述typedef struct SeqQueue{int data[MAXSIZE];int front; /*队头指针*/int rear; /*队尾指针*/}SeqQueue;（二）总体设计1、栈（1）主函数：统筹调用各个函数以实现相应功能int main()（2）空栈建立函数：对栈进行初始化。

int StackInit(SqStack *s)（3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。