链队列实验报告

* *

计算机科学与技术系

实 验 报 告

专业名称 计算机科学与技术

课程名称 数据结构与算法

项目名称 实验三队列实验

班 级

学 号 1

姓 名

同组人员 无

实验日期

* *

实验三 队列实验

实验题目：建立含有若干个元素的循环队列和链队列，并分别实现循环队列和链队列的入队和出对操作。

（1）先实现循环队列的入队和出队操作

1.问题分析

本程序要求实现建立含有若干个元素的循环队列，并实现循环队列的入队和出队操作。

完成该实验需要以下4个子任务：

○1定义一个循环队列的存储结构，定义队列的基本算法。

○2定义一个display（）函数实现队列元素的输出看入队是否成功

○3通过队列的基本算法实现队列的出队操作

○4在主函数中完成操作

测试数据设计如下：

1 2 3 4 5

6

2.概要设计

为了实现上述程序功能，需要：○1声明一个循环队列○2定义出队列的基本算法，○3通过键盘输入5个整数，入队，出队 ○4在主函数中先往队列里输入5个元素，然后入队，输出，看入队是否成功，然后出队，再调用display（）函数* *

看是否出队。

1） 本程序包含7个函数：

1主函数main()

2.置空队：InitQueue()

3.判对空: QueueEmpty()

4.判队满：QueueFull()

5.入队:Add()

6.出队:Delete()

7.display()

各函数关系如下：

InitQueue()

QueueEmpty()

Main () QueueFull()

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 数据结构实验

链队列和循环队列

班 级：

学 号：

姓 名：

评语：

成绩： 指导教师：

批阅时间： 年 月 日 《 数据结构 》实验报告

- 1 -

线性数据结构算法实现与应用报告要求

1目的与要求:

1）掌握栈与队列的数据类型描述及特点；

2）掌握栈的顺序和链式存储存表示与基本算法的实现；

3）掌握队列的链式存储表示与基本操作算法实现;

4) 掌握栈与队列在实际问题中的应用和基本编程技巧;

5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性；

7）认真书写实验报告，并按时提交。

2 实验内容或题目

以下题目学生根据自己的兴趣和能力可选作一道作为实验题目：

1） 根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作（出栈和入栈等）；

2） 根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作（出入队列等）；

3） 参考书上表达式求值例题，应用栈的基本操作实现带括号表达式求值运算及其进出栈模拟过程（给出程序执行过程中栈的变化过程）；

4） 阅读P83栈与递归的实现一节内容和3阶汉诺塔问题。使用栈数据结构解决3阶汉诺塔问题，编写程序并模拟栈及其汉诺塔的搬运过程（给出程序执行过程栈的变化过程与圆盘的搬动状态）。

实验一 单链表的基本操作（必做）

一、实验目的

1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。

2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。

3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。

二、实验内容

1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。

2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。

三、实验步骤

1.定义一个链表结构体。。

2.利用插入功能插入一个结点。

3.利用删除功能删除一个结点。

四、程序运行测试

1.利用插入功能插入一个结点。

2.利用删除功能删除一个结点。

五、实验报告要求

1.绘制链表操作实现的流程图。

2.详细给出程序运行测试结果（包括测试数据和测试结果）。

3.选试验步骤2-3中的任意一个，给出程序的详细注释。 4.参考程序中某一部分功能的改进（选做）

5.实验心得与体会

6.附录，实验用源程序

六、参考源代码

#include

#include

typedef struct LNode

{int data;

struct LNode *next;

}Lnode, *LinkList;

//假设下面的单链表均为带头结点。

void CreatLinkList(LinkList &L,int j)

{//建立一个单链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;

L=(LinkList )malloc(sizeof(Lnode));

L->next=NULL;

q=L;

cout<<"在单链表内输入整数："<

for(int i=0;i

cin>>p->data;

p->next=q->next;

BUAAOS——Lab3实验报告

lab3实验报告

思考题

3.1 为什么我们在构造空闲进程链表时必须使⽤特定的插⼊的顺序？(顺序或者逆序)

完成空闲链表的插⼊后，

envs数组下标正好对应链表中的由前到后的顺序，因此调⽤空闲进程数组时优先调⽤下标最⼩的。

3.2 思考

env.c/mkenvid 函数和envid2env 函数:

请你谈谈对

mkenvid 函数中⽣成id 的运算的理解，为什么这么做？

根据进程数组下标给每个进程⼀个独⼀⽆⼆的进程ID，同时还可以通过进程号获取数组偏移量找到进程块进⽽获得进程的全部信息。

为什么

envid2env 中需要判断

e->env_id != envid 的情况？如果没有这步判断会发⽣什么情况？

进程块也许会被替换，⽽ID只与⼀个进程块对应，如果没有这⼀步，可能会执⾏错误的进程块。

3.3 结合

include/mmu.h中的地址空间布局，思考

env_setup_vm 函数：

我们在初始化新进程的地址空间时为什么不把整个地址空间的

pgdir 都清零， ⽽是复制内核的

boot_pgdir作为⼀部分模板？(提⽰:

mips 虚

拟空间布局)因为每个进程都需要拥有内核的页表信息，这样才能够在陷⼊内核时正确执⾏，因此需要把内核拥有的虚拟地址对应的页表进⾏拷贝。

UTOP 和 ULIM 的含义分别是什么，在 UTOP 到 ULIM 的区域与其他⽤户区 相⽐有什么最⼤的区别？

UTOP是⽤户进程读写部分的最⾼地址，

ULIM是⽤户进程的最⾼地址，

UTOP到

ULIM的区域为⽤户进程的进程块还有页表，不能被⽤户⾃⼰更改只能读取。

在 step4 中我们为什么要让

pgdir[PDX(UVPT)]=env_cr3?(提⽰: 结合系统⾃ 映射机制)

env_cr3是页⽬录的物理地址，

pgdir[PDX(UVPT)]对应页⽬录的页⽬录项。

谈谈⾃⼰对进程中物理地址和虚拟地址的理解。

进程对应的地址都是虚拟地址，所有的物理地址只能从页表中查询所得到。不同的进程有着不同且独⽴的虚拟地址，不同进程有可能映射到