发布时间 : 星期四 文章实验302 队列的链式表示和实现(lnkqueue)更新完毕开始阅读6191d6c8da38376baf1faef0
实验302 队列的链式表示和实现
编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化并建立链队列。 （2）入链队列。 （3）出链队列。 （4）遍历链队列。 【参考程序清单】 # include
struct Qnode * next; }Qnodetype; typedef struct
{ Qnodetype *front; Qnodetype *rear; }Lqueue;
void Lappend(Lqueue *q,int x);
/*初始化并建立链队列*/ void creat(Lqueue *q) { Qnodetype *h; int i,n,x;
printf(\输入将建立连队列元素的个数：n=\ scanf(\
h=(Qnodetype *)malloc(sizeof(Qnodetype )); h->next=NULL q->front=h; q->rear=h;
for(i=1;i,=n;i++)
{ printf(\链队列第%d个元素的值为：\，i)； scanf(\ Lappend(q,x); } }
/*如链队列*/
void Lappend(Lqueue *q,int x) { Qnodetype *s;
s=(Qnodetype *)malloc(sizeof(Qnodetype));
s->data=x;
s->next=NULL; q->rear->next=s; q->rear=s; }
/*出链队列*/
Elemtype Ldelete(Lqueue *q) { Qnodetype *p Elemtype x;
if(q->front==q->rear)
{ printf(\队列为空! \\n\ return 0; } else
{ p=q->front->next;
q->front->next=p->next; if(p->next==NULL) q->rear=q->front; x=p->data; free(p); }
printf(\出链队列元素: %d\\n\ }
/*遍历链队列*/
void display(Lqueue *q) { Qnodetype *p;
p=q->front->next; /*指向第一个数据元素结点*/ if(! p) printf(\队列为空! \\n\ else
{ printf(\链队列元素依然为:\ while(p!=NULL)
{ printf(\ p=p->next;
} printf(\遍历链队列结束!\\n\ } }
void main() { Lqueue *p; int x,cord;
printf(\第一次操作请选择初始化并建立链队列! ******\\n\ do
{ printf(\主菜单==========\\n\ printf(\ 1 初始化并建立链队列\； printf(\ 2 入列队列 \\n\ printf(\ 3 出链队列 \\n\ printf(\ 4 遍历链队列 \\n \ printf(\ 5 结束程序运行 \\n \ printf(\ scanf(\ switch(cord) { case 1:
{ p=(Lqueue *)malloc(sizeof(Lqueue)); crear(p); display(p); }break; case 2:
{ printf(\请输入队列元素的值：x=\； scanf(\ Lappend(p.x); display(p) }break; case 3:
{ Ldelete(p); display(p); }break; case 4:
{display(p);}break; case 5:
{exit(0);} }
}while(cord<=5); }
思考：
（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？ （2）一个程序中如果要用到两个栈，可通过两个栈共享一维数组来实现，即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？
四、程序调试及输出结果 五、实验小结 六、选做实验 1.设计一个算法，利用一个栈对单链表实现逆置，即利用一个栈将单链表（a1，a2，a3·····，an）（其中n?0）逆置为（an，an-1，····，a2，a1）。 2.设计一个算法，用一个栈S将一个队列Q逆置。 （1）要求采用顺序栈和顺序队列来实现。
（2）要求采用链栈和链队列来实现。
3.括号匹配的检验。假设表达式中允许有两种括号：圆括号和方括号，启潜逃的顺序随意，即（（）【】）或【（【】【】）】等为正确格式，【（】）或（（（】均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如，考虑下列的括号序列： 【 （ 【 】 【 】 ） 】 1 2 3 4 5 6 7 8 当计算机接受了第1个括号“【”以后，它期待着与其匹配的第8个括号“】”的出现，然而等来的却是第2个括号“（”，此时第1个括号“【”只能暂时靠边，而迫切等待与第2个括号“（”相匹配的第7个括号“）”的出现，类似地，只等来了第3个括号“【”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，以此类推，即可得出最终结果。可见这个处理过程正好和栈的特点相吻合。要求：赌如圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。 测试数据： （1）输入（【】（）），结果为“匹配”。 （2）输入【（）】，结果为“此串括号匹配不合法”
【实现提示】 设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是左括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入都有括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初试和结束时，栈应该是空的。
4.设停车场内只有一个可停放n辆汽吃的狭长通道，且只有大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，一次由北向南排列（大门在最南端，最先到达的第辆车停放在车场的最北端），若车场内已停满n辆车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆在按原次序进入车场，每辆停放在车场的车在它离开车场时必需按它停留的时间长短交纳费用。 试为停车场编制按上述要求进行管理的模拟程序。 【实现提示】
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”的信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场內或便道上的停车位置；若是车辆离去；则输出汽车在停车场内停留的时间和应缴纳的费用（在便道上停留的时间不计费）。栈以顺序结构实现，队列以链表实现。 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 设n=2，输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’,1,15）,(‘A’，3，20)，（‘A’4，25），（‘A’，5，30），（‘D’2，35）（‘D’4，40），（‘E’，0，0）.每一组输入数据包括三个数据项：汽车“到达”或“离去”的信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
11.3 树和二叉树（实验3）
一、实验目的
1.掌握二叉树的结构特征，以及各种存储结构的特点及使用范围 2.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求
1.认真阅读和掌握本实验的程序 2.上机运行本程序
3.保存和打印出程序的运行结果，并结合程序进行分析。
4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。 三、实验内容
1、输入字符序列，建立二叉链表。
2、按先序、后序和后序遍历二叉树（递归算法）。 3、按某种形式输出整棵二叉树。 4、求二叉树的高度。
5、求二叉树的叶结点个数。 6、交换二叉树的左右子树。
7、借助队列实现二叉树的层次遍历。
8、在主函数中设计一个简单的菜单分别调试上述算法。 为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素）。图11.2所示二叉树的输入数据顺序应该是：（1，a），（2，b），（3，c），（4，d），（6，e），（7，f），（9，g），（13，h）。