LAB05+队列的操作及应用
Lab05．队列的操作及应用
【实验目的和要求】
1．掌握队列的顺序表示和链表表示下的基本操作；
2．深入理解深度优先搜索和广度优先搜索的思想并能正确描述其算法；
3．会应用广度优先搜索算法解决较复杂的问题。
【实验内容】
1．编写一个C源程序，其中包含顺序表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。
2．编写一个C源程序，其中包含链表表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。
3. 简述深度优先搜索和广度优先搜索的思想，并给出具体的算法步骤。
4．应用广度优先搜索算法求解农夫过河问题。
【实验仪器与软件】
1．CPU主频在1GHz以上，内存在512Mb以上的PC；
2．VC6.0，Word 2003及以上版本。
实验讲评：
实验成绩：
评阅教师：
2012 年月日
Lab05．队列的操作及应用
一、顺序表示的队列基本操作
1．顺序表示的队列操作基本源程序
#include
#include
typedef int DataType;
#define MAXNUM 100/*队列中最大元素个数*/
struct SeqQueue{/*顺序队列类型定义*/
int f,r;
DataType*q;
};/*为了算法设计上的方便：f指出实际队头元素所在的位置，r 指出实际队尾元素所在位置的下一个位置。*/
typedef struct SeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/
创建空队列
PSeqQueue createEmptyQueue_seq(int m) {
PSeqQueue paqu;
paqu= (PSeqQueue)malloc(sizeof(struct SeqQueue));
if (paqu!=NULL) {
paqu->f = NULL;
paqu->r = NULL;
else printf("Out of space!! \n");
return paqu;
}
判断队列是否为空
int isEmptyQueue_seq( PSeqQueue paqu ){
return (paqu->f == NULL);
}
进队运算
void enQueue_seq( PSeqQueue paqu, DataType x ) { /* 在队尾插入元素x */
if( (paqu->r + 1) % MAXNUM == paqu->f )
printf( "Full queue.\n" );
else { paqu->q[paqu->r] = x;
paqu->r = (paqu->r + 1) % MAXNUM;
}
}
出队运算
void deQueue_seq( PSeqQueue paqu ) {
/* 删除队列头部元素*/
if( paqu->f == paqu->r )printf( "Empty Queue.\n" ); else paqu->f = (paqu->f + 1) % MAXNUM;
取队列头部元素运算
DataType frontQueue_seq( PSeqQueue paqu ) {
if( paqu->f == paqu->r )
printf( "Empty Queue.\n" );
else return (paqu->q[paqu->f]);
}
int main() //主函数
{
PSeqQueue pp;
int n,m;
printf("\n please input the values(<100) of n = ");
scanf("%d", &n);
printf(" please input the values of m = ");
scanf("%d", &m);
pp =createEmptyQueue_seq(n); // 创建顺序表示的空队列}
二、链表表示的队列基本操作
1．链表表示的队列基本操作源程序
#include
#include
typedef int DataType;
structNode;
typedef struct Node*PNode;
struct Node{/*结点结构*/
DataType info;
PNode link;
};
struct LinkQueue{/*链接队列类型定义*/
PNode f;/*头指针*/
PNode r;/*尾指针*/
};
typedef struct LinkQueue *PLinkQueue;
/*链接队列类型的指针类型*/
创建链接表示的空队列
PLinkQueue createEmptyQueue_link( int m ) { PLinkQueue plqu;
plqu= (PLinkQueue)malloc(sizeof(struct LinkQueue)); if (plqu!=NULL) {
plqu->f = NULL;
plqu->r = NULL;
}
else printf("Out of space!! \n");
return plqu;
}
判断队列是否为空
int isEmptyQueue_link( PLinkQueue plqu ) {
return (plqu->f == NULL);
}
进队运算
void enQueue_link( PLinkQueue plqu, Datatype x) {
PNode p;
p = (PNode )malloc( sizeof( struct Node ) ); /*申请新结点空间*/ if ( p == NULL )printf("Out of space!"); /*申请新结点失败*/
else
{ p->info = x;
p->link = NULL; /*填写新结点信息*/
if (plqu->f == NULL) plqu->f = p; /*插入前是空队列*/
else plqu->r->link = p; /*将新结点插入*/
plqu->r = p; /*修改队尾指针*/
}
}
出队运算
void deQueue_link( PLinkQueueplqu) {
PNodep;
if( plqu->f == NULL ) printf( "Empty queue.\n " );
/*队列已空*/
else { p = plqu->f;
plqu->f = p ->link; /*修改队头指针*/
free(p); /*释放已经删除结点空间*/
}
}
取队列头部元素运算
Datatype frontQueue_link( PLinkQueue plqu ) {
if( plqu->f == NULL ) printf( "Empty queue.\n " );
/*队列已空*/
else return (plqu->f->info);
}
int main() //主函数
{
PLinkQueue pp;
int n,m;
printf("\n please input the values(<100) of n = ");
scanf("%d", &n);
printf(" please input the values of m = ");
scanf("%d", &m);
pp =createEmptyQueue_link(n); // 创建顺序表示的空队列}
三、深度优先搜索的思想及算法
1．深度优先搜索的思想
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。在深度优先搜索中，对于当前发现的结点，如果它还存在以此结点为起点而未探测到的边，就沿此边继续搜索下去，若当结点的所有边都己被探寻过．将回溯到当前结点的父结点，继续上述的搜索过程直到所有结点都被探寻为止。
深度优先搜索在树的遍历中也称作树的先序遍历。对于树而言，深度优先搜索的思路可以描述为：
(1)将根结点置为出发结点。
(2)访问该出发结点．
(3)依次将出发结点的子结点置为新的出发结点．进行深度优先遍历(执行(2))。
(4)退回上一层的出发结点。
2．深度优先搜索算法
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点mr 符合条件THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END;
四、广度优先搜索的思想及算法
1．广度优先搜索的思想
从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。
2．广度优先搜索算法
list[1]:=source; {加入初始结点，list为待扩展结点的表}
head:=0; {队首指针}
foot:=1; {队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目标结点THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}
五、农夫过河问题求解
1．农夫过河问题
一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。
2．问题需求分析
他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。
另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？
3．抽象数据类型设计
求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。
用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。
广度优先：
广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。
要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。
由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。
4．算法与数据结构的设计
(1)安全状态的判断函数
int safe(int location)
{
// 若状态安全则返回true
if ((goat(location) == cabbage(location)) && (goat(location) != farmer
(location)))
return (0);
// 羊吃白菜
if ((goat(location) == wolf(location)) && (goat(location) != farmer (location)))
return (0);
// 狼吃羊
return (1); // 其他状态是安全的
}
(2)个体状态判断函数
int farmer(int location)
{
//判断农夫的位置
return (0 != (location &0x08));
}
int wolf(int location)
{
//判断狼的位置
return (0 != (location &0x04));
}
int cabbage(int location)
{
//判断白菜的位置
return (0 != (location &0x02));
}
int goat(int location)
{
//判断羊的位置
return (0 != (location &0x01));
}
5．算法的精化与程序的实现
精化:要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。
实现:完成了上面的准备工作，现在的问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。
为避免不必要的瞎费功夫，要求在序列中不应该出现重复的状态。为了实现广度优先搜索，算法中需要使用了一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。
由于在这个问题的解决过程中需要列举的所有状态(二进制0000 ~ 1111)一
共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，算法中把这个顺序表叫做route。route的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后我们可以利用route 顺序表元素的值建立起正确的状态路径。
6．程序的调试与计算结果的分析
用队列解决农夫过河问题
#include
#include
typedef int DataType;
顺序队列：类型和界面函数声明
struct SeqQueue
{
顺序队列类型定义
int MAXNUM; // 队列中最大元素个数
int f, r;
DataType *q;
};
typedef struct SeqQueue *PSeqQueue; // 顺序队列类型的指针类型
PSeqQueue createEmptyQueue_seq(int m)
{
创建一个空队列
PSeqQueue queue = (PSeqQueue)malloc(sizeof(struct SeqQueue));
if (queue != NULL)
{
queue->q = (DataType*)malloc(sizeof(DataType) *m);
if (queue->q)
{
queue->MAXNUM = m;
queue->f = 0;
queue->r = 0;
return (queue);
}
else
free(queue);
}
printf("Out of space!!\n"); // 存储分配失败
return NULL;
}
int isEmptyQueue_seq(PSeqQueue queue)
{
判断队列是否为空
return (queue->f == queue->r);
}
void enQueue_seq(PSeqQueue queue, DataType x)
// 在队尾插入元素x
{
if ((queue->r + 1) % queue->MAXNUM == queue->f) printf("Full queue.\n");
else
{
queue->q[queue->r] = x;
queue->r = (queue->r + 1) % queue->MAXNUM;
}
}
void deQueue_seq(PSeqQueue queue)
// 删除队列头部元素
{
if (queue->f == queue->r)
printf("Empty Queue.\n");
else
queue->f = (queue->f + 1) % queue->MAXNUM; }
DataType frontQueue_seq(PSeqQueue queue)
{
if (queue->f == queue->r)
printf("Empty Queue.\n");
else
return (queue->q[queue->f]);
}
个体状态判断函数
int farmer(int location)
{
//判断农夫的位置
return (0 != (location &0x08)); }
int wolf(int location)
{
//判断狼的位置
return (0 != (location &0x04)); }
int cabbage(int location)
{
//判断白菜的位置
return (0 != (location &0x02)); }
int goat(int location)
{
//判断羊的位置
return (0 != (location &0x01)); }
安全状态的判断函数
int safe(int location)
{
// 若状态安全则返回true
if ((goat(location) == cabbage(location)) && (goat(location) != farmer
(location)))
return (0);
// 羊吃白菜
if ((goat(location) == wolf(location)) && (goat(location) != farmer
(location)))
return (0);
// 狼吃羊
return (1); // 其他状态是安全的
}
main()
{
int i, movers, location, newlocation;
int route[16]; //用于记录已考虑的状态路径
PSeqQueue moveTo; //用于记录可以安全到达的中间状态
moveTo = createEmptyQueue_seq(20); //创建空队列
enQueue_seq(moveTo, 0x00); //初始状态进队列
for (i = 0; i < 16; i++)
route[i] = - 1;
准备数组route初值
route[0] = 0;
while (!isEmptyQueue_seq(moveTo) && (route[15] == - 1))
{
location = frontQueue_seq(moveTo); //取队头状态为当前状态
deQueue_seq(moveTo);
for (movers = 1; movers <= 8; movers <<= 1)
//考虑各种物品移动
if ((0 != (location &0x08)) == (0 != (location &movers)))
//农夫与移动的物品在同一侧
{
newlocation = location ^ (0x08 | movers); //计算新状态
if (safe(newlocation) && (route[newlocation] == - 1))
//新状态安全且未处理
c++,链队列的基本操作(创建,销毁,查找,删除,插入等)
链队列的基本操作（创建，销毁，查找，删除，插入等）#include
数据结构(C语言)队列的基本操作
实验名称：实验四队列的基本操作 实验目的 掌握队列这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序队列或链式队列，并完成下列操作： （1）初始化队列； （2）队列是否为空； （3）出队； （4）入队。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; //链表单链表 typedef struct Node *PNode; int dui; dui =1; struct Node { int info; PNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue *PLinkQueue; （二）总体设计 程序由主函数、创建队列函数、判断是否为空队列函数、入队函数、出队函数、取数函数、显示队列函数、菜单函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 main() { PLinkQueue a; //定义链表a int b,c,e; //b 菜单选择c选择继续输入e输入元素 do { //菜单选择 mune(); scanf("%d",&b);
switch(b) { case 1://初始化 a=create(); //初始化队列 case 2: //入队 do { printf("\n请输入需要入队的数："); if(e!=NULL) { scanf("%d",&e); enQueue(a,e); } printf("是否继续入队？(是:1 否：0)\n"); scanf("%d",&c); } while(c==1); break; case 3: //出队 c=frontQueue(a); deQueue(a); if(dui!=0) { printf("\n出队为:%d\n",c); } dui=1; break; case 4: //显示队中元素 showQueue(a); break; case 5: return; default: printf("输入错误，程序结束!\n"); return; } } while(a!=5); { return 0; } } （三）各函数的详细设计： Function1: PLinkQueue create(void)//创队
队列的基本操作代码
队列的基本操作代码： #include
3 栈和队列答案
第3章栈和队列 一、基础知识题 3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2 链栈中为何不设置头结点? 3.3 循环队列的优点是什么? 如何判别它的空和满? 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) { x=Pop(&S1) ; Push(&tmp,x); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x); } (3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) { i=Pop(&T); Push(S,i);
栈和队列的基本操作
《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 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。 int stackempty(SqStack *s) （4）入栈函数：将元素逐个输入栈中。 int Push(SqStack *s,int x) （5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。 int Pop(SqStack *s,int x) （6）进制转换函数：将十进制数转换为R进制数 int conversion(SqStack *s) 2、队列 （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）空队列建立函数：对队列进行初始化。 SeqQueue *InitQueue() （3）返回队头函数：判断队是否为空，若不为空则返回队头元素。 int QueueEmpty(SeqQueue *q) （4）入队函数：将元素逐个输入队列中。 void EnQueue(SeqQueue *q,int x) （5）出队函数：若队列不空，则删除队列元素，并用x返回其值。 int DeQueue(SeqQueue *q) （6）计算队长函数：计算队列的长度。 int QueueEmpty(SeqQueue *q) （7）输出辉三角函数：按一定格式输出辉三角。 void YangHui(int n)
队列的基本操作及其应用
广西工学院计算机学院 《数据结构》课程实验报告书实验四队列的基本操作及其应用 学生姓名：李四 学号：2012 班级：计Y124 指导老师：王日凤 专业：计算机学院软件学院 提交日期：2013年6月20日
1．实验目的 1）通过对队列特点的分析，掌握队列的存储结构及其基本操作，学会定义队列的顺序存储结构和链式存储结构，在实际问题中灵活运用。 2）掌握队列先进先出的特点，掌握队列的基本操作，如出队列、入队列、判队列空、判队列满等，熟悉各种操作的实现方法。 3）通过具体的应用实例，进一步熟悉和掌握队列的实际应用。 2.实验内容 （1）建立一个含n个数据的队列，实现队列的基本操作。包括： ?//1. 初始化,构造一个空队列 void initQueue(Queue &Q) ?//2. 判断队列空, 空则返回true bool QueueEmpty(seqQueue &Q) ?//3. 判断队列满, 满则返回true bool QueueFull(seqQueue &Q) ?//4. 取队头元素, 用x返回队头元素，返回true；空队列则返回false Bool QueueHead(seqQueue &Q, elementType &x) ?//5. 入队列，在队尾插入新元素x （流程图） bool pushQueue (seqQueue &Q, elementType x) ?//6. 出队列，用x带回队头元素，并在队头删除，返回true，队列空则返回false（流程图）bool popQueue (seqQueue &Q, elementType &x) ?//7. 输出队列,从队头到队尾依次输出 void printQueue(seqQueue Q) （2）队列应用：利用队列操作打印杨辉三角形的前n行（如n=7）。 3．实验要求 （1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。 （2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。 （3）实验课上进行答辩。 （4）实验报告当场交。报告内容包括：实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。
栈和队列的基本操作的实现
封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______2010\4\12
【实验目的】 1.理解并掌握栈和队列的逻辑结构和存储结构； 2.理解栈和队列的相关基本运算； 3.编程对相关算法进行验证。 【实验内容】 （一）分别在顺序和链式存储结构上实现栈的以下操作（含初始化，入栈，出栈，取栈顶元素等）： 1.构造一个栈S，将构造好的栈输出； 2.在第1步所构造的栈S中将元素e 入栈，并将更新后的栈S输出； 3.在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。（二）分别在链队列和循环队列上实现以下操作（初始化，入队，出队，取队头元素等）： 1.构造一个队列Q，将构造好的队列输出； 2.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出； 3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。
【要求】 1.栈和队列中的元素要从终端输入； 2.具体的输入和输出格式不限； 3.算法要具有较好的健壮性，对运行过程中的错误 操作要做适当处理。 三、实验步骤 1．本实验用到的数据结构 (1)逻辑结构：线性结构 (2)存储结构：程序一、四（顺序存储结构）； 程序二、三（链式存储结构）； 2．各程序的功能和算法设计思想 程序一：顺序栈 # include
试验 --循环队列的基本操作及应用
数据结构实验报告 ----试验三循环队列的基本操作及应用 一、问题描述： 熟悉并掌握循环队列的相关操作，自己设计程序，实现循环队列的构造、清空、销毁及队列元素的插入和删除等相关操作。 二、数据结构设计： #define MAXQSIZE 10 //最大队列长度 struct SqQueue { QElemType *base; //初始化动态分配存储空间 Int front; // 头指针，若队列不空，只想对列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的 //下一个位置 }; 三、功能设计： 程序中所涉及到的函数如下： Status InitQueue(SqQueue &Q) //构造一个空队列Q Status DestroyQueue(SqQueue &Q) //销毁队列Q,Q不再存在 Status ClearQueue(SqQueue &Q) //将Q清为空队列 Status QueueEmpty(SqQueue Q) //若队列Q为空队列，则 //返回TRUE，否则返回FALSE int QueueLength(SqQueue Q) //返回Q的元素个数，即队列长度Status GetHead(SqQueue Q,QElemType &e)//若队列不空，则用e返回Q的对 //头元素，并返回OK，否则返回ERROR Status EnQueue(SqQueue &Q,QElemType e)//插入元素e为Q的新的队尾元素Status DeQueue(SqQueue &Q,QElemType &e)//若队列不空，则删除Q的队头 //元素，用e返回其值，并返回 //OK，否则返回ERROR Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))//从队头到队尾依次 //对队列Q中每个元素调用函数 //vi()。一旦vi失败，则操作失败四、源程序： // c1.h (程序名) #include
栈和队列的基本操作实现及其应用
实验二栈和队列的基本操作实现及其应用 一_一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 一_二、实验内容 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef 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) 一_三、数据结构与核心算法的设计描述 1、初始化栈 /* 函数功能：对栈进行初始化。参数：栈(SqStack S)。 成功初始化返回0,否则返回-1 */ int InitStack(SqStack &S) { S.base=(SElemType *)malloc(10*sizeof(SElemType)); if(!S.base) //判断有无申请到空间 return -1; //没有申请到内存,参数失败返回-1 S.top=S.base; S.stacksize=STACK_INIT_SIZE; S.base=new SElemType; return 0; } 2、判断栈是否是空 /*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/ int StackEmpty(SqStack S) { if(S.top==S.base) return -1; else return 0; } 3、入栈 /*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */ int Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType));
数据结构 栈和队列的基本操作实现及其应用
实验二栈和队列的基本操作实现及其应用 一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容（可任选或全做） 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列， 是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef 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、 及输出队列中元素。 [实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。 题目三、Rails
Description There 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 that time. 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. Input The 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. Output
数据结构实验二-栈和队列的基本操作与应用
实验报告 课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________ 系别 ___ 计算机学院_______________ 专业 __________________ 班级/学号______ _________ 学生姓名_____________________ __ 实验日期__________________ 成绩_______________________ 指导教师____ __________________
一、实验内容： 本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的 运用，其中包含优先级的判断。 二、设计思想 1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先 级 2.优先级关系用“>”“<”“=”来表示三种关系 3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作 符栈 4.运用入栈出栈优先级比较等方式完成运算 三、主要算法框架 1.建立两个栈InitStack(&OPTR); InitStack(&OPND); 2.Push“#”到 OPTR 3.判断优先级做入栈出栈操作 If“<” Push(&OPTR, c); If“=” Pop(&OPTR, &x) If“>” Pop(&OPTR, &theta); Pop(&OPND, &b);
Pop(&OPND, &a); Push(&OPND, Operate(a, theta, b)); 四、调试报告 遇到的问题与解决 1.C语言不支持取地址符，用*S代替&S来编写代码 2.一开始没有计算多位数的功能只能计算一位数，在几个中间 不含运算符的数字中间做p = p*10+c运算。代码如下：p = p * 10 + c - '0'; c = getchar(); if (In(c)) { Push(&OPND, p); p = 0; } 主要算法改进设想： 1.可以用数组储存优先级 2.可以用C++编写，C++支持取地址符&。 五、实验总结
队列的常见操作
数据结构面试之四——队列的常见操作 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 四、队列的基本操作 1.用数组构造队列 队列即是满足先进先出的链表。用数组存储的话，同样需要满足队列头front出栈，队列末尾rear入栈。而对于数组来讲，rear和front可以代表数组头和尾。不能简单的固定rear 和front的大小为maxSize和0，因为可能出现中间元素为空的现象。所以，对于数组队列来讲，可以想象成环式存储，因为每一次入队后rear+1，每一次出队后front+1。这就需要控制front和rear的大小，每一次修改只要满足front=（front+1）%maxSize，rear=（rear+1）%maxSize即可满足要求。 同样需要注意：入队操作前先判定队列是否已经满；出队操作前先判定队列是否为空。 template
数据结构实验二(栈和队列)
实验二栈和队列的基本操作及其应用 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈和队列的特点，即后进先出和先进先出的原则。 3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序 存储结构和链式存储结构上的实现。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生 可以根据自己的情况任选一个！ 题目一：回文判断（*） [问题描述] 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 [基本要求] （1）数据从键盘读入； （2）输出要判断的字符串； （3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出 “Yes”，否则输出“No”。 [测试数据] 由学生任意指定。 题目二：顺序栈和循环队列基本操作（*） [基本要求] 1、实现栈的基本操作 六项基本操作的机制是：初始化栈：init_stack(S)；判断栈空：stack_empty(S)；取栈顶元素：stack_top(S,x)；入栈：push_stack(S,x)；出栈：pop_stack(S)；判断栈满：stack_full(S) 2、实现队列的基本操作 六项基本操作的机制是：初始化队列：init_queue(Q)；判断队列是否为空：queue_empty(Q)；取队头元素：queue_front(Q,x)；入队：enqueue(Q,x)；出队：outqueue(Q,x)；判断队列是否为满：queue_full(Q) [测试数据]
由学生任意指定。 题目三：商品货架管理（**） [问题描述] 商店货架以栈的方式摆放商品。生产日期越近的越靠近栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上货。入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，使生产日期越近的越靠近栈底。 [基本要求] 设计一个算法，保证每一次上货后始终保持生产日期越近的商品越靠近栈底。 [实现提示] 可以用一个队列和一个临时栈作为周转。 [测试数据] 由学生任意指定。 三、实验前的准备工作 1、掌握栈的逻辑结构和存储结构。 2、熟练掌握栈的出栈、入栈等操作。 3、掌握队列的逻辑结构和存储结构。 4、熟练掌握队列的出队、入队等操作 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 *2、写出算法设计思路。 3、实验上要写出多批测试数据的运行结果。 4、结合运行结果，对程序进行分析。 题目四：Rails（ACM训练题） Description There 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 that time. It was possible to establish only a surface track. Moreover, it turned out that the
链队列基本操作的C++实现
#include
顺序队列的基本操作
#include
实验二栈队列的实现及应用
百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct
1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B
D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z
百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode
栈和队列的基本操作讲解
《数据结构与算法》实验报告 专业班级姓名学号 实验项目 实验二栈和队列的基本操作。 实验目的 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。 int stackempty(SqStack *s) （4）入栈函数：将元素逐个输入栈中。 int Push(SqStack *s,int x) （5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。 int Pop(SqStack *s,int x) （6）进制转换函数：将十进制数转换为R进制数 int conversion(SqStack *s) 2、队列 （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）空队列建立函数：对队列进行初始化。 SeqQueue *InitQueue() （3）返回队头函数：判断队是否为空，若不为空则返回队头元素。 int QueueEmpty(SeqQueue *q) （4）入队函数：将元素逐个输入队列中。 void EnQueue(SeqQueue *q,int x) （5）出队函数：若队列不空，则删除队列元素，并用x返回其值。 int DeQueue(SeqQueue *q) （6）计算队长函数：计算队列的长度。 int QueueEmpty(SeqQueue *q) （7）输出杨辉三角函数：按一定格式输出杨辉三角。 void YangHui(int n) （三）各函数的详细设计： 1、栈 （1）int main()主函数 定义s为栈类型 调用函数建立空栈